Ha a legutóbbi programváltozatban i értékét növelni kezdjük, nyomasztó lassulásnak leszünk tanúi: az első 100 szó leszármazottaihoz egy századmásodperc sem kell, az első 1000 szóéihoz 2,5 másodperc, az első 10000 szóéihoz 662. (Értelemszerűen a számok önmagukban jelentőség nélküliek, nyilván csak az arányuk érdekes.)
Felvethető erre, hogy hiszen úgyis végtelen sok időnk van, de azért érdemes lehet eltűnődni azon: hogyan tehetnénk hatékonyabbá a programot? Azt, hogy egy szót előállítottunk-e már, egy lista elemei alapján vizsgálja a program: ha minden igaz, ehhez rossz esetben a lista összes elemét meg kell néznie. Vajon a python további adatszerkezeteivel nem gyorsíthatnánk-e a program futásán?
A lista mellett elhelyezhetnénk egy halmazban is a szavakat – ezzel nyilván nő a tárigény, de vajon mennyit nyerünk a gyorsabb kereséssel? Vagy ha a szavak egy szótár kulcsai lennének, akkor akár a hozzájuk vezető utat is tárolhatnánk…
Lássuk most az ezt megvalósító programot.
def rule1(list, dict, i):
word= list[i]
if word[-1]=='I':
neww= word+'U'
if neww not in dict:
list+= [neww]
dict[neww]= dict[word]+'U'
def rule2(list, dict, i):
word= list[i]
neww= word+word[1:]
if neww not in dict:
list+= [neww]
dict[neww]= dict[word]+'D'
def rule3(list, dict, i):
word= list[i]
for j in range(1, len(word)-2):
if word[j:j+3]=='III':
neww= word[:j]+'U'+word[j+3:]
if neww not in dict:
list+= [neww]
dict[neww]= dict[word]+'H'+str(j)
def rule4(list, dict, i):
word= list[i]
for j in range(1, len(word)-1):
if word[j:j+2]=='UU':
neww= word[:j]+word[j+2:]
if neww not in dict:
list+= [neww]
dict[neww]= dict[word]+'E'+str(j)
def rules(list, dict, i):
rule1(list, dict, i)
rule2(list, dict, i)
rule3(list, dict, i)
rule4(list, dict, i)
return i+1
i= 0
list= [ 'MI' ]
dict= { 'MI': ''}
while i<11:
i= rules(list, dict, i)
print(dict)
Ahogy korábban beharangoztuk, visszakerült a négy függvénybe annak vizsgálata, hogy a szót korábban megtaláltuk-e (illetve kihasználtuk, hogy a lista mellett a szótár is mutabilis adatszerkezet: a függvények mindkettőnek megváltoztathatják az értékét, így már csak az immutabilis i változó értékét kell visszaadniuk).
És végül a szótár tartalma (ezúttal nem csak áttördelve, hanem át is rendezve: az átrendezés a fabejárás sorrendjének felel meg, ami egyúttal –a levezetési szabályokat tekintve– sajátos ábécésorrendet is tükröz):
{
'MI': '',
'MIU': 'U',
'MII': 'D',
'MIUIU': 'UD',
'MIIU': 'DU',
'MIIII': 'DD',
'MIUIUIUIU': 'UDD',
'MIIUIIU': 'DUD',
'MIIIIU': 'DDU',
'MIIIIIIII': 'DDD',
'MUI': 'DDH1',
'MIUIUIUIUIUIUIUIU': 'UDDD',
'MIIUIIUIIUIIU': 'DUDD',
'MIIIIUIIIIU': 'DDUD',
'MUIU': 'DDUH1',
'MIUU': 'DDUH2',
'MIIIIIIIIU': 'DDDU',
'MIIIIIIIIIIIIIIII': 'DDDD',
'MUIIIII': 'DDDH1',
'MIUIIII': 'DDDH2',
'MIIUIII': 'DDDH3',
'MIIIUII': 'DDDH4',
'MIIIIUI': 'DDDH5',
'MIIIIIU': 'DDDH6',
'MUIUI': 'DDH1D'
}
A sebességnövekedés lenyűgöző: azzal, hogy az első 10000 szó 145294 leszármazottjának levezetése során szótárban kerestük a már előállított szavakat, a program majdnem három nagyságrenddel rövidebb idő alatt fejeződik be.
