Списки с одновременным доступом Тима Брея

В посте Concurrent List Update With Shuffling Тим описывает задачу, которую решил когда-то давно.

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

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

Как была организована работа со страницей. Записывает он все это так: сначала указано количество элементов, их четыре. Дальше перечислены сами элементы:

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 из приведенного примера, в то время как оно ползет до своего места, то мы его не найдем.

Тим Брей спрашивает, не придумал ли он чего странное, но в комментариях пока ничего эдакого не нашли.

Спасибо Maniac'у за ссылку.


(Пост опубликован в рамках недели борьбы с велосипедизмом)

Развернутые списки

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

Развернутые списки - это простой пример структуры данных, которая знает о существовании кэша и умеет это использовать.

Есть примеры и посложнее, например деревья Ван Эмде Боаса (они же vEB деревья).
Вообще с этими деревьями интересно получилось. По привычке я пошла в Википедию и долго тупила в картинку, пытаясь понять что же там изображено. Я всегда думала, что они выглядят вот так (картинка из слайдов Descent into Cache-Oblivion [.pdf]):

После чего нашла упоминания того, что это ненастоящие деревья Ван Эмде Боаса. Поскольку картинка из Википедии мне ничем не помогла, я попыталась найти труд самого Ван Эмде Боаса. Он называется Design and Implementation of an Efficient Priority Queue и его предлагают покупать за деньги. Короче, если вы знаете ссылку на хорошее описание, киньте ее, пожалуйста.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Ссылки по теме:
Cache-oblivious data structures
Несколько ссылок на материалы про кэш
Unrolled linked lists

Красно-черные деревья

Прежде чем начинать говорить о красно-черных деревьях, немного о бинарных деревьях вообще. Важно, чтобы дерево было сбалансированным, чтобы длины поддеревьев отличались не больше чем на единицу. Если это не так, работа с таким деревом становится более затратной по времени и смысла в таком дереве уже нет. Однако, при операциях вставки и добавления дерево идет вразнос. Одни ветки становятся сильно длинее других. Его можно сбалансировать и привести ветки в порядок. Для этого придуманы самобалансирующиеся деревья - при вставке элементов им ветки выравнивают. Но балансирование - дорогая операция. Лучше всего - золотая середина. Красно-черное дерево, где узлы помечены черным и красным цветами, называют "достаточно сбалансированным". Длины поддеревьев у него могут отличаться больше, чем на единицу. Но никогда больше чем в два раза.

Пример использования из реальной жизни: std::map'ы обычно реализуют через красно-черные деревья.

Картинка из Википедии, которую обычно приводят в качестве примера красно-черного дерева, мне не нравится.



Эта картинка дает неверное впечатление. Дерево, изображенное на ней, сбалансировано. И разноцветные вершины расположены рядами. И создается ощущение, что оно всегда так. Вот картинка получше (из статьи Advanced Haskell Data Structures: Red-Black Trees):


Формальное описание красно-черного дерева и его свойств вы найдете в Википедии, а я вам предлагаю посмотреть вставку элеметов в красно-черное дерево под бодрящую музыку.



Если хочется расширить и углубить свое знание красно-черных деревьяв - вот вам хорошая лекция по красно-черным деревьям. На английском.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Фильтр Блума

Фильтр Блума - это структура данных, придуманная Бёртоном Блумом в 1970 году, которая позволяет быстро проверять принадлежность элемента множеству, при этом не затратная по памяти.

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

Фильтр Блума может сработать ложно. То есть элемента во множестве нет, а он говорит, что есть. И чем больше элементов в множестве, тем выше вероятность ложного срабатывания. Однако, если вы знаете, что основной массы элементов в вашем множестве нет, то этот фильтр очень удобен. Вы сначала прогоняете их все через фильтр. А потом проверяете еще раз каким-нибудь иным более точным образом.
Ложные срабатывания - не единственная проблема фильтра Блума. Еще из него нельзя удалять элементы. Есть различные расширения фильтра Блума, которые все-таки позволяют это делать, но, понятное дело, не бесплатно.

Пример использования из Википедии:
Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Пост Will it optimize?

Will it optimize? - опросник, в котором вам предлагается угадать будет ли GCC проводить оптимизацию кода. Сложно и познавательно.

Там очень здоровая шапка, чуть вниз отмотайте.

Спасибо Maniac'у за ссылку.

Расстояние Левенштейна

В институтах всех нас учат сравнивать две строки по принципу равны/не равны и искать строку в подстроке. На практике же, когда строки не равны, интересен вопрос, а насколько отличаются две строки?

Расстояние Левенштейна определяет, сколько раз надо добавить/удалить/заменить символ, чтобы одну строку превратить в другую. Например, расстояние между словами kitten и sitting равно трем. Этот, и похожие алгоритмы используется в спеллчекерах, при распознавании текста, да и много еще где.

Алгоритм подсчета расстояния Левенштейна описан в Википедии, с псевдокодом. Есть на русском.

Еще одно описание алгоритма, с ява-апплетом, который умеет считать расстояние Левенштейна.

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

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Неделя борьбы с велосипедизмом

Все любят смеяться над новичками, которые норовят придумать свой уникальный алгоритм или хэш со сложностью доступа O(n) в лучшем случае (true story!). Однако бывает, что мозг далеко уже не младших программистов порождает нежизнеспособных колченогих уродцев, которые значительно хуже существующих аналогов. А остановить их некому. Поэтому на этой неделе я сделаю несколько постов про алгоритмы и структуры данных, которые не входят в стандартный курс по программированию. Это не какие-то передовые достижения науки, да и информацию по ним по всем можно легко найти в Интернете. Но если не знаешь, что именно искать, то можно так никогда и не найти.

Updated 24.08.2010
В рамках недели были рассмотрены следующие темы
Расстояние Левенштейна
Фильтр Блума
Красно-черные деревья
Развернутые списки
Списки с одновременным доступом Тима Брея
И бонус с дружественного блога Поиск подстроки в строке: алгоритм Кнута-Морриса-Пратта

Ссылки по теме:
What should be in your programming toolbox?
5 more essentials for your programming toolbox
Programmer’s Toolbox Part 3: Consistent Hashing. Об этом же на русском Консистентные хэши (Consistent hashing)

Paris Game AI Conference 2010. Общие впечатления

Вы думали, про конференцию уже всё? Нифига.

Я причесала старые два поста. Все общие замечания про конференцию я вынесла сюда. Дописала недостающие куски, добавила фотографии, добавила ссылки на слайды, которые выложил Шампандар.

Кроме меня отчеты уже написали: Шампандар, Микко Мононен и Бьярн Кнафла. У Шампандара много фотографий хорошего качества, его жена фотографировала. Микко в отдельном посте выложил слайды и сурсы.

Когда я упоминаю Шампандара, вопрос, который мне чаще всего задают "а кто это?". Это программист, специализирующийся на игровом ИИ, ведет aigamedev.com, работает по контрактам на разные девелоперские конторы. Работал в компании Rockstar, работал над Killzone 2. Организовал конференцию, о которой я так много рассказываю, за что ему большое спасибо.

Я до этого была только на русскоязычных конференциях, тут же была жуткая смесь европейских языков. Очень много франкоговорящих товарищей. И еще разные акценты английского. Неожиданно сложно было понимать финский и итальянский акценты. Русских не встречала, вообще русскоговорящих не было.

Но программеры, они все прям как у нас. Во время кофе-брейков многие мялись и мучались. Я тоже мялась и мучилась. Тяжело это - общаться.

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

Шампандар круто управлял временем, расхождения с расписанием у него были максимум минут десять. Для тех, кто раньше бывал на конференциях, это много о чем должно сказать. Как он это делал: во время вопросов и ответов он в какой-то момент объявлял "следующий вопрос - последний". И все.

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


CNAM


Указатель


Нам туда, вниз


Я получила бэджик!


Зачем-то были закрыты последние ряды. Не знаю зачем.


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


Программка и бэджик













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