GitLab

This lab took me ~1 hour. The lab itself I think is pretty good. Here's my feedback.

1. The Random.nextInt() function used to generate array lengths in the stress test can generate negative numbers. It should be surrounded with a Math.abs() to prevent that.
2. The stress test often led to my computer running out of memory on the heap because Random.nextInt() can generate massive values for array lengths. I think we should use Random.nextInt() % 1000 or something like that.
3. I had some issues with using linearSearch() as the ground truth value for binarySearch() when the randomly generated array in the stress test had duplicate values. For example, one of my randomly generated arrays had the needle value at both index 674 and 675. The linearSearch() found 674, while my binarySearch() found 675. I'm not sure how to address this, although I did find I could avoid duplicates if I used a sufficiently small array (i.e. Random.nextInt() % 900 was fine for the length).

@amathuku (1) noted (2) it's supposed to generate massive arrays (in fact, one of the edge cases that nobody is going to get right is when the array is slightly larger than Integer.MAX_INT / 2) (3) that indicates that your binarysearch isn't right (after it finds the location, it should search left to check that there's nothing equal to it there)

@blank If we want to have it generate massive arrays, I suggest we turn the number of trials down. My heap couldn't handle 10000 trials, and I suspect many students will also run into this.

Edit: After playing around with this a bit, turning down the trials sometimes didn't help because nextInt() generates such big array lengths. This may have to be a test that can only be run remotely (assuming the docker images are allowed to have larger heaps)

@amathuku we can also teach them how to increase the heap size; i'll think about what i want to do here

@blank Has the generation of massive sorted arrays been clocked? Clocking it on my laptop, for the first array generated, it takes 245.486 sec to generate and sort.

I wrote this code quickly to see what the first few arrays would look like in terms of length, and estimate sorting times, but wow - no way even the generation finishes in a reasonable time, let alone the sorting.

Also, random testing showed that -Xmx6G ran out of heap space with 1720005005 elements.

Random r = new Random(1337);
int[] arrLengths = new int[10000];
long startPop = 0;
long endPop = 0;
for (int i = 0; i < 10000; i ++) {
    arrLengths[i] = Math.abs(r.nextInt());
    int[] tmpArr = new int[arrLengths[i]];
    startPop = System.currentTimeMillis();
    for (int j = 0; j < arrLengths[i]; j ++) {
        tmpArr[j] = r.nextInt();
    }
    endPop = System.currentTimeMillis();
    System.out.printf("%d - %f sec unsorted\n", arrLengths[i], (endPop - startPop) / 1000.);
}

1460590454 - 17.442000 sec unsorted
1392053364 - 16.932000 sec unsorted
1720005005 - 20.631000 sec unsorted
1682607903 - 20.263000 sec unsorted
545797189 - 6.544000 sec unsorted
268931894 - 3.308000 sec unsorted
887295268 - 10.701000 sec unsorted
1227825441 - 14.731000 sec unsorted
1806136363 - 21.427000 sec unsorted
313644513 - 3.745000 sec unsorted
20052559 - 0.228000 sec unsorted
51411673 - 0.614000 sec unsorted
620132068 - 7.477000 sec unsorted
1086159616 - 12.935000 sec unsorted
439880199 - 5.316000 sec unsorted
1935113921 - 23.389000 sec unsorted
822153385 - 9.951000 sec unsorted
854322708 - 10.400000 sec unsorted
1855749859 - 22.558000 sec unsorted
1617450689 - 19.540000 sec unsorted
258518178 - 3.135000 sec unsorted

Process finished with exit code -1

This is 251.267 sec just to generate 21 elements. Sorting adds a LOT of time to this. I don't think this scale of stress testing is feasible.

closed