Быстрый поиск подходящего значения

[Igors]

Добрый день

Есть двухсвязный список каждый элемент которого имеет целое значение (ключ).  Задача: как можно быстрее найти любой элемент со значением меньше заданного порога N. Список может меняться от одного поиска ко другому, однако N (порог) может только увеличиваться при следующем поиске.  

Критично по скорости, так что "no containers/STL etc. please"

Спасибо

[SimpleSunny]

А список как заполняется?
Может стоит на этапе заполнения попутно искать такой элемент.

[Igors]

А список как заполняется?
Может стоит на этапе заполнения попутно искать такой элемент.

Так и было  (это подзадача для "потокобезопасного кэша"). На 1 нитке действительно все Ок. как только обращаемся к элементу кэша, пере-линкуем его в голову списка. Это стандартная реализация LRU кэша (и Qt тоже). Однако с 2 и более нитками такая перелинковка требует блокировки, и это обходится очень дорого при интенсивном использовании кэша. Прямой перебор значительно быстрее, вот как бы его маленько улучшить?

[alexman]

Не знаю правильно ли я понял, но можно попробовать хранить индекс, а при добавлении элемента перестраивать индекс. Ну а далее поиск займет O(log(длина списка)).

[Igors]

Не знаю правильно ли я понял, но можно попробовать хранить индекс, а при добавлении элемента перестраивать индекс. Ну а далее поиск займет O(log(длина списка)).

Неправильно. В списке нет индекса, просто каждый элемент указывает на следующий (и предыдущий). "Перестраивать при добавлении" не катит по причинам изложенным в #2

[alexman]

Не знаю правильно ли я понял, но можно попробовать хранить индекс, а при добавлении элемента перестраивать индекс. Ну а далее поиск займет O(log(длина списка)).

Неправильно. В списке нет индекса, просто каждый элемент указывает на следующий (и предыдущий). "Перестраивать при добавлении" не катит по причинам изложенным в #2

Так что нельзя организовать индекс-сортировку в отдельном контейнере?

[Igors]

Так что нельзя организовать индекс-сортировку в отдельном контейнере?

Муля, не нервируй меня

В теме ясно сказано "крытычно по скорости"

[Waryable]

Однако с 2 и более нитками такая перелинковка требует блокировки, и это обходится очень дорого при интенсивном использовании кэша. Прямой перебор значительно быстрее...

Здесь у меня взникает вопрос: получается, что во время перебора последовательности изменение самой последовательности не критично? Иначе перебор сам потребует блока.

[Igors]

Здесь у меня взникает вопрос: получается, что во время перебора последовательности изменение самой последовательности не критично? Иначе перебор сам потребует блока.

Допускается любое изменение изменение порядка данных в списке (но не их удаление/добавление/изменение). Прелесть "списка" в том что он позволяет делать перестановки без всяких доп. блоков.

Первое что приходит в голову: "а давайте сначала пройдемся по всему списку и все подходящие элементы перенесем в начало - и тогда на следующих запросах уже будем просто подряд брать"

Но так не проходит  Подходящих может быть очень мало, и молотьба по всему списку в минус. Да и ключи подходящих могут "подрасти" к следующему запросу - и они уже будут "неподходящими"

[Waryable]

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

[Igors]

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

Выше уже говорилось откуда растут эти ноги    http://www.prog.org.ru/index.php?topic=16223.msg108905#msg108905

Порог N есть mAccessTotal (общее число обращений к кэшу), а ключ есть mAccessCount (член страницы, номер последнего к ней обращения)