ЗНАНИЯ

Адитья Бхаргава - Грокаем алгоритимы

Author

Привет.
Я давно не писал тебе о какой-нибудь книге, которую прочитал. Связано это с тем, что литература последних четырех месяцев - строго техническая, и, ясен пень, читать про то, какой Троелсон молодец и как он легко и понятно объясняет идею абстрактных классов, не  хочется и не нужно.
Собственно, "Грокаем алгоритмы" - книга про алгоритмы. Отличие от предыдущих книг этого года, пожалуй, в том, что она - интересная и живая.

Адитья Бхаргава - Грокаем алгоритимы

Но давай, лучше, поиграем. 
Так. Загадай число от 1 до 1000. Теперь прикинь, сколько, максимально, мне потребуется подходов, чтобы отгадать число? 1000. Справедливо. Типа:
- Это 1?
- не
- 2?
- не
- 3?
- все еще нет
- о, знаю! это 4?
- скучная игра, честно говоря...

Такой перебор понятен. И сегодняшнему компьютеру не долго перебрать 1000 чисел. А если их много? Ну прям много. Прям по меркам компьютера много. 
Спрошу еще раз: сколько мне нужно подходов, чтобы определить число? В общем, ответ 10 (почему 10, а не 9 или 11 - в конце рида).
Ну ок. 10. А как работает? Давай, я предположу, что загаданное тобой число - 595. Не думаю, что я угадал (шансов 1 к 1000, ну), но, как только поймешь, как это все работает - попробуй со своим числом.

Time for magic.
Итак, я называю тебе число, а ты говоришь: твое число больше/меньше/равно. Давай:
я: это 500? [1]
ты: больше
я: 750? [2]
ты: меньше
я: тогда давай 625  [3]
ты: все еще меньше
я: 563? [4]
ты: больше
я: ага. между 625 и 563. Ну норм. это 591? [5]
ты: нет, но уже близко
я: так больше или меньше?
ты: больше
я: 608? [6]
ты: меньше
я: 599? [7]
ты: все еще меньше
я: между 591 и 599. Разница в 8 шагов. Возьму 595 [8]
ты: равно

Нудная часть.
Смотри, шагов всего 8. Даже меньше 10. Алгоритм, наверное, понятен. На всякие случай, задумка в том, чтобы брать значение из середины диапазона. Задуманное число окажется по одну сторону от этой середины (или это оно и окажется). Тогда диапазон можно сократить вдвое. Поэтому алгоритм и называется бинарным поиском. Важное условие: массив, в котором мы ищем должен быть сортирован.

Так, а почему 10?
Связано с бинарностью. Помнишь, информатика, 9й класс - степени двойки? 1, 2, 4, 8, 16... Всего в наш диапазон входила 1000 чисел. Ближайшее число больше 1000 и являющееся степенью двойки - 1024 (10^2).  

И зачем?
Ну, например, поиск в списке контактов (в соцсети или телефонной книге) происходит так. Есть список контактов (друзей), он отсортирован по алфавиту. И компьютер ищет. Берет элемент посередине и сравнивает с поисковым запросом. Если не совпало, сравнивает строки и смотрит, куда ему двигаться - вверх или вниз.

А теперь про книгу
Книга - огонь. Она достаточно емко и понятно объясняет 10 популярных алгоритмов, которые используются как в гигантах facebook, google, netflix, так и в типовых задачах. Становится понятно, как передаются пароли, работает система антиплагиат, и как Яндекс.Метро строит самый быстрый маршрут из А в Б.
Самым впечатляющим моментом, для меня, стала глава про "поиск по k-соседей". Дело в том, что, в университете,  препод пытался объяснить нам алгоритм 2 месяца и тряс его с нас на экзамене. Я прям не понял ничего. А тут - разобрался пока ехал домой. Вот настолько книга легко объясняет

Кому читать

  • Самоучкам. Определенно. 
  • Тем, у кого не было дисциплины "Алгоритмы и структуры данных" (как у меня) 
  • Тем, у кого была, но он ничего не понял (как я, будь у меня такая дисциплина).
  • Гуманитариям? Ну, я не хочу писать "для расширения кругозора". Но именно за этим. Хуже вам точно не будет. Вообще, вам уже трудно сделать хуже...

#книги