У него был огромный упорядоченный список, разбитый на страницы. Получается, что каждая страница - это тоже список, но не большой. В качестве элементов списка он в примерах использует целые числа. Я расскажу только как была организована работа с одной страницей, полное описание смотрите по ссылке.
Тиму надо было работать со списком в многопоточном приложении, количество локов должно быть минимально. Для поиска он использовал бинарный поиск, который умеет работать с дубликатами, в данном случае это важно.
Как была организована работа со страницей. Записывает он все это так: сначала указано количество элементов, их четыре. Дальше перечислены сами элементы:
4: 10, 20, 30, 40
Теперь мы добавляем туда число 15, которое должно разместиться между 10 и 20. Допустим, что у нас есть еще свободное место на странице, а число 4 означает только число элементов, которые используются в данный момент.
Начинаем процесс вмешивания (shuffling-in) нового злемента
4: 10, 20, 30, 40, 40
Теперь увеличиваем счетчик
5: 10, 20, 30, 40, 40
Перемещаем элемент...
5: 10, 20, 30, 30, 40
5: 10, 20, 20, 30, 40
И в конце ставим элемент на его законное место.
5: 10, 15, 20, 30, 40
Удаление происходит аналогично.
Итого: можно искать по списку в то время, когда в него кто-то пишет. Но если пишут несколько потоков, то приходится список лочить.
Основной минус всего этого - если мы начали искать число 15 из приведенного примера, в то время как оно ползет до своего места, то мы его не найдем.
Тим Брей спрашивает, не придумал ли он чего странное, но в комментариях пока ничего эдакого не нашли.
Развернутый список, отличается от обычного тем, что в его узле содержится несколько элементов, а не один, как в обычном. И такое простое решение обеспечивает очень интересные преимущества перед обычным списком. Во-первых, экономится память. Приятно, но это не главное. Главное, что в кэш теперь попадает не один элемент, а сразу пачка, и это сказывается на производительности самым положительным образом. Количество элементов в узле развернутого списка удобно выбирать таким, чтобы они как раз укладывались в кэш-линию.
Развернутые списки - это простой пример структуры данных, которая знает о существовании кэша и умеет это использовать.
Есть примеры и посложнее, например деревья Ван Эмде Боаса (они же vEB деревья). Вообще с этими деревьями интересно получилось. По привычке я пошла в Википедию и долго тупила в картинку, пытаясь понять что же там изображено. Я всегда думала, что они выглядят вот так (картинка из слайдов Descent into Cache-Oblivion [.pdf]): После чего нашла упоминания того, что это ненастоящие деревья Ван Эмде Боаса. Поскольку картинка из Википедии мне ничем не помогла, я попыталась найти труд самого Ван Эмде Боаса. Он называется Design and Implementation of an Efficient Priority Queue и его предлагают покупать за деньги. Короче, если вы знаете ссылку на хорошее описание, киньте ее, пожалуйста.
Прежде чем начинать говорить о красно-черных деревьях, немного о бинарных деревьях вообще. Важно, чтобы дерево было сбалансированным, чтобы длины поддеревьев отличались не больше чем на единицу. Если это не так, работа с таким деревом становится более затратной по времени и смысла в таком дереве уже нет. Однако, при операциях вставки и добавления дерево идет вразнос. Одни ветки становятся сильно длинее других. Его можно сбалансировать и привести ветки в порядок. Для этого придуманы самобалансирующиеся деревья - при вставке элементов им ветки выравнивают. Но балансирование - дорогая операция. Лучше всего - золотая середина. Красно-черное дерево, где узлы помечены черным и красным цветами, называют "достаточно сбалансированным". Длины поддеревьев у него могут отличаться больше, чем на единицу. Но никогда больше чем в два раза.
Пример использования из реальной жизни: std::map'ы обычно реализуют через красно-черные деревья.
Картинка из Википедии, которую обычно приводят в качестве примера красно-черного дерева, мне не нравится.
Эта картинка дает неверное впечатление. Дерево, изображенное на ней, сбалансировано. И разноцветные вершины расположены рядами. И создается ощущение, что оно всегда так. Вот картинка получше (из статьи Advanced Haskell Data Structures: Red-Black Trees):
Фильтр Блума - это структура данных, придуманная Бёртоном Блумом в 1970 году, которая позволяет быстро проверять принадлежность элемента множеству, при этом не затратная по памяти.
Фильтр Блума представляет собой битовый массив, в которой с помощью нескольких хэш-функций отображается каждый элемент. Картинка из Википедии. Фильтр Блума может сработать ложно. То есть элемента во множестве нет, а он говорит, что есть. И чем больше элементов в множестве, тем выше вероятность ложного срабатывания. Однако, если вы знаете, что основной массы элементов в вашем множестве нет, то этот фильтр очень удобен. Вы сначала прогоняете их все через фильтр. А потом проверяете еще раз каким-нибудь иным более точным образом. Ложные срабатывания - не единственная проблема фильтра Блума. Еще из него нельзя удалять элементы. Есть различные расширения фильтра Блума, которые все-таки позволяют это делать, но, понятное дело, не бесплатно.
Пример использования из Википедии: Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.
В институтах всех нас учат сравнивать две строки по принципу равны/не равны и искать строку в подстроке. На практике же, когда строки не равны, интересен вопрос, а насколько отличаются две строки?
Расстояние Левенштейна определяет, сколько раз надо добавить/удалить/заменить символ, чтобы одну строку превратить в другую. Например, расстояние между словами kitten и sitting равно трем. Этот, и похожие алгоритмы используется в спеллчекерах, при распознавании текста, да и много еще где.
Вообще этих расстояний много разных, по вышеприведенным ссылкам найдете. Например есть расстояние Дамерау — Левенштейна, чуть посложнее, в него добавляется перестановка.
Все любят смеяться над новичками, которые норовят придумать свой уникальный алгоритм или хэш со сложностью доступа O(n) в лучшем случае (true story!). Однако бывает, что мозг далеко уже не младших программистов порождает нежизнеспособных колченогих уродцев, которые значительно хуже существующих аналогов. А остановить их некому. Поэтому на этой неделе я сделаю несколько постов про алгоритмы и структуры данных, которые не входят в стандартный курс по программированию. Это не какие-то передовые достижения науки, да и информацию по ним по всем можно легко найти в Интернете. Но если не знаешь, что именно искать, то можно так никогда и не найти. Updated 24.08.2010 В рамках недели были рассмотрены следующие темы Расстояние Левенштейна Фильтр Блума Красно-черные деревья Развернутые списки Списки с одновременным доступом Тима Брея И бонус с дружественного блога Поиск подстроки в строке: алгоритм Кнута-Морриса-Пратта
Я причесала старые два поста. Все общие замечания про конференцию я вынесла сюда. Дописала недостающие куски, добавила фотографии, добавила ссылки на слайды, которые выложил Шампандар.
Когда я упоминаю Шампандара, вопрос, который мне чаще всего задают "а кто это?". Это программист, специализирующийся на игровом ИИ, ведет aigamedev.com, работает по контрактам на разные девелоперские конторы. Работал в компании Rockstar, работал над Killzone 2. Организовал конференцию, о которой я так много рассказываю, за что ему большое спасибо.
Я до этого была только на русскоязычных конференциях, тут же была жуткая смесь европейских языков. Очень много франкоговорящих товарищей. И еще разные акценты английского. Неожиданно сложно было понимать финский и итальянский акценты. Русских не встречала, вообще русскоговорящих не было.
Но программеры, они все прям как у нас. Во время кофе-брейков многие мялись и мучались. Я тоже мялась и мучилась. Тяжело это - общаться.
Веселый студент из Дублина, который сидел рядом со мной, выдвинул интересную теорию. Докладчики отличались по поведению в зависимости от специализации: там были бизнесмены, программисты и преподаватели из вузов. Бизнесмены держались уверенно, напористо и складно говорили, преподаватели также были уверены, но без напора, программисты же с видимым усилием боролись с желанием спрятаться под стол.
Шампандар круто управлял временем, расхождения с расписанием у него были максимум минут десять. Для тех, кто раньше бывал на конференциях, это много о чем должно сказать. Как он это делал: во время вопросов и ответов он в какой-то момент объявлял "следующий вопрос - последний". И все.
Главный недостаток конференции - отсутствие WiFi. Я и еще два чувака нылись по этому поводу в твиттере всю конференцию. Меня это сильно расстроило, потому что я планировала создать эдакий эффект присутствия. Твитить, даже запостить видео. Вот вам видео, чего добру пропадать.
CNAM
Указатель
Нам туда, вниз
Я получила бэджик!
Зачем-то были закрыты последние ряды. Не знаю зачем.
Конференция была несколько омрачена традиционной французской забавой - забастовкой. Трудящиеся массово бастовали в связи с реформой пенсионной системы. Как несложно догадаться, условия выхода на пенсию меняют в худшую сторону. В связи с чем не работал некоторый транспорт, были отменены авиарейсы. Тут очень хорошо выступил спонсор - рекрутинговая компания Game Talents. Они обновляли информацию о ситуации в аэропортах на доске объявлений в реальном времени (WiFi, как мы помним, отсутствовал). Также они обещали отвезти людей в аэропорты. Отвезли или нет - не знаю, а вот доску объявлений видела своими глазами.
Программка и бэджик
Еще один минус, правда организаторы конференции тут ни при чем... В Париже, да и вообще во Франции, очень странные отели. Там тебя подстерегают неожиданности. Например, ты входишь в номер и входишь прямо в кровать. Или вот: кондиционер есть, но в шкафу. В одном номере у нас раковина была прямо в комнате. В каких-то ситуациях это даже удобно, на утро после верчеринки можно одним броском с кровати засунуть голову под кран с холодной водой. Будьте готовы, короче, если соберетесь поехать.
