Russian Qt Forum
Декабрь 14, 2017, 18:14 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: [РЕШЕНО] Быстрый поиск ближайшего значения  (Прочитано 501 раз)
deMax
Программист
*****
Offline Offline

Сообщений: 501



Просмотр профиля
« : Август 11, 2017, 15:04 »

Как быстро найти число в массиве больше заданного? Допусти {1,10,100,150} на 15 вывести 100.
Есть QMap::lowerBound(const Key &key) вроде то что нужно, но придется хранить значения для ключей.
« Последнее редактирование: Август 14, 2017, 08:07 от deMax » Записан
Bepec
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 7591


W7 x64, Qt SDK 4.7.2, Руки v1.5


Просмотр профиля
« Ответ #1 : Август 11, 2017, 16:09 »

Ну, если массив маленький( до 10к), то проще отсортировать и пройтись.
Если массив средний, то ассоциативные контейнеры помогут.
Если массив ахренительный, то разбивать поиск по частям, параллельно.
Если данных ну просто офилиард, то загнать всё нафиг в sql и туда гонять запросы Веселый
Записан

"Мастер простых решений" Ɋt

чОрный список: Spark
m_ax
Neo
******
Offline Offline

Сообщений: 1752



Просмотр профиля
« Ответ #2 : Август 11, 2017, 20:01 »

Как быстро найти число в массиве больше заданного? Допусти {1,10,100,150} на 15 вывести 100.
Есть QMap::lowerBound(const Key &key) вроде то что нужно, но придется хранить значения для ключей.
Если предполагается, что последовательность отсортирована, то стандартный std::lower_bound, а если нет.. То да, фактически остаётся перебор
Код
C++ (Qt)
template <class InputIt>
InputIt greater_than(InputIt first, InputIt last, int val)
{
   auto it_res = std::find_if(first, last, [&](int x){ return x >= val; });
   if (it_res == last)
       return last;
 
   first = it_res;
 
   while ((first = std::find_if(++first, last, [&](int x){ return x >= val; })) != last)
   {
       if (*first <= *it_res)
           it_res = first;
   }
 
   return it_res;
}
 
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 9854


Просмотр профиля
« Ответ #3 : Август 12, 2017, 06:31 »

std изучается настолько усердно что упускается то немногое ценное что там есть  Улыбающийся Ну какое же lower_bound если больше заданного? Для этого есть std::upper_bound. Конечно в любом случае требуется сортированный массив

Да, и кстати это работает быстрее ассоциативного контейнера
Записан
deMax
Программист
*****
Offline Offline

Сообщений: 501



Просмотр профиля
« Ответ #4 : Август 14, 2017, 07:40 »

Спасибо. std::lower_bound подойдет, не знал, не пользовался  Обеспокоенный (хотя QMap::lower_bound приходилось использовать)

Массив очень маленький, просто шерстить его нужно в paintevent.
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Страница сгенерирована за 0.069 секунд. Запросов: 23.