Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу.
В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно
получать std::distance и привязывать его к вновь вставленной записи.
На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).
Re: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, _agg, Вы писали:
_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно _>получать std::distance и привязывать его к вновь вставленной записи. _>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).
Как часто нужно делать вставки/удаления? Судя по интерфейсу, добавление всегда делаются в начало или конец контейнера, верно?
Самое простое, наверное, будет Skip list. Не самое производительное для поиска по индексу, но если много добавлений/удалений то должно хорошо зайти.
Re: Нужна идея сортированной последовательности с доступом по индексу
_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно _>получать std::distance и привязывать его к вновь вставленной записи. _>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).
Кроме ожидаемого размера важно знать соотношение частот вставок/удалений/запросов.
И соотношение требований по максимальному/амортизированному времени обработки запросов разных типов.
Варианты:
1) Сортированный массив
2) Самодельный set, на сбалансированном дереве, с хранением числа дочерних элементов в каждом узле.
3) список массивов (вложенные массивы, понятно, отсортированы).
Поддерживать средний размер массива на уровне N^(1/2)
Время доступа/вставки, тоже будет O(N^(1/2)).
4) (только для строк) — цифровой бор (tire) с хранением числа дочерних элементов в узле.
Тут важно знать какие значения могут принимать символу строки.
(Если ограниченное подмножество, например, только английский алфавит -ё можно существенно оптимизировать.)
Re: Нужна идея сортированной последовательности с доступом по индексу
_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>В идеале нужен std::set только с доступом по индексу.
Вы хотя бы задачу внятно сформулируйте:
1. Какой индекс присваивается вновь вставленной строке? Как вы его собираетесь получать? Искать с помощью get(index)?
2. "сортированный контейнер" где операция сравнения того чего вы сортируете?
3. Индексы после добавления меняются?
4. Какие требования к объёмам данных и скорости работы?
5. чем вас вместо int64 не устраивает int128 (он же guid?)
Re: Нужна идея сортированной последовательности с доступом по индексу
_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>В идеале нужен std::set только с доступом по индексу.
1. Должен ли контейнер хранить данные в сортированном виде?
Ну т.е. должно ли выполняться условие get(N) < get(N+1) ?
2. При вставке/удалении индексы у элементов меняются?
3. Пропуски в индексах допускаются?
Т.к. подробности неизвестны, то буду фантазировать
Вариант 1.
Храним тупо в массиве, при вставке/удалении поднимаем флаг isDirty.
Когда нужна сортированная последовательность — строим массив индексов и сортируем его, не трогая основные данные.
Массив индексов хранится рядом с данными. Можно вместо флага при вставке/удалении тупо зачищать этот массив. Тогда пустой массив служит сигналом, что надо выполнить сортировку.
Вариант 2.
Взять какой-нить flat_set. Если в бусте такого нет, то состряпать самому на базе массива. Добавляются элементы всегда в конец массива.
Вместо указателей использовать индексы в массиве. При построении дерева перестраиваются только индексы, элементы в массиве не перемещаются.
При удалении индекс помечать как невалидный (можно положить в список свободных) и при следующей вставке переиспользовать.
_____________________
С уважением,
Stanislav V. Zudin
Re: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, _agg, Вы писали:
_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно _>получать std::distance и привязывать его к вновь вставленной записи. _>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).
Обычный связный список, aka linked list. Все требуемые операции за O(log(n)). Если все еще медленно, то прикрутить поверх hash map в качестве индекса, будет O(1). Быстрее уже никак.
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, _agg, Вы писали:
_>>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно _>>получать std::distance и привязывать его к вновь вставленной записи. _>>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).
KP>Как часто нужно делать вставки/удаления? Судя по интерфейсу, добавление всегда делаются в начало или конец контейнера, верно?
KP>Самое простое, наверное, будет Skip list. Не самое производительное для поиска по индексу, но если много добавлений/удалений то должно хорошо зайти.
Обратил внимание тоже на этот алгоритм и нашел его реализацию на github :
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, 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.
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, sergii.p, Вы писали:
SP>Здравствуйте, _agg, Вы писали:
_>>В идеале нужен std::set только с доступом по индексу.
SP>возможно вам нужен boost::flat_set . Там есть метод nth(size_type). Удаление можно сделать в два приёма erase(nth())
Во отлично, спасибо большое
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
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 тоже попробую
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, kov_serg, Вы писали:
_>Вы хотя бы задачу внятно сформулируйте: _>1. Какой индекс присваивается вновь вставленной строке? Как вы его собираетесь получать? Искать с помощью get(index)? _>2. "сортированный контейнер" где операция сравнения того чего вы сортируете? _>3. Индексы после добавления меняются? _>4. Какие требования к объёмам данных и скорости работы? _>5. чем вас вместо int64 не устраивает int128 (он же guid?)
1. Вновь вставленной строке присваивается индекс = std::distance(begin_iterator, inserted_iterator)
2. Операция сравнения :
Здравствуйте, Miroff, Вы писали:
M>Обычный связный список, aka linked list. Все требуемые операции за O(log(n)). Если все еще медленно, то прикрутить поверх hash map в качестве индекса, будет O(1). Быстрее уже никак.
Так неполучится, да и последовательность в которую вставляю должна быть сортированной, то есть индекс реально можно будет получить только после вставки и сортировки.
Re: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, _agg, Вы писали:
_>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).
boost::multi_index
"For every complex problem, there is a solution that is simple, neat,
and wrong."
Re: Нужна идея сортированной последовательности с доступом по индексу
_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно _>получать std::distance и привязывать его к вновь вставленной записи. _>На практике при миллионе записей работает очень медленно, у кого есть идея решения буду премногоблагодарен ).
Можно хранить массив (vector) элементов, плюс мапу key => index.
В мапе хранить индексы позиции элемента в массиве.
Перед добавлением проверяем уникальность по мапе, потом кладём в конец массива и прежний count добавляем по ключу в мапу.
Оператор [] можно перегрузить по индексу и по ключу — две перегрузки.
Re: Нужна идея сортированной последовательности с доступом по индексу
_>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>В идеале нужен std::set только с доступом по индексу. Получается при каждой новой вставке нужно _>получать std::distance и привязывать его к вновь вставленной записи.
Но ведь получается что при вставке меняются индексы в среднем у половины всего контейнера.
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Miroff, Вы писали:
M>Обычный связный список, aka linked list. Все требуемые операции за O(log(n)). Если все еще медленно, то прикрутить поверх hash map в качестве индекса, будет O(1). Быстрее уже никак.
И как в него за логарифм вставить так, чтоб сохранить сортированность?
Re: Нужна идея сортированной последовательности с доступом по индексу
А на практике, какие сценарии возможны?
1 удаление чередуется с доступом по индексу равномерно? — это хреновый вариант
2 операции удаления группируются 'кучками'? — в таком случае можно перестраивать индексы лишь по необходимости, а не после каждого удаления
Как много веселых ребят, и все делают велосипед...
Re[3]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, Miroff, Вы писали:
M>>Обычный связный список, aka linked list. Все требуемые операции за O(log(n)). Если все еще медленно, то прикрутить поверх hash map в качестве индекса, будет O(1). Быстрее уже никак.
TB>И как в него за логарифм вставить так, чтоб сохранить сортированность?
Бинарным поиском
Re[4]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, _agg, Вы писали:
_>Так неполучится, да и последовательность в которую вставляю должна быть сортированной, то есть индекс реально можно будет получить только после вставки и сортировки.
Тебе на самом деле не нужна сортировка, тебе нужна структура, которая автоматически обеспечивает отношение порядка. По классике для этого используются разновидности бинарных деревьев, типа красно/черного дерева. Но на списках и хэшах тоже можно не хуже.
Re[5]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, T4r4sB, Вы писали:
TB>Бинарным поиском по связному списку? TB>И как ты возьмёшь середину, например?
У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?
Re[6]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Miroff, Вы писали:
TB>>И как ты возьмёшь середину, например?
M>У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?
Если хранить индекс, то зачем нужен список?
_____________________
С уважением,
Stanislav V. Zudin
Re[6]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Miroff, Вы писали:
M>У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?
Эммм, а какая будет сложность вставки в середину тогда?
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, _agg, Вы писали:
_>>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>>В идеале нужен std::set только с доступом по индексу.
TB>Но ведь получается что при вставке меняются индексы в среднем у половины всего контейнера.
Да, ну и что? Это же не означает, что операции с ними нельзя делать быстрее чем за линейное время.
позволяют делать за время O(logN) не только вставку, поиск и удаление узла по значению ключа, но и аналогичные операции по порядковому индексу. Причём независимо от того какие операции и в каком порядке выполняются (а не как, например, тут
предложили лениво сортировать, что очевидно ужасно работает для чередующихся запросов).
Из накладных расходов — лишь необходимость хранить рядом с каждым элементом дополнительный счётчик под это дело.
То есть не смотря на то, что при вставке элемента в дерево индексы поменяются у O(N) элементов, augmented BST позволяет делать обновление индексов во время вставки/удаления за ту же временную сложность O(logN).
Собственно, std::set хотя везде и реализуется через деревья поиска (потому что требования составлены так, что иначе их или не соблюсти, или это будет очень непрактично), но наружу этот интерфейс деревьев не показывает, хотя в реализации в целом там почти всё нужно есть.
И поэтому приходится копипастить почти такую же реализацию двоичных деревьев поиска к себе в проект, чтобы можно было хранить там размеры поддеревьев и обращаться к ним, и, соответственно, получить возможность доступа по порядковому индексу.
Re[7]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Если хранить индекс, то зачем нужен список?
Чтоб вставлять и удалять за логарифмическое время. Тебя же никто не заставляет поддерживать индекс и список в постоянно синхронизированном состоянии. Индекс может обновляться в фоновом режиме при актуальном обращении к элементу. В чем прелесть реальных задач, в отличие от книжных алгоримов, ты можешь оптимизировать только то что важно конкретно для твоего сценария, а не сферический средний случай в вакууме.
Re[3]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Miroff, Вы писали:
SVZ>>Если хранить индекс, то зачем нужен список?
M>Чтоб вставлять и удалять за логарифмическое время. Тебя же никто не заставляет поддерживать индекс и список в постоянно синхронизированном состоянии. Индекс может обновляться в фоновом режиме при актуальном обращении к элементу. В чем прелесть реальных задач, в отличие от книжных алгоримов, ты можешь оптимизировать только то что важно конкретно для твоего сценария, а не сферический средний случай в вакууме.
Не проходит по условиям задачи.
Требуется и хранить данные упорядоченно и без пропуска индексов.
А это означает, что при каждой модификации коллекции придется сперва искать в индексе, а потом его модифицировать.
Вот и получается, что список лишний.
_____________________
С уважением,
Stanislav V. Zudin