Challenge #2: Improving CrimeLab Performance

Android Programming (3rd Edition) 10. Using Fragment Arguments
1

Hello all,

I am trying to solve the second challenge of this chapter, but I am having issues with any of the solutions I can think of.

The first step that I took was inside the CrimeLab class:
I have changed the internal representation of the crimes from an ArrayList to a HashTable, with the UUID as a key.

public class CrimeLab {

    [...]

    private Hashtable<UUID, Crime> mCrimes;

    [...]

    private CrimeLab(Context context) {
        mCrimes = new Hashtable<>();
        for (int i = 0; i < 100; i++) {

            Crime crime = new Crime();
            crime.setTitle("Crime #" + i);
            crime.setSolved(i % 2 == 0); // Every other one

            mCrimes.put(crime.getId(), crime);
        }
    }

    [...]

    public Crime getCrime(UUID id) {
        return mCrimes.get(id);
    }
}

Since a good hash table implementation has an average search complexity of O(1), I think this will improve the performance of getCrime(), compared to the previous implementation which had a complexity of O(n).

However, since the challenge states that “making sure that CriminalIntent’s existing behavior remains unchanged as you refactor.”, I still need to get an ordered list of crimes in order to display them in the fragment, and I am a bit puzzled here…

My first solution was to implement the ‘getCrimes()’ method in the most simple way:

public List<Crime> getCrimes() {
    return new ArrayList<>(mCrimes.values());
}

However, with this solution, I get a list of crimes that are not ordered at all.

I then tried to refine a bit the solution above, sorting the array before returning it.
I have done this by slightly modifying the Crime class, implementing the Comparable<T> interface, and using the Collections.sort() method to sort the array.

public class Crime implements Comparable<Crime> {

    [...]

    @Override
    public int compareTo(Crime o) {
        return getTitle().compareTo(o.getTitle());
    }
}

Here, I am sorting the crimes per title…

public class CrimeLab {

    [...]

    public List<Crime> getCrimes() {
        ArrayList<Crime> crimes = new ArrayList<>(mCrimes.values());
        Collections.sort(crimes);

        return crimes;
    }

    [...]
}

However, I am still not satisfied with this solution.
Sorting over title does not bring the exact same result, since ‘Crime #10’ will always come before ‘Crime #2’ for example.

So the only viable solution I see, is to maintain both an ArrayList and a HashTable inside the CrimeLab class, each containing the complete list of crimes. Doing this will also avoid having to implement the Comparable<T> interface inside the Crime class, thus removing the need to take a decision on the sort criteria.

But I find this solution pretty ugly, since it will waste memory for storing twice the same information.

public class CrimeLab {

    [...]

    private Hashtable<UUID, Crime> mCrimesHashTable;
    private List<Crime>            mCrimesList;

    [...]

    private CrimeLab(Context context) {
        mCrimesHashTable = new Hashtable<>();
        mCrimesList      = new ArrayList<>();
        
        for (int i = 0; i < 100; i++) {

            Crime crime = new Crime();
            crime.setTitle("Crime #" + i);
            crime.setSolved(i % 2 == 0); // Every other one

            mCrimesHashTable.put(crime.getId(), crime);
            mCrimesList.add(crime);
        }
    }

    public List<Crime> getCrimes() {
        return mCrimesList;
    }

    public Crime getCrime(UUID id) {
        return mCrimesHashTable.get(id);
    }
}

Is this the optimal solution ?

In terms of complexity, it should be:

  • getCrime(UUID id) has a theoritical complexity of O(1), since a hash table is used
  • getCrimes() has a complexity of O(1) since it does not do any computation at all

However, as mentioned before, I am still asking myself if a better solution could be achieved by only using one single data structure to store the list of crimes. But, right now, I don’t see how…

2

Just change:

from:

private Hashtable<UUID, Crime> mCrimes;

to:

Map<UUID,Crime> mCrimes = new LinkedHashMap();

and:

return new ArrayList<>(mCrimes.values());

You will get a ordered list :wink:

1 Like
3

Oh…
My…
God…

Coming from a C background, I still think I have to get over all the different Java data structure interface implementations :slight_smile:

Thank you so much for the tip!

4

This is a very smart way. Thank you :slight_smile:

5

I’m posting the full solution for CrimeLab.java based on what @hugleo had to say, since it wasn’t immediately obvious to me, so maybe it will help others too.

package com.bignerdranch.android.criminalintent;

import android.content.Context;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.UUID;

public class CrimeLab {
    private static CrimeLab sCrimeLab;

    private Map<UUID,Crime> mCrimes;

    public static CrimeLab get(Context context) {
        if (sCrimeLab == null) {
            sCrimeLab = new CrimeLab(context);
        }
        return  sCrimeLab;
    }

    private CrimeLab(Context context) {
        mCrimes = new LinkedHashMap<>();
        for (int i = 0; i < 100; i++) {
            Crime crime = new Crime();
            crime.setTitle("Crime #" + i);
            crime.setSolved(i % 2 == 0); // Every other one
            mCrimes.put(crime.getId(), crime);
        }
    }

    public List<Crime> getCrimes() {
        return new ArrayList<>(mCrimes.values());
    }

    public Crime getCrime(UUID id) {
        return mCrimes.get(id);
    }

}
5 Likes
6

Great solution! If you wanted to save memory and sacrifice a little bit of efficiency per getCrime invocation (O(1) -> O(log(n))), you could just sort the list based on the UUID values before the list instantiation and perform a binary search on those values.

Here is the private constructorof CrimeLab:

private CrimeLab(Context context) {
 UUID[] uuidArray = new UUID[100];
 for(int i = 0; i < 100; i++) {
 uuidArray[i] = UUID.randomUUID();
 }
 Arrays.sort(uuidArray);
 mCrimes = new ArrayList<>();
 for(int i = 0; i < 100; i++) {
 boolean isEven = i % 2 == 0;
 Crime crime = new Crime(uuidArray[i]);
 crime.setTitle("Crime #" + i);
 crime.setSolved(isEven);
 crime.setPoliceRequired(!isEven);
 mCrimes.add(crime);
 }
}

Constructor in Crime.java:

public Crime(UUID uuid) {
 mId = uuid;
 mDate = DateFormat.getDateInstance(DateFormat.FULL).format(new Date());
}

Here is the compareTo() Implementation in Crime.java:

@Override
public int compareTo(@NonNull Crime o) {
 return mId.compareTo(o.getId());
}

Finally, here’s the binary search on getCrime(UUID id):

public Crime getCrime(UUID id) {
 Crime selectedCrime = new Crime(id);
 int index = Collections.binarySearch(mCrimes, selectedCrime);
 return mCrimes.get(index);
}

To improve on this, you could pass in the crime object opposed to the id in order to avoid unnecessary object creation. Hope this helps!