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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

var shelf = new List<Product>
{
    new Product("3800200101112", "Брашно"),
    new Product("3800200104403", "Захар"),
    new Product("3800200107251", "Олио"),
    new Product("3800200102690", "Ориз"),
    new Product("3800200109958", "Сол"),
    new Product("3800200105837", "Кафе"),
};

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

Идеята

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

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

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

Виж го

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

static int Find(List<Product> shelf, string barcode)
{
    for (int i = 0; i < shelf.Count; i++)
    {
        if (shelf[i].Barcode == barcode)
        {
            return i;
        }
    }
    return -1;
}

int rice = Find(shelf, "3800200102690");
Console.WriteLine("3800200102690 -> " + rice + " " + shelf[rice].Name);
Console.WriteLine("3800200100000 -> " + Find(shelf, "3800200100000"));

Изход

3800200102690 -> 3 Ориз
3800200100000 -> -1

static int Find(List<Product> shelf, string barcode)
{
    for (int i = 0; i < shelf.Count; i++)
    {
        if (shelf[i].Barcode == barcode)
        {
            return i;
        }
    }
    return -1;
}

int rice = Find(shelf, "3800200102690");
int missing = Find(shelf, "3800200100000");

Стъпка по стъпка, с думи

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

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

Пробвай

Попълни

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

static int Find(List<Product> shelf, string barcode)
{
    for (int i = 0; i < shelf.Count; i++)
    {
        if (shelf[i].Barcode == barcode)
        {
            return i;
        }
    }
    return ;
}

Провери

Идеята

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

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

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

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

static int Comparisons(List<Product> shelf, string barcode)
{
    int count = 0;
    foreach (Product product in shelf)
    {
        count++;
        if (product.Barcode == barcode)
        {
            return count;
        }
    }
    return count;
}

Console.WriteLine("Брашно: " + Comparisons(shelf, "3800200101112"));
Console.WriteLine("Ориз: " + Comparisons(shelf, "3800200102690"));
Console.WriteLine("Липсващ: " + Comparisons(shelf, "3800200100000"));

Изход

Брашно: 1
Ориз: 4
Липсващ: 6

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

• Баркодът липсва (най-лош случай) O(n)
• Първият продукт (най-добър случай) O(1)

Алгоритъм	n = 10	n = 1000	n = 100 000
Баркодът липсва (най-лош случай)	10	1000	100 000
Първият продукт (най-добър случай)	1	1	1

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

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

Пробвай

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

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

static int Comparisons(List<Product> shelf, string barcode)
{
    int count = 0;
    foreach (Product product in shelf)
    {
        count++;
        if (product.Barcode == barcode)
        {
            return count;
        }
    }
    return count;
}

Console.WriteLine("Сол: " + Comparisons(shelf, "3800200109958"));

Отговор

Сол: 4

Сол: 6

Сол: 5

Провери

Виж го

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

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

var barcodes = new List<string>
{
    "3800200101112", "3800200104403", "3800200107251",
    "3800200102690", "3800200109958", "3800200105837",
};
Console.WriteLine(barcodes.IndexOf("3800200102690"));
Console.WriteLine(barcodes.IndexOf("3800200100000"));
Console.WriteLine(barcodes.Contains("3800200102690"));
Console.WriteLine(shelf.FindIndex(p => p.Barcode == "3800200102690"));

Изход

3
-1
True
3

IndexOf връща мястото или -1, Contains само True или False, а FindIndex търси по правило, дадено с ламбда. И трите минават от първия елемент нататък: O(n).

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

Пробвай

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

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

static int Find(List<Product> shelf, string barcode)
{
    for (int i = 0; i < shelf.Count; i++)
    {
        if (shelf[i].Barcode == barcode)
        {
            return i;
        }
        else
        {
            return -1;
        }
    }
    return -1;
}

Console.WriteLine(Find(shelf, "3800200101112"));
Console.WriteLine(Find(shelf, "3800200102690"));

Изход

0
-1

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

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

1static int Find(List<Product> shelf, string barcode)2{3 for (int i = 0; i < shelf.Count; i++)4 {5 if (shelf[i].Barcode == barcode)6 {7 return i;8 }9 else10 {11 return -1;12 }13 }14 return -1;15}

Провери

Идеята

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

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

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

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

• таблица баркод → продукт (Dictionary): 50 000 стъпки веднъж, а после всяко търсене е O(1) средно;
• подреден списък и двоично търсене: подреждането е O(n log n) веднъж, а всяко търсене после е O(log n), около 16 сравнения при 50 000.

var byBarcode = new Dictionary<string, Product>();
foreach (Product product in shelf)
{
    byBarcode[product.Barcode] = product;
}
Console.WriteLine(byBarcode["3800200102690"].Name);
Console.WriteLine(byBarcode.ContainsKey("3800200100000"));

Изход

Ориз
False

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

Упражнение

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

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

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

Изход

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

Още задачи

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

Тест

Провери се

1. Списъкът има 10 000 неподредени продукта. Колко сравнения прави линейното търсене за продукт, който го няма?

1Около 1410 000

2. Продуктът е там, а всяко място е еднакво вероятно. Колко сравнения са нужни средно при n продукта?

Около log nВинаги nОколо n/2

3. Защо find не връща 0, когато продуктът го няма?

Защото 0 е истинско място: първата кутияМоже да връща 0, все едно еЗащото 0 е грешка

4. Скенерът прави 2000 търсения на ден в 50 000 продукта. Кое е по-добре?

Линейно търсене всеки пътНов списък за всяко търсенеТаблица баркод → продукт, направена веднъж

5. Кога линейното търсене е точният избор?

Винаги, когато данните са многоКогато търсиш веднъж в малък или неподреден списъкСамо когато списъкът е подреден

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Времева сложност: броене на стъпки · Big-O: как расте работата · Най-добър, среден и най-лош случай · Сложност по памет
• Продължава в: Двоично търсене · Двоично търсене по отговора · Trie · Префиксни суми
• Задачи по темата: Търсене