Előfordulhat, hogy egy karakterláncban közvetlenül egymás követően több szóköz szerepel, amely a további feldolgozás szempontjából nem kívánatos. Ezért a feladat az, hogy úgy alakítsuk át a karaktersorozatot, hogy minden egynél több, egymás utáni szóköz helyett csak egyetlen egy szerepeljen. Ehhez írjunk függvényt.
Mint általában, ezt a feladatot is több módon oldhatjuk meg. Ezt láthatjuk alább, ahol az egyes függvények eltérő logikát követnek és ennek megfelelő nyelvi eszközöket használnak.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
from itertools import groupby def collapse_spaces1(text: str) -> str: # A str.replace() metódust alkalmazó megoldás ciklussal. while ' ' * 2 in text: text = text.replace(' ' * 2, ' ') return text def collapse_spaces2(text: str) -> str: # A str.replace() metódust alkalmazó rekurzív megoldás. # A rekurzió mélysége nem a szöveg hosszától, hanem a leghosszabb egymást követő szóközsorozat hosszától függ. # Ezért a Python rekurziós korlátjába (alapértelmezés szerint 1000 hívás) gyakorlatilag nem lehet belefutni. if ' ' * 2 not in text: return text return collapse_spaces2(text.replace(' ' * 2, ' ')) def collapse_spaces3(text: str) -> str: # Karakterenkénti feldolgozást alkalmazó megoldás. result = [] prev_space = False for c in text: if c == ' ': if not prev_space: result.append(c) prev_space = True else: result.append(c) prev_space = False return "".join(result) def collapse_spaces4(text: str) -> str: # Az itertools.groupby() függvényt használó megoldás. return "".join(' ' if c == ' ' else ''.join(group) for c, group in groupby(text)) |
Az első függvényben megvizsgáljuk, hogy a karakterlánc tartalmaz-e egymást követő két szóközt. Ha nem, akkor nincs teendő, a karaktersorozat az igényünknek megfelelő. Ha igen, akkor ezek mindegyikét helyettesítjük egyetlen szóközzel a replace() metódust meghívva, és aztán újra elvégezzük az első lépés szerinti ellenőrzést, hiszen lehet, hogy kettőnél több egymást követő szóköz volt a kiinduló karaktersorozatban.
A második függvénynek ugyanez a logikája, de ciklus helyett rekurziót alkalmazunk. Rekurziónál azonban mindig át kell gondolni, hogy maximum hány rekurzív hívásra lehet számítani, mert egyébként beleütközhetünk a Python rekurziós korlátjába (alapértelmezésben 1000 hívás). Ez az esetünkben nem áll fenn, mert a rekurzió mélysége nem a szöveg hosszától, hanem a leghosszabb egymást követő szóközsorozat hosszától függ, amely valós szövegekben jellemzően messze elmarad attól, hogy átlépjük a rekurziós korlátot.
E két függvénynek viszonylag egyszerű a logikája és rövid a kódja, de hátránya, hogy akár többször is végig kell menni a vizsgálandó karakterláncon. Ezt küszöböli ki a harmadik függvény, ahol csak egyszer járjuk be a bemeneti karakterláncot, és ha több egymást követő szóközt találunk, ezekből csak egyet hagyunk meg a kimeneti karaktersorozatban. E megoldás kódja azonban az előzőkéhez képest hosszabb, így a megírása – és a kód olvasójának a működés megértése – több időt igényel. Viszont az egyszeri bejárás miatt azt várjuk, hogy futási időben gyorsabb lesz.
A negyedik függvényben az itertools modul groupby() függvényét használjuk, amivel egyetlen sorban megkapjuk a kívánt eredményt. Ennek olvashatósága nem annyira jó, mint az előzőké, mert a működése kevésbé magától értetődő. Ugyanakkor, mivel az itertools modul által kínált eszközök a hivatalos dokumentáció szerint gyorsak és memóriahatékonyak (mivel a CPython implementációjában C nyelven valósították meg őket) azt várjuk, hogy e megoldás futási ideje kisebb lesz, mint az első két megoldásé.
Ami a futási időket illeti, a tesztek nem a várakozásunknak megfelelőt mutatnak, ahogy ez alább látható.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
from timeit import timeit def test_time_performances(text, *functions): for func in functions: print('{} -> {:.5f}'.format(func.__name__, timeit(lambda: func(text), number=1000))) print() tested_functions = [collapse_spaces1, collapse_spaces2, collapse_spaces3, collapse_spaces4] txt = ' A bb c d\n efg \tf g h i ' test_time_performances(txt, *tested_functions) # Eredmény: # collapse_spaces1 -> 0.00042 # collapse_spaces2 -> 0.00047 # collapse_spaces3 -> 0.00153 # collapse_spaces4 -> 0.00503 txt = ('ab cd ef gh ' * 5000) test_time_performances(txt, *tested_functions) # Eredmény: # collapse_spaces1 -> 0.55371 # collapse_spaces2 -> 0.55463 # collapse_spaces3 -> 3.18906 # collapse_spaces4 -> 11.7909 txt = 'a' + ' ' * 1000 + 'b' test_time_performances(txt, *tested_functions) # Eredmény: # collapse_spaces1 -> 0.01070 # collapse_spaces2 -> 0.01074 # collapse_spaces3 -> 0.02245 # collapse_spaces4 -> 0.00776 |
Bár a karakterenkénti feldolgozást alkalmazó algoritmus és a groupby() függvényt használó változat lineáris futásidővel rendelkeznek (O(n) ), a str.replace() metódusra épülő megoldásoknak többször is végig kell haladniuk a karakterláncon, ezért elméletileg kedvezőtlenebb az időkomplexitásuk. A CPython implementációjában azonban a str.replace() annyira optimalizált, hogy a vizsgált tesztesetek többségében ezek bizonyultak a leggyorsabbnak. A groupby() csak olyan speciális esetekben előzte meg őket, amikor a szöveg egy vagy több nagyon hosszú, összefüggő szóközsorozatot tartalmazott. Mivel ilyen bemenet a gyakorlatban ritkán fordul elő, általános célra a str.replace() metóduson alapuló megoldások tekinthetők a legjobb választásnak.
Felvetődhet még kérdésként, hogy miért nem használjuk a feladat megoldására a split() metódust argumentum nélkül meghívva: ' '.join(text.split()). Hiszen ilyenkor a metódus számára az egymást közvetlenül követő, szóköznek számító határolójelek egyetlen határolójelnek számítanak.
Ennek oka egyrészt, hogy ez a megoldás nem mindig ad kielégítő eredményt. Ugyanis a split() számára nem csak az U+0020 kódpontú szóköz számít határolójelnek, hanem többek között például az ‘\n’, ‘\t’, ‘\r’ és ‘\f’ karakterek is. Másrészt, a szöveg kezdetén vagy végén levő szóközök a split() hívása után eltűnnek.
A karakterláncokra meghívható metódusok részleteiről (beleértve a replace() és split() metódusokat) a Python tudásépítés lépésről lépésre című ekönyv „Beépített típusok nyilvános metódusai” fejezetében lehet olvasni. Rekurzióval a „Különleges függvénydefiníciók” fejezet „Amikor a kígyó a farkába harap – függvényrekurzió” alfejezete foglalkozik. Az itertools modul eszköztárának használatáról pedig a „Készétel fogyasztás – a szabványos könyvtár moduljainak használata” fejezet „Speciális iterátorok” alfejezete ad áttekintést alkalmazási példákkal. Azt, hogy milyen módokon lehet futási időt mérni a „A programvégrehajtás felfüggesztése és a futási idő mérése” című alfejezetből tudhatjuk meg.