Чисто функциональный (постоянный) кольцевой буфер - PullRequest
0 голосов
/ 19 октября 2018

Я хотел бы реализовать кольцевой буфер с использованием чисто функциональной структуры данных со следующими операциями

  • Эффективный произвольный доступ по индексу
  • Добавить вперед
  • Удалитьсо спины

Причина использования постоянной структуры данных в том, что у меня есть один поток записи и несколько потоков чтения, и я хочу избежать чтения, блокирующего запись.

Это можно сделатьлегко, когда поток чтения удерживает блокировку только во время создания снимка, а затем использует снимок для обработки.

Какая существующая структура данных поддерживает эту операцию?

  • Вдвойне-связанный список не может эффективно выполнять поиск по индексу и имеет O (n)
  • Clojure PersistentVector на основе идеального хеш-дерева Фила Багвелла, поддержка доступа по индексу в log32N и использование subvec для удаления элемента с самого начала.
  • Трижды сопоставленный массив хеша также можно использовать, храня целое число в качестве ключа, но это может быть не очень эффективнымient.

Какую другую чисто функциональную структуру данных можно использовать в этом случае?

1 Ответ

0 голосов
/ 19 октября 2018

Дерево пальца (в стандартной библиотеке как Data.Sequence) - это путь для постоянных последовательностей произвольного доступа.Я думаю, что он удовлетворяет вашим критериям - индексирование произвольного доступа составляет O (log n) (точнее, журнал расстояния индекса от края), остальные - O (1) .Мне не известны какие-либо постоянные структуры данных, которые работают лучше этого.

...