Forum » Programiranje » C++ izbira podatkovne strukture
C++ izbira podatkovne strukture
i33a ::
Pozdravljeni,
v programskem jeziku C++ razvijam algoritem, ki mora biti časovno in prostorsko kar se da učinkovit.
Moj trenutni problem je, da si želim imeti podatkovno strukturo, kamor bom vstavljal številke (uint64_t).
Vedno bi rad ven dobil in po tem tudi izbrisal tisto z najnižjo vrednostjo (to mogoče std::priority_queue). Poleg tega pa bi rad, da številke niso podvojene (ne vstavi številke v podatkovno strukturo, če je ta številka že notri).
Vem, da bi lahko vzporedno delal še nek std::set in ga imel le za preverjanje, če je element že v priority_queue, vendar me zanima če obstaja še kaj prostorsko bolj učinkovitega?
Lep dan še naprej
v programskem jeziku C++ razvijam algoritem, ki mora biti časovno in prostorsko kar se da učinkovit.
Moj trenutni problem je, da si želim imeti podatkovno strukturo, kamor bom vstavljal številke (uint64_t).
Vedno bi rad ven dobil in po tem tudi izbrisal tisto z najnižjo vrednostjo (to mogoče std::priority_queue). Poleg tega pa bi rad, da številke niso podvojene (ne vstavi številke v podatkovno strukturo, če je ta številka že notri).
Vem, da bi lahko vzporedno delal še nek std::set in ga imel le za preverjanje, če je element že v priority_queue, vendar me zanima če obstaja še kaj prostorsko bolj učinkovitega?
Lep dan še naprej
A110 ::
Ali potrebuješ dinamično ali statično? Če statiično bi že navaden quee ki ga 1x uredis (O(nlogn)) bil dovolj. Amortizirano imas potem O(1) odstranjevanje. Če mora biti dinamična bi verjetno kaka kopica (heap) ali skiplist bila najboljsa. Pomoje je skiplist najboljsa izbira. O(n) prostora in O(logn) za izbris, dodajanje, vstavljanje. Verjetno odstranjevanje še veliko manj če vedno odstrnjujes najmanjsi element.
edit: sem prebral, da mora biti dinamicna tako, da skiplist ali binary heap sta priblizno enako dobre izbire. Odvisno ali imas tudi dosti poizvedb ali ne ima prednost en ali drug. Če imaš dosti podvajanj (torej posledicno poizvedb) se ti bolj splaca skiplist ki isce v O(log(n)) ce pa malo pa Binary heap ki sicer isce v O(n) ampak ima dodajanje in iskanje minimuma v konstantnem času
edit: sem prebral, da mora biti dinamicna tako, da skiplist ali binary heap sta priblizno enako dobre izbire. Odvisno ali imas tudi dosti poizvedb ali ne ima prednost en ali drug. Če imaš dosti podvajanj (torej posledicno poizvedb) se ti bolj splaca skiplist ki isce v O(log(n)) ce pa malo pa Binary heap ki sicer isce v O(n) ampak ima dodajanje in iskanje minimuma v konstantnem času
Zgodovina sprememb…
- spremenilo: A110 ()
Blazzz ::
std::set je ze urejen, tako da ne potrebujes dodatne strukture. Ce je stevilo pricakovanih elementov nizko (< 128) bo boost::flat_set verjetno hitrejsi.
i33a ::
@A110: Pa skiplist obstaja že v STL ali kaki drugi knjižnici al je boljše, da ga kar sam spišem?
@Blazzz: Aha, zanimivo. Nisem vedel, da je std::set vedno urejen :) Ker bo število elementov lahko tudi kar veliko bom uporabil std::set.
Za pridobivanje prvega elementa uporabim iterator mySet.begin(), za izbris pa: mySet.erase(0)?
@Blazzz: Aha, zanimivo. Nisem vedel, da je std::set vedno urejen :) Ker bo število elementov lahko tudi kar veliko bom uporabil std::set.
Za pridobivanje prvega elementa uporabim iterator mySet.begin(), za izbris pa: mySet.erase(0)?
A110 ::
@A110: Pa skiplist obstaja že v STL ali kaki drugi knjižnici al je boljše, da ga kar sam spišem?
@Blazzz: Aha, zanimivo. Nisem vedel, da je std::set vedno urejen :) Ker bo število elementov lahko tudi kar veliko bom uporabil std::set.
Za pridobivanje prvega elementa uporabim iterator mySet.begin(), za izbris pa: mySet.erase(0)?
Sicer v C++ nisem nikoli pisal ampak Java in Python vem, da ga nimata in sem ga, ko sem ga potreboval napisal sam. Je pa zelo enostavna strutkura, tako da bi jo mogel dokaj hitro napisati. V bistvu je skiplist ena izmed najbolj splošno uporabnih struktur (nek jack of all trades, praktično brez slabosti) in je zelo žalostno, da ga ti glavni jeziki nimajo že implementiranega. Še bolj žalostno pa je, da na tehnološkem forumu, kjer je kar nekaj ljudi ki se izdajajo za "programerske guruje" pride tako malo predlogov o razmeroma osnovni stvari kot je izbira pdoatkovne strukture, ki bi morala biti prvi korak vsakega začetka pisanja.
Blazzz ::
Jaz bi dodal se en nivo abstrakcije, tako da lahko zamenjas strukturo v prihodnosti, ce bo potrebno. Mogoce kaj takega
class MyQueue {
public:
bool push(int64 value) {
data_.insert(value).second;
}
bool empty() const {
return data_.empty();
}
std::optional<int64> pop() {
if (data_.empty()) {
return std::nullopt;
}
auto value = *data_.begin();
data.erase(data_.begin());
return value;
}
std::optional<int64> top() const {
if (data_.empty()) {
return std::nullopt;
}
return *data_.begin();
}
private:
std::set<int64> data_;
};
MrStein ::
Še bolj žalostno pa je, da na tehnološkem forumu, kjer je kar nekaj ljudi ki se izdajajo za "programerske guruje" pride tako malo predlogov o razmeroma osnovni stvari kot je izbira pdoatkovne strukture, ki bi morala biti prvi korak vsakega začetka pisanja.
Podforum "Programiranje" je res "zanemarjen", pa še od tega kar je je skoraj polovica "domače naloge za osnovno šolo". So pač "rumene" teme bolj popularne.
Motiti se je človeško.
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!
Spura ::
kjer je kar nekaj ljudi ki se izdajajo za "programerske guruje" pride tako malo predlogov o razmeroma osnovni stvari kot je izbira pdoatkovne strukture, ki bi morala biti prvi korak vsakega začetka pisanja.
Ker je vprasanje specificno kaj je na voljo v C++ stdlibu kar lahko tip na hitro ponuca, in tega pac jst ne vem. Verjetno noce sam pisat podatkovnih struktur, drugace bi se dal debatirat. Pac implementiraj heap v arrayu Heap (data structure) @ Wikipedia, ampak to je stara stvar, ki so jo vcasih na faksih ucil, pa ne sledim vsem novim data-structurjem ker je vsega prevec.
DamijanD ::
Meni je zanimivo, da skiplist obstaja od 1990, pa ga na faksu okrog 2000 nismo niti omenili 
mn ::
Jaz bi vseeno uporabil std::vector, ki ga držiš sortiranega.
Predvidevam, da začneš z nekim začetnim setom podatkov.
Dodaš jih v vector in jih sortiraš.
Potem ko dodajaš nove, najdeš pravilno pozicijo za nove v sortiranem seznamu z std::equal_range. Če že obstaja, pair ni enak ne narediš nič. Če je pair (first in second), ki ti ga vrne equal_range enak, potem imaš točno pozicijo kjer je treba novega vnesti. std::equal_range je bisekcija in je iskanje posledično izredno hitro.
Vzameš prvi element iz seznama, in narediš memcpy vseh vrednosti od drugega do tega iteratorja za eno int_64 ne levo. To lahko delaš ker je std::vecztor.data() neprekinjem del pomnilnika, in ker ne spreminjaš size-a.
Si pa malo premalo napisal koliko od teh predpostavk zgoraj drži, ker kar sem opisal je best case za std::vector.
Za resno analizo, boš pa moral stvar implementirati in pognati performančne teste.
Predvidevam, da začneš z nekim začetnim setom podatkov.
Dodaš jih v vector in jih sortiraš.
Potem ko dodajaš nove, najdeš pravilno pozicijo za nove v sortiranem seznamu z std::equal_range. Če že obstaja, pair ni enak ne narediš nič. Če je pair (first in second), ki ti ga vrne equal_range enak, potem imaš točno pozicijo kjer je treba novega vnesti. std::equal_range je bisekcija in je iskanje posledično izredno hitro.
Vzameš prvi element iz seznama, in narediš memcpy vseh vrednosti od drugega do tega iteratorja za eno int_64 ne levo. To lahko delaš ker je std::vecztor.data() neprekinjem del pomnilnika, in ker ne spreminjaš size-a.
Si pa malo premalo napisal koliko od teh predpostavk zgoraj drži, ker kar sem opisal je best case za std::vector.
Za resno analizo, boš pa moral stvar implementirati in pognati performančne teste.
MrStein ::
Pa upoštevati, da se lahko na drugem hardveru drugače obnaša (koda, ki je na enem počasnejši, je lahko na drugem hitrejši).
Motiti se je človeško.
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Analiza kode: goto rabimo po pametiOddelek: Novice / Znanost in tehnologija | 13801 (10361) | one too many |
| » | [C++] Naloga seznamOddelek: Programiranje | 3287 (2562) | Matic1911 |
| » | [C++] velikost matrikeOddelek: Programiranje | 1699 (1511) | Jean-Paul |
| » | std containers vs. own custom containersOddelek: Programiranje | 3770 (3591) | Mmm'Aah |
| » | c++ programOddelek: Programiranje | 1132 (987) | Gundolf |