• Post Reply Bookmark Topic Watch Topic
  • New Topic

Subsets - Difference in Pairs  RSS feed

 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello all,

I am trying to write a program that takes an array, effectively sorts the array with quickSort, then for each pair in the sorted array with a specified distance passed by reference (via the parameter in the method), it adds the difference to an ArrayList. The method effectively returns an ArrayList with integer pairs that are different. Please let me know if you need further clarification. For some reason, my code is returning an error in memory (in fact sometimes it does not even run). Now, from my understanding quicksort is the sort to use if the program does not use memory. However, if the program uses a substantial amount of memory, one should use Merge Sort. Please tell me where I'm going wrong. Thanks!



The error being generated comes from my main method where I initiate an improved for loop to print out Pairs from the declared arraylist. It is not running right now for example.

 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In case if you ladies and gentlemen are wondering, here is the error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:3210)
at java.util.Arrays.copyOf(Arrays.java:3181)
at java.util.ArrayList.grow(ArrayList.java:261)
at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235)
at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227)
at java.util.ArrayList.add(ArrayList.java:458)
at DifferencePairs.findPairs(DifferencePairs.java:20)
at DifferencePairs.main(DifferencePairs.java:72)

This is the Pair class:



 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru Gelajo wrote:. . . specified distance passed by reference (via the parameter in the method)
There ain't no such thing as pass by reference in Java®.
. . . quicksort is the sort to use if the program does not use memory. However, if the program uses a substantial amount of memory, one should use Merge Sort.
What does that mean and where did you get it from? Do you mean that merge sort requires lots of memory to be executed? There are different reasons for choosing quicksort or merge sort.
Please tell me where I'm going wrong. Thanks!
. . . The error being generated comes from my main method where I initiate an improved for loop to print out Pairs from the declared arraylist. It is not running right now for example.
Don't know. I think it very unlikely that you are running out of memory in that for‑each loop. You must be creating an infinite recursion somewhere. Try putting some print statements in the main method so you know how far your program has got before you run out of memory.

You don't need to write pair.toString(); simply writing System.out.println(pair) will implicitly call its toString method. It is safer that it won't throw an Exception if pair is null.
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The stack trace for that exception suggests you are trying to add so many pairs to the List that you are exhausting the memory available.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
. . . The error being generated comes from my main method where I initiate an improved for loop to print out Pairs from the declared arraylist. It is not running right now for example.
Don't know. I think it very unlikely that you are running out of memory in that for‑each loop. You must be creating an infinite recursion somewhere. Try putting some print statements in the main method so you know how far your program has got before you run out of memory.

You don't need to write pair.toString(); simply writing System.out.println(pair) will implicitly call its toString method. It is safer that it won't throw an Exception if pair is null.

Hello Campbell, apologies for some of those extremely vague explanations. What I meant by quickSort and its memory constraints is that one uses quickSort if the algorithm will fit in memory. One uses MergeSort if external storage is needed. Although both algorithms are technically O(n log n) average case, quick sort is still faster.

With that said, I will follow your advice. Thanks!
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru Gelajo wrote:. . . . What I meant by quickSort and its memory constraints is that one uses quickSort if the algorithm will fit in memory. One uses MergeSort if external storage is needed. Although both algorithms are technically O(n log n) average case, quick sort is still faster.
That sounds incorrect. Both can use built‑in memory, but merge sort requires more memory for its intermediate stages. There is another reason why you might want to use merge sort in preference to quicksort. Look at this method and this one.
. . . Thanks!
[edit] Forgot to say, That's a pleasure
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!