Kada naudoti susietą sąrašą pagal masyvo / masyvų sąrašą?

Aš naudoju daugybę sąrašų ir masyvų, bet vis dar turiu susidurti su scenarijumi, kuriame masyvų sąrašas negali būti naudojamas kaip lengvai, jei ne paprastesnis, susietas sąrašas. Tikėjausi, kad kas nors gali duoti man keletą pavyzdžių, kai susietas sąrašas yra žymiai geresnis.

135
26 дек. nustatyti faceless1_14 26 dec. 2008-12-26 09:52 '08 at 9:52 2008-12-26 09:52
@ 13 atsakymų

Susieti sąrašai yra tinkamesni už masyvus, kai:

  1. jums reikia nuolatinių įterpimų / išbraukimų iš sąrašo (pvz., realaus laiko skaičiavimais, kai laiko nuspėjamumas yra būtinas)

  2. Nežinote, kiek elementų bus sąraše. Jei naudojate matricas, gali tekti iš naujo nustatyti ir kopijuoti atmintį, jei masyvas tampa per didelis.

  3. jums nereikia atsitiktinės prieigos prie bet kokių elementų

  4. Norite įterpti elementus į sąrašo vidurį (pvz., Prioritetinės eilės)

Tinkleliai yra pirmenybė, kai:

  1. jums reikia indeksuotos / atsitiktinės prieigos prie elementų

  2. Iš anksto žinote masyvo elementų skaičių, kad matricai būtų galima skirti tinkamą atminties kiekį.

  3. Jums reikia greičio, kai rūšiuojate visus sekos elementus. Galite pasiekti rodyklę prie masyvo, kad galėtumėte pasiekti kiekvieną elementą, o jums reikia ieškoti mazgo pagal rodyklę kiekvienam susieto sąrašo elementui, kuris gali sukelti puslapių gedimus, o tai gali lemti našumo sumažėjimą.

  4. atmintis yra problema. Užpildytos matricos užima mažiau atminties nei susieti sąrašai. Kiekvienas masyvo elementas yra tik duomenys. Kiekvienas susieto sąrašo mazgas reikalauja duomenų ir vieno (arba daugiau) nuorodų į kitus susieto sąrašo elementus.

„Array“ sąrašai (pvz., „Net“) suteikia jums masyvų privalumus, tačiau dinamiškai paskirsto išteklius jums, todėl nereikia per daug nerimauti dėl sąrašo dydžio ir galite ištrinti bet kurio indekso elementus be jokių pastangų ar pasikartojimų. elementų maišymas. Veikimo požiūriu masyvai yra lėtesni nei žaliavos.

217
26 дек. Atsakymą Lamar pateikė 26 d. 2008-12-26 10:12 '08, 10:12, 2008-12-26 10:12

Įrenginiai turi O (1) atsitiktinę prieigą, tačiau labai brangu pridėti medžiagą ar pašalinti daiktus.

Susieti sąrašai yra tikrai pigūs, jei norite pridėti ar pašalinti elementus bet kur ir pakartotinai, bet atsitiktinė prieiga yra O (n).

46
26 дек. Atsakymas duotas Dustin 26 d. 2008-12-26 10:08 '08, 10:08 2008-12-26 10:08

Jei norite pridėti kitų atsakymų, dauguma masyvų sąrašo diegimų rezervo papildomą talpą sąrašo pabaigoje, kad naujus elementus būtų galima pridėti prie sąrašo O (1) laikų pabaigos. Kai masyvo talpa viršijama, naujas didesnis masyvas yra priskirtas viduje, o visi seni elementai nukopijuojami. Paprastai nauja masyvas yra dvigubai didesnis už seną. Tai reiškia, kad vidutiniškai naujų elementų įtraukimas į masyvų sąrašo pabaigą yra O (1) operacija šiose realizacijose. Todėl, net jei nežinote elementų skaičiaus iš anksto, masyvų sąrašas gali būti greitesnis nei susietas sąrašas, jei norite pridėti elementų, jei juos įtraukiate į pabaigą. Akivaizdu, kad naujų elementų įterpimas į savitą vietą masyvų sąraše vis dar yra O (n) operacija.

Prieiga prie masyvų sąrašo elementų taip pat yra greitesnė nei susietas sąrašas, net jei skambučiai yra nuoseklūs. Taip yra dėl to, kad masyvo elementai yra saugomi nepertraukiamoje atmintyje ir gali būti lengvai saugomi. Mazgai su sąrašu gali būti išsklaidyti keliuose puslapiuose.

Jei žinote, ką ketinate įterpti ar ištrinti savavališkose vietose, rekomenduoju naudoti tik susietą sąrašą. Array sąrašai bus greitesni visai kitai.

14
26 дек. Jay Conrod atsakymas, gruodžio 26 d 2008-12-26 12:13 '08, 12:13, 2008-12-26 12:13
 Algorithm ArrayList LinkedList seek front O(1) O(1) seek back O(1) O(1) seek to index O(1) O(N) insert at front O(N) O(1) insert at back O(1) O(1) insert after an item O(N) O(1) 

„ArrayLists“ yra tinkamas rašyti kartą skaitomiems ar daugeliui priedų, bet ne geras, kai pridedate / ištrinate prieš tai viduryje.

12
01 авг. atsakymas pateikiamas Vpn_talent 01 rug . 2017-08-01 11:52 '17 at 11:52 2017-08-01 11:52

Sąrašų pranašumas atsiranda, jei norite įterpti elementus viduryje ir nenorite pradėti matricos dydžio keitimo ir judančių dalykų.

Jūs teisus, kad taip paprastai nėra. Turėjau keletą tokių konkrečių atvejų, bet ne per daug.

7
26 дек. atsakymą pateikė Uri 26 d. 2008-12-26 10:07 '08, 10:07 2008-12-26 10:07

Tai yra dažniausiai panaudoti kolekcija.

„ArrayList“:

  • Įterpti / ištrinti pabaigoje apskritai O (1) blogiausiu atveju O (n)

  • Įterpti / ištrinti O (n) viduryje

  • gauti bet kokią padėtį O (1)

Susietas sąrašas

  • Įterpti / ištrinti bet kurioje padėtyje O (1) (atkreipkite dėmesį, jei turite nuorodą į elementą)

  • išgauti O (n) viduryje

  • ištraukti pirmąjį arba paskutinį O (1) elementą

Vektorius: nenaudokite. Tai senas įgyvendinimas, panašus į „ArrayList“, bet su visais sinchronizuotais metodais. Tai nėra teisingas požiūris į bendrąjį sąrašą daugiapakopėje aplinkoje.

Hashmap

Įterpti / pašalinti / pašalinti raktą į O (1)

„TreeSet“ įterpti / ištrinti / yra O (log N)

„HashSet“ įterpti / ištrinti / yra / dydis O (1)

2
04 июля '15 в 16:26 2015-07-04 16:26 atsakymą pristato Praveen Kumar Verma liepos 4 d. 15 d. 16:26 2015-07-04 16:26

Viskas priklauso nuo to, kokio tipo operacijos atliksite iteracijos metu, visos duomenų struktūros turi kompromisą tarp laiko ir atminties, ir, priklausomai nuo mūsų poreikių, turime pasirinkti tinkamą DS. Taigi yra atvejų, kai „LinkedList“ yra greitesnis nei masyvas, ir atvirkščiai. Apsvarstykite tris pagrindines duomenų struktūrų operacijas.

  • Paieška

Kadangi masyvas yra indekso duomenų struktūra, paieškos masyvas.get (indeksas) užtruks O (1) kartus, o susietas sąrašas nėra DS indeksas, todėl jums reikia eiti per indeksą, kur indeksas <= n, n yra susieto sąrašo dydis, todėl masyvas turi greitesnį susietą sąrašą su atsitiktine prieiga prie elementų.

Q. Koks yra šio grožio grožis?

Kadangi matricos yra gretimos atminties blokai, didelės jų dalys bus įkeliamos į talpyklą, kai jos bus pirmą kartą pasiekiamos, todėl ji gana greitai pasiekia likusių masyvo elementų prieigą, nes mes pasiekiame masyvo nuorodų vietovės elementus, taip pat padidėja spragų praleidimas, taip sumažinant spragų praleidimus, talpyklos vieta reiškia operacijas, esančias talpykloje, todėl veikia daug greičiau nei atmintis, daugiausia masyvo, mes maksimaliai padidiname prieigos prie nuoseklaus elemento tikimybę „ntu“ talpykloje. Nors susieti sąrašai nebūtinai yra gretimose atminties blokuose, nėra jokių garantijų, kad sąraše eilės rodomi elementai iš tikrųjų yra vienas šalia kito atmintyje, o tai reiškia, kad, pavyzdžiui, įeina mažiau talpyklų. daugiau talpyklų praleidžiama, nes kiekvienai prieigai prie atitinkamo sąrašo elemento reikia perskaityti iš atminties, kuri padidina laiką, per kurį reikia prieiti prie jų ir pabloginti našumą, taigi, jei darysime daugiau atsitiktinės prieigos prie panašių paieškos operacijų, masyvas bus greitas, kaip aprašyta toliau.

  • Įterpti

Tai yra greita ir paprasta „LinkedList“, nes priedas yra O (1) operacija „LinkedList“ („Java“), palyginti su masyvu, apsvarstykite atvejį, kai masyvas yra pilnas, turinį reikia nukopijuoti į naują masyvą, jei masyvas užpildytas, jis įterpia elementą į O (n) ArrayList blogiausiu atveju, o „ArrayList“ taip pat turi atnaujinti savo indeksą, jei įterpiate kažką bet kur, išskyrus masyvo pabaigą, jei susieto sąrašo atveju nereikia keisti jo dydžio, tiesiog reikia atnaujinti rodyklės.

  • Ištrinimas

Jis veikia kaip įterpimas ir yra geresnis „LinkedList“ nei masyve.

1
16 апр. Atsakymas pateikiamas Harleen 16 balandžio. 2016-04-16 12:32 '16 at 12:32 2016-04-16 12:32

Hmm, Arraylist galima naudoti šiais atvejais:

  • Nežinote, kiek elementų bus.
  • bet jums reikia prieiti prie visų elementų atsitiktinai naudojant indeksavimą

Pvz., Turite importuoti ir pasiekti visus kontaktų sąrašo elementus (kurių dydis jums nežinomas)

0
26 дек. Atsakymą pateikė Raghu 26 d. 2008-12-26 10:28 '08, 10:28 2008-12-26 10:28

Manau, pagrindinis skirtumas yra tai, ar dažnai įterpti ar ištrinti elementus iš sąrašo viršaus.

Su masyvu, jei ištrinsite kažką iš sąrašo viršaus, nei sudėtingumas yra o (n), nes visi masyvo elementų rodikliai turės judėti.

Su susietu sąrašu, tai yra o (1), nes jums reikia tik sukurti mazgą, paskirti galvą ir priskirti nuorodą į kitą kaip ankstesnį skyrių.

Kai dažnai įterpiate ar ištrinate sąrašo pabaigą, pageidautina matricos, nes sudėtingumas yra o (1), reindeksavimas nereikalingas, bet susietam sąrašui jis bus o (n), nes reikia pereiti nuo galvos iki paskutinio mazgo.

Manau, kad paieška susietuose sąrašuose ir matricose bus o (log n), nes tikriausiai naudosite dvejetainę paiešką.

0
31 янв. atsakymas pateikiamas Curious_goat, sausio 31 d 2016-01-31 19:00 '16 19:00 val. 2016-01-31 19:00

Tiesą sakant, atminties vietovė turi didžiulį poveikį veikimui per faktinį apdorojimą.

Didesnis diskų srautų naudojimas apdorojant „didelius duomenis“ ir atsitiktinę prieigą parodo, kaip struktūrizuojant jūsų programą galima žymiai pagerinti našumą platesniu mastu.

Jei yra būdas pasiekti masyvą nuosekliai, tai yra pats efektyviausias būdas. Tokio tikslo projektavimas turėtų būti bent jau apsvarstytas, jei jis yra svarbus.

0
07 июня '18 в 7:46 2018-06-07 07:46 atsakymą pateikė vartotojo3150186 birželio 07 '18, 07:46 2018-06-07 07:46

1) Kaip paaiškinta pirmiau, įterpimo ir ištrynimo operacijos suteikia gerą našumą (O (1)) „LinkedList“, palyginti su „ArrayList“ (O (n)). Todėl, jei paraiška yra reikalinga dažnai papildyti ir ištrinti, tada „LinkedList“ yra geriausias pasirinkimas.

2) „Arraylist“ (O (1)), bet ne „LinkedList“ (O (n)), paieškos operacijos (gauti metodą) atliekamos greitai, todėl, jei yra mažiau pridėti ir ištrinti operacijas ir daugiau paieškos užklausų, „ArrayList“ bus geriausias pasirinkimas. .

0
05 сент. atsakymą pateikė Avanish Kumar 05 sep . 2015-09-05 15:01 '15 15:01 2015-09-05 15:01

Aš atlikdavau lyginamąją analizę ir nustatiau, kad sąrašo klasė iš tikrųjų yra greitesnė nei „LinkedList“ atsitiktiniam įterpimui:

Naudokite susietą sąrašą „Radix Sort“ pagal masyvus ir polinomines operacijas.

0
24 янв. atsakymą pateikė gizgok Jan 24 2013-01-24 18:30 '13, 6:30 val. 2013-01-24 18:30

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