Сообщение Re: Можно ли оптимизировать std::list для поиска? от 18.02.2016 11:20
Изменено 18.02.2016 11:20 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) или персистентности итераторов, то вектор часто лучше.
Здравствуйте, 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) или персистентности итераторов, то вектор часто лучше.