» »

Učinkovito iskanje intervalov [Psevdokoda]

Učinkovito iskanje intervalov [Psevdokoda]

marjan_h ::

Imam številsko os in na njej točke. Nekatere so bolj skupaj in nekatere narazen. Kako bi učinkovito poiskal intervale množice točk.

Primer:
Iz tega:
__+__+___+____________++____+__+_+____________+_____+


bi rad dobil nekaj takšnega:
__+______+____________+__________+____________+_____+


Torej za interval množice točk najdem prvo točko in drugo zadnjo točko. Tako da dobim par[x,y].

Problem je v tem dolžina intervalov ni točno določena, samo vem da so gruče točk na osi in te so kratki intervali, potem je dolgi interval in spet kratki kjer je gruča.

Hvala za pomoč.

WarpedGone ::

Najprej jasno defniraj kakšne sorte intervalov želiš iskat.
Če nekaj "ne veš", kako ti naj povemo kako se to, kar ne veš, učinkovito najde?
Zbogom in hvala za vse ribe

marjan_h ::

Intervali so; kratek-dolg-kratek-dolg...

Išče se kratke intervale kjer je množica točk, potem sledi dolg interval kjer ni nobene točke. Nato se ponovi. Išče se samo na 1-D številski osi.

Moja nedelujoča rešitev je takšna:


x = 0;
y = 0;

while (i < interval)
   while (j = i + 1 < interval)
      if (interval(j) - interval(i) < konstanta)
             j++;
   x = interval(i);
   y = interval(j);



Tako se najde en interval, [x,y] želel bi imeti množico kratkih intervalov znotraj katerih bi bile točke.

Saj zato me zanima, če ima kdo izkušnje z algoritmi kjer se išče gruče točk, ker intervali niso določeni, nekje je kratek interval dolg 20, nekje 30. Dolgi so pa okoli 400 do 500, vendar ne nujno.

jype ::

Kako so videti tvoji vhodni podatki?

Zgodovina sprememb…

  • spremenilo: jype ()

marjan_h ::

Vhodni podatek, je dejansko vektor, ki vsebuje števila:
Primer:
[23,39,42,300,312,342,500...]

To so točke na 1D x osi. To je vse. Izračunam razdalje med posameznimi števili, vidim da je nekje 20-30 razlike nekje več kot 400. Vendar moramo biti pazljivi saj je nekje točk več na intervalu nekje pa samo 2.

Ni nujno da za vse dobro dela, vendar mora za vsaj večino.

jype ::

Omisli si en parameter, recimo "spread", ki ti pove, po koliko elementov naprej skačeš (in potem z bisekcijo backtrackaš po elementih nazaj, če si že preskočil veliki interval) in malo eksperimentiraj z njim, da ga čimbolj optimalno nastaviš.

marjan_h ::

Metoda bisekcije? Kako si točno mislil? Metoda se uporablja za iskanje elementov v urejeni tabeli.

Sorry ker ne razumem, vendar me že glava boli od programiranja.

Hvala za odgovor.

jype ::

Imaš parametra spread in diff, naprej skačeš vrednost parametra spread polj in gledaš, če je razlika večja od diff. Recimo da je polje [0,5,10,15,500,510,520,1005,1010,1015,...]

Podaš 3 za spread in 100 za diff in začneš s prvim elementom in skočiš naprej za 3 polja, ugotoviš, da je 15 - 0 = 15, kar je manjše od tipičnega velikega intervala, zato skočiš še za tri, dobiš 520 - 15 = 505 kar implicira, da si preskočil veliki interval, zato (v splošnem najučinkoviteje z bisekcijo, lahko pa tudi po vrsti) iščeš element med 3 in 6, kjer je razlika večja od diff.

WarpedGone ::

Če se greš takšno "mehko" metodo, kjer je njen rezultat odvisen od nekih magičnih parametrov, je dobro zraven vedet sploh kakšen namen želiš dosečt.
Se greš kompresijo podatkov? Mora bit lossless? Se greš kej tretjega in si lahko "mal" nenatančen?
Zbogom in hvala za vse ribe

jype ::

Brez magičnih parametrov bo rešitev znatno kompleksnejša in za specifičen primer, ki ga opisuje, praktično vedno manj učinkovita.

Spura ::

Ce dopuscas intervale dolzine 0 (torej iz ene tocke) potem je povsem nemogoce brez nekih dodatnih parametrov, ki jih moras izbrat.
Na splosno moras zahtevat postavljat nek minimum razdalj med tockami al pa recimo stevilo grup, ki jih hoces dosezt. Lahko imas meta hevristiko ko variras stevilo grup in racunas neko metriko, na podlagi katere izberes. Brez tega pa bolj tezko, ker ce zdruzujes une tocke k so blizu in imas poljubno stevilo grup, potem ponavadi algoritem kot najboljso resitev najde kopico grup iz malo tock, ki so si res blizu. Kar je pa ponavadi dalec od tega kar bi clovek izbral.

marjan_h ::

Naloga je točno to kar želim, poiskati množice točk. Nobenega kompresijskega algoritma in podobno.

Spomnil sem se na dendrogram in drevesno strukturo. Mogoče je to rešitev, vsaj boljša. Če kdo napiše tukaj psevdokodo za boljšo rešitev, jo lahko uporabi.

Haniball ::

Glede na opis problema, bi rekel da imaš opravka s clusteringom. Zakaj torej ne bi uporabil kar za to namenskih algoritmov?
Pa če te tvoje vektorje točk dodajaš inkrementalno, lahko uporabiš kak lazy learning algoritem ala kNN: K-nearest neighbors algorithm @ Wikipedia


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[C#] Bisekcija

Oddelek: Programiranje
183300 (2672) b4d
»

Naprednješa knjiga o programiranju (koncepti, ...)

Oddelek: Programiranje
366145 (5316) noraguta
»

Matematika.. 0=1 in deljenje z nič itd.. =) (strani: 1 2 )

Oddelek: Znanost in tehnologija
767936 (6829) DimmniBurek
»

Iskanje naslednje ponovitve - najboljši algoritem (strani: 1 2 )

Oddelek: Programiranje
724448 (3506) Thomas
»

Matematicni "paradox" - vsaj. (strani: 1 2 3 4 5 6 )

Oddelek: Znanost in tehnologija
26016276 (12324) Thomas

Več podobnih tem