Неасимптотическая оптимизация параллельного бинпоиска

Правка ru2, от green_gold_dog, 2023-02-15 19:32:44

Сегодня я придумал такую оптимизацию: если сейчас запрос сведён к [l, r], то можно брать за mid не (l + r) / 2, а l + (r — l) / 3, то есть треть отрезка. Тогда если ответ в этом запросе окажется в первой трети, то мы уменьшились в 3 раза, а не в 2, что очевидно лучше. Если же ответ окажется в другой части, то мы уменьшимся всего на 1/3, но тогда позже мы пройдёмся по новому mid этого запроса в той же итерации, и тогда мы сократимся ещё хотя-бы на 1/3. В таком случае останется как максимум 2/3*2/3=4/9 (даже меньше, т.к. в этом случае мы опять его сократим на этой итерации) части запроса, что меньше 1/2, то есть количество итерации сократится. Это должно достаточно часто ускорять решение. Ещё можно попробовать брать не треть, а допустим четверть, пятую или две пятых отрезка.

Теги параллельный бинпоиск

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский green_gold_dog 2023-02-15 19:32:44 0 Мелкая правка: ' а l + (r — l) / 3, т' -> ' а l + (r - l) / 3, т'
ru1 Русский green_gold_dog 2023-02-15 19:30:28 843 Первая редакция (опубликовано)