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