Развернутый список, отличается от обычного тем, что в его узле содержится несколько элементов, а не один, как в обычном.
И такое простое решение обеспечивает очень интересные преимущества перед обычным списком. Во-первых, экономится память. Приятно, но это не главное. Главное, что в кэш теперь попадает не один элемент, а сразу пачка, и это сказывается на производительности самым положительным образом. Количество элементов в узле развернутого списка удобно выбирать таким, чтобы они как раз укладывались в кэш-линию.
Развернутые списки - это простой пример структуры данных, которая знает о существовании кэша и умеет это использовать.
Есть примеры и посложнее, например деревья Ван Эмде Боаса (они же vEB деревья).
Вообще с этими деревьями интересно получилось. По привычке я пошла в Википедию и долго тупила в картинку, пытаясь понять что же там изображено. Я всегда думала, что они выглядят вот так (картинка из слайдов Descent into Cache-Oblivion [.pdf]):
После чего нашла упоминания того, что это ненастоящие деревья Ван Эмде Боаса. Поскольку картинка из Википедии мне ничем не помогла, я попыталась найти труд самого Ван Эмде Боаса. Он называется Design and Implementation of an Efficient Priority Queue и его предлагают покупать за деньги. Короче, если вы знаете ссылку на хорошее описание, киньте ее, пожалуйста.
(Пост опубликован в рамках недели борьбы с велосипедизмом)
Ссылки по теме:
Cache-oblivious data structures
Несколько ссылок на материалы про кэш
Unrolled linked lists
My code::dive talk video is available: New Q&A
2 дня назад
13 коммент.:
откуда берется макрос dcbt? (не нашел ее описание в инете)
современные компиляторы разве не пользуются префетч?
в с++0x не включили named функции?
заранее большое спасибо за ответ
А развёрнутые списки используют "как есть"? Мне казалось, все предпочитают держать вектор векторов, а не список векторов.
Отправил статью на адрес в профайле.
указатель на указатель вряд ли позволит держать все данные рядом (плохая локализация кеша) да и указатели почти не подвержены оптимизации автоматом компилятора
Занимался я cache-oblivious алгоритмами для себя в этом семестре, поэтому могу кое-чего рассказать. :)
С деревьями вана Эмде Боаса история такая: изначально его деревья служили для того, чтобы при некоторых ограничениях на ключ иметь возможность делать O(log log n) лукап и (могу врать) Succ, Pred. Фишка деревьев была в том, что все множество билось на куски по sqrt(n) элементов, и они распихивались по O(sqrt(n)) узлам.
Потом появилась cache-oblivious модель вычислений, в которой сложность алгоритма -- это количество memory-transfers между уровнями памяти (ну в CO есть еще пару предположений, но не суть). Чтобы более-менее неплохо укладывать деревья в памяти, умные ребята обратились к идеям ван Эмде Боаса. И то, что показано на рисунке, -- это van Emde Boas _layout_, а не tree (а. к. а. способ укладки).
Для сбалансированного бинарного дерева с n элементами vEB-layout определяется так:
1) Если n == 1, то vEB-layout такого дерева -- просто сам элемент.
1) Иначе разобъем дерево по уровню высоты h / 2; тогда в верхней части (пусть это часть #0) получим O(sqrt(n)) элементов, а снизу получим O(sqrt(n)) висящих деревьев (пронумеруем их слева направо). Заметим, что в каждом поддереве тоже O(sqrt(n)) элементов.
Теперь выложим исходное дерево в памяти следующим образом: сначала в vEB-layout-е выложим верхнюю часть (#0), а затем все остальные также в vEB-layout-е (т. о. vEB-layout -- рекурсивно определяемое понятие).
Если повтыкать теперь на текст выше и на картинку -- станет ясно. :)
Зачем это нужно: пусть у нас есть сбалансированное бинарное дерево поиска, выложенное в памяти в inorder-обходе. Известно, что поиск ключа требует O(log n) операций сравнения. Хочется понять, сколько обращений в память потребует поиск элемента. Вот утверждается, что в плохом случае это потребует O(log (n/B)) пересылок памяти (B -- размер блока данных, передаваемых между уровнями памяти; грубо говоря, размер кеш-строки).
По некоторым причинам, это плохо. :) Например, известно, что можно обойтись O(log_B(n)) пересылками памяти (что, если подумать, в разы лучше). Как этого достичь? Выложим дерево в vEB-layout-е!
Далее доказательство идет примерно так: так как vEB-layout определяется рекурсивно, то можно выбрать, как говорят, такой уровень детализации, что все дерево будет разбито на кусочки-треугольнички из O(B) элементов, которые в памяти лежат одним куском и, соответственно, подгружаются за O(1) операцию. Соответственно, любой путь от корня до вершины разбивается на кусочки длины O(log B) внутри которых не происходит I/O-операций. Соответственно, на весь lookup потребуется не более O(log n / log B) = O(log_B(n)) I/O.
В общем, без картинки звучит невнятно, проще объяснить с рисунком. :) Но на пальцах идея такая: начиная с какого-то момента все поддерево, куда возможно придется идти, влезет в кеш-лайн, и после этого момента не будет никаких кеш-промахов.
Почитать и посмотреть картинки по CO можно, например, тут: link.
Впрочем, все, что я написал, есть по ссылке на одноименный пост в MSDN. :)
Отличное описание vEB-tree есть в лекциях MIT:
http://courses.csail.mit.edu/6.851/spring07/scribe/lec12.pdf
@aamonster: извините, но как вы будете удалять из вектора за время O(1)?
aamonster
А развёрнутые списки используют "как есть"? Мне казалось, все предпочитают держать вектор векторов, а не список векторов.
Какой-либо статистики у меня по этому поводу нет.
Список векторов хорош тем, что позволяет объединить плюсы списков и векторов.
2 ilyaraz: как правило, я буду удалять из одного из векторов "второго уровня" за время O(m), m - длина вектора. И с вероятностью 1/m - удалять из вектора-оглавления длиной ~n/m (n - число элементов). Итого получаем O(m)+1/m*O(n/m) = O(m)+O(n/m^2).
Для развёрнутого списка будет просто O(m). А теперь можно прикинуть, при каком соотношении между m и n это будет одно и то же.
Эстеты могут сделать три уровня вложенности (хе-хе, ext2 не напоминает? ;-))
2 Alena:
Это понятно. Но когда количество элементов списка более-менее предсказуемо (скажем, не больше количества пикселов изображения) - эти преимущества особой роли не играют.
Впрочем, я не о преимуществах. Просто с тем, что люди используют для таких нужд массив массивов, я сталкивался. А со списком массивов - кажется, нет. Вот и спрашиваю - оно реально используется?
Кстати, если они реально используются - то почему нет в boost? (стандартное хранилище велосипедов).
P.S. А за саму тему - спасибо... О велосипедах надо знать. Я, к примеру, только недавно открыл для себя пирамиду.
23Skidoo, Sandello, ilyaraz спасибо, стало понятнее.
aamonster
Вот и спрашиваю - оно реально используется?
Какие-то громкие примеры использования мне не известны. Так люди по форумам рассказывают, что реализовывают развернутые списки, задают вопросы.
Кстати, если они реально используются - то почему нет в boost?
Это я не знаю :-)
если не изменяет память, представленную структуру Кормен называет heap (что в русском переводе - пирамида)
Andrey
если не изменяет память, представленную структуру Кормен называет heap (что в русском переводе - пирамида)
Не, heap - это совершенно другая структура данных
Отправить комментарий