I created a bit of a hybrid based on a suffix array / dictionary. Thanks to saibot for suggesting it first and all other people helping and suggesting.
This is what I came up with:
public class CitiesCollection
{
private Dictionary<int, City> _cities;
private SuffixDict<int> _suffixdict;
public CitiesCollection(IEnumerable<City> cities, int minLen)
{
_cities = cities.ToDictionary(c => c.Id);
_suffixdict = new SuffixDict<int>(minLen, _cities.Values.Count);
foreach (var c in _cities.Values)
_suffixdict.Add(c.Name, c.Id);
}
public IEnumerable<City> Find(string find)
{
var normalizedFind = _suffixdict.NormalizeString(find);
foreach (var id in _suffixdict.Get(normalizedFind).Where(v => _cities[v].Name.IndexOf(normalizedFind, StringComparison.OrdinalIgnoreCase) >= 0))
yield return _cities[id];
}
}
public class SuffixDict<T>
{
private readonly int _suffixsize;
private ConcurrentDictionary<string, IList<T>> _dict;
public SuffixDict(int suffixSize, int capacity)
{
_suffixsize = suffixSize;
_dict = new ConcurrentDictionary<string, IList<T>>(Environment.ProcessorCount, capacity);
}
public void Add(string suffix, T value)
{
foreach (var s in GetSuffixes(suffix))
AddDict(s, value);
}
public IEnumerable<T> Get(string suffix)
{
return Find(suffix).Distinct();
}
private IEnumerable<T> Find(string suffix)
{
foreach (var s in GetSuffixes(suffix))
{
if (_dict.TryGetValue(s, out var result))
foreach (var i in result)
yield return i;
}
}
public string NormalizeString(string value)
{
return value.Normalize().ToLowerInvariant();
}
private void AddDict(string suffix, T value)
{
_dict.AddOrUpdate(suffix, (s) => new List<T>() { value }, (k, v) => { v.Add(value); return v; });
}
private IEnumerable<string> GetSuffixes(string value)
{
var nv = NormalizeString(value);
for (var i = 0; i <= nv.Length - _suffixsize ; i++)
yield return nv.Substring(i, _suffixsize);
}
}
Usage (where I assume mycities to be an IEnumerable<City> with the given City object from the question):
var cc = new CitiesCollection(mycities, 3);
var results = cc.Find("york");
Some results:
Find: sterda elapsed: 00:00:00.0220522 results: 32
Find: york elapsed: 00:00:00.0006212 results: 155
Find: dorf elapsed: 00:00:00.0086439 results: 6095
Memory usage is very, very acceptable. Only 650MB total having the entire collection of 3,000,000 cities in memory.
In the above I'm storing Id's in the "SuffixDict" and I have a level of indirection (dictionary lookups to find id=>city). This can be further simplified to:
public class CitiesCollection
{
private SuffixDict<City> _suffixdict;
public CitiesCollection(IEnumerable<City> cities, int minLen, int capacity = 1000)
{
_suffixdict = new SuffixDict<City>(minLen, capacity);
foreach (var c in cities)
_suffixdict.Add(c.Name, c);
}
public IEnumerable<City> Find(string find, StringComparison stringComparison = StringComparison.OrdinalIgnoreCase)
{
var normalizedFind = SuffixDict<City>.NormalizeString(find);
var x = _suffixdict.Find(normalizedFind).ToArray();
foreach (var city in _suffixdict.Find(normalizedFind).Where(v => v.Name.IndexOf(normalizedFind, stringComparison) >= 0))
yield return city;
}
}
public class SuffixDict<T>
{
private readonly int _suffixsize;
private ConcurrentDictionary<string, IList<T>> _dict;
public SuffixDict(int suffixSize, int capacity = 1000)
{
_suffixsize = suffixSize;
_dict = new ConcurrentDictionary<string, IList<T>>(Environment.ProcessorCount, capacity);
}
public void Add(string suffix, T value)
{
foreach (var s in GetSuffixes(suffix, _suffixsize))
AddDict(s, value);
}
public IEnumerable<T> Find(string suffix)
{
var normalizedfind = NormalizeString(suffix);
var find = normalizedfind.Substring(0, Math.Min(normalizedfind.Length, _suffixsize));
if (_dict.TryGetValue(find, out var result))
foreach (var i in result)
yield return i;
}
private void AddDict(string suffix, T value)
{
_dict.AddOrUpdate(suffix, (s) => new List<T>() { value }, (k, v) => { v.Add(value); return v; });
}
public static string NormalizeString(string value)
{
return value.Normalize().ToLowerInvariant();
}
private static IEnumerable<string> GetSuffixes(string value, int suffixSize)
{
var nv = NormalizeString(value);
if (value.Length < suffixSize)
{
yield return nv;
}
else
{
for (var i = 0; i <= nv.Length - suffixSize; i++)
yield return nv.Substring(i, suffixSize);
}
}
}
This bumps the load time up from 00:00:16.3899085 to 00:00:25.6113214, memory usage goes down from 650MB to 486MB. Lookups/searches perform a bit better since we have one less level of indirection.
Find: sterda elapsed: 00:00:00.0168616 results: 32
Find: york elapsed: 00:00:00.0003945 results: 155
Find: dorf elapsed: 00:00:00.0062015 results: 6095
I'm happy with the results so far. I'll do a little polishing and refactoring and call it a day! Thanks everybody for the help!
And this is how it performs with 2,972,036 cities:
This has evolved into a case-insensitive, accent-insensitive search by modifying the code to this:
public static class ExtensionMethods
{
public static T FirstOrDefault<T>(this IEnumerable<T> src, Func<T, bool> testFn, T defval)
{
return src.Where(aT => testFn(aT)).DefaultIfEmpty(defval).First();
}
public static int IndexOf(this string source, string match, IEqualityComparer<string> sc)
{
return Enumerable.Range(0, source.Length) // for each position in the string
.FirstOrDefault(i => // find the first position where either
// match is Equals at this position for length of match (or to end of string) or
sc.Equals(source.Substring(i, Math.Min(match.Length, source.Length - i)), match) ||
// match is Equals to on of the substrings beginning at this position
Enumerable.Range(1, source.Length - i - 1).Any(ml => sc.Equals(source.Substring(i, ml), match)),
-1 // else return -1 if no position matches
);
}
}
public class CaseAccentInsensitiveEqualityComparer : IEqualityComparer<string>
{
private static readonly CompareOptions _compareoptions = CompareOptions.IgnoreCase | CompareOptions.IgnoreNonSpace | CompareOptions.IgnoreKanaType | CompareOptions.IgnoreWidth | CompareOptions.IgnoreSymbols;
private static readonly CultureInfo _cultureinfo = CultureInfo.InvariantCulture;
public bool Equals(string x, string y)
{
return string.Compare(x, y, _cultureinfo, _compareoptions) == 0;
}
public int GetHashCode(string obj)
{
return obj != null ? RemoveDiacritics(obj).ToUpperInvariant().GetHashCode() : 0;
}
private string RemoveDiacritics(string text)
{
return string.Concat(
text.Normalize(NormalizationForm.FormD)
.Where(ch => CharUnicodeInfo.GetUnicodeCategory(ch) != UnicodeCategory.NonSpacingMark)
).Normalize(NormalizationForm.FormC);
}
}
public class CitiesCollection
{
private SuffixDict<City> _suffixdict;
private HashSet<string> _countries;
private Dictionary<int, City> _cities;
private readonly IEqualityComparer<string> _comparer = new CaseAccentInsensitiveEqualityComparer();
public CitiesCollection(IEnumerable<City> cities, int minLen, int capacity = 1000)
{
_suffixdict = new SuffixDict<City>(minLen, _comparer, capacity);
_countries = new HashSet<string>();
_cities = new Dictionary<int, City>(capacity);
foreach (var c in cities)
{
_suffixdict.Add(c.Name, c);
_countries.Add(c.Country);
_cities.Add(c.Id, c);
}
}
public City this[int index] => _cities[index];
public IEnumerable<string> Countries => _countries;
public IEnumerable<City> Find(string find, StringComparison stringComparison = StringComparison.OrdinalIgnoreCase)
{
foreach (var city in _suffixdict.Find(find).Where(v => v.Name.IndexOf(find, _comparer) >= 0))
yield return city;
}
}
public class SuffixDict<T>
{
private readonly int _suffixsize;
private ConcurrentDictionary<string, IList<T>> _dict;
public SuffixDict(int suffixSize, IEqualityComparer<string> stringComparer, int capacity = 1000)
{
_suffixsize = suffixSize;
_dict = new ConcurrentDictionary<string, IList<T>>(Environment.ProcessorCount, capacity, stringComparer);
}
public void Add(string suffix, T value)
{
foreach (var s in GetSuffixes(suffix, _suffixsize))
AddDict(s, value);
}
public IEnumerable<T> Find(string suffix)
{
var find = suffix.Substring(0, Math.Min(suffix.Length, _suffixsize));
if (_dict.TryGetValue(find, out var result))
{
foreach (var i in result)
yield return i;
}
}
private void AddDict(string suffix, T value)
{
_dict.AddOrUpdate(suffix, (s) => new List<T>() { value }, (k, v) => { v.Add(value); return v; });
}
private static IEnumerable<string> GetSuffixes(string value, int suffixSize)
{
if (value.Length < 2)
{
yield return value;
}
else
{
for (var i = 0; i <= value.Length - suffixSize; i++)
yield return value.Substring(i, suffixSize);
}
}
}
With credit also to Netmage and Mitsugui. There are still some issues / edge-cases but it's continually improving!
