Listing 11.7, pg. 207 - linear search algorithm efficient?


#1

I’m wondering about efficieny of the linear search algorithm. Is this algorithm efficent for the given situation of about 500+ or more Crime objects? It may just be the emulator lagging, I’m not sure. I filled the ArrayList with 1,000 Crime objects and randomly clicked Crimes in the list to open. Crime #50 - no lag, Crime #132 - no lag, and so on. As I got closer to the Crimes in the 400s+, there was a slightly noticeable lag of a second or two before displaying the Crime in fragment. I haven’t formally studied any algorithms yet so I don’t know what to implement as a possible faster solution if the algorithm is indeed slow natured in large data sets.

Algorithmic efficiency is beyond the scope of the book so I’m not expecting an answer. Feel free to share any input if you want. Thanks!


 UUID crimeId = (UUID)getIntent().getSerializableExtra(CrimeFragment.EXTRA_CRIME_ID);
	  for(int i=0; i < mCrimes.size(); i++){
		  		if(mCrimes.get(i).getId().equals(crimeId)){
		  			mViewPager.setCurrentItem(i);
		  			break;
		  		}

#2

It’s definitely not the most efficient choice. We chose a linear search because it is concise and performs fine in a program of this size.

However, even at 1000 crimes I don’t think that the bottleneck is going to be this linear search. I would bet on file I/O instead.

RAM is fast, and O(n) isn’t great, but it’s not terrible, either. Saving to file also has O(n) complexity, but the constant factor is much greater since you’re going out to solid state storage. A real app would instead use a SQLite database instead of a flat file, and save incrementally rather than saving the entire dataset at once.


#3

Oh ok, thanks for the explanation.