From 153bea9aec88fc2aa5f25660b37bb705d29c4ed9 Mon Sep 17 00:00:00 2001
From: Sergey Matveev <stargrave@stargrave.org>
Date: Thu, 8 Apr 2021 15:58:47 +0300
Subject: [PATCH] =?utf8?q?Crit-bit=20=D0=B4=D0=B5=D1=80=D0=B5=D0=B2=D1=8C?=
 =?utf8?q?=D1=8F=20=D0=BD=D0=B0=20=D0=B7=D0=B0=D0=BC=D0=B5=D0=BD=D1=83=20s?=
 =?utf8?q?et,=20dict,=20heapq?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

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
аналогично?
-- 
2.48.1