Crit-bit деревья на замену set, dict, heapq

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

оставить комментарий

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