0
Контексталгоритмы поиска
У меня есть список заказанных (по имени) объектов города в памяти, и мне нужно, чтобы получить список этих городов, как я печатаю характер, немного похож на предложение коробка.
Например:
Если список имеет Мадрид и Марсель название городов среди других, когда я нажимаю символ «M» Мне нужно получить Мадрид и Марсель в возвращаемом списке. Что ж, через пару лет я буду запускать пару потоков, чтобы ускорить работу, но в настоящее время с LINQ и TPL, и после нескольких тестов я пришел к выводу, что более быстрый способ использовать эти новые библиотеки вместо того, чтобы делать это вручную. Поэтому я написал несколько скриптов и проверил их друг против друга. Каждый код отрезала работает в своем собственном классе:
//Snippet 1
List<ICity> objCities = new List<ICity>();
foreach (ICity objCity in this.m_objCities)
{
if (objCity.Name.Length >= pName.Length)
{
if (objCity.Name.Substring(0, pName.Length).Equals(pName))
{
objCities.Add(objCity);
}
}
else if (objCitys.Count > 0)
{
break;
}
}
return objCities;
// SNIPPET 2
ICollection<ICity> objCities = base.m_objCities.Where((ICity pCity) =>
{
bool bFound = false;
if (pCity.Name.Length >= pName.Length)
{
bFound = pCity.Name.Substring(0, pName.Length).Equals(pName);
}
return bFound;
}).ToList();
return objCities;
// SNIPPET 3
ICollection<ICity> objCities = base.m_objCities.AsParallel().Where((ICity pCity) =>
{
bool bFound = false;
if (pCity.Name.Length >= pName.Length)
{
bFound = pCity.Name.Substring(0, pName.Length).Equals(pName);
}
return bFound;
}).ToList();
return objCities;
// SNIPPET 4
//Used as a class member
private List<ICollection<IStation>> objLastCities = new List<ICollection<IStation>>();
int iNameCount = pName.Length;
ICollection<ICity> objCities = null;
if (this.m_iLastNameCount == 0 || iNameCount == 1)
{
objCities = base.m_objCities.Where((ICity pCity) =>
{
bool bFound = false;
if (pCity.Name.Length >= pName.Length)
{
bFound = pCity.Name.Substring(0, pName.Length).Equals(pName);
}
return bFound;
}).ToList();
this.objLastCities.Clear();
this.objLastCities.Add(objCities);
this.m_iLastNameCount = 1;
}
else
{
if (iNameCount > this.m_iLastNameCount)
{
objCities = this.objLastCities[this.m_iLastNameCount - 1].Where((ICity pCity) =>
{
bool bFound = false;
if (pCity.Name.Length >= pName.Length)
{
bFound = pCity.Name.Substring(0, pName.Length).Equals(pName);
}
return bFound;
}).ToList();
this.objLastCities.Add(objCities);
this.m_iLastNameCount++;
}
else
{
objCities = base.m_objCities.Where((ICity pCity) =>
{
bool bFound = false;
if (pCity.Name.Length >= pName.Length)
{
bFound = pCity.Name.Substring(0, pName.Length).Equals(pName);
}
return bFound;
}).ToList();
this.objLastCities.RemoveAt(iNameCount - 1);
objCities = this.objLastCities[iNameCount - 1];
this.m_iLastNameCount--;
}
this.objLastCities.Add(objCities);
}
return this.objLastCities[this.objLastCities.Count - 1];
// Snippet 5
////Member objects
private List<ICollection<ICity>> objLastCities = new List<ICollection<ICity>>();
private int m_iLastNameCount = 0;
private Dictionary<char, ICollection<ICity>> m_objCitiesByKey = null;
////Code that runs in the class contructor
this.m_objCitiesByKey.Add('A', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'A'; }).ToList());
this.m_objCitiesByKey.Add('B', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'B'; }).ToList());
this.m_objCitiesByKey.Add('C', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'C'; }).ToList());
this.m_objCitiesByKey.Add('D', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'D'; }).ToList());
this.m_objCitiesByKey.Add('E', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'E'; }).ToList());
this.m_objCitiesByKey.Add('F', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'F'; }).ToList());
this.m_objCitiesByKey.Add('G', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'G'; }).ToList());
this.m_objCitiesByKey.Add('H', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'H'; }).ToList());
this.m_objCitiesByKey.Add('I', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'I'; }).ToList());
this.m_objCitiesByKey.Add('J', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'J'; }).ToList());
this.m_objCitiesByKey.Add('K', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'K'; }).ToList());
this.m_objCitiesByKey.Add('L', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'L'; }).ToList());
this.m_objCitiesByKey.Add('M', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'M'; }).ToList());
this.m_objCitiesByKey.Add('N', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'N'; }).ToList());
this.m_objCitiesByKey.Add('O', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'O'; }).ToList());
this.m_objCitiesByKey.Add('P', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'P'; }).ToList());
this.m_objCitiesByKey.Add('Q', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'Q'; }).ToList());
this.m_objCitiesByKey.Add('R', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'R'; }).ToList());
this.m_objCitiesByKey.Add('S', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'S'; }).ToList());
this.m_objCitiesByKey.Add('T', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'T'; }).ToList());
this.m_objCitiesByKey.Add('U', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'U'; }).ToList());
this.m_objCitiesByKey.Add('V', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'V'; }).ToList());
this.m_objCitiesByKey.Add('W', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'W'; }).ToList());
this.m_objCitiesByKey.Add('X', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'X'; }).ToList());
this.m_objCitiesByKey.Add('Y', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'Y'; }).ToList());
this.m_objCitiesByKey.Add('Z', base.m_objCities.Where((ICity pCity) => { return pCity.Name[0] == 'Z'; }).ToList());
////Code Running in a Methods
int iNameCount = pName.Length;
ICollection<ICity> objCities = null;
if (this.m_iLastNameCount == 0 || iNameCount == 1)
{
objCities = this.m_objCitiesByKey[pName[0]];
this.objLastCities.Clear();
this.objLastCities.Add(objCities);
this.m_iLastNameCount = 1;
}
else
{
if (iNameCount > this.m_iLastNameCount)
{
objCities = this.objLastCities[this.m_iLastNameCount - 1].Where((ICity pCity) =>
{
bool bFound = false;
if (pCity.Name.Length >= pName.Length)
{
bFound = pCity.Name.Substring(0, pName.Length).Equals(pName);
}
return bFound;
}).ToList();
this.objLastCities.Add(objCities);
this.m_iLastNameCount++;
}
else
{
objCities = base.m_objCities.Where((ICity pCity) =>
{
bool bFound = false;
if (pCity.Name.Length >= pName.Length)
{
bFound = pCity.Name.Substring(0, pName.Length).Equals(pName);
}
return bFound;
}).ToList();
this.objLastCities.RemoveAt(iNameCount - 1);
objCities = this.objLastCities[iNameCount - 1];
this.m_iLastNameCount--;
}
this.objLastCities.Add(objCities);
}
return this.objLastCities[this.objLastCities.Count - 1];
Основываясь на результате, я получаю с помощью класса Stopwatch, более быстрый скрипт - это номер 4, но я ожидал, что он будет номером 5, учитывая, что все города разделены в словаре, но к сожалению, класс словаря, похоже, замедляет работу.
Итак, вы, ребята, видите какой-либо способ улучшить производительность здесь?
Благодаря
Сколько городов вы его тестировали? – svick
Ваша оптимизация приносит в жертву простоту. Я не могу себе представить, что различия с простым решением plinq (3) достойны жертвы. Или они? И: не можете ли вы сначала выбрать страну, а затем предложить городам на выбор? –
Да, если замедление достаточно велико, чтобы быть заметным, 3 кажется лучшим выбором. Но вы упомянули, что города уже отсортированы по имени. В этом случае вы не могли бы использовать двоичный поиск, чтобы найти, с чего начать, а затем перейти оттуда с помощью plinq или без него? – Jamie