Наиболее подходящий алгоритм для поиска цены?

Question

[Максим]

Здравствуйте!

Подскажите, какой алгоритм использовать или как лучше сделать. У меня есть объект/ассоциативный массив (зависит от языка) с ценами (цены с центами) в виде ключей и названием в виде текста, что-то типа: [1=>'name1', 2=>'name2'...55233=>'name555']. Цены будут отсортированы. Всего будет около 50к элементов. На вход, мне поступает цена, например 5.23 и мне среди всех ключей надо найти, либо ключ = 5.23, либо наиболее близкий в меньшую сторону.

Я думаю, решать это с помощью бинарного поиска, может что-то есть эффективнее? Если, важно, то задачу буду решать на js.

Comments

[Aetae]

В общем случае ничего эффективнее нет. В частном, если есть какие-то закономерности - можно заранее подготовить оптимизированную для поиска структуру. Но в целом если запросов будет не миллионы в секунду, то перебор 50к - это ни о чём, особо думать об оптимизации на данном этапе нет смысла.

[Максим]

Aetae, про выборки тоже думал. Есть определенная статистика, частых цен. Например, выше 200$ очень редко, чаще < 5$. Поиск будет делаться каждую секунду, одновременно будет 0-10 таких поисков. Если, подробнее. То, это что-то типа казино. Человек ставит 1$ и с каждой секундой его доллар увеличивается и исходя из значения показывается приз. И вот одновременно, там будет играть около 10 игроков и все это с сокетами. Поэтому, чтобы не было никаких задержек желательно сделать все оптимально.

[Михаил Ливач]

Насколько понимаю, ключи - это цены в виде центов ( то есть не 5.23, а 523).

В приёмах работы с Redis я подсмотрел одну идею, которая в вашем случае может выглядеть так:

let idx = prices.keys();
// затем надо вставить в этот массив элементы, кратные 100
// и отсортировать в обратном порядке , поскольку нужна равная или меньшая цена
// ...


// для цены 5.23 заведомо существующие границы - это 500 и 600
let possibleKeys = idx.slice( idx.indexOf(600), idx.indexOf(500) );
// первое из значений, которое существует как ключ в prices, и есть искомое

Конечно, это имеет смысл только в случае, когда поиск - многократный по одному набору данных

Answer 1

[Wataru]

Чтобы сделать бинарный поиск, вам нужен массив объектов с ценами и названиями. Что-то вроде

[1=>{cost:1, name:"name1"} .... 117=>{cost:55233, name:"name555"}]

(не уверен, что правильно описал на js).

Но, по идее, все нормальные языки умеют что-то вроде lower_bound для ассоциативных массивов. Именно эту функцию и надо вызвать. А дальше выбрать лучший из текущего и предыдущего или следующего элемента (в зависимости, как в вашем языке lower_bound работает).

Можно поискать какие-нибудь js библиотеки с нормальным ассоциативным массивом, который это умеет.
Будет также работать за логарифм.

Answer 2

[xmoonlight]

Максим, всё просто.
Всегда держите актуальную кривую распределения "интервал-количество". Создаёте и обновляете её по мере поступления новых данных. Это называется итеративной сегментацией данных.
Поиск в меньшую сторону выполняете сразу с нужного сегмента, смещаясь влево на один интервал: ищите только в нём.

Чем больше данных в одном сегменте, тем больше интервалов и создавайте. Это уменьшит время на поиск нужного Вам значения.