Re[3]: Нужна идея сортированной последовательности с доступом по индексу
От: Miroff Россия  
Дата: 16.02.22 13:01
Оценка:
Здравствуйте, _agg, Вы писали:

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


Тебе на самом деле не нужна сортировка, тебе нужна структура, которая автоматически обеспечивает отношение порядка. По классике для этого используются разновидности бинарных деревьев, типа красно/черного дерева. Но на списках и хэшах тоже можно не хуже.
Re[5]: Нужна идея сортированной последовательности с доступом по индексу
От: Miroff Россия  
Дата: 16.02.22 13:07
Оценка: :))
Здравствуйте, T4r4sB, Вы писали:

TB>Бинарным поиском по связному списку?

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

У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?
Re[6]: Нужна идея сортированной последовательности с доступом по индексу
От: Stanislav V. Zudin Россия  
Дата: 16.02.22 13:09
Оценка:
Здравствуйте, Miroff, Вы писали:

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


M>У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?


Если хранить индекс, то зачем нужен список?
_____________________
С уважением,
Stanislav V. Zudin
Re[6]: Нужна идея сортированной последовательности с доступом по индексу
От: T4r4sB Россия  
Дата: 16.02.22 13:10
Оценка:
Здравствуйте, Miroff, Вы писали:

M>У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?


Эммм, а какая будет сложность вставки в середину тогда?
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
От: watchmaker  
Дата: 16.02.22 13:24
Оценка: +1
Здравствуйте, T4r4sB, Вы писали:

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


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

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

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


Да, ну и что? Это же не означает, что операции с ними нельзя делать быстрее чем за линейное время.

Например, уже предложенные сбалансированные двоичные деревья поиска
Автор: Chorkov
Дата: 15.02.22
позволяют делать за время O(logN) не только вставку, поиск и удаление узла по значению ключа, но и аналогичные операции по порядковому индексу. Причём независимо от того какие операции и в каком порядке выполняются (а не как, например, тут
Автор: ononim
Дата: 16.02.22
предложили лениво сортировать, что очевидно ужасно работает для чередующихся запросов).
Из накладных расходов — лишь необходимость хранить рядом с каждым элементом дополнительный счётчик под это дело.

То есть не смотря на то, что при вставке элемента в дерево индексы поменяются у O(N) элементов, augmented BST позволяет делать обновление индексов во время вставки/удаления за ту же временную сложность O(logN).

Собственно, std::set хотя везде и реализуется через деревья поиска (потому что требования составлены так, что иначе их или не соблюсти, или это будет очень непрактично), но наружу этот интерфейс деревьев не показывает, хотя в реализации в целом там почти всё нужно есть.
И поэтому приходится копипастить почти такую же реализацию двоичных деревьев поиска к себе в проект, чтобы можно было хранить там размеры поддеревьев и обращаться к ним, и, соответственно, получить возможность доступа по порядковому индексу.
Re[7]: Нужна идея сортированной последовательности с доступом по индексу
От: Miroff Россия  
Дата: 16.02.22 13:28
Оценка:
Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Если хранить индекс, то зачем нужен список?


Чтоб вставлять и удалять за логарифмическое время. Тебя же никто не заставляет поддерживать индекс и список в постоянно синхронизированном состоянии. Индекс может обновляться в фоновом режиме при актуальном обращении к элементу. В чем прелесть реальных задач, в отличие от книжных алгоримов, ты можешь оптимизировать только то что важно конкретно для твоего сценария, а не сферический средний случай в вакууме.
Re[3]: Нужна идея сортированной последовательности с доступом по индексу
От: T4r4sB Россия  
Дата: 16.02.22 13:28
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Да, ну и что? Это же не означает, что операции с ними нельзя делать быстрее чем за линейное время.


W>Например, уже предложенные сбалансированные двоичные деревья поиска
Автор: Chorkov
Дата: 15.02.22
позволяют делать за время O(logN) не только вставку, поиск и удаление узла по значению ключа, но и аналогичные операции по порядковому индексу.


Хм, да, и правда, достаточно в каждом узле хранить количество всех "потомков".
Re[8]: Нужна идея сортированной последовательности с доступом по индексу
От: Stanislav V. Zudin Россия  
Дата: 16.02.22 13:49
Оценка:
Здравствуйте, Miroff, Вы писали:

SVZ>>Если хранить индекс, то зачем нужен список?


M>Чтоб вставлять и удалять за логарифмическое время. Тебя же никто не заставляет поддерживать индекс и список в постоянно синхронизированном состоянии. Индекс может обновляться в фоновом режиме при актуальном обращении к элементу. В чем прелесть реальных задач, в отличие от книжных алгоримов, ты можешь оптимизировать только то что важно конкретно для твоего сценария, а не сферический средний случай в вакууме.


Не проходит по условиям задачи.
Требуется и хранить данные упорядоченно и без пропуска индексов.
А это означает, что при каждой модификации коллекции придется сперва искать в индексе, а потом его модифицировать.
Вот и получается, что список лишний.
_____________________
С уважением,
Stanislav V. Zudin
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.