Mx21
@Mx21
Software engineer

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

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

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

Я думаю, решать это с помощью бинарного поиска, может что-то есть эффективнее? Если, важно, то задачу буду решать на js.
  • Вопрос задан
  • 165 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Чтобы сделать бинарный поиск, вам нужен массив объектов с ценами и названиями. Что-то вроде
[1=>{cost:1, name:"name1"} .... 117=>{cost:55233, name:"name555"}]
(не уверен, что правильно описал на js).

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

Можно поискать какие-нибудь js библиотеки с нормальным ассоциативным массивом, который это умеет.
Будет также работать за логарифм.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Максим, всё просто.
Всегда держите актуальную кривую распределения "интервал-количество". Создаёте и обновляете её по мере поступления новых данных. Это называется итеративной сегментацией данных.
Поиск в меньшую сторону выполняете сразу с нужного сегмента, смещаясь влево на один интервал: ищите только в нём.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы