Challenge Q2: Improving CrimeLab Performance


#1

I was wondering what the best solution would be in this challenge? I thought maybe converting the List to an ArrayList<> or LinkedList<> might be best but after thinking about it maybe it’s not. I think having a <key, Value> pair may be better. Something like a SparseArray or a HashMap/ArrayMap. I think ArrayMap would be the best since the UUID is an object and not a primitive type making the SparseArray implementation less desirable. The UUID can be used as the key referencing the Object mCrime.

I was wondering what you would recommend for this particular problem?


#2

I think there is a different solution to increase the perfomance in CrimeLab when you are trying to getCrime you are using UUID where in you compare that to every other id in list and return it back rather you can pass the adapter position and return that positioned crime in list would do the trick you dont have to compare the whole list this way.


#3

I am also curious to the solution on this challenge. I don’t think I quite understand this explanation:[quote=“reddy, post:2, topic:11572”]
rather you can pass the adapter position and return that positioned crime in list would do the trick you dont have to compare the whole list this way.
[/quote]

Does this mean do away with the ID altogether?


#4

I used a LinkedHashMap (with the UUIDs as the keys) in order to keep the crimes in the order they were inserted.


#5

@bignerd @cstewart Hi staff :grinning: Thanks for this great book. Loving every single page :clap::grinning:, an absolute page turner. However, I am currently stuck at this challenge. Some clues on how to improve CrimeLab’s performance would be great. Probably reading resources or name of a search algorithm. Something to get me started or to think in the lines of… Thanks! :grinning: :v:


#6

A LinkedHashMap sounds like a great solution. The big hit to performance in the book’s code is the loop that iterates over all of the crimes until it finds the correct one. A HashMap could solve this problem since it can lookup crimes instantly. The downside is that a HashMap does not guarantee the order of your items (which is important to us).

A LinkedHashMap has order built in and has a fast lookup time.


#7

This is how my CrimeLab.java looks like

public class CrimeLab {

private static CrimeLab crimeLab;
private List<Crime> crimes;
private Map<UUID, Crime> crimeMap;

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

private CrimeLab(Context context) {
    crimes = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        Crime crime = new Crime();
        crime.setTitle("Crime #" + i);
        crime.setSolved(i % 2 == 0);
        crimes.add(crime);
    }

    // Data representation for optimized crime search
    crimeMap = new HashMap<>();
    for (Crime crime : crimes) {
        crimeMap.put(crime.getId(), crime);
    }
}

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

public Crime getCrime(UUID id) {
    for (Crime crime : crimes) {
        if (crime.getId().equals(id)) return crime;
    }
    return null;
}

public Crime getCrimeQuickly(UUID id) {
    return crimeMap.get(id);
}

}

I have indexed the Crime objects by their corresponding IDs (UUID). However, even though I read about preserving the insertion order in the case of LinkedHashMap, it did not really strike me to use it. Anyways, considering that I am not impeded by the inherent unordered state of HashMap, does the LinkedHashMap
still provide better performance?