» »

Problem (za Stratosa?)

Problem (za Stratosa?)

Thomas ::

Najhitrejši algoritem, ki iz stringa S potegne tak substring T, da je L(T)*O(S,T) maksimalen.

L(T) - je dolžina Tja.

O(S,T) - število pojavljanj Tja v Sju.

O(S,T) mora biti več kot 1.

:\

StratOS ::

what ?

To pišeš v zvezi s čim ?

Z hitrostjo iskanja določenega stringa v stringu ???
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Zgodovina sprememb…

  • spremenila: StratOS ()

Thomas ::

Ja no, če ne razumeš prvega posta, potem sem naredu napako v naslovu te teme.

;)
Man muss immer generalisieren - Carl Jacobi

JerKoJ ::

A prekrivanje velja
npr : S='aaa' in T='aa' ali je v tem primeru O(S,T)=2 al ne

Thomas ::

Zelo dobro vprašanje JerKoJ.

NE sme se prekrivat.

:)
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Hm... da spet zakompliciram binarno ali textualno oz. lowercase / upercase / mixed case / allcase


cist brez veze
AaA..... pčih
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

Kakor ti najbolj ljubo. ;)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

No ... dej ti (Stratos) reši tega, za kerga ni reference na netu. Ki niti ni tolk enostaven, kot tisti tvoji.

:D
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Oki, problem sploh ni tako težak.
Navaden brute bi bil takšen :

Najhitrejši algoritem, ki iz stringa S potegne tak substring T, da je L(T)*O(S,T) maksimalen.

L(T) - je dolžina Tja.
O(S,T) - število pojavljanj Tja v Sju.
O(S,T) mora biti več kot 1.

če se odločimo da gremo samo na textualno razliko, moramo vedeti sledeče logične zaključke :

Dolžina T-ja oz sam iskani string, ta je znana
Gremo pač od začetne črke v S-ju in iščemo prvo ponavljanje T-ja, ker isti T ne more biti v S-ju med iskanim indexom in iskani index+dolžina (T) povečamo start point iskanja T-ja v S-ju za dolžino T-ja ...
ponavljamo dokler ne pridemo do konca.

Če najdemo več T-jev v S-ju je O(S,T) > 0, sama logika ti pove da bo hitrost iskanja večja čim večjo dolžino bo T imel relativno na S, kar ti pove tudi tvoja formula.

Procesorsko hitreje v določenih primerih prideš do zaključka, če upoštevaš le prvo črko T -ja in iščeš to v S-u, vse pa je odvisno od dolžine T in S a ter število ponavljanj prve črke T -ja v S-u.
Torej iščeš prvo črto T-ja v S u in ko to najdeš preveriš na tem mestu še ponavljanje celotnega T-ja v s-u, če ne pa nadaljuješ z iskanjem na index-u + dolžina T in zopet iščeš naslednja ponavljanja črk.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Zgodovina sprememb…

  • spremenila: StratOS ()

Thomas ::

Stratos

> Dolžina T-ja oz sam iskani string, ta je znana

Od kod ti pa to?

Potencialno je vsak substring T stringa S, ki je krajši od polovice Sja, kandidat za zadani pogoj.

Nič ni znana! Če boš pa za vsak tak string izvedel tvojo proceduro ... bo pa dolga.

Ni tko anfoh, ni!

>:D
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Jaz sem ti dal le dva načina, jih je pa več odvisno kakšen je svoj S in T string oziroma kakršna koli povezava.

Zgornji brute se pa najbolj obnesejo !
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

No, bom povedal. Počasi.

Najprej poiščeš karakter, ki se največkrat pojavlja v stringu.

Kako to najhitreje narediš?

Kdo ve?

:)

Man muss immer generalisieren - Carl Jacobi

StratOS ::

Sej sem ti v zgornjih postih povedal od česa je hitrost iskanja odvisna.
Še enkrat od velikosti stringov ( originalnega in iskalnega )
in od entropije stringov.


Jaz sem ti dal le dva načina, jih je pa več odvisno kakšen je svoj S in T string oziroma kakršna koli povezava


Kar si ti začel sem v bistu že jaz načel, vendar pa kakor si ti povedal HITROST v tvoji smeri predvsem odvisna od entropije in seguence S in T-ja.
Hitrostni algoritem za izračun le tega je torej odvisen od tega, in tudi pristop k problemu je odvisen od tega.

Če hočeš ti lahko dam enih 5 različnih primerov za reševanje, algoritem pa je seveda odvisen od samih stringov in zgoraj navedenih parametrov, zaporedij in entropij ter velikosti.

Govorimo o hitrosti in ne o algoritmu !
Hitrost algoritma oz. procesorsko gledano hitrost izvajanja algoritma in izračun končnega rezultata pa je spet drugo poglavje.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Zgodovina sprememb…

  • spremenila: StratOS ()

Thomas ::

Po moje se brezveze izvijaš - direktno (in pošteno) rečeno!

Jasno, da je odvisno od entropije stringov. Tudi korenjenje floata je odvisno od tega kako je "skravžan" input ... Tudi je sortni algoritem odvisen od pred(ne)urejenosti tabele ...

To je jasna stvar.

Ti meni daj en dober algoritem - ali pa reci, da ne znaš.

Ali pa odgovori vsaj na podvprašanje.

:)
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Kot sem ti že povedal moreš problem konkretizirati, jaz sem se že v večini primerov že dosti ubadal z procesorsko gledano hitrostjo obdelave stringov in sem našel 5 različnih tipov k pristopu.

Kot sem ti lepo napisal ti lahko povem v čem je fora, testiral sem predvsem v VB, ki je zaradi vmesnega člena ( runtime dll ) pri takšnih operacijah izreeedno počasen.

Tudi tista tvoja matematičen izraz ni preveč točen in velja splošno. Res pa je da je to entropijska velikostna funkcija obeh stringov.

Lahko ti povem kako gre funkcija Instr() v VB deluje.
Deluje totalno brute, mislim pa da vsaka funkcija ki išče določen string v drugem stringu deluje tako, zakaj torej uporabiti ukazni iskalec celotnega stringa v stringu.
To je dobro le pri krajših dolžinah stringov.

Če imaš velik string ( predvidevam, ker se ti gre za hitrost ) je seveda sam algoritem odvisen od entropije in velikosti stringov.

Algoritem je dober če je programer dober, in če veš kaj več o tvojem iskalnem stringu oz stringu v katerem iščeš.
To je tvoje izhodiššče, dokler sistem točno določiš - konkretiziraš.

Primer :
Vedno bomo iskali string "ABC"
string="00000000000000000000ABC"
1.
zdaj pa premisli : brute force bi iskal string "A" po 20 loopih bi ga našel, pregledati bi moral ali je še sledeči string "B" in "C", da bi spoznal da je, torej 3 korake več če bi iskal string "ABC" bi ga našel v 21 poskusu.

2.
string="AAAAAAAAAAAAAAAAAAAAABC"
če bi tu iskal "A" bi uporabil vsaj eno korak več pri vsakem koraku ( pregled ali je sledeči string "B" ).

3.
string="ABABABABABABABABABABABC"
če bi tu iskal "A" bi uporabil min 2 koraka več pri vsakem koraku, če bi iskal "AB" bi uporabil enako št. korakov kot pri 1.), prav tako kot če bi iskal "ABC".

Če sedaj gledamo relativno hitrost kot št. korakov in ne procesorsko hitrost, ki po možnosti tebe zanima ( še zdaj nisi specificiral kaj misliš kot hitrost ) vidimo da je funkcija ki nam bo to opisala odvisna seveda od velikosti stringa in našega iskanega stringa v njem in število kombinacij iskanega stringa v našem stringu in vseh njegovih ( iskanih ) podstringov, kar pa ni enako entropiji ( to je le stanje neurejenosti sistema ), entropija sistema je v tem mišljena na ponavljanje našega iskanega stringa v stringu.
Od tebe je potem odvisno ali boš iskal prvo črko iskanega stringa v stringu, prve dve ozirama kakšen koli substring ali del iskanega stringa.
Če te zanima le število ponaljanj iskanega stringa v stringu je rezultat vedno isti, ne glede na pot iskanja in sequenco iskanja iskalnega stringa v stringu, ki si jo izbral, le število korakov pri tem se lahko zelko razlikuje.
Če hočeš statistično res dobiti minimum korakov moraš sistem prej kombinacijsko/entropijsko obdelati.
Kakšen del stringa v iskanem stringu boš iskal in kako ga boš iskal ti da ta funkcija.
Iščeš kombinacije vseh stringov in podstringov iskanega stringa v stringu za dan primer, ko najdeš pri kerem substringu iskanega stringa ja najmanj možnih kombinacij izbereš za iskanje le tega.

Da ne bom pametoval ...
tule je naprimer izsek stringa "...ABABERTFFJTZJABECEF#$%RTNGN$%&ABRZJCVXVBMKKHL.."
iščeš string "ABECEDA" v zgornjem (delnem) stringu.
Z frekvenčno analizo si ugotovil, da se string ABEC najmanjkrat pojavlja v celotnem izbranem stringu stringa.
Torej iščeš "ABEC" v celotnem stringu in ko ga najdeš skušaš še najti celoten iskani string stringa.
Tudi sequenca ponavljanja je matematično zanimiva, lahko bi izmed teh delov odkril da se izmed "ABEC" pri nam še relativno manj ponavlja "A??E?D"
toda se pri programskemu delu to precej pozna, kajti pri vsakem koraku imaš za dani korak še 3 dodatne korake ( da preveriš ).

To je le računalniško najboljši sistem za najkrajše število korakov.
Če te še kaj bolj zanima si pa lahko prebereš kakšno bukvo o kombinatoriki, neurejenosti in podobnem pa mi potem mal bolj zabluzi z nekim primerom.
Torej če sistem ti točno določiš ima samo eno najkrajšo pot kar se tiče programskih minimalnih korakov pri tem ( dobiti pa število ponaljanj stringa v stringu).

Za vsak razlićen primer imamo le vedno en postopek/algoritem s katerim bomo prišli do konca, število korakov in algoritem sam se pa od primera do primera razlikuje. Odvisen je le od začetnih pogojev, entropije in ostalih parametrov.

Po moje se dobro izvijam - direktno (in pošteno) rečeno, ker sam nisi nič konkretiziral.
Dej dejanski primer in povej kaj za vraga smatraš kot hitrost ...


Upam da sem bil dovolj konkreten in sem hkrati rešil tvoj problem, za najkrajše število programskih korakov pa lahko za velik sistem razpišeš nagrado !!
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Zgodovina sprememb…

  • spremenila: StratOS ()

Thomas ::

Kaj pa (prvo) podvprašanje?

Kako bi najhitreje določil tisti karakter, ki se največkrat pojavlja v stringu?

A je tud vse preodvisno. >:D
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Statistika, totalni brute, potem pa izbezat kaj se da za določen sistem ...

Povej kakšen problem imaš, jaz mam kar podobnega, no ne gre se za minimum korakov ampak minimum poti itd ...
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

Ma jest mam problemov čez glavo. Numerična stabilnost pa to ... ampak ni za tukaj. Tisto delam podnevi in razpravljam o tem - ne.

Tukaj poživljam sceno. Teoretiziram in se igram.

So - kako boš določil (v najmanj ciklih) katerega karakterja je največ v stringu?

:)

Man muss immer generalisieren - Carl Jacobi

Primoz ::

Znak, ki se največkrat pojavi v nizu...

algoritem, ki vedno deluje....
znak po znak.. pa stejemo

Zahtevnost: k*n (linearna), kar ni tako slabo.. ampak v bistvu je slabo.

Moj genetski optimizator se pa še sesuva (in daje čudne rezultata.. pri različnih random nizih BISTVENO različne rezultate - sicer je res, da se s tem nisem ukvarjal več ko 1h ... pa vendar) tako da... ga trenutno še ne morem uporabiti za kaj pametnega.
There can be no real freedom without the freedom to fail.

Thomas ::

Lep, kmečki odgovor! Naposled. Pa še dokaj dober.

Ampak ... a se da kaj bolje, kot iti skozi string in prišteti 1 tabeli, na indexu trenutnega karakterja? :\
Man muss immer generalisieren - Carl Jacobi

Primoz ::

V primeru res dolgega niza.. in če ne potrebujemo števila znakov, bi se mogoče izplačala statistična metoda... Na "random" ali kakorkoli že (samo neodvisno od vsebine niza) izberemo en odstotek znakov (kaj statistično pomembnega - 15% - 50%) in potem preverimo na tem vzorcu. V večini primerov (veliki nizi) bi dobili DOKAJ merodajen rezultat, lahko pa tudi POPOLNOMA sfalimo.

Zahtevnost: k*n (pri čemer je k približno pol zgornjega), kar je bolje vendar ne bistveno. Lahko pa sfalimo (zgoraj ne moremo).
There can be no real freedom without the freedom to fail.

Thomas ::

Statistika ne potrebuje 50%, da bi bila zanesljiva. Za zares dolge nize, lahko dobiš skoraj zanesljivo odgovor že na stotinki pregledanega.

Je tako?

Potem pride preverba, če je res. Kakšna ideja v zvezi s tem?

:)
Man muss immer generalisieren - Carl Jacobi

Primoz ::

Če je string res dolg... pa je znakov, ki jih je največ dejansko VIDNO več... lahko naprimer rečemo da je aritmetična sredina njihovih ascii kod... nekje blizu tega znaka... kar ne pobere veliko časa, ker čez zanko vlačimo samo 2 spremenljivki (seštevek in število). Drugače pa ... ali uporabljamo ta podatek v kakšnem večjem algoritmu, ali tukaj govorimo o tem podatku kot podatku samem zase?
There can be no real freedom without the freedom to fail.

Primoz ::

Ok... prejsnji predlog je "rahlo" sumljivo cuden. V primeru, da bi imeli možnost kakšnega časovno nezahtevnega "randoma"... bi lahko statistično funkcijo nekajkrat ponovili (s čimer bi zmanjšali možnost napake (ne izključili) - v primeru, da se rezultati ujemajo, postavi pa se vprašanje, kaj pa, če se ne?)

Drugič... zgornjo statistično funkcijo se da rahlo spremeniti, tako da procentualen delež vzorcev v vsoti pada z dolžino niza (in obratno) - ob predpostavki, da dolžino vemo. S tem rešimo težavo s kratkimi nizi in znižamo časovno zahtevnost POD linearno odvisnost.
There can be no real freedom without the freedom to fail.

Thomas ::

Tako je - pod linearno odvisnost pridemo, da določimo najverjetnejši znak, ki se največkrat pojavlja v stringu.

Ampak mene zanima, če nam ta podatek kaj koristi tudi, ko iščemo dejansko najverjetnejši znak.

:\
Man muss immer generalisieren - Carl Jacobi

Primoz ::

Dejansko najverjetnejši znak je tisti, ki ga po tem postopku samplinga v n ponovitvah iskanja najpogostejšjega znaka dobimo največkrat. Če je pa to najpogostejši znak... je pa drugo vprašanje. Čeprav je ZELO verjetno, da je.
Še posebej... če besedilo nima kakšne zanimive interne ureditve... tak algoritem na 100 ponovitvah abecede zagotovo daje "zanimive" rezultate...
There can be no real freedom without the freedom to fail.

Zgodovina sprememb…

  • spremenil: Primoz ()

Thomas ::

Sej. Ampak recimo, da veš, da je A najverjetneje najpogostejši znak.

Ti ta vednost lahko kaj pomaga pri dejanskem štetju? In kako?

:)
Man muss immer generalisieren - Carl Jacobi

Primoz ::

Na idejni ravni težko... razen da v primeru da bi verjetno lahko rekli, da če je dobljen znak (s samplingom) enak kot predvideni... lahko kar nehamo.

Po drugi strani pa na izvedbeni ravni... lahko na podlagi predvidevanj o najpogostejših znakih le-te stlačimo skupaj v isti mem page oz. v registre ali karkoli...
There can be no real freedom without the freedom to fail.

Thomas ::

Naprimer če kaže, da je najpogostejšega znaka več od polovice, potem se splača it štet samo tisti znak in nobenega drugega.

Če je končen rezultat res več od polovice - smo že nekoliko optimizirali.

Ampak to je šele začetek problema. Zdaj moramo pa preveriti še najpogostejši substring. :)

Man muss immer generalisieren - Carl Jacobi

StratOS ::

Hm, zanimivo mislim da se vrtimo v krogu.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

MH0 ::

Ja seveda, če pa se ti (StratOS) brezveze izvijaš :-)

Primoz ::

Da bo šla debata naprej...
najbolj kmečko butasat metoda je generiranje tabele vzorcev in njihovo preštetje. Sicer je stvar požrešna kot le kaj in tudi počasna... ampak deluje :)
There can be no real freedom without the freedom to fail.

StratOS ::

as i told u : No pain no gain.

Analiza pa boš mel minimalno/najgitrejšo rešitev.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

Kaj Stratos, če je analiza dražja od brute force? :D

No potem ko imamo top char, moramo videti, če je katerega para znakov več kot top char-a polovic ...

Preden pa gremo za vsak par XY štet, lahko preverimo, če se sploh splača.

MIN(O(S,"X"),O(S,"Y")) >= O(S,"(XY"))

Ja?

:)
Man muss immer generalisieren - Carl Jacobi

Primoz ::

Ja... samo vprašanje je, če se splača. Če bomo to potem ponovili še za tretji znak itd... moramo na koncu še vedno spobat vsaj nekaj vzorcev z bruteforce... in tako se lahko celo zgodi, da imamo na koncu bolj zahteven algoritem od debilnega brute forcea.
There can be no real freedom without the freedom to fail.

Thomas ::

Bemo ja! Taf tole, taf! :D

Ampak ko se začne zares, je zmeraj tako.

Kolikor je meni znano, optimalni algoritem za tole še ni splošno znan.

:)
Man muss immer generalisieren - Carl Jacobi

zdravcc ::

Ok, danes sem si prvic vzel cas in slucajno prebral tale topic, moj odgovor sledi.

Thomas: Kaj ti si nor in se po moznosti gres boga, oziroma mislis da je StratOS bog, se ti sploh zavedas kaksen problem si predstavil!? ;)

Resevanje tega problema je popoln nesmisel (no ja ;) ?), berite naslednje:
Pri tem programu je edina moznost, da testiras vse kombinacije stringov takole:
1, 1+2, 1+2+3, 1+2+3+...+n; 2, 2+3, 2+3+4, 2+3+4+...+n; ..+n; n; (stevilke pomenijo zaporedne stevilke znakov)

zdej pa podrobnosti:
-najbolje je, da v buffer shranjujes moznosti, ki si jih sprobal(torej ob tem vse prve kombinacije; s tem, da je pri prvi kombinaciji za vse ostale string z +n nesmiseln, stalno je string zadnje

...+n kombinacije nesmiseln za naslednjo y iteracijo kar bi lahko pomenilo, da je +(n-1) povsem nesmiseln za naslednjo kombinacijo ampak ni res, torej je tukaj ze paradox, ki je neresljiv v realnem

koncnem prostoru, resljiv je le kompleksnem neskoncnem prostoru, kar je za racunalnik nemogoce, ampak ker prizkusamo vse kombinacije tega problema na sreco ni) in ob njih napises stevilo

ponavljanj, iz njega potem preverjas ce je kter string se tak v drugih y iteracijah in vecas stevec v bufferju pri stringu, ki se ponovi.
Kje je problem, problem je v tistem ker na sreco preizkusamo vse kombinacije?! potem pa moramo se cel buffer preracunat, da dobimo maximalno vrednost racuna, ki si ga predlozil.
To kar si ti nacel je podobno problemu trgovskega potnika, ki ni resljiv v realnem casu.

Ampak si postavil zelo dober problem, ki se ga ne da resiti na klasicen nacin, zato je potrebno risati preko okvirja slike in biti utvarjalen, mislim, da imam resitev!?
Namig: bifurkacije, vreme, kaos.
Amapak bos ob ze napisanem moral se sam biti zeloooo ustvarjalen.(kot da ze sama napisana teorija ne bi bila dovolj tezka ;) )

Kaj mislis zakaj ni nobene reference na netu!?

Nisem pa ziher.


Dovolj. :)

Thomas ::

Zdravcc

Tako je! Pa še hujša postane stvar, ko se vprašamo - ne kateri substring - pač pa kateri subset pokriva največ prostora!

Substringov je cca kvadrat dolžine polovic.

Subsetov je pa 2dolžina stringa.

Ampak če hočemo imeti dober pregled nad stringom (datoteko), je to tisto, kar rabimo.

:)
Man muss immer generalisieren - Carl Jacobi


Vredno ogleda ...

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

Iskanje podvojenih zaporedij

Oddelek: Programiranje
91734 (1514) Gundolf
»

[vb] Branje formata števil

Oddelek: Programiranje
91371 (1172) Tugo
»

[Delphi] lexicographic order

Oddelek: Programiranje
201008 (889) mISOk
»

int to string v c++

Oddelek: Programiranje
272228 (1956) OwcA
»

Loopy problem

Oddelek: Programiranje
281396 (905) snow

Več podobnih tem