Към съдържанието
wannacode

Линейно търсене

Накратко: Линейното търсене проверява елементите един по един, докато намери търсения или стигне края: O(n) сравнения, и работи с неподреден списък.

Проблем

Скенерът на склада

В склада продуктите са записани в списък в реда, в който са дошли: брашно от понеделник, захар от вторник, олио, ориз. Работникът сканира кутия, а програмата трябва да намери продукта по баркод:

shelf = [
    Product("3800200101112", "Брашно"),
    Product("3800200104403", "Захар"),
    Product("3800200107251", "Олио"),
    Product("3800200102690", "Ориз"),
    Product("3800200109958", "Сол"),
    Product("3800200105837", "Кафе"),
]

Баркодовете не са подредени. Не можеш да отвориш списъка по средата и да кажеш „оризът е по-нататък“: следващият баркод може да е всякакъв. Как намираш продукта, и колко струва това, когато продуктите са 50 000, а сканиранията 2000 на ден?

Идеята

Поглеждаш всяка кутия

Щом редът не помага, остава едно: започваш от първата кутия и сравняваш баркода ѝ с търсения. Ако съвпада, готово: връщаш мястото. Ако не, минаваш на следващата. Ако кутиите свършат, продуктът го няма.

Това е линейно търсене: минаваш елементите един по един, докато намериш търсения или стигнеш края. Връща се мястото (индексът) или знак за „няма“: None.

Виж го

Указателят по рафта

def find(shelf, barcode):
    for i, product in enumerate(shelf):
        if product.barcode == barcode:
            return i
    return None
rice = find(shelf, "3800200102690")
print("3800200102690 ->", rice, shelf[rice].name)
print("3800200100000 ->", find(shelf, "3800200100000"))
Изход
3800200102690 -> 3 Ориз
3800200100000 -> None

def find(shelf, barcode):
    for i, product in enumerate(shelf):
        if product.barcode == barcode:
            return i
    return None




rice = find(shelf, "3800200102690")
missing = find(shelf, "3800200100000")
Стъпка по стъпка, с думи
  1. Скенерът чете баркода на ориза: 3800200102690. find тръгва от първата кутия.
  2. Сравнява баркода на всяка кутия с търсения: брашно, захар, олио. Не съвпада.
  3. Четвъртата кутия е оризът. return 3: намерен след 4 сравнения.
  4. Баркод, който складът го няма: 3800200100000. find тръгва пак от началото.
  5. Указателят минава всяка кутия и нито една не съвпада.
  6. Кутиите свършиха: return None след 6 сравнения. Липсващият продукт е най-лошият случай: n сравнения при n кутии.

Оризът е намерен след 4 сравнения. Липсващият баркод минава всички 6 кутии: само така може да се каже, че го няма.

В Python -1 е истински индекс: shelf[-1] е последният продукт. Ако find връщаше -1, код като shelf[find(shelf, code)].name щеше да даде кафето за баркод, който го няма, без никаква грешка. Затова „няма“ е None, а shelf[None] спира веднага с TypeError.

Пробвай

Попълни

Какво връща find, когато кутиите свършат?

def find(shelf, barcode):
    for i, product in enumerate(shelf):
        if product.barcode == barcode:
            return i
    return

Идеята

Колко сравнения

Броят сравнения зависи от това къде е продуктът:

  • най-добрият случай: първата кутия, 1 сравнение;
  • най-лошият случай: последната кутия или продукт, който го няма, n сравнения;
  • обикновеният случай: ако всяко място е еднакво вероятно, средно около n/2.

Най-лошият и обикновеният случай растат с n, затова линейното търсене е O(n). Програмата брои:

def comparisons(shelf, barcode):
    count = 0
    for product in shelf:
        count += 1
        if product.barcode == barcode:
            return count
    return count
print("Брашно:", comparisons(shelf, "3800200101112"))
print("Ориз:", comparisons(shelf, "3800200102690"))
print("Липсващ:", comparisons(shelf, "3800200100000"))
Изход
Брашно: 1
Ориз: 4
Липсващ: 6

Пусни двата крайни случая на голям склад. Броим по едно сравнение на кутия:

  • Баркодът липсва (най-лош случай) O(n)
  • Първият продукт (най-добър случай) O(1)
Алгоритъмn = 10n = 1000n = 100 000
Баркодът липсва (най-лош случай)101000100 000
Първият продукт (най-добър случай)111
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

Първата кутия струва 1 сравнение при всяко n: O(1). Липсващият продукт струва n: при 100 000 продукта са 100 000 сравнения. Паметта е O(1): един индекс.

Пробвай

Предвиди изхода

Солта е петата кутия на рафта. Колко сравнения прави търсенето?

def comparisons(shelf, barcode):
    count = 0
    for product in shelf:
        count += 1
        if product.barcode == barcode:
            return count
    return count




print("Сол:", comparisons(shelf, "3800200109958"))
Отговор

Виж го

Вградените търсят по същия начин

Всеки език има готово търсене в списък. Отвътре то е същият цикъл:

barcodes = [
    "3800200101112", "3800200104403", "3800200107251",
    "3800200102690", "3800200109958", "3800200105837",
]
print(barcodes.index("3800200102690"))
print("3800200100000" in barcodes)
try:
    barcodes.index("3800200100000")
except ValueError as e:
    print("ValueError:", e)
Изход
3
False
ValueError: '3800200100000' is not in list
index връща мястото, а ако го няма, хвърля ValueError. in дава само True или False. И двете минават от първия елемент нататък: O(n). Затова if code in barcodes: barcodes.index(code) търси два пъти.

Едно извикване изглежда като една операция, но вътре са до n сравнения. Вградената функция е по-бърза от твоя цикъл с някакъв постоянен множител, не с порядък.

Пробвай

Намери грешката

Колега е написал търсенето така. Брашното се намира, а оризът „го няма“:

def find(shelf, barcode):
    for i, product in enumerate(shelf):
        if product.barcode == barcode:
            return i
        else:
            return None
    return None
print(find(shelf, "3800200101112"))
print(find(shelf, "3800200102690"))
Изход
0
None

На кой ред е грешката?

Избери реда с грешката.

Идеята

Кога е точно на място и кога не

Линейното търсене е точният избор, когато:

  • продуктите са малко: десет или сто сравнения не се усещат;
  • търсиш веднъж: всеки по-бърз начин първо иска поне n стъпки за подготовка;
  • данните са неподредени или се менят постоянно, и няма какво да поддържаш.

Не е, когато търсенията са много. 2000 сканирания на ден в 50 000 продукта са до 100 000 000 сравнения. Тогава подготвяш данните веднъж:

  • таблица баркод → продукт (dict): 50 000 стъпки веднъж, а после всяко търсене е O(1) средно;
  • подреден списък и двоично търсене: подреждането е O(n log n) веднъж, а всяко търсене после е O(log n), около 16 сравнения при 50 000.
by_barcode = {product.barcode: product for product in shelf}
print(by_barcode["3800200102690"].name)
print(by_barcode.get("3800200100000"))
Изход
Ориз
None

Таблицата струва памет: още n места. Това е същата размяна време срещу памет като set-а в урока „Сложност по памет“.

Упражнение

Всички кутии на един продукт

Реши задачата в редактора си.

Ревизия. Един продукт може да е дошъл с няколко доставки и да е на няколко места в списъка. Напиши find_all(shelf, barcode), която връща всички места на баркода, а не само първото. Рафтът е като горе, плюс още ориз и още сол накрая (места 6 и 7).

Изход
Ориз: 3, 6
Сол: 4, 7

Още задачи

  • Последното място. Върни последното място на баркода. Откъде е по-добре да започнеш?
  • По име, без значение главни и малки. Намери продукта по име („ориз“ и „Ориз“ са същото). Колко сравнения има в най-лошия случай?
  • Продукти под минимума. Изреди всички продукти с наличност под 10 бройки. Може ли да спреш преди края?

Тест

Провери се

1. Списъкът има 10 000 неподредени продукта. Колко сравнения прави линейното търсене за продукт, който го няма?
2. Продуктът е там, а всяко място е еднакво вероятно. Колко сравнения са нужни средно при n продукта?
3. Защо find не връща 0, когато продуктът го няма?
4. Скенерът прави 2000 търсения на ден в 50 000 продукта. Кое е по-добре?
5. Кога линейното търсене е точният избор?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·