C # - Need suggestions for improving code section
I have a function that takes three different people objects and generates a new compatibility object based on the combined values in the people objects.
However, about 1/3 of the time, the three "people" objects it receives as input are the same as before, although perhaps in a different order. In these cases, I do NOT want to create a new "score" object, but simply return the value contained in the existing object.
Initially, the program simply iterates over the objects in the "compatibility" list, looking for the one belonging to the three "people" (since each "compatibility" object contains an array of people objects). This method is very slow considering that there are over a thousand "compatibility" objects and over a million "people" objects.
I got the idea of using a dictionary where the key is a number that I generated by concatenating the ID values of three people into a single UInt64 using XOR and storing the evaluation objects as dictionary values rather than a list. This cuts the time by about half and is acceptable in terms of timing, but there are too many collisions and it returns the wrong score too often.
Any suggestions or pointers would be much appreciated.
Edit: To add to the original question, each "people" object has a bunch of other fields that I could use, but the problem is creating a key that is UNIQUE and COMMUTATIVE.
I think you are looking at things in an overly complex way. Take the 3 PersonID values and sort them so that they are always in the same order, no matter what order they were passed in. Then set the value in the hash table using the three PersonIDs as the key, separated by a hyphen or some other character not found in the PersonID value. Then check if there is a value in the hash table with that key.
So, if the three PersonIDs are 10, 5 and 22, the hash key could be something like "5-10-22".
a source to share
The best option would be a custom class IEqualityComparer
. Declare yours Dictionary
like this
Dictionary<List<People>, Compatability> people =
new Dictionary<List<People>, Compatability>(new PersonListComparer());
You need to create a class PersonListComparer
that implements IEqualityComparer<List<People>>
. You need to implement two methods: one that gets the hash code and one that compares equality. Dictionary
will use GetHashCode
to determine if two POSSIBLY lists are equal, and a method Equals
to determine if they are actually valid (in other words, the hashcode is fast, but can give false positives, but never false negative). Use the existing hashing algorithm (XOR) for GetHashCode
and then just create the two lists explicitly in the method Equals
.
This should do the trick!
a source to share
Why not use people's names as a dictionary key? (Sort the names first so the order doesn't matter.) IE, John, Alice and Bob become something like my_dictionary ["Alice_Bob_John"] <- if this key exists, you've already computed the score, otherwise you need to compute it. As an alternative to my hack of the line above, you can actually use a structure:
NameTriple n = new NameTriple("John", "Alice", "Bob");
// NameTriple internally sorts the names.
my_dictionary[n] ...
If you want to keep everything in memory and not use a database, I would recommend something similar to a tree structure. Assuming your object IDs are sorted and order doesn't matter, you can accomplish this with nested dictionaries.
Namely, a Dictionary<Key, Dictionary<Key, Dictionary<Key, Compatibility>>>
should do the trick. Sort the identifiers and use the smallest value in the external dictionary, the next value in the next, and the final value to find the compatibility object. This way there will be no collisions and the search should be fairly quick.
Or, now that I think again, it shouldn't be that hard. Just use a string as a key and concatenate the ids together in sorted order with "!" or something else in between that doesn't occur naturally in identifiers.
a source to share
assuming all Person objects are unique, store the UUID in the object.
in your function, statically store the quad (P1, P2, P3, V), where P1, P2, P3 are the UUIDs of the Person object, sorted (to avoid the order problem) and V is the result of the previous calculation.
then your function checks to see if there is an entry for this Face triplet if it doesn't do the work and doesn't save it.
you can store the values (P1, P2, P3, V) in a dictionary, just drop some hash of three P values