Оптимизация массива, который имеет много элементов и разных стандартов

Question

У меня есть функция, которая принимает X в качестве аргумента и случайным образом выбирает элемент из 2D-массива.2D-массив содержит тысячи элементов, каждый из которых имеет свои требования к X, хранящиеся в arr[Y][1].

Например,

• arr[0] следует выбирать только в том случае, еслиX больше 4. (arr[0][1] = 4+)

• Тогда arr[33] следует выбирать только в том случае, если X находится между 37 и 59. (arr[33][1] = 37!59)

• И arr[490] следует выбирать только тогда, когда X меньше 79. (arr[490][1] = 79-)

  И есть еще много, большинство с другим требованием X.

Каков наилучший способ решения этой проблемы, который занимает наименьшее пространство и наименьшее количество повторений элементов?

Худшим способом было бы сохранение возможных вариантов для каждого X в двумерном массиве.Но это вызвало бы много повторений и стоило бы слишком много памяти.

Затем я подумал об использовании трех массивов, разделяющих требования X +, диапазон X и X.Но это все еще звучит слишком основательно для меня, есть ли лучший способ?

Answer 1

Хотя я считаю, что повторная выборка будет оптимальным решением в вашем случае (десятки повторных выборок - это очень дешевая цена), вот алгоритм, который я бы никогда не реализовал на практике (поскольку он использует очень сложные структуры данных и меньшеэффективнее, чем пересчет), но с доказуемыми границами.Для каждого запроса требуется O(n log n) время предварительной обработки, O(n log n) память и O(log n) время, где n - количество элементов, которые вы можете потенциально выбрать.

Все концы всех диапазонов хранятся в одноммассив (назовите его ends).Например, в вашем случае у вас есть массив [-infty, 4, 37, 59, 79, +infty] (может потребоваться некоторая настройка, например, добавление +1 к правым краям диапазонов; сейчас это не важно).Идея заключается в том, что для любого X нам нужно только определить, между какими концами он находится.Например, если X=62 находится в диапазоне [59; 79] (я назову такую ​​пару интервал ).Затем для каждого интервала вы сохраняете набор всех возможных диапазонов.Для ввода X вы просто находите интервал (используя бинарный поиск), а затем выводите случайный диапазон, соответствующий этому интервалу.

Как вычислить соответствующий набор диапазонов для каждого интервала?Идем слева направо в массиве ends.Давайте предположим, что мы вычислим набор для текущего интервала и перейдем к следующему.Между этими интервалами есть какой-то конец.Если это левый конец некоторого интервала, мы добавляем соответствующий диапазон в новый набор (так как мы входим в этот диапазон).Если это правильный конец, мы удаляем диапазон.Как мы можем сделать это в O(log n) времени вместо O(n)?Это могут сделать неизменные сбалансированные наборы деревьев (по сути, они создают новые деревья вместо того, чтобы модифицировать старое).

Как вы возвращаете равномерно случайный диапазон из набора?Вы должны расширить наборы деревьев: каждый узел должен знать, сколько узлов содержит его поддерево.Сначала вы выбираете целое число в диапазоне [0; size(tree)).Затем вы смотрите на свой корневой узел и его дочерние элементы.Например, предположим, что вы выбрали целое число 15, а поддерево вашего левого ребенка имеет размер 10, а у правого - 20. Затем вы переходите к правому дочернему элементу (начиная с 15 >= 10) и обрабатываете его с целым числом 5 (начиная с 15 - 10 = 5).).Вы в конечном итоге посетите лист, соответствующий одному диапазону.Верните этот диапазон.

Извините, если это трудно понять.Как я уже сказал, это не тривиальный подход, который вам понадобится для верхних границ в худшем случае (другие обсуждаемые ранее подходы требуют линейного времени в худшем случае; повторная выборка может выполняться неопределенное время, если нет элемента, удовлетворяющего ограничениям).Это также требует осторожного обращения (например, когда некоторые диапазоны имеют совпадающие конечные точки).

Answer 2

Одним из вариантов здесь будет то, что называется «принять / отклонить выборку»: вы выбираете случайный индекс i и проверяете, удовлетворяется ли условие для X для этого индекса.Если это так, вы возвращаете arr [i] .Если нет, вы выбираете другой индекс случайным образом и повторяете, пока не найдете что-то.

Производительность будет хорошей, если большинство условий удовлетворяются для большинства значений i .Если это не так - если существует множество значений X , для которых удовлетворяется лишь небольшое количество условий, - тогда может иметь смысл попытаться предварительно вычислить что-то, что позволит вам найти(или сузить) индексы, которые допустимы для данного X .

Как это сделать, зависит от того, что вы разрешаете в качестве условия для каждого индекса.Например, если каждое условие задается интервалом, как в приведенных вами примерах, вы можете отсортировать список дважды, сначала по левым конечным точкам, а затем по правым конечным точкам.Затем определение действительных индексов для определенного значения X сводится к пересечению интервалов, левая конечная точка которых меньше или равна X, с теми, чья правая конечная точка больше или равна X.

Конечно, если выразрешите условия, отличные от «X находится в этом интервале», тогда вам потребуется другой алгоритм.