So, I’ve created some code to run tests.
It’s meant to filter through Dictionaries of any given type.
This is the extension method:
public static Dictionary<TKey, TValue> Filter<TKey, TValue>(this Dictionary<TKey, TValue> dictionary, Func<KeyValuePair<TKey, TValue>, bool> condition) {
Stack<KeyValuePair<TKey, TValue>> stack = new Stack<KeyValuePair<TKey, TValue>>();
Dictionary<TKey, TValue> filteredDictionary = new Dictionary<TKey, TValue>();
foreach (var entry in dictionary) {
stack.Push(entry);
}
while (stack.Count > 0) {
KeyValuePair<TKey, TValue> entry = stack.Pop();
if (condition(entry)) {
filteredDictionary.Add(entry.Key, entry.Value);
dictionary.Remove(entry.Key);
}
}
return filteredDictionary;
}
Then the code to generate a random list of employees:
void CreateListOfRandomEmployees(int numberOfEmployees) {
Stack<string> nameStack = new Stack<string>();
foreach (string name in randomNames) {
nameStack.Push(name);
}
for (int i = 0; i < numberOfEmployees; i++) {
string getName = nameStack.Pop();
KeyValuePair<string, Employee> newEmployee = new KeyValuePair<string, Employee>(getName, new Employee() {
name = getName,
sector = (Sector)UnityEngine.Random.Range(0, 5),
salary = UnityEngine.Random.Range(1000, 3500),
isFreelancer = UnityEngine.Random.value > 0.95f
});
listOfEmployees.Add(newEmployee.Key, newEmployee.Value);
}
}
Where the randomNames is just a string array with 1000 random names. I wasn’t worried about performance here since those “employees” are just to test.
Then, the test itself:
private void Update() {
int numberOfTests = 10;
string input = "B";
Sector sector = (Sector)UnityEngine.Random.Range(0, 5);
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();
for (int i = 0; i < numberOfTests; i++) {
Dictionary<string, Employee> filteredList = new Dictionary<string, Employee>();
Dictionary<string, Employee> topPriority = new Dictionary<string, Employee>();
Dictionary<string, Employee> midPriority = new Dictionary<string, Employee>();
Dictionary<string, Employee> lowPriority = new Dictionary<string, Employee>();
Dictionary<string, Employee> midFilterList = new Dictionary<string, Employee>();
foreach (var entry in listOfEmployees) {
midFilterList.Add(entry.Key, entry.Value);
}
topPriority = midFilterList.Filter(e => e.Value.sector == sector && e.Value.name.StartsWith(input));
midPriority = midFilterList.Filter(e => e.Value.name.StartsWith(input));
lowPriority = midFilterList.Filter(e => e.Value.sector == sector && e.Value.name.Contains(input));
foreach (var entry in topPriority) {
filteredList.Add(entry.Key, entry.Value);
}
foreach (var entry in midPriority) {
filteredList.Add(entry.Key, entry.Value);
}
foreach (var entry in lowPriority) {
filteredList.Add(entry.Key, entry.Value);
}
}
sw.Stop();
Debug.Log($"Elapsed: {sw.ElapsedMilliseconds} ms");
}
I’m getting between 14 ms and 19 ms running with the Editor on.
Since this represents 10 searches (although probably not truly representative since it’s using the same input string and sector for each of those 10 iterations), I’d guess it’s probably fast enough for mobile platforms since they’ll run the search only once, not 10 times.
Maybe I don’t need to implement tries and can just make do with “contains”. Those “names” include surnames, so there shouldn’t be any string much longer than those present in the test code.
Any thoughts?
In the actual app, I plan to use a Stack of Dictionaries to be my “filteredList” and the “midFilter” will get its values from there. So, if the user adds another character to the input, the previous “filteredList” goes to the top of the stack, and a new one is created with the filters. Then, if the user decides to remove the character that was just added, the previous list will simply be popped from the stack, instead of running the filters again.
EDIT: adding a “ToLower()” everywhere to ignore casing doubles the processing time. Any way around that?