Urejanje množic

Vse o programiranju na in za PC

Moderatorji: Kroko, tilz0R

Urejanje množic

OdgovorNapisal/-a Kroko » 16 Nov 2020, 12:56

Imam seznam množic. Nekatere od teh množic vsebujejo podmnožice (ki so tudi na na tem seznamu).
Imam funkcijo, ki preveri, če je množica podmnožica (Contains).
Rad bi množicam nastavil njihovega direktnega starša (Parent).

Se pravi, če je situacija taka:
A
|--B
|----C
|--D
|----E

bi rad dobil rezultat:
A.Parent = null
B.Parent = A
C.Parent = B
D.Parent = A
E.Parent = D

funkcija "Contains" dela takole:
A.Contains(B) = true
A.Contains(C) = true
B.Contains(A) = false
...
se pravi vrne "true" tudi za podmnožice, ki niso direktno njene ampak je še ena vmes.

Potrebujem čimhitrejši algoritem in prosim za pomoč.
http://www.planet-cnc.com poskakuješ na eni nogi in žvižgaš alpske podoknice Kroko was here!
Uporabniški avatar
Kroko
 
Prispevkov: 5022
Pridružen: 14 Jan 2015, 11:12
Kraj: Ljubljana
Zahvalil se je: 703 krat
Prejel zahvalo: 1760 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255

Re: Urejanje množic

OdgovorNapisal/-a GJ » 16 Nov 2020, 13:15

Ne vem kakšne variable so A,B... ampak recimo da so to kazalci (lahko je tudi index, ampak je počasnejši) na tvoj node oziroma množico.

Vsak node mora vsebovati kazalec na starša (parent).
Potem le v zanki gledaš parente in sub-parente od nekega node-a do null in jih vmes primerjaš z iskanim parentom, če sta enaka vrneš true.
Najhitreje je, če gedaš nazaj od sub-node-a in ne od glavnega node-a naprej!
Če si jezen, si žrtev!
GJ
 
Prispevkov: 341
Pridružen: 18 Jan 2015, 22:26
Kraj: Ljubljana
Zahvalil se je: 174 krat
Prejel zahvalo: 99 krat
Uporabnika povabil: VolkD
Število neizkoriščenih povabil: 21

Re: Urejanje množic

OdgovorNapisal/-a mucek » 16 Nov 2020, 13:24

Ne vem odgovora, ampak pred parlamentom so nazadnje za urejanje množic uporabili vodni top ... ;) ;) ;) ;) ;) ;)
... lahko pa se tudi motim ...
Uporabniški avatar
mucek
 
Prispevkov: 1754
Pridružen: 18 Jan 2015, 20:20
Kraj: Ljubljana
Zahvalil se je: 64 krat
Prejel zahvalo: 541 krat
Uporabnika povabil: s54mtb
Število neizkoriščenih povabil: 102

Re: Urejanje množic

OdgovorNapisal/-a blasny » 16 Nov 2020, 13:45

Najhitrejsi algoritem je odvisen od tega kako in kje so shranjeni podatki. V kaksni podatkovni strukturi.
Tudi nisi nic napisal, kako je implementirana funkcija Contains, ali pa vsaj kaksna je njena zahtevnost O(n).
blasny
 
Prispevkov: 582
Pridružen: 18 Jan 2015, 15:48
Kraj: Tepanjce
Zahvalil se je: 362 krat
Prejel zahvalo: 182 krat
Uporabnika povabil: VolkD
Število neizkoriščenih povabil: 21

Re: Urejanje množic

OdgovorNapisal/-a Kroko » 16 Nov 2020, 13:53

Imam std::vector v katerem so objekti.
Se pravi, da je lahko gremo čez cel vektor in vsak objekt primerjamo z vsemi (se pravi spet gremo čez cel cel vektor).
Potem moramo samo še poštudirati, kako nastavljati parenta, da se bo nastavil samo direkten starš, ne pa tudi dedi in pradedi.
http://www.planet-cnc.com poskakuješ na eni nogi in žvižgaš alpske podoknice Kroko was here!
Uporabniški avatar
Kroko
 
Prispevkov: 5022
Pridružen: 14 Jan 2015, 11:12
Kraj: Ljubljana
Zahvalil se je: 703 krat
Prejel zahvalo: 1760 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255

Re: Urejanje množic

OdgovorNapisal/-a blasny » 16 Nov 2020, 14:34

Torej imas vector mnozic? Kako je implementiran Contains?

Ce je operacija iskanja parentov tako pomembna, bi lahko imel mnozice ze shranjene v tree-ju, namesto v vectorju?
blasny
 
Prispevkov: 582
Pridružen: 18 Jan 2015, 15:48
Kraj: Tepanjce
Zahvalil se je: 362 krat
Prejel zahvalo: 182 krat
Uporabnika povabil: VolkD
Število neizkoriščenih povabil: 21

Re: Urejanje množic

OdgovorNapisal/-a Kroko » 16 Nov 2020, 15:57

bool Contains(const Obj& set, const Obj& subset);

Takole lahko začnem ampak to ni to:
Koda: Izberi vse
std::vector<Obj> list = GetList();

for (size_t i = 0; i< list.size(); i++)
{
  const Obj& test = list[i];
 
  for (size_t j = 0; j< list.size(); j++)
  {
    if (j == i) continue;
   
   if (Contains(test, list[j]))
     list[j].Parent = i;
  }
}


Nimam tree-ja, dobim list. Če bi imel tree bi bilo trivialno. Lahko bi tree zgradil vendar ga ne potrebujem.
Dejansko niti Parentov ne potrebujem - potrebujem samo globino. Na primer:
A = 0
B = 1
C = 2
D = 1
E = 2
http://www.planet-cnc.com poskakuješ na eni nogi in žvižgaš alpske podoknice Kroko was here!
Uporabniški avatar
Kroko
 
Prispevkov: 5022
Pridružen: 14 Jan 2015, 11:12
Kraj: Ljubljana
Zahvalil se je: 703 krat
Prejel zahvalo: 1760 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255

Re: Urejanje množic

OdgovorNapisal/-a blasny » 16 Nov 2020, 16:45

Jao, jao, kaksna struktura. Ampak zanimiva naloga.
Tako kot imas zdaj, ti ne bo delalo. Ne smes kar povozit parent, ker ti Contains ne pove ali je to stars, pra-stars ali pra-pra-stars. You get the point.

Dvojnemu loop-u se tudi ne mores izognit, ker ti struktura nic ne pove o starsih in otrocih. In moras to sele zvedeti, tako da klices Contains.
Vsaj kolikor razumem, je to edina operacija, ki jo imas na voljo.

Ce parenta ne potrebujes, potem ga ne rabis shranjevat. Raje povecuj stevilo parentov == kolikokrat ti Contains(text, X) vrne true.

To je kar globina drevesa. Seveda pri predpostavki, da nimas ciklov. In pri predpostavki, da ima vsak objekt samo enega parenta.
blasny
 
Prispevkov: 582
Pridružen: 18 Jan 2015, 15:48
Kraj: Tepanjce
Zahvalil se je: 362 krat
Prejel zahvalo: 182 krat
Uporabnika povabil: VolkD
Število neizkoriščenih povabil: 21

Re: Urejanje množic

OdgovorNapisal/-a blasny » 16 Nov 2020, 16:48

Ce ves, da so objekti v listi urejeni lahko optimiziras drugo zanko.
Pod urejeni pomeni: da je parent objekta vedno za objektom, ali pa vedno pred objektom.
Ce niso urejeni, potem moras imeti obe zanki taki kot ju imas zdaj.
blasny
 
Prispevkov: 582
Pridružen: 18 Jan 2015, 15:48
Kraj: Tepanjce
Zahvalil se je: 362 krat
Prejel zahvalo: 182 krat
Uporabnika povabil: VolkD
Število neizkoriščenih povabil: 21

Re: Urejanje množic

OdgovorNapisal/-a Kroko » 16 Nov 2020, 18:18

blasny je napisal/-a:... Raje povecuj stevilo parentov ...

Saj sem vedel, da je preprosta rešitev.

Sedaj so "luknje" pravilno najdene.
Clipboard01.png
http://www.planet-cnc.com poskakuješ na eni nogi in žvižgaš alpske podoknice Kroko was here!
Uporabniški avatar
Kroko
 
Prispevkov: 5022
Pridružen: 14 Jan 2015, 11:12
Kraj: Ljubljana
Zahvalil se je: 703 krat
Prejel zahvalo: 1760 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255


Vrni se na Programski jeziki

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 1 gost