No Image

Сортировка книг в библиотеке

СОДЕРЖАНИЕ
726 просмотров
10 марта 2020

Возьмём реверсно упорядоченный массив и применим к нему сортировку простыми вставками.

Смотрите, с каким скрипом происходит вставка в нужное место очередного элемента. Для него нужно освободить место вставки, из-за чего приходится сдвигать все раннее вставленные элементы.

А как было бы хорошо, если бы между раннее вставленными элементами были свободные места! Тогда не пришлось бы перетаскивать вереницы элементов только ради вставки одного.

В 2004 году трое специалистов по computer science — Майкл Бендер, Мартин Фарах-Колтон и Мигель Мостейро — решили именно так и модифицировать сортировку простыми вставками. Они предложили формировать упорядоченную часть массива, оставляя зазоры между вставленными элементами.

Библиотекарю необходимо, чтобы книги были расставлены по алфавиту на длинной полке: начиная слева от буквы «А», книги стоят впритык друг к другу до самой «Я». Если в библиотеку поступила новая книга, относящуюся к разделу «Б», то чтобы поставить её на полку в нужное место, придётся переместить каждую книгу, начиная где-то с середины раздела «Б» вплоть до последней «Я». Это сортировка простыми вставками. Однако, если бы библиотекарь резервировал свободное пространство в каждой секции, ему достаточно перемещать всего несколько книг, чтобы освобождать места для книжных новинок. Это основной принцип библиотечной сортировки.

Алгоритм

  • 1. Создаём пустой вспомогательный массив, в несколько раз больший чем основной.
  • 2. Для очередного элемента ищем место вставки во вспомогательном массиве.
  • 2.1. Если нашли место для вставки, то переносим элемент и возвращаемся в пункт 2.
  • 2.2. Если места для вставки не нашлось, производим перебалансировку вспомогательного массива и возвращаемся в пункт 2.
  • 3. После обработки всех элементов переносим их обратно в основной массив.
  • На первый взгляд кажется, что так сортировать легко и просто. Чтобы развеять эту иллюзию, ключевые пункты алгоритма рассмотрим подробнее.

    Размер вспомогательного массива

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

    Если взять слишком много — то между элементами будет достаточно много места, однако поиск места вставки и перебалансировка будут выполняться медленнее, ввиду больших расстояний между элементами. Перебалансировки будут случаться реже, но затрачивать ресурсы на них придётся больше. Если взять слишком мало, то поиск и перебалансировка будут обходиться дешевле, но переформатировать массив придётся чаще. В общем, тут ещё надо тестировать с разными значениями и методом научного тыка определить оптимальный вариант.

    Если мы определились, во сколько раз вспомогательный массив больше основного, то формула для определения точного количества элементов для него выглядит так:

    NewSize = ε × (Size + 1) − 1

    NewSize — количество элементов во вспомогательном массиве
    ε — во сколько раз вспомогательный массив больше основного
    Size — количество элементов в основном массиве

    Если мы просто умножим размер на коэффициент: то для равномерного распределения нам не хватит ячеек в количестве штук. То есть, расположить то их равномерно удаётся, но или первая заполненная ячейка или последняя будут находиться впритык к краю вспомогательного массива. А нам нужно, чтобы пустые места у заполненных ячеек были зарезервированы со всех сторон — в том числе и перед первым элементом и после последнего.

    Вроде бы пустяк, но на самом деле это важно для перебалансировки, чтобы гарантировать свободные места для вставки в любом месте, в том числе и при обработке последних элементов основного массива.

    Поиск места вставки во вспомогательном массиве

    Разумеется, тут нужен бинарный поиск. Однако классическая реализация нам не подойдёт.

    Во-первых, вспомогательный массив в основном состоит из пустоты. Поэтому, рекурсивно дихотомируя структуру, мы будем по большей части натыкаться на незаполненные ячейки. В этих случаях нужно пройтись немного влево или вправо, до ближайшей непустой ячейки. Тогда на концах отрезка будут значимые элементы, позволяющие вычислить среднее арифметическое и продолжить бинарный поиск в глубину.

    Во-вторых, не забываем о краях. Если нужно вставить минимальный или максимальный элемент, то бинарный поиск среди раннее вставленных ни к чему не приведёт. Поэтому стоит предусмотреть граничные случаи — сначала проверить, не надо ли поставить элемент возле левой или правой границы массива и если нет, то уж тогда применять бинарный поиск.

    В-третьих, учитывая специфику применения, стоит внести дополнительные поправки, чтобы минимизировать количество перебалансировок массива. Если вставляемый элемент равен значению на одном из концов отрезка, то, пожалуй, не стоит вставлять в середину отрезка. Логичнее поставить рядом с равным ему по значению элементом. Это позволит эффективнее заполнять пустое пространство вспомогательного массива.

    Можно придумать в-четвёртых, в-пятых и так далее. Качество поиска места вставки прямо влияет на скорость сортировки, так как выбор неудачных мест для вставки приводит к лишним перебалансировкам. Например, может стоит делить отрезки не точно посередине, а ближе к левому или правому краю отрезка, в зависимости от того, к какому краю ближе по значению вставляемый элемент?

    Алгоритм бинарного поиска сам по себе таит подводные камни, а с учётом вышеозначенных дополнительных нюансов окончательно становится отнюдь нетривиальной задачей.

    Перебалансировка массива

    Бинарный поиск — не самое тяжкое, что нужно реализовать в этой сортировке. Есть ещё перебалансировка.

    Когда места для вставки нет (близкие по значению элементы найдены, но между ними не оказалось свободных ячеек) необходимо перетряхнуть вспомогательный массив так, чтобы место вставки освободилось. Это встряхивание массива и есть перебалансировка.

    Читайте также:  Как придумать пароль для электронной почты пример

    Причём, перебалансировка бывает локальной или полной.

    Локальная перебалансировка

    Сдвигаем столько элементов, сколько необходимо для освобождения точки вставки. Реализация такой балансировки очень проста, надо просто выяснить ближайшую от места вставки пустую ячейку и использовать её, чтобы передвинуть несколько элементов.

    Тут возможны нюансы. Например, в какой стороне искать ближайшее вакантное место? Чтобы избежать ситуации когда сдвиг невозможен (то есть, если в какую-то из сторон все ячейки заняты до самого края массива), можно ориентироваться на положение места вставки относительно середины массива. Если нужно вставить в левой части массива, то сдвигать вправо, если в правой — влево. Если ε ≥ 2, то такой подход исключает ситуацию, при которой сдвиг невозможен (ибо в половине вспомогательного массива хватает с лихвой места для всех элементов).

    В авторской интерпретации алгоритма подразумевается именно локальная перебалансировка.

    Полная перебалансировка

    Интересной альтернативой локальной является полная перебалансировка. То есть, во вспомогательном массиве сдвинуть все имеющиеся элементы таким образом, чтобы между ними были (почти) одинаковые промежутки.

    Я попробовал оба варианта и пока что наблюдаю, что при локальной перебалансировке алгоритм работает в 1,5-2 раза быстрее чем при полной. Впрочем, от полной перебалансировки всё равно может быть толк. Например, если локальную перебалансировку приходится делать чересчур часто, то это означает, что в массиве на отдельных участках накопилось много «тромбов», тормозящих весь процесс. Полная перебалансировка, проведённая разово, позволяет одним махом избавиться от всех локальных заторов.

    Разберём, как именно производить полную перебалансировку.

    Для начала нужно вычислить, сколько максимально ячеек мы можем выделить на каждый элемент во вспомогательном массиве. При этом нужно помнить, что пустые ячейки должны быть как перед первой, так и после последней заполненной ячейки. Формула такая:

    M — количество ячеек, которое можно выделить на каждый элемент
    NewSize — размер вспомогательного массива
    Count — текущее количество непустых элементов во вспомогательном массиве

    Эту дробь нужно привести к целому значению (то есть округлить в меньшую сторону). Из формулы очевидно, что чем больше элементов уже перенесено во вспомогательный массив, тем меньше ячеек мы можем выделить под окрестности каждого элемента.

    Зная M, мы легко получаем точную позицию для каждого непустого элемента во вспомогательном массиве, на котором он должен находиться после завершения перебалансировки.

    NewPos = Number × M

    NewPos — новая позиция элемента после перебалансировки
    Number — какой это по счёту непустой элемент во вспомогательном массиве
    M — количество ячеек, которое выделено на каждый элемент

    Новые позиции известны, можно просто во вспомогательном массиве перебрать непустые элементы и их перенести на другие места? О, нет, не спешите. Надо не просто попереносить элементы, важно сохранить их очерёдность. А в результате бинарного поиска и вставки элементы могут оказаться как сильно левее так и сильно правее той позиции, в которой они должны быть после перебалансировки. И на месте, куда нужно перенести, может стоять другой элемент, который тоже нужно куда-то пристроить. Кроме того, нельзя переносить элемент, если между его старой и новой позицией во вспомогательном массиве есть другие элементы — иначе элементы перемешаются, а нам крайне важно не перепутать порядок.

    Поэтому для перебалансировки недостаточно будет пройтись обычным циклом и просто переложить каждый элемент из одного кармана в другой. Придётся ещё задействовать рекурсию. Если элемент нельзя перенести на новое место (между его старой и новой позициями оказались другие элементы), то сначала нужно разобраться (рекурсивно) с этими непрошенными гостями. И тогда всё расставится правильно.

    Вырожденный случай

    Для большинства сортировок вставками реверсно упорядоченный массив — наихудшая ситуация. И сортировка библиотекаря, увы, не исключение.

    Элементы стремятся к левому краю вспомогательного массива, в результате чего свободные места быстро заканчиваются. Приходится очень часто делать перебалансировку массива.

    Кстати, если взять почти упорядоченный массив (наилучший случай для сортировки простыми вставками), то получим ту же проблему. Вновь поступающие элементы будут забивать не левую, а правую часть вспомогательного массива, что также приведёт к слишком частым перебалансировкам.

    Library sort эффективно обрабатывает наборы случайных данных. Частичная упорядоченность (как прямая, так и обратная) ухудшает скоростные показатели.

    Алгоритмическая сложность

    На больших наборах случайных данных алгоритм даёт временну́ю сложность O(n log n). Совсем неплохо!

    На наборах случайных уникальных (или в основном уникальных) данных при правильном подборе коэффициента ε и удачной реализации бинарного поиска количество перебалансировок можно свести к минимуму, а то и избежать их вовсе. Можно утверждать, что алгоритм имеет лучшую временную сложность O(n).

    Большой процент повторяющихся по значению данных, а также наличие в массиве упорядоченных (в прямом или обратном порядке) подпоследовательностей приводит к частым перебалансировкам вспомогательного массива и, как следствие, — к деградации временно́й сложности до O(n 2 ) в наиболее неблагоприятных случаях.

    Минус алгоритма, конечно, в том, что на вспомогательный массив требуется O(n) дополнительной памяти.

    Возможные пути улучшения

    Хотя алгоритм сам по себе поучителен и эффективен на рандомных данных, за полтора десятилетия практически мало кто проявил к нему интерес.

    Читайте также:  Sony z ultra характеристики цена

    Если погуглить по запросу «library sort», то найдёте беглую статью в английской Википедии, авторский PDF (из которого мало что понятно) и редкий перепостинг этих скудных сведений. Плюс есть неплохая визуализация в Ютубе, где оригинально совместили основной и вспомогательный массивы. Все ссылки — в конце статьи.

    С поиском по запросу «библиотечная сортировка» ещё веселее — в выборке узнаете по разные сортировки, входящие в различные библиотеки, однако к аутентичной библиотечной сортировке эти алгоритмы не будут иметь отношения.

    А улучшать есть что:

    1. Эмпирический подбор оптимального коэффициента ε.
    2. Модификация (с учётом специфики общего алгоритма) бинарного поиска для максимально эффективного определения точки вставки.
    3. Минимизация расходов на перебалансировки.

    Если отшлифовать эти места, то, может, library sort по скорости даже сравняется с quick sort?

    Исходный код

    Реализацию на Python подготовить не успел, есть работающая версия на PHP.

    Фото: Александр Мельник

    В наше время все больше людей предпочитают электронные книги бумажным; но уверен, что среди читателей «Лайфхакера» немало тех, у кого дома есть старая добрая библиотека не на «электронной бумаге», а на вполне обычной. И если в электронных книгах навести порядок проще, то что делать с бумажными томами? Вот 5 способов организации бумажных книг.

    Способ №1: Создайте электронный каталог. Если книг у вас очень много, и вы при этом часто отдаете книгы знакомым и друзьям, то за всем уследить невозможно. На помощь придет Google Docs, любой офисный пакет и создание таблицы с метками и указанием того, кому и когда вы отдали ту или иную книгу и когда ориентировочно вам должны ее вернуть. А чтобы не путаться, помимо названия и автора укажите еще и номер книги в вашей библиотеке. Пронумеровать книги — это работа максимум на 1 час, зато систематизация большой бумажной библиотеки куда эффективнее, чем перевод всех книг в цифровой формат путем сканирования или поиска электронных копий в легальных и пиратских библиотеках.

    Способ № 2: Создайте бумажный каталог. Все как в предыдущем варианте, только на бумаге (большой блокнот или толстая тетрадь). Подойдет скорее людям пожилым и тем, кто стойко привязан к бумажному планированию и предпочитает ручку и страницы блокнота экранам и клавиатурам.

    Способ №3: Полки по темам / видам книг / авторам / цветам обложек. Один из оригинальных способов классификации, подсмотренный мной когда-то в тематических книжных блогах в рамках Tumblr. Если классификация по авторам и заглавиям в алфавитном порядке привычна и знакома практически каждому еще со времен пользования школьной библиотекой, то классификация по цветовой гамме обложек — нестандартное решение, но есть те, кому оно точно понравится 🙂 Заодно можно сделать книги инструментом для декорирования интерьеров.

    Способ №4: Систематизация в Evernote. Берем книгу, фотографируем обложку, добавляем заметку-примечание с названием, автором, годом издания — и всё это со своего смартфона закидываем в отдельный блокнот-каталог на Evernote. Самый дотошные «книголюбы» могут еще для каждого названия книги сгенерировать QR-код с этими данными, распечатать его и наклеить на обложку книги, а затем при необходимости достаточно навести камеру смартфона на этот код — и все данные о книге и ее владельце отобразятся на экране любого, кто взял у вас почитать книжку из домашней бумажной библиотеки.

    Способ №5: Каталог в GoodReads или аналогичных сервисах. Так можно не только систематизировать всю вашу библиотеку с хранением данных в Сети, но и оставлять рецензии о прочитанных книгах, находить у друзей интересные варианты книг для чтения, обмениваться книгами со знакомыми или покупать подержанные книги. Причем круг использования социальных сетей для любителей чтения достаточно широк: можно даже вести что-то вроде тематического книжного блога.

    Если у вас есть своя бумажная библиотека, поделитесь в комментариях, что вы делаете с книгами и как систематизируете их.

    Автор: Джесси Льюис (Jessi Lewis)

    На днях я переехала и, как и для большинства книголюбов, одной из главных перевозимых ценностей для меня стали мои книги. В новом доме теперь стоит на удивление большая коробка с надписью «В основном поэзия», а книги с рецептами перемешались с книгами о путешествиях. Пришло время упорядочить все тома. Так что мне пришлось задуматься, каким образом это можно сделать.

    Конечно, вы всегда можете систематизировать книги по алфавиту, взяв за основу название или фамилию автора. И знаете, это вполне нормально. Это отнюдь не означает, что вы схалтурили. Но я сама со временем убеждаюсь, что такая система меня не устраивает, и некоторые пользователи нашего сайта со мной согласны. Я просто не могу нормально её поддерживать. На самом деле, мне легче лишиться руки, чем сделать это. Другие пользователи «Riot» показали нам свои книжные полки, и теперь мне кажется, что систематизация книг вообще не является для кого-то из них проблемой.

    Большинство людей в конечном итоге идут другим путем – объединяют книги по общим темам. Раньше я тоже так делала: «Ах да, на этой полке стоит классика художественной литературы. А вот там хранится написанный женщинами нон-фикшн». Проблема состоит в том, что за пределами ваших собственных мыслей логика в этой системе не просматривается. И что будет, если кто-то еще, кроме вас, тоже пользуется вашими полками? Разве ваша система будет в таком случае работать?

    Читайте также:  Чем открыть формат pdo

    Другие книголюбы / дизайнеры интерьеров рассуждают о систематизации книг по цветам. Понимаю, что это отличная концепция для Pinterest, которая циркулирует в Интернете уже довольно долгое время. Посмотрите вариант расстановки книг из блога Matilda’s Shelf.

    Прекрасный пример того, как это можно сделать хорошо. Однако я не могу себе представить, как я буду искать нужный сборник стихов в большой коллекции расставленных по цвету томов. Правда, статья из «Slate» утверждает, что в данном случае красота может быть выше всякой логики. Меня это, впрочем, не убедило.

    Таким образом, передо мной встал вопрос: как еще можно систематизировать домашнюю библиотеку?

    1. По высоте.
    Знаю. Это звучит смешно, особенно в свете того, что многие книги по дизайну и искусству могут существенно отличаться размерами обложки от обычных величин. То же касается сборников стихов и пьес, которые, кажется, тяготеют к миниатюре. Кроме того, некоторые производители книжных полок (гхм… привет тебе, «Икея») не склонны принимать во внимание нестандартные размеры томов. Порой вы были бы и рады систематизировать вашу библиотеку по цвету, но проклятая книга Тафти «Визуальное представление больших объемов информации» ( The Visual Display of Quantitative Information ), оставшаяся у вас со времен аспирантуры, просто никуда не влезет. А сборник стихов Никки Финни (Nikky Finney The World Is Round ) просто затеряется среди остальных. Порой лучше расставлять книги по высоте.

    2. По старой доброй десятичной классификации Дьюи.
    Теоретически, если вас хватает на то, чтобы в уме классифицировать ваши книги в соответствии с системой Дьюи, то у вас точно ничего не потеряется. Никогда. С одной стороны, пользоваться ею проще и быстрее, чем расставлять книги по алфавиту, но с другой, она требует системы маркировки, которая может погубить обложки или засорить мысли. И, конечно, как и любая старая система, она имеет свои недостатки.

    3. По семи основным сюжетам.
    Помните, что это? В 2004 году Кристофер Букер выпустил книгу, в которой объяснил, что основные сюжеты всех книг можно разделить на семь категорий: «Победа над чудовищем», «Из грязи в князи», «Туда и обратно» и т.д. Подробнее можете почитать об этом в книге «Семь основных сюжетов: почему мы рассказываем истории» ( The Seven Basic Plots: Why We Tell Stories ). И если вы верите в лежащую в её основе юнгианскую теорию, то почему бы вам не систематизировать ваши книги, руководствуясь ею? Хотя я знаю, что некоторые писатели возражают против подобного упрощения сюжетных линий, так что кому-то это может показаться неправильным.

    4. По читаемости.
    Особенно полезно это будет в отношении книг, которые используются несколькими читателями. Да, вероятно, имеет смысл размещать детские книги пониже, а более взрослые – перемещать повыше. Янг-эдалт может стоять где-то посередине, чтобы до него доставали все.

    5. По последним прочитанным.
    Может, вам захочется отследить хронологию? Нужно ли мне стыдиться того, что Гроздья гнева я читала еще в средней школе, но до сих пор утверждаю, что это одна из моих любимых книг? Если вы решитесь на такой способ размещения томов, то у вас появится собственная вселенная непрочитанных книг, ждущих, когда на них обратят внимание, и дальняя полка «старичков», надеющихся когда-нибудь вернуться на лучшие места. Меня такая система шокировала больше, чем кто-либо может подумать. Возник вопрос: от скольких прочитанных вами книг можно избавиться, передав их кому-то еще?

    6. По сентиментальности.
    Ладно, это может показаться неуместным, но мне бы хотелось попробовать сделать это. Если бы я стала размещать книги, основываясь на своей эмоциональной с ними связи, то, возможно, я бы смогла избавиться от книг, которые никак меня не затронули. Сразу стало бы ясно, что вон тот сборник рассказов я купила как-то по прихоти и так и не смогла в него вчитаться, а вот те книжные подарки для меня и вовсе никогда не имели смысла. Могло бы это помочь мне проредить свою коллекцию? Смогла бы я освободиться от ненужного балласта, если бы стала сравнивать свое к ним отношение?

    7. По подлинным предпочтениям.
    Рискованный способ, потому что вынесение подобного рода суждений чревато большими тратами времени, проведенного в сомнениях. Хотя я вполне могу себе представить некоторых преданных любителей классики, которым понравится такой метод. Иногда нам больше нравится содержание книги, а не писательский стиль, порой наоборот. Но можете ли вы выделить книги, в которых обе эти составные части уравновешены – те, что вы сами считаете произведением искусства? И если вы это сделаете, то, наверное, сможете оценить и все остальные – сравнивая их со своими любимцами? Какую книгу я люблю больше всего? Скорее всего «Гроздья гнева» (но об этом я уже говорила).

    Мне нужно хорошенько над этим подумать, до того как я начну расставлять свои книги.

    Есть ли еще какой-нибудь способ их систематизировать? Или вы верите в книжную анархию.

    Комментировать
    726 просмотров
    Комментариев нет, будьте первым кто его оставит

    Это интересно
    Adblock
    detector