Win a copy of Programming with Types this week in the Angular and TypeScript forum
or The Design of Web APIs in the Web Services 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Knute Snortum
  • Henry Wong
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Frits Walraven
  • Joe Ess
  • salvin francis

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

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • 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: 6588
61
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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: 11
  • Mark post as helpful
  • send pies
  • 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: 14614
243
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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: 14614
243
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • 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: 6588
61
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Found another histogram using streams approach using your link. This runs 50% slower than your original proposed streaming histogram.
 
He baked a muffin that stole my car! And this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!