привет всем, возникла задача, есть вот такой интерфейс:

struct storage{
    void insert(std::string& str) = 0;
    void erase(uint64_t index) = 0 ;
    std::string& get(uint64_t index) = 0;
};

Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
получать std::distance и привязывать его к вновь вставленной записи.
На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).

Здравствуйте, _agg, Вы писали:

_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
_>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
_>получать std::distance и привязывать его к вновь вставленной записи.
_>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).

Как часто нужно делать вставки/удаления? Судя по интерфейсу, добавление всегда делаются в начало или конец контейнера, верно?

Самое простое, наверное, будет Skip list. Не самое производительное для поиска по индексу, но если много добавлений/удалений то должно хорошо зайти.

Здравствуйте, _agg, Вы писали:

_>привет всем, возникла задача, есть вот такой интерфейс:
_>

_>struct storage{
_>    void insert(std::string& str) = 0;
_>    void erase(uint64_t index) = 0 ;
_>    std::string& get(uint64_t index) = 0;
_>};
_>

_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
_>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
_>получать std::distance и привязывать его к вновь вставленной записи.
_>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).

Кроме ожидаемого размера важно знать соотношение частот вставок/удалений/запросов.
И соотношение требований по максимальному/амортизированному времени обработки запросов разных типов.


Варианты:
1) Сортированный массив
2) Самодельный set, на сбалансированном дереве, с хранением числа дочерних элементов в каждом узле.
3) список массивов (вложенные массивы, понятно, отсортированы).
Поддерживать средний размер массива на уровне N^(1/2)
Время доступа/вставки, тоже будет O(N^(1/2)).
4) (только для строк) — цифровой бор (tire) с хранением числа дочерних элементов в узле.
Тут важно знать какие значения могут принимать символу строки.
(Если ограниченное подмножество, например, только английский алфавит -ё можно существенно оптимизировать.)

Здравствуйте, _agg, Вы писали:

_>привет всем, возникла задача, есть вот такой интерфейс:
_>

_>struct storage{
_>    void insert(std::string& str) = 0;
_>    void erase(uint64_t index) = 0 ;
_>    std::string& get(uint64_t index) = 0;
_>};
_>

_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
_>В идеале нужен std::set только с доступом по индексу.
Вы хотя бы задачу внятно сформулируйте:
1. Какой индекс присваивается вновь вставленной строке? Как вы его собираетесь получать? Искать с помощью get(index)?
2. "сортированный контейнер" где операция сравнения того чего вы сортируете?
3. Индексы после добавления меняются?
4. Какие требования к объёмам данных и скорости работы?
5. чем вас вместо int64 не устраивает int128 (он же guid?)

Здравствуйте, _agg, Вы писали:

_>В идеале нужен std::set только с доступом по индексу.

возможно вам нужен boost::flat_set . Там есть метод nth(size_type). Удаление можно сделать в два приёма erase(nth())

Здравствуйте, _agg, Вы писали:

_>привет всем, возникла задача, есть вот такой интерфейс:
_>

_>struct storage{
_>    void insert(std::string& str) = 0;
_>    void erase(uint64_t index) = 0 ;
_>    std::string& get(uint64_t index) = 0;
_>};
_>

_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
_>В идеале нужен std::set только с доступом по индексу.

1. Должен ли контейнер хранить данные в сортированном виде?
Ну т.е. должно ли выполняться условие get(N) < get(N+1) ?

2. При вставке/удалении индексы у элементов меняются?
3. Пропуски в индексах допускаются?

Т.к. подробности неизвестны, то буду фантазировать

Вариант 1.
Храним тупо в массиве, при вставке/удалении поднимаем флаг isDirty.
Когда нужна сортированная последовательность — строим массив индексов и сортируем его, не трогая основные данные.
Массив индексов хранится рядом с данными. Можно вместо флага при вставке/удалении тупо зачищать этот массив. Тогда пустой массив служит сигналом, что надо выполнить сортировку.

Вариант 2.
Взять какой-нить flat_set. Если в бусте такого нет, то состряпать самому на базе массива. Добавляются элементы всегда в конец массива.
Вместо указателей использовать индексы в массиве. При построении дерева перестраиваются только индексы, элементы в массиве не перемещаются.
При удалении индекс помечать как невалидный (можно положить в список свободных) и при следующей вставке переиспользовать.

Здравствуйте, _agg, Вы писали:

_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
_>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
_>получать std::distance и привязывать его к вновь вставленной записи.
_>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).

Обычный связный список, aka linked list. Все требуемые операции за O(log(n)). Если все еще медленно, то прикрутить поверх hash map в качестве индекса, будет O(1). Быстрее уже никак.

Здравствуйте, kaa.python, Вы писали:

KP>Здравствуйте, _agg, Вы писали:

_>>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
_>>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
_>>получать std::distance и привязывать его к вновь вставленной записи.
_>>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).

KP>Как часто нужно делать вставки/удаления? Судя по интерфейсу, добавление всегда делаются в начало или конец контейнера, верно?

KP>Самое простое, наверное, будет Skip list. Не самое производительное для поиска по индексу, но если много добавлений/удалений то должно хорошо зайти.

Обратил внимание тоже на этот алгоритм и нашел его реализацию на github :

Здравствуйте, Chorkov, Вы писали:

C>Варианты:
C>1) Сортированный массив
C>2) Самодельный set, на сбалансированном дереве, с хранением числа дочерних элементов в каждом узле.
C>3) список массивов (вложенные массивы, понятно, отсортированы).
C> Поддерживать средний размер массива на уровне N^(1/2)
C> Время доступа/вставки, тоже будет O(N^(1/2)).
C>4) (только для строк) — цифровой бор (tire) с хранением числа дочерних элементов в узле.
C> Тут важно знать какие значения могут принимать символу строки.
C> (Если ограниченное подмножество, например, только английский алфавит -ё можно существенно оптимизировать.)

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

Здравствуйте, sergii.p, Вы писали:

SP>Здравствуйте, _agg, Вы писали:

_>>В идеале нужен std::set только с доступом по индексу.

SP>возможно вам нужен boost::flat_set . Там есть метод nth(size_type). Удаление можно сделать в два приёма erase(nth())


Во отлично, спасибо большое

Здравствуйте, Stanislav V. Zudin, Вы писали:


SVZ>1. Должен ли контейнер хранить данные в сортированном виде?
SVZ>Ну т.е. должно ли выполняться условие get(N) < get(N+1) ?

SVZ>2. При вставке/удалении индексы у элементов меняются?
SVZ>3. Пропуски в индексах допускаются?

SVZ>Т.к. подробности неизвестны, то буду фантазировать

SVZ>Вариант 1.
SVZ>Храним тупо в массиве, при вставке/удалении поднимаем флаг isDirty.
SVZ>Когда нужна сортированная последовательность — строим массив индексов и сортируем его, не трогая основные данные.
SVZ>Массив индексов хранится рядом с данными. Можно вместо флага при вставке/удалении тупо зачищать этот массив. Тогда пустой массив служит сигналом, что надо выполнить сортировку.

SVZ>Вариант 2.
SVZ>Взять какой-нить flat_set. Если в бусте такого нет, то состряпать самому на базе массива. Добавляются элементы всегда в конец массива.
SVZ>Вместо указателей использовать индексы в массиве. При построении дерева перестраиваются только индексы, элементы в массиве не перемещаются.
SVZ>При удалении индекс помечать как невалидный (можно положить в список свободных) и при следующей вставке переиспользовать.


1. Да контейнер должен хранить данные в сортированном виде
2. Ну пункт 1 на это отвечает, естественно меняется
3. Недопускаются пропуски в индексах

Вариант 1 — такую поделку я первое что сделал ) , но миллион вставок затем столько же удалений, вставок, получений и эту поделку я так и недождался когда она это сделает )
Вариант 2 — Вот на этом форуме в предыдущем посте про boost::flat_set упомянули буду пробовать, и на github контейнер SkipList тоже попробую

Здравствуйте, kov_serg, Вы писали:

_>Вы хотя бы задачу внятно сформулируйте:
_>1. Какой индекс присваивается вновь вставленной строке? Как вы его собираетесь получать? Искать с помощью get(index)?
_>2. "сортированный контейнер" где операция сравнения того чего вы сортируете?
_>3. Индексы после добавления меняются?
_>4. Какие требования к объёмам данных и скорости работы?
_>5. чем вас вместо int64 не устраивает int128 (он же guid?)

1. Вновь вставленной строке присваивается индекс = std::distance(begin_iterator, inserted_iterator)
2. Операция сравнения :

struct ref_str {
            ref_str() = default;
            ref_str(const l_strs::const_iterator& _it) : it_str(_it) {}
            ref_str(l_strs::const_iterator&& _it) : it_str{ std::move(_it) } {}
            bool operator<(const ref_str& rs) const {
                return *(it_str) < *(rs.it_str);
            }            
            l_strs::const_iterator it_str;
        };

3. Да конечно меняются
4. Миллион записей и столько же операций за вменяемое время секунд 10
5. Разве я говорил что меня что-то неустраивает?

Структура данных SkipList вроде подходит буду ее пробовать

Здравствуйте, Miroff, Вы писали:

M>Обычный связный список, aka linked list. Все требуемые операции за O(log(n)). Если все еще медленно, то прикрутить поверх hash map в качестве индекса, будет O(1). Быстрее уже никак.

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

Здравствуйте, _agg, Вы писали:

_>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).
boost::multi_index

Здравствуйте, _agg, Вы писали:

_>привет всем, возникла задача, есть вот такой интерфейс:
_>

_>struct storage{
_>    void insert(std::string& str) = 0;
_>    void erase(uint64_t index) = 0 ;
_>    std::string& get(uint64_t index) = 0;
_>};
_>

_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
_>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
_>получать std::distance и привязывать его к вновь вставленной записи.
_>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).

Можно хранить массив (vector) элементов, плюс мапу key => index.
В мапе хранить индексы позиции элемента в массиве.
Перед добавлением проверяем уникальность по мапе, потом кладём в конец массива и прежний count добавляем по ключу в мапу.

Оператор [] можно перегрузить по индексу и по ключу — две перегрузки.

Здравствуйте, _agg, Вы писали:


_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
_>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
_>получать std::distance и привязывать его к вновь вставленной записи.

Но ведь получается что при вставке меняются индексы в среднем у половины всего контейнера.

Здравствуйте, Miroff, Вы писали:

M>Обычный связный список, aka linked list. Все требуемые операции за O(log(n)). Если все еще медленно, то прикрутить поверх hash map в качестве индекса, будет O(1). Быстрее уже никак.

И как в него за логарифм вставить так, чтоб сохранить сортированность?

А на практике, какие сценарии возможны?
1 удаление чередуется с доступом по индексу равномерно? — это хреновый вариант
2 операции удаления группируются 'кучками'? — в таком случае можно перестраивать индексы лишь по необходимости, а не после каждого удаления

Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, Miroff, Вы писали:

M>>Обычный связный список, aka linked list. Все требуемые операции за O(log(n)). Если все еще медленно, то прикрутить поверх hash map в качестве индекса, будет O(1). Быстрее уже никак.

TB>И как в него за логарифм вставить так, чтоб сохранить сортированность?

Бинарным поиском

Здравствуйте, Miroff, Вы писали:

M>Бинарным поиском

Бинарным поиском по связному списку?
И как ты возьмёшь середину, например?