Forum » Programiranje » Podatkovna struktura poteka
Podatkovna struktura poteka
čuhalev ::
Na vhodu dobivam elemente in čas poteka. Ob vsakem trenutku bi rad izvedel čas prvega poteka katerega koli elementa. Takrat moram vse pretečene odstraniti. Če se na vhodu pojavi isti element z novim časom poteka, se mora prepisati (osvežiti).
Kaj uporabiti? Verjeno nekaj drevesnega.
Kaj uporabiti? Verjeno nekaj drevesnega.
smacker ::
Hash map za iskanje (element je key, čas poteka pa value), pa dodatno še en seznam, kjer so po vrstnem redu vpisani časi poteka. V ta seznam sproti dodajaš vpisane z "insertion sort" - vedno skrbiš da vstaviš na pravo mesto v seznamu, da ostaja seznam urejen. Na prvem mestu tega seznama maš torej čas poteka naslednjega elementa. Lahko maš seznam custom objektov, da si poleg časa not shraniš še sam element ;)
PS: vedno ko posodobiš vrednost poteka za že obstoječ element v hash mapu, moraš tisto vrednost tudi odstranit iz seznama časov poteka - poiščeš ga lahko z binary searchom ker je seznam urejen. To je edina operacija, ki se ne izvede v zahtevnosti O(1), ampak O(log2n).
PS: vedno ko posodobiš vrednost poteka za že obstoječ element v hash mapu, moraš tisto vrednost tudi odstranit iz seznama časov poteka - poiščeš ga lahko z binary searchom ker je seznam urejen. To je edina operacija, ki se ne izvede v zahtevnosti O(1), ampak O(log2n).
nightrage ::
public class TimeArrayList extends ArrayList {
}
Zgodovina sprememb…
- spremenil: nightrage ()
čuhalev ::
Zaenkrat bi bila še najboljša možnost vrsta s prednostjo v implementaciji v seznamu. S tem, da bi si dovolil ven vzeti poljubno vozlišče in ga zapolnil z zadnjim elementom, ki bi splaval navzdol (za omenjen prepis istega elementa). Informacijo o preteku prvega elementa imam tako v konstantnem času. Za iskanje elementa pa bi imel dodatno iskalno drevo in bijektivno korespondenco z omenjeno vrsto.
Si ne predstavljam, kako bi vi to naredili z hash tabelo. Bi bila uporabna za iskanje točno določenega trenutka, ne pa tistih, ki se zgodijo prej kot določen.
Si ne predstavljam, kako bi vi to naredili z hash tabelo. Bi bila uporabna za iskanje točno določenega trenutka, ne pa tistih, ki se zgodijo prej kot določen.
smacker ::
Sej sem ti napisal, da rabiš 2 strukturi. Še enkrat, bolj podrobno:
Rabiš hash tabelo, ki skrbi za preverjanje, če element že obstaja - torej da veš če samo vstaviš nov čas ali moraš prepisat obstoječega.
Za pridobitev časa pa rabiš še en preprost povezan seznam (linked list), ki mora biti ves čas urejen po času izvajanja. Za to lahko skrbiš sproti, ko bereš vhod in shranjuješ čase.
Ko bereš vhod:
a) Če še nimaš časa za element v hash-mapu:
1. vstaviš v hash map
2. vstaviš na ustrezno mesto v seznamu (če maš seznam s časi 1,3,5 in na vhodu čas 4, ga vrineš med 3 in 5). Poleg časa si hrani še ID elementa, torej maš seznam custom classov).
b) Če že maš čas za element:
1. v seznamu poiščeš in odstraniš stari čas
2. popraviš čas v hash mapu
3. vstaviš novi čas na ustrezno mesto v seznamu
Med izvajanjem programa pa preverjaš:
Če je trenutni čas manjši od prvega časa v seznamu:
1. pogledaš ID elementa, ki je prvi v seznamu in odstraniš ta element iz hash mape
2. odstraniš prvi čas iz seznama
To preverjanje ponavljaš v zanki čez cel čas izvajanja programa.
Rabiš hash tabelo, ki skrbi za preverjanje, če element že obstaja - torej da veš če samo vstaviš nov čas ali moraš prepisat obstoječega.
Za pridobitev časa pa rabiš še en preprost povezan seznam (linked list), ki mora biti ves čas urejen po času izvajanja. Za to lahko skrbiš sproti, ko bereš vhod in shranjuješ čase.
Ko bereš vhod:
a) Če še nimaš časa za element v hash-mapu:
1. vstaviš v hash map
2. vstaviš na ustrezno mesto v seznamu (če maš seznam s časi 1,3,5 in na vhodu čas 4, ga vrineš med 3 in 5). Poleg časa si hrani še ID elementa, torej maš seznam custom classov).
b) Če že maš čas za element:
1. v seznamu poiščeš in odstraniš stari čas
2. popraviš čas v hash mapu
3. vstaviš novi čas na ustrezno mesto v seznamu
Med izvajanjem programa pa preverjaš:
Če je trenutni čas manjši od prvega časa v seznamu:
1. pogledaš ID elementa, ki je prvi v seznamu in odstraniš ta element iz hash mape
2. odstraniš prvi čas iz seznama
To preverjanje ponavljaš v zanki čez cel čas izvajanja programa.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | [C#] Razširitev Linked List-aOddelek: Programiranje | 1117 (783) | Ciklamen |
| » | Naloga iz Putka - UPMOddelek: Programiranje | 2223 (1559) | NejcSSD |
| » | [Java] Multi Client chat serverOddelek: Programiranje | 2536 (1807) | javaMaster |
| » | C# HashSet<T>, HashTable kako deluje iskanje v ozadju? a lahko faila?Oddelek: Programiranje | 1552 (1333) | detroit |
| » | [java] funkcija ekvivalentna print_r v PHPOddelek: Programiranje | 1683 (1446) | sverde21 |