Forum » Programiranje » Iskanje podvojenih zaporedij
Iskanje podvojenih zaporedij
Nejc Pintar ::
Zanima me kakšen bi izgledal algoritem ki bi v binarni datoteki poiskal podvojena zaporedja bitov. Najprej najdaljše podvojeno zaporedje, nato pa do vse krajših.
Lahko je biti prvi, če si edini!
Gundolf ::
Brute force, O(n2) 
za offsete n = -N do N (N je dolžina datoteke) v eni zanki pregleduješ, če je datoteka[i] == datoteka[i+n] in si pri tem lepo zapomniš vsa zaporedja, ki si jih našel. Sicer ne boš našel najprej najdaljših ampak kar vse naenkrat.
za offsete n = -N do N (N je dolžina datoteke) v eni zanki pregleduješ, če je datoteka[i] == datoteka[i+n] in si pri tem lepo zapomniš vsa zaporedja, ki si jih našel. Sicer ne boš našel najprej najdaljših ampak kar vse naenkrat.
snow ::
from random import randint
n = 10
dat = []
for i in range(n):
dat.append(randint(0,1))
print 'data:',dat
s = n - 1
while s > 1:
zap = {}
for offset in range(0,n-s+1):
string = ""
for i in dat[offset:offset+s]:
string += str(i)
if zap.has_key(string):
zap[string] += 1
else:
zap[string] = 1
s -= 1
print zap
Opis:
Generiramo vse substringe dolžine N-1 do 2 in jih shranjujejemo v tabelo, kjer je indeks(key) kar string, njegova vrednost pa število ponovitev.
Izpis si lahko primerno urediš - npr. da ti izpiše tiste katerih vrednost je višja od 1.
Primer outputa:
data: [1, 1, 0, 1, 1, 0, 0, 0, 0, 1]
{'110110000': 1, '101100001': 1}
{'11011000': 1, '10110000': 1, '01100001': 1}
{'1100001': 1, '1011000': 1, '0110000': 1, '1101100': 1}
{'011000': 1, '100001': 1, '110000': 1, '110110': 1, '101100': 1}
{'11000': 1, '10000': 1, '01100': 1, '11011': 1, '00001': 1, '10110': 1}
{'0110': 1, '0000': 1, '0001': 1, '1100': 1, '1101': 1, '1011': 1, '1000': 1}
{'011': 1, '001': 1, '000': 2, '110': 2, '100': 1, '101': 1}
{'11': 2, '10': 2, '00': 3, '01': 2}
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
snow ::
Naprimer takole:
Namesto:
Tole:
Aja to je Python.
Tale primer z dolžino zaporedja 100 naredi praktično takoj, za 200 malo počaka (~1 sekundo), za 500 pa traja nekje 15 sekund na E6300.
data: [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0] 1000011001 2 1100101011 2 000010111 2 110010101 2 100001100 2 100101011 2 000011001 2 00000101 2 11001010 2 11010000 2 10111100 2 01100101 2 10100001 2 10010101 2 11100001 2 01011110 2 00001100 2 10000110 2 00101011 2 00010111 2 00001011 2 00011001 2 0011001 2 0001011 2 0000101 3 0100000 2 0100001 2 1100001 2 1100101 3 0010101 3 1110000 2 0001100 2 1010100 2 1011110 3 0000110 2 0000010 2 1101000 2 1010000 3 1000011 2 1000010 2 0111100 2 0101111 2 0101011 2 0110010 2 1001010 2 0010111 2 110000 2 110100 2 010100 2 010101 3 001100 2 011110 3 000110 2 000011 2 000010 4 100101 3 111100 2 101111 3 111000 2 101011 2 101010 2 110010 3 010111 3 010110 2 011001 3 001010 3 001011 3 000001 2 000101 3 100001 4 100000 2 010000 4 111010 2 101000 3 10000 6 10101 4 10100 4 01101 2 01100 3 11110 3 11010 3 01000 4 00110 3 00010 4 00011 3 10010 4 10110 2 10111 4 01110 2 01111 3 11001 4 11000 2 11100 3 11101 2 01011 5 01010 5 00001 6 00000 3 00100 2 00101 6 0110 5 0111 5 0000 9 0001 7 0011 4 0010 8 0101 10 0100 6 1111 3 1110 5 1100 6 1101 4 1010 8 1011 6 1001 5 1000 6 010 16 011 10 001 12 000 16 111 8 110 10 100 12 101 14 11 18 10 26 00 29 01 26
Namesto:
#print zap
Tole:
for key in zap.keys():
if zap[key] > 1:
print key,zap[key]
Aja to je Python.
Tale primer z dolžino zaporedja 100 naredi praktično takoj, za 200 malo počaka (~1 sekundo), za 500 pa traja nekje 15 sekund na E6300.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Gundolf ::
En zelo rahel problemček snow: Ker govorimo o datotekah (sicer ne vem kaj točno Nejc rabi) - 200 bitov (al pa bajtov, odvisno kako zapisuješ tale zaporedja, ampak razlike tu ni velike) dolga datoteka ni praktično nič. S takim algoritmom se že 1M bitov / bajtov datoteke zaradi prostorske zahtevnosti niti dotakniti ne moreš. Oz pri malo manjši 1k datoteki rabiš ~167.165.000 bitov / bajtov samo za shranjevanje vseh možnih zaporedij. To je verjetno tudi razlog, da je algoritem tako strašno počasen.
snow ::
Aja, ker nisem pastal pri popravku izpisa cele kode, sem pozabil tisto vrstico, kjer se za vsako iteracijo za določeno dolžino iskanega stringa vsi stringi pobrišejo.
Ja res je moja koda kar potratna z ramom :)
Pa dokler ni potrebe po daljših stringih (ali veliko izvajanji) tudi ni potrebe po drugih rešitvah.
Sicer pa.. a ni problem O(n^3)?
Različnih dolžin stringov: n
Primerjava stringov pa je tudi kvadratne odvisnosti, saj je potrebno primerjati vsakega z vsakim. (n-len)^2.
Ja res je moja koda kar potratna z ramom :)
Pa dokler ni potrebe po daljših stringih (ali veliko izvajanji) tudi ni potrebe po drugih rešitvah.
Sicer pa.. a ni problem O(n^3)?
Različnih dolžin stringov: n
Primerjava stringov pa je tudi kvadratne odvisnosti, saj je potrebno primerjati vsakega z vsakim. (n-len)^2.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Gundolf ::
Aja valda, na to da bi sproti brisal se pa nisem spomnil, samo vseeno je požrešna zadeva, za 1M datoteko imaš potem v eni točki 0.5M 0.5M dolgih stringov naenkrat v RAMu.
Izgleda da je, če problem tako definiraš kot si ga, res O(n3), če ga pa drugače - preveriš le pokrivanja niza s samim sabo pri vseh možnih offsetih - je pa 100% O(n2).
Izgleda da je, če problem tako definiraš kot si ga, res O(n3), če ga pa drugače - preveriš le pokrivanja niza s samim sabo pri vseh možnih offsetih - je pa 100% O(n2).
snow ::
Hm 0.5M stringov po 0.5M znese 2.5*10^11 primerjav :=)
Ena primerjava pa pomeni primerjat do max. 0.5M bitov. No saj lahko prej greš ven iz primerjave takoj ko se dva bita ne ujemata, ampak vseeno tole trajaaaaa.
Sploh pa če upoštavamo, da je potrebno pregledat 1M različnih dolžin.
Po moje ti prej zmanjka časa kot rama.
Ena primerjava pa pomeni primerjat do max. 0.5M bitov. No saj lahko prej greš ven iz primerjave takoj ko se dva bita ne ujemata, ampak vseeno tole trajaaaaa.
Sploh pa če upoštavamo, da je potrebno pregledat 1M različnih dolžin.
Po moje ti prej zmanjka časa kot rama.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Gundolf ::
Štos je v tem da ti ni treba pregledat različnih dolžin :) Ko pregledaš eno dolžino l, si hkrati pregledal že en kup dolžin < l. Samo pametno moraš pregledat. Tako se znebiš enega n-ja v časovni zahtevnosti.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Izdelava algoritmaOddelek: Znanost in tehnologija | 1462 (842) | Klemen86 |
| » | Verjetnost pri kroglicahOddelek: Šola | 1438 (1135) | Math Freak |
| » | Vitezi in oprode, nalogaOddelek: Šola | 2854 (2590) | noraguta |
| » | [JAVA] helpOddelek: Programiranje | 1502 (1216) | keworkian |
| » | problem s prekrivanjem likovOddelek: Programiranje | 1420 (1343) | McAjvar |