Самый быстрый способ сравнить объекты в C#

Question

Я пишу приложение, которое проверяет некоторые города. Часть проверки проверяет, находится ли город в списке, сопоставляя код страны и имя города (или имя города).

Я храню мой список существующих городов, как:

public struct City 
{ 
    public int id; 
    public string countrycode; 
    public string name; 
    public string altName; 
    public int timezoneId; 
} 

List<City> cityCache = new List<City>(); 

Я тогда список строк местоположения, которые содержат коды стран и название городов и т.д. Я разделить эту строку, а затем проверить, если город уже существует.

string cityString = GetCity(); //get the city string 
string countryCode = GetCountry(); //get the country string 
city = new City();    //create a new city object 
if (!string.IsNullOrEmpty(cityString)) //don't bother checking if no city was specified 
{ 
    //check if city exists in the list in the same country 
    city = cityCache.FirstOrDefault(x => countryCode == x.countrycode && (Like(x.name, cityString) || Like(x.altName, cityString))); 
    //if no city if found, search for a single match accross any country 
    if (city.id == default(int) && cityCache.Count(x => Like(x.name, cityString) || Like(x.altName, cityString)) == 1) 
     city = cityCache.FirstOrDefault(x => Like(x.name, cityString) || Like(x.altName, cityString)); 
} 

if (city.id == default(int)) 
{ 
    //city not matched 
} 

Это очень медленно для многих записей, так как я также проверяю другие объекты, такие как аэропорты и страны таким же образом. Есть ли способ ускорить это? Есть ли более быстрый набор для такого сравнения, чем List <>, и есть ли более быстрая функция сравнения, которая FirsOrDefault()?

EDIT

Я забыл опубликовать свою функцию, как():

bool Like(string s1, string s2) 
    { 
     if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) 
      return s1 == s2; 
     if (s1.ToLower().Trim() == s2.ToLower().Trim()) 
      return true; 

     return Regex.IsMatch(Regex.Escape(s1.ToLower().Trim()), Regex.Escape(s2.ToLower().Trim()) + "."); 
    } 

Answer 1

Я хотел бы использовать HashSet для CityString и COUNTRYCODE. Что-то вроде

var validCountryCode = new HashSet<string>(StringComparison.OrdinalIgnoreCase); 
if (validCountryCode.Contains(city.CountryCode)) 
{ 
} 

и т.д ...

Лично я хотел бы сделать все проверки в конструкторе, чтобы обеспечить существование только действительные объекты города.

Другие вещи, чтобы следить за производительностью

1. Используйте HashSet если вы смотрите его в действительном списке.
2. Используйте IEqualityComparer, где необходимо, повторно используйте объект, чтобы избежать затрат на строительство/GC.
3. Используйте словарь для чего вам нужно для поиска (например timeZoneId)

Edit 1

Вы cityCache может быть что-то вроде,

var cityCache = new Dictionary<string, Dictionary<string, int>>(); 
var countryCode = ""; 
var cityCode = ""; 
var id = x; 

public static IsCityValid(City c) 
{ 
    return 
     cityCache.ContainsKey(c.CountryCode) && 
     cityCache[c.CountryCode].ContainsKey(c.CityCode) && 
     cityCache[c.CountryCode][c.CityCode] == c.Id; 
} 

Edit 2

Не думал, что я должен это объяснить, но возможно, на основе комментариев.

FirstOrDefault() является операцией O (n). По сути, каждый раз, когда вы пытаетесь найти что-то в списке, вам может быть повезло, и он является первым в списке, или неудачным, и он является последним, средним числом list.Count/2. С другой стороны, словарь будет поиск O (1). Используя IEqualtiyComparer, он будет генерировать HashCode() и будет искать, в каком ведре он сидит. Если есть множество коллизий, тогда он будет использовать Equals, чтобы найти то, что вам нужно, в списке вещей в том же ведре. Даже с низким качеством HashCode() (не дожидаясь возвращения одного и того же HashCode всегда), потому что Dictionary/HashSet используйте ведра счисления большого числа, вы разделите свой список, уменьшив количество необходимых вам условий.

Итак, список из 10 объектов означает, что вы в среднем работаете LIKE 5 раз. Словарь из тех же 10 объектов, что и ниже (в зависимости от качества HashCode), может быть всего одним вызовом HashCode(), за которым следует один вызов Equals().

Answer 2

Это звучит как хороший кандидат на двоичное дерево.

Для бинарных реализаций дерева в .NET см: Objects that represent trees

EDIT:
Если вы хотите найти коллекцию быстро, и что коллекция особенно велика, то лучшим вариантом является для сортировки и реализовать алгоритм поиска на основе этой сортировки.

Двоичные деревья - хороший вариант, когда вы хотите быстро искать и вставлять предметы относительно редко. Тем не менее, чтобы сохранить ваши поиски, вам нужно использовать балансировочное двоичное дерево.

Для правильной работы вам также понадобится стандартный ключ для использования в ваших городах. Цифровой ключ был бы лучше, но строки тоже могут работать отлично. Если вы объедините свой город с другой информацией (например, государством и страной), вы получите отличный уникальный ключ. Вы также можете изменить регистр на все верхние или нижние регистры, чтобы получить ключ, не учитывающий регистр.

Если у вас нет ключа, вы не можете сортировать свои данные. Если вы не можете сортировать свои данные, тогда не будет много «быстрых» вариантов.

EDIT 2:
Я заметил, что ваша функция, как редактирует ваши строки много. Редактирование строки - чрезвычайно дорогостоящая операция. Вам будет намного лучше выполнять функции ToLower() и Trim() один раз, предпочтительно, когда вы сначала загружаете свои данные. Это, вероятно, значительно ускорит вашу функцию.