HashSet與列表性能很明顯，泛型的搜索性能HashSet<T>類高于泛型類。List<T>班級(jí)，等級(jí)。只需將基于散列的密鑰與List<T>班級(jí)，等級(jí)。然而，計(jì)算散列鍵本身可能需要一些cpu周期，因此對(duì)于少量項(xiàng)，線性搜索可以真正替代HashSet<T>.我的問(wèn)題是：盈虧平衡在哪里？為了簡(jiǎn)化場(chǎng)景(為了公平起見)，讓我們假設(shè)List<T>類使用元素的Equals()方法標(biāo)識(shí)項(xiàng)。
3 回答
陪伴而非守候
TA貢獻(xiàn)1757條經(jīng)驗(yàn) 獲得超8個(gè)贊
HashSet<T>List<T>
List<T>List<T>.
List<T>
1 item LIST strs time: 617ms1 item HASHSET strs time: 1332ms2 item LIST strs time: 781ms2 item HASHSET strs time: 1354ms3 item LIST strs time : 950ms3 item HASHSET strs time: 1405ms4 item LIST strs time: 1126ms4 item HASHSET strs time: 1441ms5 item LIST strs time: 1370ms5 item H ASHSET strs time: 1452ms6 item LIST strs time: 1481ms6 item HASHSET strs time: 1418ms7 item LIST strs time: 1581ms7 item HASHSET strs time: 1464ms8 item LIST strs time: 1726ms8 item HASHSET strs time: 1398ms9 item LIST strs time: 1901ms9 item HASHSET strs time: 1433ms1 item LIST objs time: 614ms1 item HASHSET objs time: 1993ms4 item LIST objs time: 837ms4 item HASHSET objs time: 1914ms7 item LIST objs time: 1070ms7 i tem HASHSET objs time: 1900ms10 item LIST objs time: 1267ms10 item HASHSET objs time: 1904ms13 item LIST objs time: 1494ms13 item HASHSET ob js time: 1893ms16 item LIST objs time: 1695ms16 item HASHSET objs time: 1879ms19 item LIST objs time: 1902ms19 item HASHSET objs time: 195 0ms22 item LIST objs time: 2136ms22 item HASHSET objs time: 1893ms25 item LIST objs time: 2357ms25 item HASHSET objs time: 1826ms28 item LIST objs time: 2555ms28 item HASHSET objs time: 1865ms31 item LIST objs time: 2755ms31 item HASHSET objs time: 1963ms34 item LIST objs time: 3025ms34 item HASHSET objs time: 1874ms37 item LIST objs time: 3195ms37 item HASHSET objs time: 1958ms40 item LIST objs time: 3401ms4 0 item HASHSET objs time: 1855ms43 item LIST objs time: 3618ms43 item HASHSET objs time: 1869ms46 item LIST objs time: 3883ms46 item HASHS ET objs time: 2046ms49 item LIST objs time: 4218ms49 item HASHSET objs time: 1873ms
下面是代碼：
static void Main(string[] args){
int times = 10000000;
for (int listSize = 1; listSize < 10; listSize++)
{
List<string> list = new List<string>();
HashSet<string> hashset = new HashSet<string>();
for (int i = 0; i < listSize; i++)
{
list.Add("string" + i.ToString());
hashset.Add("string" + i.ToString());
}
Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
list.Remove("string0");
list.Add("string0");
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
hashset.Remove("string0");
hashset.Add("string0");
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
Console.WriteLine();
}
for (int listSize = 1; listSize < 50; listSize+=3)
{
List<object> list = new List<object>();
HashSet<object> hashset = new HashSet<object>();
for (int i = 0; i < listSize; i++)
{
list.Add(new object());
hashset.Add(new object());
}
object objToAddRem = list[0];
Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
list.Remove(objToAddRem);
list.Add(objToAddRem);
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
timer = new Stopwatch();
timer.Start();
for (int i = 0; i < times; i++)
{
hashset.Remove(objToAddRem);
hashset.Add(objToAddRem);
}
timer.Stop();
Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
Console.WriteLine();
}
Console.ReadLine();}
largeQ
TA貢獻(xiàn)2039條經(jīng)驗(yàn) 獲得超8個(gè)贊
紅糖糍粑
TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超6個(gè)贊
從本質(zhì)上說(shuō)，比較兩種結(jié)構(gòu)是毫無(wú)意義的。性能行為不同的人。使用傳達(dá)意圖的結(jié)構(gòu)。即使你說(shuō)List<T>不會(huì)有重復(fù)，迭代順序也不重要，使其與HashSet<T>，使用它仍然是一個(gè)糟糕的選擇。List<T>因?yàn)樗娜蒎e(cuò)能力相對(duì)較低。
盡管如此，我會(huì)檢查其他方面表現(xiàn)，
+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition | Removal | Memory |
| | access | | | | | |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T> | O(1) | O(n) | O(n) | O(1)* | O(n) | Lesser |
| HashSet<T> | O(n) | O(1) | n/a | O(1) | O(1) | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+
* Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it.
** The superior scalability of HashSet<T> has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.
- 3 回答
- 0 關(guān)注
- 718 瀏覽
添加回答
舉報(bào)
0/150
提交
取消