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;
//片段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;
//片段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;
//片段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];
根據我在秒錶類的幫助下得到的結果,更快的腳本是數字4,但我期待它是數字5,因爲所有的城市都分成了字典,但是不幸的是,字典課似乎是緩慢的方式。
那麼你們看到有什麼方法可以改善這裏的表現嗎?
謝謝
您測試過多少個城市? – svick 2012-04-09 08:45:48
您的優化犧牲了簡單性。我很難想象用簡單的plinq解決方案(3)的差異值得犧牲。或者他們?而且:你不能讓用戶先選擇一個國家,然後再提供城市進行選擇嗎? – 2012-04-09 20:23:30
是的,除非減速大到足以引起注意,3看起來是最好的選擇。但是你提到城市已經按名稱排序了。在這種情況下,您是否可以使用二分搜索來查找從哪裏開始尋找,然後從那裏開始,無論是否使用plinq? – Jamie 2012-04-13 20:36:34