# BusyNumeric

class BusyNumeric {}

Description:
More optimal search of numbers satisfying the condition

Представьте отель. По условиям задачи каждый номер может быть выбран с одинаковой вероятностью, но выбранный номер может быть занят и тогда продолжаем поиск.

Рассматриваем два случая:

1. Отель, в котором девяносто девять номеров заняты и один — свободен;
2. Отель, в котором один номер занят и девяносто девять — свободны.

Классические способы поиска свободного отеля:

1. Отфильтровать номера, а после среди них выбрать случайный;
2. Выбирать номер и проверять удовлетворяет ли он условиям.

Почему фильтровать не эффективно: нам потребуется обойти весь отель и проверить каждый номер.

Почему подходить к случайному номеру не эффективно: проблема возникает в худшем случае. Когда свободен только один номер, в среднем мы пройдемся по каждому номеру по сто раз, прежде чем дойдем до свободного номера. Сложность алгоритма: O(n²).
Просмотренные номера эффективно записываются и не проходят фильтр дважды, но количество операций проверки: записан ли он — не уменьшается

Касательно формулировки задачи. Есть реальный пример, где несколько ячеек заняты, а остальные свободны — змейка, генерируем еду везде, где ничего не находится. Там вариант с выбором случайной точки очень хорошо отрабатывает.

BusyNumeric учитывает эти две особенности. Работает в среднем в два раза быстрее, если совмещать худший и лучший случаи

В общем весело
Работает всего в несколько шагов:

• Выбираем случайный сегмент, а в нем случайный элемент

• Если соответствует условию, возвращаем элемент. Завершаем поиск

• Иначе исключаем элемент путем раздвоения текущего сегмента так, чтобы элемент не оказался ни в одном сегменте общего списка

• Повторяем

• Проводилось около тридцати запусков стратегий «фильтровать всё» и «разделять на сегменты» в худшем и лучшем сценариях: все элементы не удовлетворяют условию и все — удовлетворяют. Списки состояли из 10_000 элементов и выполняли работу по созданию массива из 1_000 элементов. Всего вышло четыре конфигурации по тридцать запусков. Разброс времени выполнения существенный, но соотношение оставалось стойким.
• Как и ожидалось, производительность при пустом фильтре уступает: в среднем до трех раз (усредненно для двух сценариев) — преймущество алгоритма зависит от сложности производимой работы для каждого элемента. А также от процента удовлетворяющих элементов. От их количества результат не зависит. Что стало лично для меня неожиданностью — при значимом увеличении сложности работы: по созданию массивов до 10_000-го размера, — преймущество алгоритма преуменьшалось. Видимо относительно малый объем накладных расходов на работу алгоритма накапливался в условиях торможения Node.js процесса.
• Производилась ещё контрольная серия запусков. В которых а) результат фильтра hard_operation был непредсказуем и зависел от случайности. Алгоритм проходил все элементы, а не останавливался на первом удовлетворяющем; б) без внешнего эффекта hard_operation: для 100_000 элементов разница достигает тысячи раз (~ 3мс:3000мс) — это для абсолютного фильтра-пустышки (команда создания большого массива сохранялась).
  Проверялось изменится ли соотношение. — Cлучайный возвращаемый результат фильтра не влияет на результат; аннулирование внешних эффектов позволило движку оптимизировать .filter и, в меньшей степени, BusyNumeric. Однако, этот пример является полностью синтетическим.

// Чтобы убрать внешний эффект, закомментируйте участок `globalThis[my_symbol] =`
const hard_operation = (satisfies: boolean) => (item, index) => {
    const my_symbol = Symbol(`${item}_${index}`);
    globalThis[my_symbol] = [...new Array(HARD_OPERATION_MULTIPLIER)];
    return satisfies; /* Math.random() >= 0.5 */
}

Итого, когда всё «лагает» и у вас наихудший случай, избегайте этого алгоритма как огня. Однако уже задаче создания массива из 20-ти элементов среднее время выполнения для обоих случаев выравнивается. Худший случай остается в пользу стратегии фильтра. Этот алгоритм ещё можно пробовать оптимизировать: а) использовав структуру бинарного дерева для так называемых диапазонов (набор занятых пространств на основе которых быстро вычисляются сегменты); б) избегая вставки диапазонов до того, как потребуется пересчитать сегмент. Например, рассматривая левую часть, нам не нужно пересчитывать правую. Сейчас эти оптимизации не применются, так как они значительно усложнят код. Если они потребуются независимо от языка программирования, оставьте issue (отчёт об аспекте чего-либо) к репозиторию проекта.

- this.busy_areas.findLastIndex((area) => end > area[1]) + 1;

+ binary_search(this.busy_areas.length - 1, (index: number) => {
+	 const value = this.busy_areas[index]?.[1];
+	 const biggest = end < value;
+	 if (biggest) {
+	 	return 1;
+	 }
+	 return (
+	 	+(
+	 		(this.busy_areas[index + 1]?.[1] ?? Number.MAX_SAFE_INTEGER) > end
+	 	) - 1
+	 );
+ }) + 1;

~ + 15% производительности на тестах без тяжелой работы и теми же 10_000 элементами

const hotel = new BusyNumeric(12);
hotel.bifurcate(7);
hotel.bifurcate(0);
hotel.bifurcate(1);
hotel.bifurcate(2);
hotel.bifurcate(3);

expect(hotel.range).toBe(12);
expect(hotel.peak_start_busy).toBe(true);
expect(hotel.peak_end_busy).toBe(false);
expect(hotel.segments_count()).toBe(2);
expect(hotel.segment(0)).toStrictEqual({
    size: 3,
    left: [0, 3],
    right: [7, 7],
});
expect(hotel.segment(1)).toStrictEqual({
    size: 5,
    left: [7, 7],
    right: undefined,
});
expect(hotel.segment(3)).toBe(undefined);
expect(hotel.busy_areas).toStrictEqual([
    [0, 3],
    [7, 7],
]);

const hotel = new BusyNumeric(10_000);
while (true) {
  if (!hotel.segments_count()) {
    break;
  }
  const { left, size } = hotel.segment(random(hotel.segments_count() - 1))!;
  const i = (left?.[1] ?? -1) + random(size - 1) + 1;
  if (hard_operation(i)) {
    return i;
  }
  hotel.bifurcate(i);
}