OldComp.cz

Komunitní diskuzní fórum pro fanoušky historických počítačů


Právě je 28.03.2024, 13:39

Všechny časy jsou v UTC + 1 hodina [ Letní čas ]




Odeslat nové téma Odpovědět na téma  [ Příspěvků: 10 ] 
Autor Zpráva
 Předmět příspěvku: ZX Spectrum Basic
PříspěvekNapsal: 06.04.2020, 16:39 
Offline
Pan Štábní

Registrován: 23.06.2013, 23:49
Příspěvky: 1100
Has thanked: 100 times
Been thanked: 157 times
Zdravim, mám otázku ohledně jednoho algoritmu v basicu, ale nechci zakládat přímo konkrétní vlákno, ale spíš nějaké univerzální.

Jedná se o algoritmus na Levenštejnovu vzdálenost:

https://cs.wikipedia.org/wiki/Leven%C5%A1tejnova_vzd%C3%A1lenost
http://oldcomp.cz/viewtopic.php?f=26&t=8427

Sesmolil jsem něco, ale nechci to postovat dál, protože by se to určitě dalo napsat lépe. Tak bych byl rád kdyby se na to někdo znalejší kouknul. Dík. :help:

_________________
Z80 Forth compiler (ZX Spectrum 48kb): https://codeberg.org/DW0RKiN/M4_FORTH


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 06.04.2020, 16:57 
Offline
Pan Štábní

Registrován: 23.06.2013, 23:49
Příspěvky: 1100
Has thanked: 100 times
Been thanked: 157 times
Udělal jsem nějaké testy a při deklaraci matice basic vždy vynuluje prvky. To pomůže, protože zkouším teď:
Kód:
function LevenshteinDistance(char s[1..m], char t[1..n]):
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t
  declare int d[0..m+1, 0..n+1]
 
  set each element in d to zero
 
  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m + 1:
      d[i, 0] := i
 
  // target prefixes can be reached from empty source prefix
  // by inserting every character
  for j from 1 to n + 1:
      d[0, j] := j
 
  for j from 1 to n + 1:
      for i from 1 to m + 1:
          if s[i - 1] = t[j - 1]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution
 
  return d[m, n]

_________________
Z80 Forth compiler (ZX Spectrum 48kb): https://codeberg.org/DW0RKiN/M4_FORTH


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 06.04.2020, 19:07 
Offline
Pan Štábní

Registrován: 23.06.2013, 23:49
Příspěvky: 1100
Has thanked: 100 times
Been thanked: 157 times
Podle me v tom pseudocodu z wiki je chyba
Kód:
for j from 1 to n + 1:
      for i from 1 to m + 1:
          if s[i - 1] = t[j - 1]:
Nacitaji znak PRED retezcem...
Tohle je jedna z variant prepisu do basicu. Rychlost uz je slusna, misto 3 hodin je to ted 9 vterin u "rosettacode" a "raisethysword".
Kód:
10  REM ZX Spectrum Levenshtein
20  INPUT "first word:",n$
30  INPUT "second word:",m$
40  LET n=LEN n$+1:LET m=LEN m$+1:DIM d(m,n)
50  FOR i=1 TO m-1:LET d(i+1,1)=i:NEXT i
60  FOR j=1 TO n-1:LET d(1,j+1)=j:NEXT j
70  FOR j=1 TO n-1
80    FOR i=1 TO m-1
90       LET r=d(i,j):IF n$(j TO j)=m$(i TO i) THEN LET r=r-1:REM substitution
100      IF r>d(i,j+1) THEN LET r=r-1:REM insertion
110      IF r>d(i+1,j) THEN LET r=r-1:REM deletion
120      LET d(i+1,j+1)=r+1
130   NEXT i
140 NEXT j
150 PRINT "The Levenshtein distance between """;n$;""", """;m$;""" is ";r+1;"."

Plus pridal jsem dalsi optimalizaci, kdy se nejlepsi vysledek (mezi nahrazenim, vlozenim a umazanim) muze zlepsovat vzdy o 1. Doufam ze to funguje ve vsech pripadech... :D

_________________
Z80 Forth compiler (ZX Spectrum 48kb): https://codeberg.org/DW0RKiN/M4_FORTH


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 06.04.2020, 21:17 
Offline
Pan Generální

Registrován: 01.12.2017, 21:01
Příspěvky: 2062
Bydliště: BA-Petržalka :(
Has thanked: 18 times
Been thanked: 323 times
To dva krát použité m-1 a n-1... nebolo by lepšie dať
Kód:
40  LET n=LEN n$:LET m=LEN m$:DIM d(m+1,n+1)

a ďalej už iba m a n bez -1?

_________________
Oznamy o novom príspevku mi na mail chodia iba sporadicky, takže keď sa nehlásim v diskusii, tak je to tým. V 80% nepríde mail vôbec.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 06.04.2020, 23:24 
Offline
Pan Štábní

Registrován: 23.06.2013, 23:49
Příspěvky: 1100
Has thanked: 100 times
Been thanked: 157 times
Ja jsem to celou dobu menil, zacinal jsem s +2... :D Tady uz jsem nenavratne konvertoval na prvni index 0. Prilis mnoho C.
Ale mas pravdu, tohle vypada lepe.
Kód:
10  REM ZX Spectrum Levenshtein
20  INPUT "first word:",n$
30  INPUT "second word:",m$
40  LET n=LEN n$:LET m=LEN m$:DIM d(m+1,n+1)
50  FOR i=1 TO m:LET d(i+1,1)=i:NEXT i
60  FOR j=1 TO n:LET d(1,j+1)=j:NEXT j
70  FOR j=1 TO n
80    FOR i=1 TO m
90       LET r=d(i,j):IF n$(j TO j)=m$(i TO i) THEN LET r=r-1:REM substitution
100      IF r>d(i,j+1) THEN LET r=r-1:REM insertion
110      IF r>d(i+1,j) THEN LET r=r-1:REM deletion
120      LET d(i+1,j+1)=r+1
130   NEXT i
140 NEXT j
150 PRINT "The Levenshtein distance between """;n$;""", """;m$;""" is ";r+1;"."

Jen ted uz vysledek nebude d(m,n), ale d(m+1,n+1). a nebo stale r+1. :D
Kdyz se vyhazi REM a predela 90
Kód:
90       LET r=d(i,j):IF n$(j TO j)=m$(i TO i) THEN LET d(i+1,j+1)=r:GOTO 130
tak je to rychlejsi, ale uz to nevypada tak prehledne.

_________________
Z80 Forth compiler (ZX Spectrum 48kb): https://codeberg.org/DW0RKiN/M4_FORTH


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 06.04.2020, 23:51 
Offline
Pan Generální

Registrován: 01.12.2017, 21:01
Příspěvky: 2062
Bydliště: BA-Petržalka :(
Has thanked: 18 times
Been thanked: 323 times
_dworkin píše:
...Jen ted uz vysledek nebude d(m,n), ale d(m+1,n+1). a nebo stale r+1. :D ...

Asi nechápem. Ono je snáď jedno, či to +1 dáš k LEN alebo až k DIM, výsledok je stále +1. Ak nie, treba pridať zátvorky.

n$(i TO i) ? Obyčajné n$(i) a n$(j) by nefungovalo rovnako?

_________________
Oznamy o novom príspevku mi na mail chodia iba sporadicky, takže keď sa nehlásim v diskusii, tak je to tým. V 80% nepríde mail vôbec.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 07.04.2020, 00:05 
Offline
Pan Štábní

Registrován: 23.06.2013, 23:49
Příspěvky: 1100
Has thanked: 100 times
Been thanked: 157 times
PotPalo píše:
_dworkin píše:
...Jen ted uz vysledek nebude d(m,n), ale d(m+1,n+1). a nebo stale r+1. :D ...

Asi nechápem. Ono je snáď jedno, či to +1 dáš k LEN alebo až k DIM, výsledok je stále +1. Ak nie, treba pridať zátvorky.

Rozdil je zda m/n ukazuje delku retezce a nebo velikost pole. U delky retezce me ted vypadlo 4x odcitani a zrychlilo se to o 0.04 vteriny. .) Ta delka je ulozena v posledni polozce toho pole. Proto je to d(max_m,max_n) a nebo d(delka_m+1,delka_n+1). Neumim to lepe vysvetlit.
PotPalo píše:
n$(i TO i) ? Obyčajné n$(i) a n$(j) by nefungovalo rovnako?

Super, tohle jsem nevygooglil kdyz jsem hledal jak se sakra vytahuje znak z retezce. Mam pocit ze jsem to uz zapomnel podruhe... Nasel jsem pouze tu ( TO ) variantu http://www.worldofspectrum.org/ZXBasicManual/zxmanchap8.html. Hned je to zase rychlejsi. :D O 0.56 vterin! .)

Pocitano porad k "rosettacode" a "raisethysword".
Kód:
10  REM ZX Spectrum Levenshtein
20  INPUT "first word:",n$
30  INPUT "second word:",m$
40  LET n=LEN n$:LET m=LEN m$:DIM d(m+1,n+1)
50  FOR i=1 TO m:LET d(i+1,1)=i:NEXT i
60  FOR j=1 TO n:LET d(1,j+1)=j:NEXT j
70  FOR j=1 TO n
80    FOR i=1 TO m
90       LET r=d(i,j):IF n$(j)=m$(i) THEN LET r=r-1:REM substitution
100      IF r>d(i,j+1) THEN LET r=r-1:REM insertion
110      IF r>d(i+1,j) THEN LET r=r-1:REM deletion
120      LET d(i+1,j+1)=r+1
130   NEXT i
140 NEXT j
150 PRINT "The Levenshtein distance between """;n$;""", """;m$;""" is ";r+1;"."

Hmmm... o dalsich 0.15 vetrin bych to zrychlil pri
Kód:
75    LET c$=n$(j)
80    FOR i=1 TO m
90       LET r=d(i,j):IF c$=m$(i) THEN LET r=r-1
...ale to zas uz neni ono...

_________________
Z80 Forth compiler (ZX Spectrum 48kb): https://codeberg.org/DW0RKiN/M4_FORTH


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 07.04.2020, 00:38 
Offline
Pan Generální

Registrován: 01.12.2017, 21:01
Příspěvky: 2062
Bydliště: BA-Petržalka :(
Has thanked: 18 times
Been thanked: 323 times
Namiesto riadkov 90, 100 a 110 by sa dalo použiť aj:
Kód:
LET r=d(i,j)-(n$(j)=m$(i))-(r>d(i,j+1))-(r>d(i+1,j))

Neodskúšané, snáď som sa niekde nepomýlil. Či je to rýchlejšie neviem. Keď sa to dá na jeden riadok aj s oboma FOR-NEXT, to už rýchlejšie bude.

_________________
Oznamy o novom príspevku mi na mail chodia iba sporadicky, takže keď sa nehlásim v diskusii, tak je to tým. V 80% nepríde mail vôbec.


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 07.04.2020, 03:59 
Offline
Pan Štábní

Registrován: 23.06.2013, 23:49
Příspěvky: 1100
Has thanked: 100 times
Been thanked: 157 times
Tak nejrychlejsi varianta neni kdyz to dam na jeden radek. Teda zkousel jsem
Kód:
90       LET r=d(i,j)-(n$(j)=m$(i)):LET r=r-(r>d(i,j+1)):LET d(i+1,j+1)=r+(r<=d(i+1,j))
Ale je to kupodivu pomalejsi. Asi protoze radek 100 je skoro vzdy FALSE?
Kód:
10  REM ZX Spectrum Basic - Levenshtein distance
20  INPUT "first word:",n$
30  INPUT "second word:",m$
40  LET n=LEN n$:LET m=LEN m$:DIM d(m+1,n+1)
50  FOR i=1 TO m:LET d(i+1,1)=i:NEXT i
60  FOR j=1 TO n:LET d(1,j+1)=j:NEXT j
70  FOR j=1 TO n
80    FOR i=1 TO m
90       LET r=d(i,j)-(n$(j)=m$(i)):REM substitution
100      IF r>d(i,j+1) THEN LET r=r-1:REM insertion
110      LET d(i+1,j+1)=r+(r<=d(i+1,j)):REM deletion
120   NEXT i
130 NEXT j
140 PRINT "The Levenshtein distance between """;n$;""", """;m$;""" is ";d(m+1,n+1);"."

Mel jsem neprijemny zasek, kdy me to psalo vadne vysledky... Nemuzu se uz spolehnout na promnenou "r" a nevsim jsem si ze promnenou "m" pouzivam v testu k ulozeni minut...
Prohodil jsem "vysledek=r+1-podminka" za "vysledek=r+opacna podminka".
Zustal tam jeden IF THEN, at je aspon videt co to vsechno umi. :D
Lepsi to uz nebude, za me uz dobry. Prijde me to konkurenceschopny ostatnim jazykum. Mozna je to ale tim, ze jsem ten kod sesmolil, takze pro me vypada srozumitelne... :D
Ted jeste zjistit jak to dat na rosettacode, nemam login...

_________________
Z80 Forth compiler (ZX Spectrum 48kb): https://codeberg.org/DW0RKiN/M4_FORTH


Nahoru
 Profil  
 
 Předmět příspěvku: Re: ZX Spectrum Basic
PříspěvekNapsal: 07.04.2020, 04:04 
Offline
Pan Štábní

Registrován: 23.06.2013, 23:49
Příspěvky: 1100
Has thanked: 100 times
Been thanked: 157 times
Dival se nekdo na ten jazyk J? WTF! :D
https://rosettacode.org/wiki/Levenshtein_distance#J

_________________
Z80 Forth compiler (ZX Spectrum 48kb): https://codeberg.org/DW0RKiN/M4_FORTH


Nahoru
 Profil  
 
Zobrazit příspěvky za předchozí:  Seřadit podle  
Odeslat nové téma Odpovědět na téma  [ Příspěvků: 10 ] 

Všechny časy jsou v UTC + 1 hodina [ Letní čas ]


Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 5 návštevníků


Nemůžete zakládat nová témata v tomto fóru
Nemůžete odpovídat v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete přikládat soubory v tomto fóru

Hledat:
Přejít na:  
Založeno na phpBB® Forum Software © phpBB Group
Český překlad – phpBB.cz