[問題] list和array的搜尋速度

看板C_and_CPP作者 (累人啊....)時間16年前 (2009/11/10 11:12), 編輯推噓5(5推 0噓 20→)
留言25則, 8人參與, 最新討論串1/1
如題,請問一下,若我現在有一個class class a{ int val1; int val2; ... } 以這個class來新增物件,然後用list當作容器裝起來 以及array(也就是a container[100]) 若現在要在裡面搜尋某個物件時 何者的速度快呢? 這是今天和老闆間的討論....@@ 我對這部份沒什麼概念,希望有熟悉的大大給我答案 並請提供一個有利的證據,讓我下次可以拿去跟老闆說.....^^ 再麻煩各位囉,謝謝... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 163.18.48.28
→
11/10 11:24, , 1F
要快不如用Hash
11/10 11:24, 1F
→
11/10 11:37, , 2F
O(1) 和 O(n) 哪個快？ QQ
11/10 11:37, 2F
→
11/10 11:57, , 3F
不懂....
11/10 11:57, 3F
推
11/10 12:05, , 4F
要看你知不知道某物件是放在哪個index下 這樣才有O(1)
11/10 12:05, 4F
→
11/10 12:05, , 5F
假設不知道的情況下 O(lgn) vs O(n) 的確前者會快，但這
11/10 12:05, 5F
→
11/10 12:06, , 6F
都是worst case 我也覺得如果只是考慮search那用hash最快
11/10 12:06, 6F
→
11/10 12:22, , 7F
不懂hash,剛查了一下,hash與set,map相關,阿我現在的結構
11/10 12:22, 7F
→
11/10 12:23, , 8F
都是list,意思是要快就要用hash,要砍掉重練?
11/10 12:23, 8F
→
11/10 12:26, , 9F
以及回到原來的問題,list,array,哪個快啊?
11/10 12:26, 9F
推
11/10 12:30, , 10F
要搜尋的東西有沒有排序過會影響純List與Array的速度.
11/10 12:30, 10F
→
11/10 12:30, , 11F
有排序過的資料是Array快, 如果沒排序要地毯搜索那一樣
11/10 12:30, 11F
→
11/10 12:30, , 12F
慢, 在這種情況你只能比較Array與List的存取速度而已.
11/10 12:30, 12F
→
11/10 13:48, , 13F
意思是在沒有排序的情況下會一樣慢囉?
11/10 13:48, 13F
→
11/10 13:50, , 14F
沒排序都只能linear search O(n)
11/10 13:50, 14F
推
11/10 14:48, , 15F
沒有排序的情況，還是random access的array比較快
11/10 14:48, 15F
→
11/10 14:49, , 16F
如果List實作是用指標串起來的link list(如std::list)
11/10 14:49, 16F
→
11/10 14:49, , 17F
linear search的速度比不上random access的array
11/10 14:49, 17F
→
11/10 14:50, , 18F
當然我不清楚你這裡講的array和list分別是哪一種實作品
11/10 14:50, 18F
→
11/10 15:30, , 19F
恩~,list就如你所說,不過不知道什麼是random access耶
11/10 15:30, 19F
→
11/10 15:30, , 20F
我指的array就如同上面的宣告的那種.....
11/10 15:30, 20F
推
11/10 16:48, , 21F
如果是native array，它作線性搜尋會比std::list快
11/10 16:48, 21F
→
11/10 20:40, , 22F
恩...謝謝,不過速度是有很明顯的差距嗎,還是快沒多少..
11/10 20:40, 22F
推
11/11 00:45, , 23F
呵呵呵 這個不知道是哪一家的陷阱題 loop array的複雜度
11/11 00:45, 23F
→
11/13 19:50, , 24F
list 是比較有彈性 和 空間利用 array是效率快但彈性小
11/13 19:50, 24F
→
11/13 19:51, , 25F
list的記憶體配置空間不是連續的 array是 所以array較快
11/13 19:51, 25F
‣ 更多 tyc5116 的文章
文章代碼(AID): #1A-DeWfy (C_and_CPP)