Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Objedninjenje nizova i listi

[es] :: Art of Programming :: Objedninjenje nizova i listi

[ Pregleda: 3762 | Odgovora: 16 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Objedninjenje nizova i listi30.10.2006. u 12:48 - pre 211 meseci
Da li neko zna algoritam preko koga se može ostvariti tip koji objedinjuje svojstva listi i nizova u smislu da se može elementima pristzpati preko indeksa (ali u logaritamskom vremenu, ne u konstantnom kao kod nizova) a da se umetanje sadržaja u sredinu (kao i vađenje sadržaja iz stringa) vrše takođe u logaritamskom vremenu?

Primer:

Razmotrimo nizove znakova (stringove).

U stringu "kojim" se slovo "m" nalazi na petom mestu. Kada se ivadi podstring "oj" dobija se string "kim" kod koga je slovo "m" na trećem mestu.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 12:56 - pre 211 meseci
Binarno stablo bi moglo da radi ono shto ti zelish ...
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

1jedini
Dejan Milosavljevic
BG

Član broj: 102721
Poruke: 74
80.227.58.*



Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 16:28 - pre 211 meseci



Ako hoces i nesto gotovo da probas u c++-u onda je std::map (skoro) jedino resenje.


AKA DDMM
 
Odgovor na temu

Milan Aksic

Član broj: 412
Poruke: 1053
*.medianis.net.



Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 17:00 - pre 211 meseci
Vec ti je odgovoreno, resenje koje bi ti verovatno odgovaralo je binarano stablo gde je vreme ubacivanja i pristupa podatku "uglavnom" log(n).
Ali, kako u obicnom binarnom stablu, najgori slucaj moze da bude vreme n za ubacivanja i pristup podataka (u najcescim implementacijama to bi se dogodilo kada bi se ubacivao, po odgovarajucem kriterijumu za te podatke, sortirani niz, iako opet u tom slucaju mozes da primenis binarno pretrazivanje trebao bi da znas kada je niz koji se ubacuje sortiran a kada nije), mozda bi umesto njega hteo da razmotris upotrebu balansiranih binarnih stabala.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 20:08 - pre 211 meseci
Rekao bih da niste u pravu. Stablo ima osobine listi, ali ne i nizova. Neka imam stablo sa 107 članova. Kako da nađem u njemu milioniti član "sleva udesno" u stablu u logaritamskom vremenu?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 20:27 - pre 211 meseci
Pamtish dodatnu informaciju za svaki cvor koja ce ti reci koliko ima cvorova u njegovom podstablu.

recimo da trazish N-ti chlan niza.

Code:

trazi(cvor c, int N){
  if (c.levo.brojSinova < N){
    if (c.levo.brojSinova==N-1) trazeni_cvor=c;
    else trazi(c.desno,N-1-c.levo.brojSinova);
  }
  else trazi(c.levo,N);
}



mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

Milan Aksic

Član broj: 412
Poruke: 1053
*.medianis.net.



Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 22:10 - pre 211 meseci
Nedeljko, ili ti nisi razumeo moj odgovor ili ja nisam razumeo tvoje pitanje :)
Bolje da prikazem graficki:
Code:

       5                Balansirano binarno stablo ili nebalansirano
     /   \\              binarno stablo u najboljem slucaju.
    3     8             Da bi se pronasao broj 7 vrse se 3 poredjenja.
   / \\   / \\            Vreme pristupa je log2(n).
  2   4 7   9
 /           \\
1             10

1                       Nebalansirano binarno stablo u najgorem
 \\                      slucaju, npr. kada se u odredjenoj implementaciji
  2                     ubacuje redom sortirani niz od najmanjeg ka vecem
   \\                    gde se prvo proverava da li je podatak koji se
    3                   ubacuje veci od trenutnog a tek onda ako nije da li
     \\                  je manji ili jednak.
      4                 Da bi se pronasao broj 7 vrse se 7 poredjenja.
       \\                Vreme pristupa je n.
        5
         \\
          6
           \\
            7
             \\
              8
               \\
                9
                 \\
                  10

|1|2|3|4|5|6|7|8|9|10|  Obican niz ili lista.
                        Da bi se pronasao broj 7 vrse se 7 poredjenja.
                        Vreme pristupa je n.

Citat:
Neka imam stablo sa 107 članova. Kako da nađem u njemu milioniti član "sleva udesno" u stablu u logaritamskom vremenu?
Ako bas hoces da koristis niz i da clanovima niza pristupas u logaritamskom vremenu, onda niz mora da bude sortiran i da se koristi binarno pretrazivanje (npr. ako je niz sortiran od manjeg ka vecem, podelis niz na pola, ako je podatak koji se trazi jednak trenutnom pretrazivanje se prekida jer je odgovarajuci clan pronadjen, ako je podatak veci od trenutnog clana trazi se u desnoj polovini niza u suprotnom trazi se u levoj polovini nizi, ovo se ponavlja dok se ne pronadje clan koji je jednak podatku koji se trazi ili dok ne preostane samo jedan neodgovarajuci clan koji naravno ne moze dalje da se deli).

Ako ti je ovo isuvise strano, predlazem ti da prvo procitas neku knjigu o algoritmima i strukturama podataka.

[Ovu poruku je menjao Milan Aksic dana 30.10.2006. u 23:48 GMT+1]
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 22:47 - pre 211 meseci
Milane, nisi ga razumeo shta hoce.

Dakle, ono shto on zeli je sledece :
kada se to stablo rastavi (i dobije se nekakav niz), zeli da zna koji elemenat je na N-tom mestu. Pazi, niz koji dobijesh ne mora da bude sortiran po vrednosti!!!

U stvari, ono po chemu se ova nasha struktura razlikuje od klasichnog binarnog stabla pretrazivanja je to shto ne postoji kljuch po kom poredimo vrednosti!

Ako nekom nije jasno shta sam hteo da kazem, potrudicu se da malo pojasnim (da ne kucam inache u prazno ako je svima jasno shta je pisac hteo da kaze) :)
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

Milan Aksic

Član broj: 412
Poruke: 1053
*.medianis.net.



Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 23:00 - pre 211 meseci
E sada mi jasno sta je hteo, ali ne iz tvoje poslednje poruke :) nego iz primera u tvojoj predposlednjoj poruci, koji sam ovoga puta malo bolje pogledao :)
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Objedninjenje nizova i listi30.10.2006. u 23:16 - pre 211 meseci
Da, moj poslednji post je katastrofalno nejasno napisan :)
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Objedninjenje nizova i listi31.10.2006. u 13:55 - pre 211 meseci
Citat:
RooTeR: Pamtish dodatnu informaciju za svaki cvor koja ce ti reci koliko ima cvorova u njegovom podstablu.[/code]

Znam da je dovoljno pamtiti broj čvorova u levom podstablu. Međutim, tu nastaje problem prilikom umetanja i brisanja. Naime, te informacije u čvorovima treba ažurirati prilikom umetanja i brisanja, a broj čvorova kod kojih bi ažuriranje bilo potrebno zavisi linearno od ukupnog broja čvorova. Zbog ažuriranja tih dodatnih informacija vreme umetanja i brisanja ne bi više bilo logaritamsko, već linearno.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Objedninjenje nizova i listi31.10.2006. u 17:08 - pre 211 meseci
Citat:
Nedeljko: Znam da je dovoljno pamtiti broj čvorova u levom podstablu. Međutim, tu nastaje problem prilikom umetanja i brisanja. Naime, te informacije u čvorovima treba ažurirati prilikom umetanja i brisanja, a broj čvorova kod kojih bi ažuriranje bilo potrebno zavisi linearno od ukupnog broja čvorova. Zbog ažuriranja tih dodatnih informacija vreme umetanja i brisanja ne bi više bilo logaritamsko, već linearno.


Ne, broj cvorova koje treba azurirati je log N!
jer kad ubacish neki novi cvor, menjacesh informaciju samo njegovim prethodnicima, a njih ima log N ...
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Objedninjenje nizova i listi31.10.2006. u 20:22 - pre 211 meseci
To bi bilo tako kada ne bi trebalo ažurirati informaciju o broju čvorova levo od datog čvora. Znam ja za razne vrste balansiranih stabala, kao i da ona imaju logaritamske karakteristike nalaženja, umetanja i brisanja, ali ovde čvor nosi još jednu informaciju koju treba ažurirati.

Pretpostavimo da kada u drvo d dodajemo na m-to mesto (sleva udesno) element x dobijamo drvo d'. Sa c1,...,cn označimo niz koji se dobija od drveta d (komp ga naravno neće generisati, ovo je samo oznaka). Tada drvetu d' odgovara niz c1,...,cm-1,x,cm,...cn. Za k>=m je u prvom nizu ck imao k-1 prethodnika, a u novom k. To znači da se za k>=m informacija o broju čvorova levo od čvora koji odgovara elementu ck povećala za jedan, to jest da tu informaciju treba ažurirati u svim čvorovima cm,...,cn, a njih ima n-m+1.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Objedninjenje nizova i listi31.10.2006. u 21:05 - pre 211 meseci
Nisi u pravu!

Recimo da imash ovakvo stablo :

Code:

         x3
        /  \
      x2   x5
     /    /  \
   x1    x4  x6


i ona predstavlja niz : x1, x2, x3, x4, x5, x6

E sad, ti zelish da na trece mesto ubacish elemenat E.
Dakle, niz ce izgledati ovako : x1, x2, E, x3, x4, x5, x6

a stablo ce izgledati ovako :

Code:

         x3
        /  \
      x2    x5
     /  \  /  \
   x1   E x4  x6


E sad, kad ti to E ubacish na svoje mesto, koje cesh cvorove morati da azurirash?
x2 i x3.
x4, x5 i x6 necesh biti potrebe da se azuriraju, jer E nije njihov potomak, pa samim tim i ne utiche na broj cvorova u njihovom podstablu.
Dakle, potrebno je azurirati samo one cvorove u cijem se podstablu nalazi novoubaceni cvor (a takvih cvorova ima log N)!

Mislim da je jednostavnije da se za svaki cvor pamti kompletna velicina njegovog podstabla, a ne samo velicina njegovog levog podstabla!


mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

qdot
Mladen Srdic
Nova Pazova

Član broj: 51019
Poruke: 25
80.93.240.*



Profil

icon Re: Objedninjenje nizova i listi01.11.2006. u 00:29 - pre 211 meseci
Mislim da vam je potrebno neshto kao kolekcija binomnih stabala...imaju dobru osobinu shto uvek znate koliko elemenata se nalazi u datom binomnom stablu(ako je stablo reda k,onda stablo ima 2k elemenata),a dodavanje se vrshi u O(log n) vremenu gde je n broj chvorova u kolekciji.Ne znam bash sve pojedinosti ali mislim da je ovo ono shto moze da zadovolji vashe potrebe.

Evo i slike kako otprilike izgledaju binomna stabla stepena 0,1,2 i 3...



Mladen.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Objedninjenje nizova i listi01.11.2006. u 07:38 - pre 211 meseci
RooTeR

Sada sam te razumeo. Ja sam mislio da u svakom čvoru pamtim broj svih čvorova levo od njega (nezavisno od toga da li su mu u levom podstablu ili ne). Tako bi u tvom primeru po mojoj definiciji x1 bio levo od x6 i tada bih morao da ažuriram x3-x6 jer bi npr. x6 nakon umetanja bio sedmi po redu, a pre umetanja šesti po redu. Međutim, ako u čvoru pamtiš broj čvorova u njegovim podstablima, onda zaista treba ažurirati samo čvorove na grani umetnutog čvora. Time je problem rešen. Hvala.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Objedninjenje nizova i listi01.11.2006. u 13:33 - pre 211 meseci
@Nedeljko:

Molim i drugi put! :)
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

[es] :: Art of Programming :: Objedninjenje nizova i listi

[ Pregleda: 3762 | Odgovora: 16 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.