Что: 153bea9aec88fc2aa5f25660b37bb705d29c4ed9
Когда: 2021-04-08 15:58:47+03:00
------------------------------------------------------------------------
Темы: djb
------------------------------------------------------------------------
Crit-bit деревья на замену set, dict, heapq

http://cr.yp.to/critbit.html
DJB пишет crit-bit деревья настолько клёвая, простая и быстрая
структура, что ей можно бы было заменить зоопарк примитивов например в
том же Python. Мол штатная практика это использовать хэш таблицы где
нужно находить по точным соответствиям; или кучи (heap), где нужно
искать минимум; или AVL, красно-чёрные деревья для остального.

* хэш таблицы поддерживают вставку, удаление и точный поиск.
  crit-bit поддерживают вставку, удаление, точный поиск и упорядоченные
  операции типа нахождения минимума. Плюс crit-bit гарантирует хорошую
  производительность, в отличии от хэшей где некоторые данные могут
  деградировать её
* heap поддерживает вставку, удаление и нахождение минимума. crit-bit,
  кроме указанного выше, ещё и поиск по общему суффиксу
* структуры общего назначения, типа AVL или B-деревьев, поддерживают
  аналогичные операции что и crit-bit, но crit-bit быстрее и проще,
  особенно для строк разной длины. B-деревья представлены в виде очень
  удобных блоков памяти для работы с диском, но такое же дружелюбное
  "кластеризованное" представление crit-bit деревьев тоже сделать легко
* представьте насколько будут довольны программисты, если ваш встроенный
  базовый тип данных не только позволит искать "x", но и упорядочивать
  строки после "x". С хэш таблицами этого не сделать, а AVL сложнее и
  медленнее

* Most people don't seem to realize how fast crit-bit trees can be;
* Most people don't seem to realize how small crit-bit trees can be;
* Most people don't seem to realize that crit-bit trees support all of
  the standard data-structure operations. PATRICIA is often dismissed as
  being large and complicated, but pure crit-bit trees are actually
  quite small and simple

DJB уже замечен в гениальных изобретениях и творениях. И замечен в
полном отсутствии пиара или популяризации. Может быть и с crit-bit
аналогично?

------------------------------------------------------------------------
оставить комментарий: mailto:comment@blog.stargrave.org?subject=Re:%20Crit-bit%20%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F%20%D0%BD%D0%B0%20%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD%D1%83%20set%2C%20dict%2C%20heapq%20%28153bea9aec88fc2aa5f25660b37bb705d29c4ed9%29

------------------------------------------------------------------------
Сгенерирован: SGBlog 0.34.0