Chapter 15: Keresés

A keresés egy fontos és nagyon gyakori művelet, amit a számítógépek bármikor végre tudnak hajtani. Keresés indul meg, amikor valaki leüti a ctrl-f billentyűt, ami a "find" parancs gyorsbillentyűje. Vagy amikor egy felhasználó használja a type-to-t, hogy gyorsan kiválaszson egy elemet, vagy amikor a webszerver információt vesz át a vásárlótól, hogy megjelenítsen neki egy számára elkészített weboldalt, a várárlásához.

Sokféle módja van annak, hogy adatot keressünk. A google erre az egy dologra alapította a multimilliomos társaságát, ez tény. Ez a fejezet bemutatja, hogyan használj fel két egyszerű módot arra, hogy keress. Ezek a lineáris keresés és a bináris keresés.

15.1 Beolvasás fájlból

Mielőtt arról beszélnénk, hogyan keressünk, szükségünk lesz adatbeolvasásra fájlból. Az adat bekérése fájlból sokkal több mókával járó módszer, mintha be kéne gépelnünk kézzel.

Mondjuk kell alkotnunk egy programot, ami lehetővé teszi számunkra, hogy gyorsan megtaláljunk egy szupergonoszt. Kezdésnek, a programunknak szüksége lesz egy adatbázisra a szupergonoszokról. Ahhoz, hogy letöltsük ezt az adathalmazt, töltsd le és mentsd el az alábbi fájlt:
http://ProgramArcadeGames.com/chapters/16_searching/super_villains.txt
Ez egy véletlenszerű nevekkel feltöltött fájl, amiket a nine.frenchboy.net oldal generált. A legutóbbi látogatásom óta sincs nekik szuper-gonosz generátorjuk.

Mentsd el ezt a fájlt és emlékezz a könyvtárra, ahová mentetted.

Ugyanabban a könyvtárban, ahová a super_villains.txt fájlt mentetted, hozz létre, mentsd el, és futtasd az alábbi python programot:

file = open("super_villains.txt")

for line in file:
    print(line)

Mindössze egy új parancskód van ebben a fájlban, és ez a megnyitás: open. Mivel ez egy beépített függvény, mint amilyen a print, ezért nem szükséges importálni semmit. A teljes leírása és dokumentációja megtalálható ennek a függvénynek ezen a helyen: Python documentation, de jelen pillanatban ez technikai részlet, mivel nem lesz még rá szükség.

A fenti programnak két problémája van, de már be lehet vele mutatni, hogyan olvassunk egy fájlt. Az első sor megnyit egy fájlt és készenlétbe helyezi azt az olvasáshoz. A fájl neve az idézőjelek közt van. Az új file változó egy objektum, amely az olvasott fájlra mutat. A harmadik sorban az történik, hogy egy for ciklus fut le, hogy sorról-sorra beolvassa a fájlt. Gondolj úgy a file változóra, mint egy sorokból álló listára, és a line nevű új változó fog egyenként mutatni ezekre a sorokra, ahogy a program végigfut a cikluson.

Próbáld meg futtatni a programot. Az egyik probléma, hogy a szöveg dupla-sorközzel lesz kiírva. Ennek az az oka, hogy minden sor, amit áthúzunk a line változóba tartalmaz egy carriage return-t (kocsi visszát) a szöveg részeként. Emlékszel, hogy a kocsi vissza és a sorkitöltés már meg lett említve az Első Fejezetben? A print parancs is hozzáad egy kocsi visszát, ezért lesz dupla sorközös a megjelenített szöveg.

A másik probléma az, hogy a fájl meg van nyitva, nem lesz lezárva. Ez nem olyan nyilvánvaló probléma, mint a dupla-sorköz, de ugyanolyan fontos. A Windowsos operációs rendszer csak meghatározott számú fájlt képes egyszerre nyitva tartani. Általában egy program egy fájl nyit meg egyszerre. Ha a fájlt nyitva hagyjuk, akkor azzal más programokat korlátozunk és a rendszer forrásait csökkentjük. Fontos, hogy bezárjuk a fájlt, hogy a Windows tudja, a program már nem dolgozik a továbbiakban azon a fájlon. Ezesetben nem nagyon fontos ezt megtenni, mivel a Windows magától is bezárja, amikor észleli, hogy már nem dolgozik a fájllal senki sem. De ez akkor is egy rossz programozói szokás, szóval frissítsük a kódunkat:

file = open("super_villains.txt")

for line in file:
    line = line.strip()
    print(line)

file.close()	

A fenti kilistázás már jobb. Két új dolog is van benne. A negyedik sorban van egy hívás, a strip eljárást hívja meg, ami minden String osztályba be van építve. Ez a függvény visszaad egy új stringet, ahol már nincsenek felesleges sorok, mint az eredeti stringben. Nem átalakítja az eljárás a stringet, hanem egy újat hoz létre. Ez a kódsor nem fog működni:

line.strip()

Ha a programozó azt szeretné, hogy az eredeti változó mutasson az új változóra, akkor értéket kell adnia a megadott stringnek, ahogy az a negyedik sorban van.

A második kiegészítés a hetes sorban van. Ez zárja le a fájlt, így az operációs rendszernek nem kell körbe futnia, és letakarítani minden nyitott fájlt miután a program véget ért.

15.2 Beolvasás tömbbe

Hasznos, ha beolvassuk a fájl tartalmát egy tömbbe, így a program hozzáférhet később is. Ezt könnyedén megtehetjük a Pythonban, az alábbi kóddal:

# Egy fájl beolvasása lemezről és tömbbe helyezése
file = open("super_villains.txt")

name_list = []
for line in file:
    line = line.strip()
    name_list.append(line)

file.close()	

Ez kombinálja azt, ahogyan beolvassuk a fájlt, azzal, hogyan készítsünk egy üres tömböt, és töltsük azt fel új adattal, ahogy azt már a hetedik fejezetben is láttuk. Ahhoz, hogy megbizonyosodhassunk arról, hogy a fájl be lett olvasva a tömbbe, a programozó kiírathatja a tömb hosszát:

print( "Ott ahol",len(name_list),"név van a fájlban.")

Vagy a programozó kiírathatja a teljes tartalmát a tömbnek:

for name in name_list:
    print(name)

Menjünk tovább és bizonyosodjunk meg arról, hogy beolvastuk a fájlt, mielőtt másik keresést hajtanánk végre rajta.

15.3 Lineáris keresés

Ha egy program tömbben tárolja az adatokat, akkor hogyan lehet megtalálni benne a keresett elemeket? Ezt megtehetjük kétféleképpen. Az első eljárás a lineáris keresés. Ez az első elemmel kezdi, és összehasonlítja azokat amíg meg nem találja a keresett elemet (vagy végére ér az elemeknek).

15.3.1 Lineáris keresés algoritmus

# Lineáris keresés
i = 0 
while i < len(name_list) and name_list[i] != "Morgiana the Shrew":
    i += 1
	
if i < len(name_list):
    print( "A név ezen a pozíción van:", i)
else:
    print( "A keresett név nem volt a listában." )

A lineáris keresés még egyszerűbb. A második sor egy növekvő változót hoz be, ami nyomonköveti, hogy hol járunk a listában, és a programnak mit kell ellenőrízni a következőben. Az első elem, amit megnéz az a nulla, így i felveszi a nulla értékét.

A következő sor már egy kicsit összetettebb. A számítógépnek szüksége van arra, hogy ismétlődjön, amíg egy vagy két dolog nem történik. Ez megtalálja az elemet, vagy kifogy az elemekből. Az első összehasonlítás úgy néz ki, hogy a jelenlegi elem, amit ellenőrzünk, az kisebb legyen mint a lista hossza. Ha így van, akkor ismételjük meg a ciklust. A másik feltételünk úgy néz ki, hogy a jelenlegi elemünk egyenlőségét vizsgálja a keresett elemével.

Ez az ellenőrzés nézi azt is, hogyha a program kifogyik az elemekből, máskülönben a program nem létező elemeket vizsgálna, és hibát jelezne.

A negyedik sor egyszerűen a következő elemre ugrik, ha a kereső feltétel teljesül a harmadik sorban, akkor tovább keres.

A ciklus végére a program ellenőrzi, hogy elértük e a lista végét a hatodik sorban. Emlékezz, hogy egy n elemű lista az nulla és n-1 közé esik. Továbbá ha i egyenlő a lista hosszával, akkor a végére értünk. Ha kevesebb, akkor megtaláltuk az elemet.

15.4 Lineáris keresés változatai

A lineáris keresésre való változatokat használhatjuk arra, hogy gyakran használt algoritmusokat hozzunk létre. Például, mondjuk van egy listányi idegenünk. Szeretnénk megnézni, hogy van e köztük zöld színű. Vagy mind zöld? Melyik a zöld?

Kezdésnek definiálni kell az idegeneket:

class Alien:
	color = ""
	name = ""
	weight = 0
	height = 0

Akkor most kell létrehozni egy függvényt, hogy leellenőrízzük, hogy ennek van e olyan értéke amit keresünk. Ez esetben, zöld? Most vegyük azt, hogy a szín az egy szöveges változó, és nekünk át kell alakítanunk, mert lehet hogy nagybetűs.

def hasProperty(my_alien):
    if my_alien.color.upper() == "GREEN":
        return True
    else:
        return False

15.4.1 Legalább egy elemnek van ilyen tulajdonsága?

Legalább egy idegen zöld? Lellenőrízhetjük. Íme, háttérben rejtező alap algoritmus:

def checkIfOneItemHasProperty1(list):
    i = 0
    while i < len(list) and not hasProperty(item):
        i += 1

    if i < len(list):
        # megtaláljuk az elemet ami bír ezzel a jellemzővel
        return True
    else:
        # nincs ilyen elem
        return False

Ezt szintén megtehetjük egy for ciklussal. Ez esetben a ciklus ki fog lépni, egy return-t használva, amikor megtalálja az elemet. A kód rövidebb, de nem minden programozó szeretné ezt. Némely programozó úgy érezné, hogy a ciklust nem kéne befejezni ilyen korán egy return vagy break paranccsal. Az egész egyéni véleményen múlik, vagy azon a személyen, aki a személyes véleményt hozza, aki fizeti a számlát.

def checkIfOneItemHasProperty2(list):
    for item in list:
        if hasProperty(item):
            return True
    return False

15.4.2 Minden elemnek van ilyen tulajdonsága?

Minden idegen zöld? Ez a kód nagyon hasonló az előzőhöz. Vedd észre a különbségeket és figyeld meg, hogy mi lehet az oka ennek.

def checkIfAllItemsHaveProperty(list):
    for item in list:
        if not hasProperty(item):
            return False
        return True

15.4.3 Készítsünk egy listát, ami minden elemet összehasonlít egy tulajdonság alapján

Mi van akkor, ha szeretnéd megkapni az összes olyan idegent, aki zöld? Ez a kombinációja lesz az előző kódnak, és a kódnak, amit a hetedik fejezetben írtunk le, és az elemeket hozzácsatolta a listához.

def getMatchingItems(list):
    matchingList = []
    for item in list:
        if hasProperty(item):
            matchingList.append(item)
    return matchingList

Ezeket a gyakori algoritmusokat használhatjuk egy nagyobb probléma megoldásakor, mint amilyen megtalálni az összes nem érvényes vásárlói címet egy listában

15.5 Bináris keresés

Gyorsabb módja a keresésnek, ha bináris keresést hajtunk végre. A bináris keresés során hasonló dolgot művelünk, mint a klasszikus játékban: Gondoltam egy számra egy és száz között. Ahhoz, hogy könnyebben megérthessük az eljárást, módosítsuk a játékot, Gondoltam egy számra egy és százhuszonnyolc köztre, A szám intervalluma így egy és százhuszonnyolc közé esik majd.

Ha valaki a lineáris keresést használná ahhoz, hogy kitalálja a titkos számot, akkor a játék hosszú és unalmas lenne.

Gondoltam egy számra egy és százhuszonnyolc között:  1
Túl kevés. 
Gondoltam egy számra egy és százhuszonnyolc között:  2
Túl kevés. 
Gondoltam egy számra egy és százhuszonnyolc között:  3
Túl kevés. 
....
Gondoltam egy számra egy és százhuszonnyolc között:  93
Túl kevés. 
Gondoltam egy számra egy és százhuszonnyolc között:  94
Helyes! 

A legtöbb ember bináris keresést használ arra, hogy egy számot megtaláljon. Íme egy példa arra, amikor bináris kereséssel játszunk:

Gondoltam egy számra egy és százhuszonnyolc között:  64
Túl kevés. 
Gondoltam egy számra egy és százhuszonnyolc között:  96
Túl sok.
Gondoltam egy számra egy és százhuszonnyolc között:  80
Túl kevés.
Gondoltam egy számra egy és százhuszonnyolc között:  88
Túl kevés.
Gondoltam egy számra egy és százhuszonnyolc között:  92
Túl kevés.
Gondoltam egy számra egy és százhuszonnyolc között: 94
Helyes!

Mindig, amikor egy körben már találgatott a játékos, akkor a játékos a felét veszi annak, ami túl kevés, vagy túl sok volt.

Egy bináris keresés esetén fontos, hogy nyomon kövessük a felső és alsó határt a listában, mivel a válasz abban lesz. A számítógép vagy a számkitaláló játékos felveszi a középpontját ezeknek az elemeknek. Áttekintve a példát:

Az alsó határ 1, a felső határ 128, a számtani közép nem más lesz, mint $\dfrac{1+128}{2} = 64.5$.

Találd ki egy számot 1 és 128 közt: 64
Túl kevés. 

Az alsó határ most 65, a felső határ 128, a számtani közép $\dfrac{65+128}{2} = 96.5$.

Találd ki a számot 1 és 128 közt:  96
Túl sok.

Az alsó határ 65, felső határ 95, a számtani közép $\dfrac{65+95}{2} = 80$.

Találd ki a számot 1 és 128 közt:  80
Túl kevés.

Az alsó határ 81, felső határ 95, a számtani közép $\dfrac{81+95}{2} = 88$.

Találd ki a számot 1 és 128 közt:  88
Túl kevés. 

Az alsó határ 89, felső határ 95, a számtani közép $\dfrac{89+95}{2} = 92$.

Találd ki a számot 1 és 128 közt:  92
Too low.

Az alsó határ 93, felső határ 95, a számtani közép $\dfrac{93+95}{2} = 94$.

Találd ki a számot 1 és 128 közt:  94
Talált!

A bináris keresés láthatóan kevesebb találgatást igényel. A legrosszabb esetben is 1 és 128 közt megtalálja a számot 7 találatból. Még egy kereséssel felemelhetjük a felső határt 256-ra. 9 találgatással már 1 és 512 közé mehetünk. 32 próbálkozással bárki kitalálhatja a számot 1 és 4.2 millió közt.

Ha képet akarunk kapni arról, hogy milyen nagyságban találgathatunk ennek segítségével, akkor ez a formula segít $n=x^{g}$ , ahol $n$ a nagysága a listának, és a $g$ a találgatások száma. Például:
$2^7=128$ (7 találgatás képes megtalálni a számot 128 különböző szám közül)
$2^8=256$
$2^9=512$
$2^{32}=4,294,967,296$

Ha megvan a probléma mérete, akkor már el tudjuk képzelni, hogy mennyi találgatásra van szükségünk, használjuk a log függvényt. Különösen, a log base 2-t. Ha nem határozod meg az alapot, akkor a legtöbben arra gondolnak, hogy a természetes logaritmusnak az alapja $e \approx 2.71828$, ami nem az, amit mi akartunk. Például, ha logaritmust használunk a második alapon, akor ezt találjuk:
$log_2 128 = 7$
$log_2 65,536 = 16$

Na elég a matekból! Hol van a kód? A kódja a bináris keresésnek sokkal összetettebb, mint egy lineáris keresésnek:

#bináris keresés
key = "Morgiana the Shrew";
lower_bound = 0
upper_bound = len(name_list)-1
found = False
while lower_bound <= upper_bound and not found:
    middle_pos = (lower_bound+upper_bound) // 2
    if name_list[middle_pos] < key:
	    lower_bound = middle_pos + 1 
    elif name_list[middle_pos] > key:
	    upper_bound = middle_pos - 1
    else:
        found = True

if found:
    print("A név ezen a pozíción van: ", middle_pos)
else:
    print("A név nincs a listában.")

Mivel a lista a nulladik elemmel kezdődik, ezért a harmadik sorban az alsó határérték nulla lesz. A negyedik sor a felső határt az összes elem mínusz egyre teszi. Így egy 100 elemből álló listánál az alsó határ 0 a felső határ 99 lesz.

A logikai változó az ötödik sorban arra lesz használva, hogy a while ciklus tudja azt, hogy az elemet megtaláltuk-e.

A hatodik sor azt teszteli, hogy az elemet megtaláltuk-e, vagy kifogytunk az elemekből. Ha kifogytunk az elemekből, akkor az alsó határértéktől a felsőig kerestünk.

A hetedik sor megkeresi a számtani közepet. Nem lehetséges megadni a számtani közepet, úgy, hogy 64,5, mégha matematikailag helyes is volna. J.K. Rowling elég okos volt ahhoz, hogy megalkossa a $9\frac{3}{4}$ platformot, de ez itt nem fog működni. Használjuk inkább az ötödik fejezetben megtanult műveletet. Ez hasonló a / művelethez, de a // művelet az osztás egész eredményét adja vissza. Például 11//2 ötöt fog válaszul adni, és nem 5,5-t.

A nyolcas sorban kezdődik az, hogy a program ellenőrzi azt, hogy a találgatás túl sok vagy túl kevés volt, vagy helyes. Ha a találgatás túl alacsony, akkor az alsó határértéket fogja megemelni. Ellenben, ha túl sok a mondott szám, akkor a felső határértéket fogja csökkenteni. Ha a válasz helyes, akkor a found felveszi az igaz/True értéket, és a keresés véget ért.

15.6 Áttekintés

15.6.1 Kvízkérdések

Click here for a multiple-choice quiz.

15.6.2 Feladatlap

Click here for the chapter worksheet.

15.6.3 Labor feladat

Click here for the chapter lab.

You are not logged in. Log in here and track your progress.