📚 Hub Books: Онлайн-чтение книгПсихологияХакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще - Али Альмоссави

Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще - Али Альмоссави

Шрифт:

-
+

Интервал:

-
+
1 ... 4 5 6 7 8 9 10 11 12 ... 22
Перейти на страницу:

Для начала заметим, что метод 1 несет в себе определенный ритм. Чарли берет одну пачку конвертов, затем просматривает другие пачки, чтобы определить, куда ее положить. Затем он берет другую пачку конвертов, просматривает остальные пачки и так далее. Мы видели подобный подход раньше, когда разбирали носки, не так ли? Разница в том, что с каждым конвертом Чарли просматривает все другие только один раз, в то время как с носками Марджи могла потратить много времени, выискивая к каждому пару в куче белья.

Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

Подход Чарли в методе 1 – характерная черта алгоритма с квадратичным временем.[24] Каждый раз, когда у вас есть набор предметов (независимо от того, одинаковые ли они или разные) и вы перебираете их все в поисках одного, у вас есть алгоритм с квадратичным временем. Другие примеры подобного алгоритма – примерка нескольких рубашек с целью выбрать подходящую к вашим брюкам или сравнение списка покупок с продуктами на полке в магазине.

В информационных технологиях многие простые способы сортировки данных протекают в квадратичном времени. Подобно методу 1 Чарли, они все работают путем сравнивания смежных пунктов и перемещения их в зависимости от того, какой больше, а какой меньше. Все подходы, построенные на принципе сравнения прилегающих точек, в среднем происходят в квадратичном времени (n2). Иначе говоря, если n – количество конвертов, мы можем описать функцию, которая располагает эти конверты в нужном порядке с помощью сравнения, как «ограниченные n2», то есть в среднем (это ключевое слово!) мы не можем это сделать быстрее. Существует также сортировка методом вставок, методом выделения и пузырьковым методом.

Когда я впервые услышал о сортировке, будучи 16-летним школьником, я сперва не понял, что может быть лучше метода с квадратичным временем. График показывает, что метод 2 значительно быстрее, чем метод 1, поэтому стоит сортировать элементы в субквадратичном времени.

Общий подход к субквадратичному способу сортировки подразумевает такие методы, как разделение и присваивание, то есть разбивание группы предметов на более мелкие группы и сортировку этих групп.[25] Разделение группы пополам есть логарифмический метод, как мы видели ранее, а помещение предметов в одну группу снова – линейный, так как мы берем один предмет один раз. Этот подход к сортировке называют линейно-логарифмическим, и можно представить, что он гораздо быстрее, чем метод с квадратичным временем и немного медленнее, чем метод с линейным временем.[26] Его можно называть лог-линейным, или просто n log n, – этот порядок складывается из времени, затрачиваемого на разделение группы (log n) и на компоновку предметов заново (n). При умножении они дают n log n. Слово «линейно-логарифмический» образовано из двух: «линейный» и «логарифмический». Это создает концепцию, более сложную, чем составляющие ее части, – совсем как с Джедвардом.[27]

Два хорошо известных линейно-логарифмических алгоритма – сортировка слиянием, изобретенная Джоном фон Нейманом в 1945 году, и быстрая сортировка, придуманная Тони Хоаром в 1959 году. Метод 2 для Чарли сходен с сортировкой слиянием. Этап разделения соответствует раскладыванию пачек конвертов на отдельные кучки. А этап обратного слияния – сравнению и совмещению этих пачек. На последнем этапе в первый раз у нас остается набор двух упорядоченных групп. Во второй раз мы получаем уже четыре упорядоченные группы. В случае с Чарли процесс будет выглядеть так:

Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

Заметьте, как он переходит от набора неотсортированных конвертов в первом этапе к набору отсортированных конвертов, хоть и одного размера, на втором. На каждом последующем этапе он совмещает группы, создавая все более длинные ряды отсортированных конвертов, пока у него не останется один ряд, содержащий все конверты. Если мы рассмотрим поближе один из таких этапов, например этап 4, то сможем увидеть, как происходит слияние.

Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

И все же метод 2 – лучший выбор исходя из увеличения скорости, которого он позволяет достичь. Преимущество Чарли в том, что у него всего 33 пачки конвертов для сортировки. Любой метод спасет его от недельных страданий из-за обожженной кожи. Если бы у него было больше конвертов, то скоростной метод 2 оказался бы более предпочтителен, и Чарли, несомненно, извлек бы пользу от знания, как быстрее сортировать почту. Ну, а пока он заканчивает свой рабочий день.

Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

ЗАВЕРШАЯ РАЗВОЗКУ ПОЧТЫ, ЧАРЛИ СЧАСТЛИВ КАК НИКОГДА: СЕГОДНЯ ОН УЗНАЛ КОЕ-ЧТО НОВОЕ. «ВЕЗДЕ ЕСТЬ МЕСТО ДЛЯ ОТКРЫТИЙ, – ГОВОРИТ ОН СЕБЕ, – ДАЖЕ ТАМ, ГДЕ НЕ ОЖИДАЕШЬ».

Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

ПОЛЬЗУЙТЕСЬ НА ЗДОРОВЬЕ. ТОНИ ХОАР. ИЗОБРЕТАТЕЛЬ МЕТОДА БЫСТРОЙ СОРТИРОВКИ

6 Стань крутым
Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

Фой недавно переехал в Эшленд. Несмотря на ухоженную бородку-эспаньолку и непременный атрибут при выходе в свет – последний номер журнала «New Yorker» (он носит его под мышкой и никогда не читает, но любит небрежно бросить перед собой на столик в кафе или ресторане); несмотря на все это, он остается аутсайдером на новом месте. Его неизменный ответ на любой серьезный вопрос «Милтон бы не пришел в восторг от этого, поверьте мне», очень скоро начинает звучать банально и претенциозно. «Что вы думаете о новой книге Карла Ова Кнаусгарда?» – Милтон бы не пришел в восторг от этого, поверьте мне». «Вам понравился новый сингл Адели, Фой?» – «Милтон бы не пришел в восторг от этого, поверьте мне».

1 ... 4 5 6 7 8 9 10 11 12 ... 22
Перейти на страницу:

Комментарии

Обратите внимание, что комментарий должен быть не короче 20 символов. Покажите уважение к себе и другим пользователям!

Никто еще не прокомментировал. Хотите быть первым, кто выскажется?