Сообщение Re: Можно ли оптимизировать std::list для поиска? от 18.02.2016 11:20
Изменено 18.02.2016 11:58 watchmaker
Здравствуйте, Went, Вы писали:
W>Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск. Но как его организовать, если у нас list?
Skip list — стандартный подход для такой ситуации. Работает хорошо.
W>Организовать параллельную мапу? Но это слишком прожорливо
Отличный вариант. Да и прожоливого там особенно ничего нет — просто хранишь указатели/итераторы в ней на оригинальные элементы в списке.
W>и трудно поддерживать синхронизацию, по-моему.
Чтобы было легко — заверни в контейнер и работай через него.
Например, посмотри на boost::multi_index — там и список и словарь можно поднять над одними данными.
W> Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?
Ну если тебе не нужно операций и свойств, которые специфичны для списков, вроде splice за O(1) или персистентности итераторов, то вектор часто лучше.
W>Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск. Но как его организовать, если у нас list?
Skip list — стандартный подход для такой ситуации. Работает хорошо.
W>Организовать параллельную мапу? Но это слишком прожорливо
Отличный вариант. Да и прожоливого там особенно ничего нет — просто хранишь указатели/итераторы в ней на оригинальные элементы в списке.
W>и трудно поддерживать синхронизацию, по-моему.
Чтобы было легко — заверни в контейнер и работай через него.
Например, посмотри на boost::multi_index — там и список и словарь можно поднять над одними данными.
W> Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?
Ну если тебе не нужно операций и свойств, которые специфичны для списков, вроде splice за O(1) или персистентности итераторов, то вектор часто лучше.
Re: Можно ли оптимизировать std::list для поиска?
Здравствуйте, Went, Вы писали:
W>Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск. Но как его организовать, если у нас list?
Skip list — стандартный подход для такой ситуации. Работает хорошо.
W>Организовать параллельную мапу? Но это слишком прожорливо
Отличный вариант. Да и прожорливого там особенно ничего нет — просто хранишь указатели/итераторы в ней на оригинальные элементы в списке.
W>но поиск происходит очень и очень часто.
А изменения насколько часты? Если их мало, а исходный список вообще никак трогать не хочется, то заводи параллельный вектор из указателей на элементы списка: его сортируй и по нему ищи. Дополнительной памяти совсем мало требуется, а стоимость поддержания сортированности будет мала, если изменения исходного списка будут редки.
W>и трудно поддерживать синхронизацию, по-моему.
Чтобы было легко — заверни в контейнер и работай через него.
Например, посмотри на boost::multi_index — там и список и словарь можно поднять над одними данными.
W> Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?
Ну если тебе не нужно операций и свойств, которые специфичны для списков, вроде splice за O(1) или персистентности итераторов, то вектор часто лучше.
W>Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск. Но как его организовать, если у нас list?
Skip list — стандартный подход для такой ситуации. Работает хорошо.
W>Организовать параллельную мапу? Но это слишком прожорливо
Отличный вариант. Да и прожорливого там особенно ничего нет — просто хранишь указатели/итераторы в ней на оригинальные элементы в списке.
W>но поиск происходит очень и очень часто.
А изменения насколько часты? Если их мало, а исходный список вообще никак трогать не хочется, то заводи параллельный вектор из указателей на элементы списка: его сортируй и по нему ищи. Дополнительной памяти совсем мало требуется, а стоимость поддержания сортированности будет мала, если изменения исходного списка будут редки.
W>и трудно поддерживать синхронизацию, по-моему.
Чтобы было легко — заверни в контейнер и работай через него.
Например, посмотри на boost::multi_index — там и список и словарь можно поднять над одними данными.
W> Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?
Ну если тебе не нужно операций и свойств, которые специфичны для списков, вроде splice за O(1) или персистентности итераторов, то вектор часто лучше.