7.1 Meklēšanas pamati

Stundas uzdevums: Saprast atšķirību starp "meklēt visu pēc kārtas" un "gudro meklēšanu". Tu izveidosi savus pirmos meklēšanas algoritmus, lai atrastu svarīgus spēles elementus spēlētāja inventārā, un sapratīsi, kāpēc datu kārtošana ir kritiska ātrdarbībai.

Teorija: Meklēšanas algoritmi

# Lineārā meklēšana - O(n)
def linear(saraksts, mērķis):
    for i, x in enumerate(saraksts):
        if x == mērķis:
            return i
    return -1

# Binārā meklēšana - O(log n) - saraksts JĀBŪT sakārtotam
def binary(saraksts, mērķis):
    lo, hi = 0, len(saraksts) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if saraksts[mid] == mērķis: return mid
        elif saraksts[mid] < mērķis: lo = mid + 1
        else: hi = mid - 1
    return -1

Vides sagatavošana (Windows)

Pirms rakstām kodu, izveidosim pareizu struktūru mūsu jaunajai tēmai.

1. Atver PowerShell vai Command Prompt.
2. Izveido jaunu mapi 7. tēmai un ieej tajā, izpildot šīs komandas:

mkdir Tema7_Algoritmi
cd Tema7_Algoritmi
    

3. Izveido tukšu Python failu šodienas stundai un atver to kodu redaktorā (piemēram, VS Code):

ni mekle_skaitli.py
code .
    

Praktiskie uzdevumi

1. uzdevums: "Kur ir mans skaitlis?"

Sāksim ar lineāro meklēšanu. Tavs uzdevums ir izveidot funkciju, kas pārbauda spēlētāja inventāru.

1. Failā mekle_skaitli.py izveido sarakstu ar nejaušiem priekšmetu ID numuriem.
2. Izveido funkciju linear_search(saraksts, mekletais).
3. Izmanto for ciklu un enumerate(), lai ietu cauri sarakstam un atgrieztu indeksa numuru, kur priekšmets atrasts.
4. Ja priekšmets nav atrasts, atgriez -1.

def linear_search(inventars, meklejama_atslega):
    for indekss, prieksmets in enumerate(inventars):
        if prieksmets == meklejama_atslega:
            return indekss
    return -1

speletaja_inventars = [45, 12, 89, 3, 99, 21]
atraduma_vieta = linear_search(speletaja_inventars, 99)

print(f"Slepenā atslēga atrasta slotā: {atraduma_vieta}")

2. uzdevums: "Grāmatas metode" un Datu kārtošana

Lai izmantotu bināro meklēšanu, dati ir jāsakārto. Sagatavosim datus un simulēsim bināro meklēšanu.

1. Pievieno esošajam kodam jaunu sarakstu: nesakartoti_dati = [42, 15, 8, 99, 23, 4, 16, 81, 100, 5, 1, 33, 50, 60, 11].
2. Izmanto Python iebūvēto funkciju sorted(), lai izveidotu jaunu, sakārtotu sarakstu un to izdrukātu.
3. Izveido daudzrindu komentāru (""" ... """), kurā apraksti soļus, kā Tu, izmantojot binārās meklēšanas loģiku, atrastu skaitli 42 šajā sakārtotajā sarakstā.

nesakartoti_dati = [42, 15, 8, 99, 23, 4, 16, 81, 100, 5, 1, 33, 50, 60, 11]
sakartoti_dati = sorted(nesakartoti_dati)
print(f"Sakārtots inventārs: {sakartoti_dati}")

"""
Binārās meklēšanas simulācija skaitlim 42:
Saraksts: [1, 4, 5, 8, 11, 15, 16, 23, 33, 42, 50, 60, 81, 99, 100]
1. solis: Vidējais elements ir 23. 42 ir lielāks, atmetam kreiso pusi un 23.
2. solis: Jauns diapazons [33, 42, 50, 60, 81, 99, 100]. Vidējais ir 60. 42 ir mazāks, atmetam labo pusi.
3. solis: Jauns diapazons [33, 42, 50]. Vidējais ir 42. Atrasts! Pārbaudes prasīja 3 soļus.
"""

3. uzdevums: "Efektivitātes mērītājs"

Cik lēna patiesībā ir lineārā meklēšana? Pārbaudīsim to ar miljonu ierakstiem!

1. Faila sākumā importē bibliotēku: import time.
2. Izmanto range() un list(), lai izveidotu sarakstu lieli_dati ar 1 000 000 secīgiem skaitļiem.
3. Mēģini atrast pēdējo skaitli (999999), izmantojot savu iepriekš izveidoto linear_search funkciju.
4. Piefiksē sākuma un beigu laiku, lai aprēķinātu, cik sekundes aizņēma meklēšana.

import time

# Izveidojam milzīgu inventāru
lieli_dati = list(range(1000000))

# Mērām laiku
sakuma_laiks = time.time()
rezultats = linear_search(lieli_dati, 999999)
beigu_laiks = time.time()

pateretais_laiks = beigu_laiks - sakuma_laiks

print(f"Skaitlis atrasts indeksā: {rezultats}")
print(f"Lineārā meklēšana aizņēma: {pateretais_laiks:.5f} sekundes")