Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Java Java Data Structures - Retired Efficiency! Implement Chooser UI

Bryan Ulziisaikhan
Bryan Ulziisaikhan
620 Points
Posted by Bryan Ulziisaikhan
Bryan Ulziisaikhan
620 Points

Maps vs ArrayList/Set in this scenario?

Hey guys, I was wondering which algorithm is better in terms of speed and efficiency? The one in the video or this one?

  1. User selects "Search by artist"
  2. Scans all songs and puts artists into set.
  3. Displays the artists from set.
  4. User chooses artist.
  5. Scans all songs with that artist, and puts them into ArrayList.
  6. Display the songs.

1 Answer

qzhangjhu
qzhangjhu
1,289 Points
qzhangjhu
qzhangjhu
1,289 Points

For the usage seen in the video so far, your algorithm is slightly better, but that is only because the intended method of Craig has not yet been fully implemented, rather than because the designer of this course did not think this through. When the course carries on, you will see the merit of generating this HashMap.

Ideally and hopefully in the videos to come, the HashMap calculated with mSongBook.byArtist() should be cached instead of generated by what we do now, so that we don't have to regenerate the HashMap once again each time we run mSongBook.getArtists() and mSongBook.getSongsForArtist(String) .

With that implemented, the running time of using a cached HashMap would be significantly better than your method of going through all the songs each time we run mSongBook.getArtists() and mSongBook.getSongsForArtist(String).

By that time, say we run mSongBook.getArtists() and mSongBook.getSongsForArtist(String):

  • Your method would take O(numberOfAllSongs) for each of this two methods;
  • Their method would take O(1) time, which means the least running time ever, for the previous one, and O(numberOfSongsForThisArtist) for the latter, which is still significantly better. (Actually I think the running time for the latter is also O(1) but I am not sure. I am new to Java so I am not clear how much optimization Java actually did regarding these data structures and there related helper methods. But even in the most primitive manner, the running time is gonna be O(numberOfSongsForThisArtist));

Also, I have not seen or anticipated how, regarding details, Craig is gonna implement and refine the rest of the app so I am not sure how exactly the algorithms is gonna be carried out. The actual final result of running time my vary from the analysis above, but the correctness of the conclusion holds: HashMap exists here for a good reason.