Našumo rinkinys ir sąrašai

Akivaizdu, kad HashSet<T> bendrosios paieškos paieškos našumas HashSet<T> didesnis nei bendrojo klasės List<T> . Tiesiog palyginkite maišos raktą su linijiniu požiūriu List<T> klasėje.

Tačiau apskaičiavimas maišos raktas gali paimti tam tikrą procesorių ciklą, todėl nedideliam elementų skaičiui tiesinė paieška gali būti tikra alternatyva „ HashSet<T> .

Mano klausimas: kur yra beprotybė?

Norėdami supaprastinti scenarijų (ir būti sąžiningai), tarkime, kad List<T> klasė naudoja elementą Equals() elementui identifikuoti.

288
30 сент. nustatė Michael Damatov rugsėjo 30 d 2008-09-30 00:24 '08 0:24 2008-09-30 00:24
@ 12 atsakymų

Daugelis žmonių sako, kad pasiekę dydį, kai greitis iš tikrųjų yra susijęs su tuo, kad „ HashSet<T> visada įveiks List<T> , tačiau tai priklauso nuo to, ką darote.

Tarkime, kad turite List<T> kuriame bus vidutiniškai 5 elementai. Didelių ciklų skaičiaus metu, jei vienas ciklas pridedamas arba ištrinamas iš vieno elemento, gali būti geriau, jei naudojate List<T> .

Aš jį patikrinau savo kompiuteryje ir, gerai, jis turi būti labai mažas, kad galėtumėte pasinaudoti „ List<T> . Trumpų eilučių sąraše pranašumas po 20 dydžio objektų po 5 dydžio

 1 item LIST strs time: 617ms 1 item HASHSET strs time: 1332ms 2 item LIST strs time: 781ms 2 item HASHSET strs time: 1354ms 3 item LIST strs time: 950ms 3 item HASHSET strs time: 1405ms 4 item LIST strs time: 1126ms 4 item HASHSET strs time: 1441ms 5 item LIST strs time: 1370ms 5 item HASHSET strs time: 1452ms 6 item LIST strs time: 1481ms 6 item HASHSET strs time: 1418ms 7 item LIST strs time: 1581ms 7 item HASHSET strs time: 1464ms 8 item LIST strs time: 1726ms 8 item HASHSET strs time: 1398ms 9 item LIST strs time: 1901ms 9 item HASHSET strs time: 1433ms 1 item LIST objs time: 614ms 1 item HASHSET objs time: 1993ms 4 item LIST objs time: 837ms 4 item HASHSET objs time: 1914ms 7 item LIST objs time: 1070ms 7 item HASHSET objs time: 1900ms 10 item LIST objs time: 1267ms 10 item HASHSET objs time: 1904ms 13 item LIST objs time: 1494ms 13 item HASHSET objs time: 1893ms 16 item LIST objs time: 1695ms 16 item HASHSET objs time: 1879ms 19 item LIST objs time: 1902ms 19 item HASHSET objs time: 1950ms 22 item LIST objs time: 2136ms 22 item HASHSET objs time: 1893ms 25 item LIST objs time: 2357ms 25 item HASHSET objs time: 1826ms 28 item LIST objs time: 2555ms 28 item HASHSET objs time: 1865ms 31 item LIST objs time: 2755ms 31 item HASHSET objs time: 1963ms 34 item LIST objs time: 3025ms 34 item HASHSET objs time: 1874ms 37 item LIST objs time: 3195ms 37 item HASHSET objs time: 1958ms 40 item LIST objs time: 3401ms 40 item HASHSET objs time: 1855ms 43 item LIST objs time: 3618ms 43 item HASHSET objs time: 1869ms 46 item LIST objs time: 3883ms 46 item HASHSET objs time: 2046ms 49 item LIST objs time: 4218ms 49 item HASHSET objs time: 1873ms 

Čia pateikiami duomenys, pateikti kaip grafikas:

2019

631
26 мая '12 в 4:35 2012-05-26 04:35 atsakymas pateikiamas innominate227 gegužės 26 d., 12 val

Jūs žiūrite į jį neteisingai. Taip, tiesinis paieškos sąrašas nugalės HashSet už nedidelį skaičių elementų. Tačiau mažų kolekcijų našumo skirtumai paprastai nesvarbu. Paprastai tai yra didelės kolekcijos, kurios jums reikia nerimauti ir ką galvojate „Big-O“ . Tačiau, jei matavote tikrąją „HashSet“ našumo spragą, galite pabandyti sukurti hibridinį „List / HashSet“, bet tai darote atlikdami daug empirinių testų - nepateikdami klausimų apie SO.

57
06 мая '10 в 6:43 2010-05-06 06:43 Atsakymą pateikė „ Eloff“ gegužės 06 d. 10 val. 6:43 2010-05-06 06:43

Nesvarbu, ar naudojant „HashSet <>“ ar „List <>“ pasirodys, kaip jums reikia prieiti prie savo kolekcijos . Jei reikia garantuoti prekių tvarką, naudokite sąrašą. Jei to nepadarysite, naudokite „HashSet“. Leiskite „Microsoft“ nerimauti įgyvendinant savo maišos algoritmus ir objektus.

„HashSet“ prieigą prie elementų, nenurodydama kolekcijos ( O (1) sudėtingumo ar šalia jo), taip pat todėl, kad „List“ garantuoja, kad, skirtingai nei „HashSet“, kai kurie elementai turi būti išvardyti (O (n) sudėtingumas).

43
30 сент. atsakymas pateikiamas 30 rugsėjo mėn. 2008-09-30 00:39 '08 0:39 2008-09-30 00:39

Tiesą sakant, nėra prasmės palyginti dvi veiklos sistemas, kurios elgiasi skirtingai. Naudokite struktūrą, kuri perduoda ketinimą. Net jei sakote, kad jūsų List<T> neturės dublikatų, o iteracijų tvarka nesvarbu, ar ji yra panaši į „ HashSet<T> , vis dar yra prastas pasirinkimas naudoti „ List<T> nes jis yra palyginti mažesnis klaidingas.

Tačiau aš patikrinsiu keletą kitų veiklos aspektų,

 +------------+--------+-------------+-----------+----------+----------+-----------+ | 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.

39
30 мая '14 в 10:45 2014-05-30 10:45 atsakymą pateikė nawfal gegužės 30 d. 14, 10:45 2014-05-30 10:45

Aš tiesiog maniau, kad norėčiau parodyti kai kuriuos scenarijus, kad būtų galima paaiškinti ankstesnius atsakymus:

  • Keletas (12-20) mažų linijų (ilgis nuo 5 iki 10 simbolių).
  • Daug (~ 10K) mažų linijų
  • Kelios ilgos eilutės (ilgis nuo 200 iki 1000 simbolių)
  • Daug (~ 5K) ilgųjų eilučių
  • Keli sveikieji skaičiai
  • Daug (~ 10 K) sveikųjų skaičių

Ir kiekvienam scenarijui, žiūrėdami į rodomas vertes:

  • Sąrašo viršuje („pradžia“, 0 rodyklė)
  • Sąrašo pradžioje („ankstyvas“, 1 rodyklė)
  • Sąrašo viduryje („vidutinis“, indeksų skaitiklis / 2)
  • Sąrašo pabaigoje („vėlai“, skaičiuokite skaičius-2)
  • Sąrašo pabaigoje („pabaiga“, indeksas-1)

Prieš kiekvieną scenarijų sukūriau atsitiktinai suskirstytus atsitiktinių eilučių sąrašus ir po to pateikiau kiekvieną sąrašą į hashset. Kiekvienas scenarijus buvo paleistas 10 000 kartų, daugiausia:

(bandomasis pseudokodas)

 stopwatch.start for X times exists = list.Contains(lookup); stopwatch.stop stopwatch.start for X times exists = hashset.Contains(lookup); stopwatch.stop 

Mėginio išėjimas

Išbandyta „Windows 7“, 12GB RAM, 64 bitų, „Xeon“ 2,8 GHz

 ---------- Testing few small strings ------------ Sample items: (16 total) vgnwaloqf diwfpxbv tdcdc grfch icsjwk ... Benchmarks: 1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec] 2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec] 3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec] 4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec] 5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec] 6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec] 7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec] 8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec] 9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec] 10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec] ---------- Testing many small strings ------------ Sample items: (10346 total) dmnowa yshtrxorj vthjk okrxegip vwpoltck ... Benchmarks: 1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec] 2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec] 3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec] 4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec] 5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec] 6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec] 7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec] 8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec] 9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec] 10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec] ---------- Testing few long strings ------------ Sample items: (19 total) hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji... ... Benchmarks: 1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec] 2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec] 3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec] 4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec] 5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec] 6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec] 7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec] 8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec] 9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec] 10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec] ---------- Testing many long strings ------------ Sample items: (5000 total) yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm ... Benchmarks: 1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec] 2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec] 3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec] 4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec] 5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec] 6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec] 7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec] 8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec] 9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec] 10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec] ---------- Testing few ints ------------ Sample items: (16 total) 7266092 60668895 159021363 216428460 28007724 ... Benchmarks: 1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec] 2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec] 3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec] 4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec] 5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec] 6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec] 7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec] 8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec] 9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec] 10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec] ---------- Testing many ints ------------ Sample items: (10357 total) 370826556 569127161 101235820 792075135 270823009 ... Benchmarks: 1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec] 2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec] 3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec] 4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec] 5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec] 6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec] 7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec] 8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec] 9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec] 10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec] 
18
26 окт. atsakymas duotas drzaus 26 okt. 2012-10-26 17:45 '12, 17:45, 2012-10-26 17:45

Raktų pakabukas priklausys nuo maišos skaičiavimo išlaidų. Hash skaičiavimai gali būti trivialūs arba ne ... :-) Visada yra System.Collections.Specialized.HybridDictionary klasė, kuri padės jums nerimauti dėl lūžio taško.

9
30 сент. Atsakymą pateikė Walden Leverich 30 rugsėjis 2008-09-30 00:29 '08 0:29 2008-09-30 00:29

Atsakymas, kaip visada, yra „ Tai priklauso .“ Manau, iš žymių, apie kurias kalbate, apie C #.

Geriausiai apibrėžta

  • Duomenų rinkinys
  • Reikalavimai naudojimui

ir parašykite keletą bandymų atvejų.

Tai taip pat priklauso nuo to, kaip surūšiuoti sąrašą (jei jis yra išrūšiuotas), kokie palyginimai turėtų būti atliekami, kiek laiko palyginimas operacija užima tam tikrą objektą sąraše, ar netgi, kaip planuojate naudoti kolekciją.

Paprastai geriausias pasirinkimas yra ne tiek duomenų, su kuriais dirbate, dydis, bet ir kaip jūs ją gausite. Ar turite kiekvieno duomenų, susijusių su konkrečia eilute ar kitais duomenimis? Dažniausiai surinkta kolekcija bus geriau. Ar duomenų saugojimo tvarka yra svarbi, ar jums reikės vienu metu pasiekti visus duomenis? Reguliarus sąrašas gali būti geresnis.

Neprivaloma:

Žinoma, pirmiau pateiktose pastabose manoma, kad „našumas“ reiškia prieigą prie duomenų. Kažkas dar reikia apsvarstyti: ko ieškote, kai sakote „našumas“? Ar atkuriama individuali veiklos vertė? Ar nustatoma didelių (10 000, 100 000 ar daugiau) vertės valdymas? Ar duomenų struktūra užpildo našumo duomenis? Duomenų trynimas? Prieiga prie atskirų duomenų bitų? Vertybių keitimas? Iteracija virš vertybių? Atminties naudojimas? Kopijuoti greitį? Pvz., Jei prieigos prie duomenų eilutės reikšme, bet pagrindiniai našumo reikalavimai yra minimalus atminties naudojimas, gali kilti prieštaringų projektavimo problemų.

6
30 сент. Atsakymą pateikė Robert P 30 Sep. 2008-09-30 00:32 '08 0:32 2008-09-30 00:32

Jūs galite naudoti „HybridDictionary“, kuri automatiškai aptinka tašką ir trunka nulines reikšmes, todėl labai svarbu, pavyzdžiui, „HashSet“.

5
23 окт. Muis atsakė spalio 23 d 2011-10-23 19:55 '11, 19:55, 2011-10-23 19:55

Tai priklauso nuo. Jei tikrasis atsakymas tikrai svarbus, atlikite kai kuriuos profilius ir sužinokite. Jei esate tikri, kad rinkinyje niekada nebus daugiau nei tam tikrų elementų, eikite su sąrašu. Jei numeris nėra ribotas, naudokite „HashSet“.

4
30 сент. Atsakymas, kurį pateikė Adam Rosenfield 30 Sep 2008-09-30 00:28 '08 0:28 2008-09-30 00:28

Tai priklauso nuo to, ką tu. Jei raktai yra sveiki, tikriausiai nereikia daug elementų, kol „HashSet“ yra greitesnis. Jei susiejate jį su eilute, jis bus lėtesnis ir priklauso nuo įvesties eilutės.

Žinoma, ar galite lengvai nutraukti etaloną?

3
30 сент. Atsakymas duotas Petro 30 rugsėjo. 2008-09-30 00:31 '08 0:31 2008-09-30 00:31

Vienas iš veiksnių, į kuriuos neatsižvelgiate, yra GetHashcode () funkcijos patikimumas. Puikios maišos funkcijos dėka „HashSet“ neabejotinai turės geresnius paieškos rezultatus. Tačiau nuo to laiko, kai maišos funkcija sumažėja, tai bus HashSet paieškos laikas.

3
30 сент. Atsakymas pateikiamas JaredPar 30 rugsėjis. 2008-09-30 01:56 '08, 1:56 am. 2008-09-30 01:56

Priklauso nuo daugelio veiksnių ... Sąrašo įgyvendinimas, procesoriaus architektūra, JVM, ciklo semantika, lygių metodų sudėtingumas ir kt. Iki to laiko, kai sąrašas yra pakankamai didelis, kad galėtų veiksmingai palyginti (1000 + elementų), „Hash“ pagal dvejetainę paiešką įveikia rankų režimo paieškas, o skirtumas tik padidėja.

Tikiuosi, kad tai padės!

1
30 сент. Atsakymas duotas Kyle 30 Sep. 2008-09-30 00:29 '08 0:29 2008-09-30 00:29

Peržiūrėkite kitus klausimus apie arba Užduokite klausimą