Искусство разрушения: HArray

Начало

Всем привет. В прошлом топике мы тестировали открытый исходный код HArray. Кто не знаком, краткое резюме по этому проекту. Первое — это Key/Value контейнер, который построен совершенно иначе, чем Hashtables или Binary Trees, на совершенно других алгоритмах. Это открывает путь принципально иных, фундаментальных преимуществ.

1. Очень высокая скорость работы. Бенчмарки можно посмотреть тут. Тестирование без всяких подвохов, Key/Value контейнер имеет достаточно простые сценарии использования. В среднем HArray в 5-10 раз быстрее работает чем типичные реализации контейнеров вроде std::map, при этом имея даже немного более широкую функциональность. И в многих кейсах работает быстрее чем Hashtables, особенно на скорости вставок. Единственный кейс где Hashtables уверенно обгоняет HArray, это ключи последовательной природы, вроде 1,2,3 и тд. Но ирония в том, что для таких ключей Вам не нужен HArray, не нужен Hashtables или другой map, а подойдет обычный массив.

2. Малое потребление памяти. Для монотонных ключей, которые имеют общий префикс (пути к файлам, пути к обьектам, словари и тд) возможна компрессия данных по сравнению с оригинальным их размером. Компрессия данных невозможна в бинарных деревьях и тем более в хештаблицах, где перерасход памяти стабильно составляет в 2-3 раза.

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

4. Специфические, но не синтетические, контр примеры. Это когда вставляются длинные ключи с похожими префиксами. Они не использовались в бенчмарках, чтобы не давать HArray явное преимущество, но на этих контр примерах потребление памяти и скорость работы может отличатся в десятки и сотни раз в пользу HArray.

5. Нет хешфункций, нет коллизий. HArray отлично работает с большими обьемами данных, вставить миллиард ключей или больше в такую структуру не проблема. При этом плавное потребление памяти и почти константное время на вставках/поиске, которое зависит скорее от длины ключа, а не от количества ключей.

6. Еще немного плюшек: Возможность задавать правила сортировки ключей внутри контейнера. Нет Stop World событий на вставке (это когда структуре в какойто момент необходимо полностью перестроится, что занимает время). Сериализация/десериализация на диск, на скоростях близких к максимальной скорости работы диска (поскольку структура сбрасывает и подымает на диск страницы памяти, а не делает обход всего графа).

7. Удаление ключей.

И на этом остановимся подробней.

Разрушение

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

В HArray, как в поисковом алгоритме который наиболее приближен (по моему мнению) к биологическим живым системам, процесс разрушения ключей очень похож на то, что происходит в живом микромире. Когда мы удаляем ключ, этот ключ должен быть разобран на базовые строительные блоки: ContentCells, BranchCells, BlockCells, VarCells. Блоки ключей которые не нужны, формируют мертвые ткани (died fibres), которые связаны между собой и готовы к переиспользованию для построения новых ключей. Если таких тканей слишком много, они должни быть выведены из контейнера, чтобы не занимать лишнюю память, а сама структура данных должна быть упрощена. Начинается обратный процесс развития, сложное схлопывается в простое и наоборот, развивается и усложняется при добавлении новых ключей.

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

Это интересный процесс. И еще интересней, повторить то, как работают клеточные автоматы.

👍НравитсяПонравилось0
В избранноеВ избранном1
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Я у Вас интересовался еще в той теме. Вы с этой реализацией сравнивали по скорости? pgm.di.unipi.it/docs

Что-то не могу на нее найти бенчмарки, где ее сравнивают с какими-то популярными имплементациями. Например std::map или std::unordered_map.
Это помогло бы оценить, стоит ли заморачиватся и ее изучать подробнее.

По алгоритимической сложности вижу что она хуже, чем у меня.
По этому пейперу, есть сравнение с бинарными деревьями и результаты не однозначны.
vldb.org/...​pvldb/vol14/p1-marcus.pdf

Хотя у меня, если с хештаблицами по скорости работы еще могут быть вопросы, то с бинарными деревьями обычно разница в 5-10 раз в мою пользу.

Нашел интересную дискуссию. Здесь автор (создатель pgm) пишет следующее

You are right, variable-length strings are difficult. You could try to pack as many characters as possible in a computer word (or in a big int data type), say P characters, and then use the PGM-index to find the strings that share a prefix of P chars with the given query string. I discussed this solution in a GitHub issue (github.com/...​-index/issues/8#issuecomm...). It may work in practice, but it’s far from being adequate if compared to trie data structures (and their recent advancements).

Поторопился бубновый, этот топик будет похоронен под темой про поздняки
Надо было сегодня постить))

Ничего страшного. Рукописи не горят © =)

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

этот высер

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

формальное описание алгоритма

Исходники открыты + есть такая страничка
github.com/...​ter/Trie_for_beginners.md

Смотри, вот пример документации на хеш таблицу от адекватных людей, которым не давит корона: people.csail.mit.edu/...​s/metreveli-cphash-tr.pdf

Что имеем у тебя? Описание книжной структуры Trie с пометками что обычные хеш-таблицы говно, и тонны исходников, в которых хрен кто разберется.

Хорошо писать документы по хештаблицам, обычно они простые как табуретки.

А вот описание подобной структуры как у меня. 80 страниц зубодробильного текста.
judy.sourceforge.net/doc/shop_interm.pdf

У меня и кода больше и все ещё сложнее, это будет минимум 100-120 страниц описания.

У меня и кода больше и все ещё сложнее, это будет минимум 100-120 страниц описания.

Ты не бойся сложностей. Глаза боятся — руки делают.

Тут вопрос не сложностей, как раз писать то что хорошо понимаешь просто. Но здесь вообще мало смысла. 100 страниц текста мало кто вообще осилит. Для большинства обывателей достаточно, что исходный код открыт и работает. А почему это работает, вопрос второй.
На данном этапе, предложение Головатого натянуть HArray на интерфейсы stl, выглядит приоритетней.

100 страниц текста мало кто вообще осилит

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

Маркетинговый булщит на DOU — а можно не надо? Нам этого дерьма хватает в RTFM, когда за 10^n страниц текста невозможно вообще понять, что умеет делать очередной пафосный фреймворк кроме как спасти мир от разрушения, сплотить всё наше поколение...

спасти мир от разрушения

В заголовке Искусство разрушения.
Откуда спасти мир ?

пафосный фреймворк

Это не фреймворк.
Это Key/Value контейнер с простеньким интерфейсом, добавить, прочитать, удалить ключ.

что умеет делать

Что умеет делать мапа и чем отличается от других ? Вверху есть 7 пунктов.

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

Тогда очень хочется спросить: что если сделать вот так: x=2, y=2,z=x,z+y, и после этого
у переменных будут такие значения: x=0,y=0,z=4
То есть, что если сделать так, чтобы информация как бы была материальной?
Не помогло бы это тебе? Например, когда значение считывается, ключ остается без него, как бы пустым.

Это какая-то слишком сильная магия.

информация как бы была материальной

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

Ага, сильная. Так ведь можно рискнуть промоделировать и физические процессы. Самые разные.

Вокруг один говнокод. АйТи индустрия погрязла в стяжательствах. Девопсы как санитары леса теперь намбе Ван. Полимеры все проспали ещё 20-30 лет назад. Умудрились накосячить даже с поисковыми алгоритмами. Приличный трай днём с огнём не сищешь в библиотеках. Мучают сервисбасы и микросервисы. Системы синкаются через пень колоду, дебажатся ещё хуже. Убогие монги скомпрометировали документо центричную модель мира. Аспектную парадигму, которая выносит ООП как стратосфера сверх глубокую кольскую скважину, даже не начали толком раскапывать. Даже несчастная страница в эмигосраче постоянно перегружается вместо копирования двух сообщений аджаксом. Не паханое болото работы. А ты про моделировать физ процессы.

Я туп, но провидец.
Все то, что ты описал, я думаю, как раз из-за того, что когда в процессоре складываются 2 и 2 и получается 4 то 2 и 2 кешируются, а не стираются.
Если я правильно понимаю.
Когда компьютеры и программы не соблюдают законы реальной физики, это ведет к зловещим эффектам.
А если соблюдают то физика и математика могут обнаруживать несоответствия там где программы пасуют.
Утечки.
Там мне кажется.
Мировое здание документов (в которых полно копий этих документов) содержит тьму несогласованностей.
Увы, чем больше копий тем больше денег требуется на подержание их целостности.
То есть, когда я про физику, я про удешевление?

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

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

Так что ты сначала определись на каком уровне чего моделировать.

Вот возьмем три бита и начнем прибавлять 1.
000, 001, 010, 011, 100, 101, 110, 111,
Меня удивило сегодня, что эта единица оказалась в итоге даже в первом разряде, хотя добавляем мы ее в третий, последний.
И получается, если в последний разряд добавлять 1 то в первом постоянно все меняется. То есть, на вопрос — можно ли подобрать такое простое число, что его какая-нибудь дешифровка даст нам «Войну и мир» можно уверенно ответить: да, но это займет много времени.
Начиная прибавление мы не знаем количества разрядов, которое понадобится для этого. Это количество неопределено, но будет определено.
А если прибавлять в начало? Поменять местами. Тогда у нас будет известно некоторое количество разрядов. Сразу известно.
И вот что я вывел из этого. Нарастающая сложность вещей это путешествие в глубину, необходимое значение которой определится только в момент достижения ее.
А если заранее определить количество разрядов, то появятся ограничения.
Вывод: живя и мирясь с ограничениями, невозможно утонуть в глубине.
Вот он и ответ на твой вопрос: на каком уровне моделировать. На самом близком к поверхности. Уход на глубину это не более чем бегство от неразрешенной задачки на тему: как разбить парадокс?
Парадоксы это одновременное существование противоположных утверждений. Но если предположить, что эти утверждения таки чем-то отличаются, то между а, б появляется и
Только вот потом начинается вот что а и, б и
Не факт что парадокс не исчезнет, он может скользнуть либо по ветке а и либо по ветке б и
Тогда снова понадобится разбивать. И так пока хватит ресурсов.
Парадокс он же глайдер, он же волна.
Даже у муравья есть парадокс — магистраль.
Ищи на поверхности, не уходи на глубину — ибо сия дыра до центра Земли, как минимум.
Не умножай сущностей, а преуменьшай их.
Где появляется бесконечность, там ты смотришь в невозможность.

То есть, на вопрос — можно ли подобрать такое простое число, что его какая-нибудь дешифровка даст нам «Войну и мир» можно уверенно ответить: да, но это займет много времени.

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

Спасибо, нет
Я и так сейчас занят тремя бесплатными своими прожектами — цветными квадратами, вассаби-двигом и последним — что-то вроде двумерного майнкрафта, где можно будет собственные биомы в интерфейсе лабать (с поведением, характеристиками, особенностями взаимодействий, картинками и анимациями)
Одним словом моделлер всего должен получиться.

Ответ на вопрос: откуда спешка?
Некоторая масса набрала неслабую скорость.
Как маховик разогналась.
Поэтому торможение/замедление должно быть крайне осторожным.

7. Удаление ключей.

Удаление отдельного ключа в мэпах/хэшах — обычно, не нужно.

Удаление отдельного ключа — несовместимо с иммутабилити (всё более популярная парадигма в современной разработке). Кроме того, это слишком «низко-контекстная» операция, относящаяся к микро-менеджменту — которой в подавляющем большинстве случаев современной разработки лучше пренебречь, чем выгребать последствия связанныe с использованием этой функциональности.

Но если у тебя АПИ/библиотека — придётся функцию-таки сделать. Всё возможно, если напрячься. :)

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

Подписаться на комментарии