Efektyvus susietas sąrašas C + +?

Šiame dokumente teigiama, kad std::list nėra veiksmingas:

std :: list yra labai neefektyvi klasė, kuri retai naudinga. Jis atlieka kiekvieno į jį įterpto elemento krūvos pasiskirstymą, todėl jis turi itin didelį pastovumą, ypač mažų duomenų tipams.

Komentaras: tai nustebino. std::list yra dvigubai susietas sąrašas, todėl, nepaisant jo neveiksmingumo statant elementus, jis palaiko laiko sudėtingumo įterpimą / ištrynimą į O (1), tačiau ši funkcija yra visiškai ignoruojama šioje cituotoje pastraipoje.

Mano klausimas yra toks: Tarkime, kad reikia nuoseklios talpos mažų dydžių homogeniškiems elementams, ir šis konteineris turi palaikyti įterpimo / panaikinimo elementą O (1), o atsitiktinės prieigos nereikia (nors parama atsitiktinei prieigai yra gera, čia nereikia). Man taip pat nereikia aukšto pastovaus veiksnio, kurį įvedė krūvos pasiskirstymas kiekvienam elemento dizainui , bent jau tada, kai elementų skaičius yra mažas. Galiausiai, iteratoriai turėtų būti panaikinti tik tada, kai atitinkamas elementas ištrinamas. Matyt, man reikia pritaikytos konteinerių klasės, kuri gali būti (arba gali būti) dvigubai susieto sąrašo variantas. Kaip turėčiau sukurti šį konteinerį?

Jei minėtos specifikacijos neįmanoma pasiekti, galbūt turėčiau turėti pasirinktinį atminties paskirstiklį, tarkim, bump paskirstytuvą? Žinau, kad std::list skiria paskirstytoją kaip antrojo šablono argumentą.

Redaguoti: aš žinau, kad aš neturėčiau pernelyg daug nerimauti dėl šios problemos - pakankamai greitai. Tai tik hipotetinis klausimas , todėl aš neturiu išsamesnio naudojimo atvejo. Nedvejodami atsipalaiduokite kai kuriais reikalavimais!

Edit2: Suprantu, kad du O (1) sudėtingumo algoritmai gali turėti visiškai skirtingus rezultatus dėl jų pastovių veiksnių skirtumo.

41
16 авг. nustatė user8385554 16 rug . 2017-08-16 18:44 '17, 6:44 pm 2017-08-16 18:44
@ 11 atsakymų

Reikalavimas, kad iteratoriai būtų neteisingi, išskyrus ištrauką iš mazgo, yra draudžiamas kiekviename konteineryje, kuriame nėra atskirų mazgų, ir labai skiriasi nuo, pavyzdžiui, list ar map .
Tačiau pastebėjau, kad beveik visais atvejais, kai maniau, kad tai buvo būtina, paaiškėjau, kad galėčiau padaryti be nedidelės drausmės. Galbūt norėtumėte patikrinti, ar galite tai padaryti, jūs laimėjote.

Nors std::list „teisingas“ dalykas, jei jums reikia kažko panašaus sąrašo (daugiausia CS klasės), teiginys, kad tai beveik visada yra neteisingas pasirinkimas, deja, yra teisus. Nors O (1) reikalavimas yra visiškai teisingas, vis dėlto tai yra baisu, atsižvelgiant į tai, kaip kompiuterinė įranga veikia, o tai suteikia jai didžiulį nuolatinį veiksnį. Atkreipkite dėmesį, kad ne tik savavališkai dedami objektai, bet ir palaikomi mazgai (taip, jūs galite kažkaip susikurti tai su paskirstytojo pagalba, bet taip nėra). Vidutiniškai turite dvi atskiras garantuotas talpyklas už viską, ką darote, plius iki vieno dinaminio paskirstymo mutacijų operacijoms (vienas objektui ir kitas mazgas).

Redagavimas: kaip nurodyta toliau, „@ratchetfreak“, std::list paprastai sutraukia objektą ir mazgo paskirstymą į vieną atminties bloką kaip optimizavimą (panašiai kaip, pvz., make_shared ), todėl vidutinis atvejis yra šiek tiek mažiau katastrofiškas (vienas paskirstymas vienam mutacija ir viena garantuota atminties talpykla vietoj dviejų).
Šiuo atveju gali būti, kad naujas, skirtingas dėmesys gali būti, kad tai gali būti visiškai neveiksminga. Objekto išdėstymas dviem rodikliais reiškia krypties keitimą, o dereferenciją, kuri gali trukdyti automatiniam išankstiniam atsisiuntimui.
Kita vertus, objekto prefiksas su rodikliais reiškia, kad grąžinate objektą atgal, naudodami du rodykles, o tai reiškia iki 16 baitų 64 bitų sistemoje (tai gali lemti vidutinio dydžio objekto atskyrimą palei ribinę talpyklą). Be to, reikėtų std::list kad std::list negali leisti, pavyzdžiui, nutraukti. SSE kodas tik todėl, kad jis prideda paslėptą nuokrypį kaip ypatingą siurprizą (pvz., „Xor-trick“ tikriausiai netaikoma pėdsakui sumažinti su dviem rodikliais). Turėtų būti daug „saugių“ priedų, kad įsitikintumėte, jog į sąrašą įtraukti objektai vis dar veikia taip, kaip reikia.
Negaliu pasakyti, ar tai yra realios veiklos problemos, ar tik mano nepasitikėjimas ir baimė, bet manau, kad yra teisinga pasakyti, kad žolėje gali būti daugiau gyvulių nei galima tikėtis.

Tai yra be priežasties, kad aukštos klasės C + + ekspertai (ypač „Stroustrup“) rekomenduoja naudoti std::vector , nebent turite tikrai gerą priežastį.

Kaip ir daugelis kitų, aš stengiausi būti protingais (ar išradi) kažką geresnio nei std::vector tam tikroje konkrečioje specializuotoje problemoje, kur, atrodo, galite padaryti geriau, bet paaiškėja, kad tiesiog naudojant std::vector vis dar beveik visada yra geriausias arba antras geriausias variantas (jei std::vector nėra geriausias, paprastai std::deque tai, ko jums reikia).
Turite daug mažiau paskyrimų nei bet kokio kito požiūrio, mažiau atminties fragmentacijos, mažiau paspaudimų ir daug daugiau naudingos atminties prieigos modelio. Ir atspėti, ką jis lengvai pasiekia ir veikia.
Tai, kad kartais įterpimas reikalauja, kad visų elementų kopija būtų (dažniausiai) bendra problema. Jūs manote, kad taip, bet ne. Tai vyksta retai, ir tai yra tiesinės atminties bloko kopija, kuri tiksliai atitinka procesorius (skirtingai nei daugelis dvigubų instrukcijų ir atsitiktinių atminties perėjimų).

Jei reikalavimas neatšaukti iteratorių iš tikrųjų yra būtinas, galite, pavyzdžiui, susieti std::vector objektus su dinaminiu bitratu arba, jei trūksta kažko geresnio, std::vector<bool> . Tada naudokite reserve() , kad perskirstymai nebūtų atlikti. Kai ištrinate elementą, neištrinkite, bet pažymėkite jį tik kaip ištrintą rastriniame vaizde (skambinkite destruktoriumi rankiniu būdu). Tinkamu laiku, kai žinote, kad yra normalu panaikinti iteratorius, vadinkite „dulkių siurblio“ funkciją, kuri suspausto tiek bitų vektorių, tiek objekto vektorių. Visi netikėti iteraciniai atšaukimai ten išnyko.

Taip, tai reikalauja, kad būtų pašalintas vienas papildomas bitų elementas, kuris yra erzina. Tačiau std::list turi paremti du rodiklius, be tikrojo objekto, ir turi atlikti paskirstymus. Naudojant vektorių (arba du vektorius), prieiga vis dar yra labai efektyvi, kaip tai vyksta talpykloje. Iteracija, netgi patikrindama nuotolinius mazgus, vis dar reiškia, kad jūs judate tiesiai arba beveik tiesiškai per atmintį.

18
17 авг. atsakymas duotas Damonui 17 d. 2017-08-17 14:23 '17, 14:23 pm 2017-08-17 14:23

Jūsų reikalavimai tiksliai atitinka „ std::list , išskyrus tai, kad jums patinka, kad jums nepatinka mazgo pasiskirstymas.

Protingas požiūris yra pradėti nuo viršaus ir daryti tiek, kiek reikia:

  • Tiesiog naudokite std::list .

    Lyginamoji analizė: ar numatytasis skirstytuvas yra per lėtas jūsų tikslams?

    • Ne: viskas paruošta.

    • Taip: 2

  • Naudokite std::list su esamu priskirtu paskirstikliu, pvz., „Boost pool“ skirstytuvu

    Įvertinkite: paskirstomasis baseinas Per daug sulėtinkite savo tikslus?

    • Ne: viskas paruošta.

    • Taip: 3

  • Naudokite std::list naudodami rankinį pasirinktinį paskirstytuvą, smulkiai suderintą su jūsų unikaliais poreikiais, remiantis visais profiliais, atliktais 1 ir 2 veiksmuose

    Bandymas, kaip ir anksčiau, ir tt ir pan

  • Pagalvokite apie tai, ką darote egzotiškesni.

    Jei pasieksite šį etapą, turėtumėte turėti labai gerai užduotą klausimą „SO“ su ​​daugybe informacijos apie tai, ko jums reikia (pvz., „Man reikia išspausti n mazgus į keliną“, o ne „šį dokumentą“, šis dalykas yra lėtas, ir tai skamba blogai “).

border=0

Ps. Pirmiau pateikiamos dvi prielaidos, tačiau abu reikia dėmesio:

  • kaip nurodo Baum mit Augen, nepakanka atlikti paprastą laiko tarpą, nes jūs turite būti tikri, kur vyksta jūsų laikas. Tai gali būti pats paskirstytojas arba talpyklos praleidimas dėl atminties išdėstymo ar kažko kito. Jei kažkas yra lėta, vis tiek turite būti tikri, kodėl prieš žinodami, ką reikia keisti.
  • jūsų reikalavimai priimami kaip nurodyta, bet ieškant būdų, kaip atsipalaiduoti jūsų reikalavimai, dažnai yra lengviausias būdas ką nors greičiau atlikti.

    • Ar jums tikrai reikia nuolatinio įterpimo ir ištrynimo visur, ar tiesiog priešais ar atgal, arba abu, bet ne viduryje?
    • Ar jums tikrai reikia tokių iteratoriaus atšaukimo apribojimų, ar jie gali būti atsipalaiduoti?
    • Ar yra kokių nors prieigos modelių, kuriuos galite naudoti? Jei dažnai pašalinate elementą iš priekio ir tada jį pakeiskite nauju, ar galite tiesiog ją atnaujinti?
87
16 авг. atsakymas pateikiamas nenaudingas 16 rug. 2017-08-16 19:00 „17, 7 val. 2017-08-16 19:00

Arba galite naudoti augančią masyvą ir aiškiai valdyti nuorodas, kaip indeksus masyve.

Nepanaudoti masyvo elementai įterpiami į susietą sąrašą naudojant vieną iš nuorodų. Kai elementas ištrinamas, jis grįžta į nemokamą sąrašą. Išnaudojus nemokamą sąrašą, padidinkite masyvą ir naudokite šį elementą.

Jei turite naujų nemokamų elementų, turite dvi parinktis:

  • pridėkite juos prie nemokamo sąrašo vienu metu,
  • pridėkite juos pagal užklausą, remiantis laisvo sąrašo elementų skaičiumi ir masyvo dydžiu.
18
16 авг. Yves Daoust atsakymas 16 rug . 2017-08-16 19:23 '17 19:23 pm 2017-08-16 19:23

std::list yra dvigubai susietas sąrašas, todėl, nepaisant jo neveiksmingumo elementų konstravimo, jis palaiko O (1) laiko sudėtingumo įterpimą / ištrynimą , tačiau ši funkcija visiškai ignoruojama šioje cituotoje pastraipoje.

Jis jį ignoravo , nes tai buvo melas .

Algoritminio sudėtingumo problema yra ta, kad ji paprastai vertina vieną dalyką. Pavyzdžiui, kai sakome, kad įterpimas į std::map yra O (log N), tai reiškia, kad jis atlieka O (log N) palyginimus. Iš iteracijos, atminties talpyklos linijų ir kt. Neapskaitoma.

Tai, žinoma, labai supaprastina analizę, tačiau, deja, nebūtinai neabejotinai atspindi įgyvendinimo sudėtingumą realiame pasaulyje. Visų pirma viena ryški prielaida yra ta, kad atminties paskirstymas yra pastovus laikas. Ir tai yra drąsus melas.

Bendrosios paskirties atminties skirstytuvai (malloc ir co) negarantuoja blogiausio atminties paskirstymo sudėtingumo. Blogiausiu atveju, kaip taisyklė, tai priklauso nuo operacinės sistemos, o Linux atveju gali būti ir OOM žudikas (ištrinti dabartinius procesus ir nužudyti, kad būtų atkurta atmintis).

Specialiosios atminties skirstytuvai gali būti pastovūs ... tam tikru paskirstymų skaičiaus intervalu (arba maksimaliu paskirstymo dydžiu). Kadangi pavadinimas „Big-O“ turi ribą begalybėje, jis negali būti vadinamas O (1).

Ir todėl, kai derva atitinka kelius, std::list įgyvendinimas paprastai neapima įterpimo (delete) O (1) funkcijos, nes įgyvendinimas priklauso nuo faktinio atminties paskirstytojo, o ne idealaus.


Tai gana slegia, bet jūs neturite prarasti vilties.

Visų pirma, jei galite nustatyti viršutinę elementų skaičiaus ribą ir galite priskirti tiek daug atminties, galite sukurti atminties skirstytuvą, kuris atmintį paskirstytų pastoviu laiku, suteikiančiu O (1) iliuziją.

16
17 авг. Matthieu M. atsakymas . 2017-08-17 10:50 '17 10:50 2017-08-17 10:50

Naudokite du std::list s: vieną „nemokamą sąrašą“, kuris iš anksto buvo platinamas daugeliu mazgų paleidimo metu, o kitas „aktyvus“ sąrašas, į kurį splice mazgai iš nemokamo sąrašo. Tai yra pastovus laikas ir nereikalauja paskirstymo mazgo.

7
16 авг. Atsakymą pateikė Mark B 16 rug. 2017-08-16 18:53 '17, 18:53 pm 2017-08-16 18:53

Naujoje „ slot_map“ sąlygoje reikalaujama, kad O (1) būtų įterpta ir pašalinta.

Taip pat yra nuoroda į vaizdo įrašą su siūlomu įgyvendinimu ir kai kuriais ankstesniais darbais.

Jei daugiau žinome apie faktinę elementų struktūrą, gali būti ir daug geresnių specializuotų asociacijų konteinerių.

5
17 авг. atsakymas duotas Surt Aug 17 2017-08-17 08:18 '17 at 8:18 2017-08-17 08:18

Aš siūlau daryti tai, ką sako @Yves Daoust, išskyrus susieto sąrašo naudojimą laisvam sąrašui, naudokite vektorių. Spustelėkite ir spustelėkite nemokamus indeksus vektoriaus gale. Jis nusidėvėjo O (1), įterpia, ieško ir ištrina, ir nereiškia jokio žymeklio vykdymo. Ji taip pat nereikalauja jokio erzinančio platintojo verslo.

4
17 авг. Atsakyti Dan 17 rug. 2017-08-17 12:08 '17, 12:08 2017-08-17 12:08

Antras atsakymas @Useless, ypač PS 2 punktas dėl reikalavimų peržiūros. Jei susilpninsite iteratoriaus atšaukimo apribojimą, tuomet naudokite std::vector<> standartinę Stroustrup sąlygą konteineriui su nedideliu elementų skaičiumi (dėl priežasčių, jau minėtų komentaruose). Su SO susiję klausimai .

Nuo C ++ 11 yra ir std::forward_list .

Be to, jei į konteinerį įdėtų daiktų standartinis krūvos pasiskirstymas nėra pakankamai geras, norėčiau pasakyti, kad jums reikia labai atidžiai stebėti tikslius reikalavimus ir juos tikslinti.

2
17 авг. atsakymą pateikė Pablo H 17 rug. 2017-08-17 02:51 '17 at 2:51 am 2017-08-17 02:51

Aš tik norėjau pateikti šiek tiek komentaro apie jūsų pasirinkimą. Aš esu didelis vektoriaus gerbėjas dėl savo skaitymo greičio ir galite tiesiogiai pasiekti bet kurį elementą ir, jei reikia, rūšiuoti. (pvz., klasės / struktūros vektorius).

Bet kokiu atveju, aš išsiblaškęs du puikūs patarimai, kuriuos norėjau atskleisti. Su vektoriaus įdėklais gali būti brangus, todėl tvarkingas triukas, nedėkite, jei galite palikti be to. atlikite įprastą „push_back“ (įdėkite į pabaigą), tada pakeiskite elementą į norimą.

Tas pats su pašalinimu. Jie yra brangūs. Todėl pakeiskite jį paskutiniu elementu, ištrinkite.

2
18 авг. atsakymas pateikiamas ViperG 18 rug . 2017-08-18 20:49 '17, 08:49 PM 2017-08-18 20:49

Ačiū už visus atsakymus. Tai paprastas, bet ne griežtas testas.

 // list.cc #include <list> using namespace std; int main() { for (size_t k = 0; k < 1e5; k++) { list<size_t> ln; for (size_t i = 0; i < 200; i++) { ln.insert(ln.begin(), i); if (i != 0  i % 20 == 0) { ln.erase(++++++++++ln.begin()); } } } } 

ir

 // vector.cc #include <vector> using namespace std; int main() { for (size_t k = 0; k < 1e5; k++) { vector<size_t> vn; for (size_t i = 0; i < 200; i++) { vn.insert(vn.begin(), i); if (i != 0  i % 20 == 0) { vn.erase(++++++++++vn.begin()); } } } } 

Šis bandymas yra skirtas patikrinti, ar std::list teigia, kad jis sėkmingas su - O (1) įterpimu ir ištrinimu. Ir dėl pozicijų, kurias prašau įterpti / ištrinti, ši lenktynė yra stipriai iškreipta prieš std::vector , nes ji turi perkelti visus šiuos elementus (todėl, O (n)), o std::list nereikia daryti.

Dabar juos surenku.

 c> 

Ir patikrinkite laiką. Rezultatas:

  time ./list ./list 4.01s user 0.05s system 91% cpu 4.455 total time ./vector ./vector 1.93s user 0.04s system 78% cpu 2.506 total 

std::vector laimėjo.

Sudarytas su O3 optimizacija, std::vector vis dar laimi.

  time ./list ./list 2.36s user 0.01s system 91% cpu 2.598 total time ./vector ./vector 0.58s user 0.00s system 50% cpu 1.168 total 

std::list turėtų paskatinti kiekvieno elemento krūvos pasiskirstymą, o std::vector gali paskirstyti krūvos atmintį paketiniu režimu (nors tai gali būti priklausoma nuo įgyvendinimo), todėl std::list insert / delete turi didesnį pastovų koeficientą, nors tai yra O (1).

Nenuostabu, kad šis dokumentas sako

std::vector gerai mylimas ir gerbiamas.

EDIT: std::deque kai kuriais atvejais yra dar geriau, bent jau šiai užduočiai .

 // deque.cc #include <deque> using namespace std; int main() { for (size_t k = 0; k < 1e5; k++) { deque<size_t> dn; for (size_t i = 0; i < 200; i++) { dn.insert(dn.begin(), i); if (i != 0  i % 20 == 0) { dn.erase(++++++++++dn.begin()); } } } } 

Nėra optimizavimo:

 ./deque 2.13s user 0.01s system 86% cpu 2.470 total 

Optimizuotas su O3 :

 ./deque 0.27s user 0.00s system 50% cpu 0.551 total 
1
18 авг. atsakymas, kurį pateikė user8385554 18 rug . 2017-08-18 20:06 '17 - 20:06 2017-08-18 20:06

Paprasčiausias būdas pamatyti visus jūsų reikalavimus:

  • Įterpimas / ištrynimas su pastoviu uždelsimu (patikimas nuolat slopinamas laikas, tinkamas įterpimui).
  • Nėra krūvos paskirstymo / išleidimo elemente.
  • Neteisingas iteratorius, kai ištrinamas.

... būtų kažkas panašaus, tiesiog naudojant std::vector :

 template <class T> struct Node { // Stores the memory for an instance of 'T'. // Use placement new to construct the object and // manually invoke its dtor as necessary. typename std::aligned_storage<sizeof(T), alignof(T)>::type element; // Points to the next element or the next free // element if this node has been removed. int next; // Points to the previous element. int prev; }; template <class T> class NodeIterator { public: ... private: std::vector<Node<T>>* nodes; int index; }; template <class T> class Nodes { public: ... private: // Stores all the nodes. std::vector<Node> nodes; // Points to the first free node or -1 if the free list // is empty. Initially this starts out as -1. int free_head; }; 

... ir, tikiuosi, su geresniu pavadinimu nei Nodes (aš truputį girtas ir aš nesu labai gerai šiuo metu pavadinimais). Aš paliksiu jus įgyvendinti, bet tai yra bendra idėja. Kai ištrinate elementą, tiesiog ištrinkite dvigubai susietą sąrašą naudodami indeksus ir spustelėkite tuščią galvą. Iteratorius negalioja, nes jis saugo vektoriaus indeksą. Įdėję patikrinkite, ar galva yra laisva -1. Jei ne, perrašykite mazgas į šią poziciją ir spustelėkite. Priešingu atveju push_back į vektorių.

Iliustracija

Diagrama (mazgai saugomi gretimi std::vector viduje, mes paprasčiausiai naudojame indekso nuorodas, kad praleistume elementus be atšakų, kartu su ištrinamais ir įterptais elementais bet kuriuo metu):

Tarkime, mes norime ištrinti mazgą. Tai yra standartinis dvigubų susietų nuorodų ištrynimas, išskyrus tai, kad vietoj rodyklės mes naudojame indeksus, o taip pat priversti mazgas į nemokamą sąrašą (kuriame yra tik manipuliavimas sveikaisiais skaičiais):

Pašalinkite nuorodų parinktis:

Ištrynus mazgų į sąrašą:

Tarkime, kad įterpėte šį sąrašą. В этом случае вы удаляете свободную головку и перезаписываете node в этой позиции.

После вставки:

Вставка в середину в постоянное время также должна быть легко понята. В основном вы просто вставляете в свободную головку или push_back в вектор, если свободный стек пуст. Затем вы выполняете стандартную двойную привязку списка. Логика для бесплатного списка (хотя я сделал эту диаграмму для кого-то еще, и она включает SLL, но вы должны получить идею):