Win a copy of TDD for a Shopping Website LiveProject this week in the Testing forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Frits Walraven
Bartenders:
  • Piet Souris
  • Himai Minh

Subsets - Difference in Pairs

 
Ranch Hand
Posts: 186
1
Netbeans IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 186
1
Netbeans IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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:



 
Marshal
Posts: 75650
354
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 75650
354
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 186
1
Netbeans IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 75650
354
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Onion rings are vegetable donuts. Taste this tiny ad:
Free, earth friendly heat - from the CodeRanch trailboss
https://www.kickstarter.com/projects/paulwheaton/free-heat
reply
    Bookmark Topic Watch Topic
  • New Topic