• 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
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Program hangs while counting number of occurrences of each element in ArrayList<Integer>

 
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Problem statement: Given a list/array of integers, count the number of occurrences of each element and print only those elements which occur once.

For the above problem, I have executed the following code. This works for small size lists of integers. However when the list size goes beyond 99999, the code hangs.


I understand that ArrayList works well for accessing the elements and the time complexity is less. However is it the right collection to be used, when iterating over such a large size data?
What kind of approach we need to take, to come up with an effective solution, while dealing with huge volumes of data? [ In view with deciding the right data structure/collection ]
This was also asked as an interview question a couple of times.
 
Saloon Keeper
Posts: 9742
80
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
With your nested loops you visit each number N times. A better approach is to use a Map to keep a histogram. This allows you to visit each number only once.


 
Mary Rani
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you. This approach works better and could get the unique list in lesser time.

Can you please suggest some links/documentation which can clearly explain what kind of data structure/collection we can choose based on the operation to be performed [ search, sort, count, add, delete ], data size, less execution time and efficient memory management ?
This would help clear some concepts for me.
 
Sheriff
Posts: 17345
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You can also build a histogram using a stream and Map.merge:

Try that out here: https://repl.it/@jlacar/HistogramMapMerge

From there, you could apply a filter of elements where count == 1 -- I'll leave that as an exercise for you to figure out.
 
Junilu Lacar
Sheriff
Posts: 17345
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There are actually better ways to create a histogram with steams than what I showed above though. Just search for java streams histogram
 
Carey Brown
Saloon Keeper
Posts: 9742
80
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Found another histogram using streams approach using your link. This runs 50% slower than your original proposed streaming histogram.
 
girl power ... turns out to be about a hundred watts. But they seriuosly don't like being connected to the grid. Tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic