Последовательный поиск

Последовательный поиск — поиск в конечном линейном списке с последовательным доступом. Такой список представляет собой итератор. Сразу же с порога коллизия в терминологии. Здесь важно, что мы можем двигаться только вперед (в некоторых экзотических случаях и назад), но произвольного доступа у нас нет. То есть мы не можем вытащить элемент с конкретным номером.

Пусть у нас есть итератор из ключей $K_1, K_2, \dotsc, K_n$ (на их структуру нам пока наплевать). Нам нужно понять, есть ли в этом наборе ключ $t$ , и, если он есть, найти его номер.

Банальная идея «начать с начала и искать, пока не найдешь» не так уж и плоха. Код, реализующий этот подход

function search(iterable x, target) -> bool:
    for index, element of enumerate(x):
        if element == target:
            return index
    return not found

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

Понятно, что такой алгоритм работает за время $O(n)$ .

Показатель времени работа такого алгоритма — количество проверок (сравнений) $C$ . Если позиция целевого элемента равновероятно может равняться любому числу от $1$ до $n$ , то ожидаемое количество проверок

\expect C = \sum\limits_{i=1}^n i \cdot \prob(i) = \frac{1}{n} \sum\limits_{i=1}^n i = \frac{n+1}{2}

Упорядоченная последовательность

Пусть все элементы нашего итератора упорядочены, то есть $x_j > x_i$ для $j > i$ .

Мы хотим найти элемент $t$ и его позицию. Если на какой-то итерации $i$ элемент $x_i$ оказался больше $t$ , то дальше продолжать смысла нет: из-за упорядоченности итератора все остальные

function search(iterable x, target):
    for index, element of enumerate(x):
        if element == target:
            return index
        if element > target:
            return not found

    return not found

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

Частота обращений

Возвращаемся к неупорядоченным итераторам aka линейным спискам с последовательным доступом.

Мы предполагали, что все аргументы последовательного поиска равновероятны. Вообще это не так. Распределение вероятностей может быть любым.

Пусть вероятность запроса на поиск ключа $K_j$ равна $p_j$ . И пусть ответ на наш запрос всегда есть, то есть искомый элемент точно в итераторе.

\sum\limits_{j=1}^n p_j = 1

Математическое ожидание количества проверок в алгоритме последовательного поиска равно

\expect C = \sum\limits_{j=1}^n j \cdot p_j

Количество сравнений $\expect C$ не может быть больше энтропии.

Пусть есть какое-то «идеальное» распределение вероятностей $q_1, q_2, \dotsc, q_n$

Если нам подвластна структура итератора, то минимальное ожидаемое время работы достигается при

p_1 \ge p_2 \ge \dotsb \ge p_n

То есть, нам нужно переупорядочить элементы так, чтобы вероятности запроса на них убывали.

Вообще, это все немного противоречит самой концепции итераторов, но допустим, что мы с самого начала определяем структуру итератора, а потом этим пользуемся.

Распределение Зипфа

Более типично для реальных ситуаций распределение Зипфа:

p_1 = \frac{1}{H_n} \quad p_2 = \frac{1}{2 H_n} \quad \cdots \quad p_j = \frac{1}{j H_n} \quad \cdots \quad p_n = \frac{1}{n H_n}

Джордж Кингсли Зипф (George Kingsley Zipf), изучая статистические закономерности в естественных языках, обнаружил, что $n$ -е по частоте слово встречается с частотой, примерно обратно пропорциональной $n$ .

По этому распределению $p_i = c/j$ . Осталось найти константу из условия нормировки

\sum\limits_{j=1}^n p_j = 1 \implies c \cdot H_n = 1 \implies c = \frac{1}{H_n}

При таком распределении ожидаемое количество сравнений

\expect C = \frac{n}{H_n} \sim \frac{n}{\ln n}

Получается, что это почти в $\ln n / 2$ раз быстрее, чем при предположении о равномерном распределении.

Распределение Парето

Еще более близкое к реальному распределение Парето (наиболее известное как правило 80-20), которое на самом деле возникло в процессе изучения спроса и транзакций. Человеческим языком его можно сформулировать так «80% транзакций работают с 20% данных».

Коротко, можно записать это распределение (с упорядоченными вероятностями) формулой

\frac{p_1 + p_2 + \dotsb + p_{\lfloor 0.2 \cdot n \rfloor}}{p_1 + p_2 + \dotsb + p_m} = 0.8

На практике, значения 20% и 80% могут чуть-чуть отличатся, поэтому целесообразно ввести коэффициент

\theta = \frac{\log 0.8}{\log 0.2}

Из формулы-определения следуют формулы для вероятностей в терминах коэффициента $\theta$

p_1 = \frac{1}{n^\theta} \quad p_2 = \frac{2^\theta - 1}{n^\theta} \quad \cdots \quad p_j = \frac{j^\theta - (j-1)^\theta}{n^\theta} \quad \cdots \quad p_n = \frac{n^\theta - (n-1)^\theta}{n^\theta}

Теперь можно найти ожидаемое количество сравнений

\expect C = \sum\limits_{j=1}^n j \cdot \frac{j^\theta - (j-1)^\theta}{n^\theta} = \frac{1}{n^\theta} \sum\limits_{j=1}^n j \cdot \big( j^\theta - (j-1)^\theta \big) = n + 1 - \frac{1}{n^\theta} \sum\limits_{j=1}^n j^\theta

Используя асимптотическую оценку суммы $\sum\limits_{j=1}^n j^\theta \sim n^{\theta+1} / (\theta+1) + n^\theta/2 + O(n^{\theta-1})$ получаем, что

\expect C = n + 1 - \frac{1}{n^\theta} \sum\limits_{j=1}^n j^\theta = \frac{\theta}{\theta+1} \cdot n + \frac{1}{2} + O \left( \frac{1}{n} \right)

Результат довольно хороший. При коэффициенте $\theta = \log_{0.2}{0.8} \approx 0.139$ количество сравнений оценивается по только что выведенной формуле как $0.5 + 0.122037 \cdot n$ .

Несмотря на немного разную грубость в оценках по Зипфу и по Паретто, распределение Паретто выигрывает у распределение Зипфа примерно до значения $n = 3586$ .

Самоорганизующийся список

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

Можно для каждой записи в списке хранить счётчик обращений к ней, и на основе значений этих счётчиков переупорядочивать записи. Вариант конечно рабочий, но эту дополнительную память лучше потратить на реализацию нелинейных методов поиска. Можно ли реализовать самоорганизовывающийся список без дополнительной памяти? Можно.

Идея довольно простая: после обращения к какой-то записи перемещать её в начало списка. В результате наиболее часто используемые записи окажутся в начале списка. Эта эвристика называется «move to front» (MTF)

Пусть вероятность запроса на поиск ключа $R_j$ равна $p_j$ . Тогда в предельное среднее число сравнений, совершаемых при поиске ключа, равно

\expect C = 1 + 2 \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{p_i \, p_j}{p_i + p_j}

Пусть $f_m (x_1, x_2, \dotsc, x_m)$ равно бесконечной сумме всех различных упорядоченных произведений $x_{i_1}, x_{i_2}, \dotsc, x_{i_k}$ , для которых $1 \le i_1, i_2, \dotsc, i_k \le m$ , причём каждая из переменных $x_1, x_2, \dotsc, x_m$ входит во все произведения.

Например,

f_2 (a, b) = \sum\limits_{i=0}^\oo \sum\limits_{j=0}^\oo \, \bigl( a^{i+1} \cdot b \cdot (a+b)^j + b^{i+1} \cdot a \cdot (a+b)^j \bigr)

f_3(a, b, c) = \sum\limits_{i=0}^\oo \sum\limits_{j=0}^\oo \sum\limits_{k=0}^\oo \, \bigl( a^{i+1} b^{j+1} c + a^{i+1} c^{j+1} b + b^{i+1} a^{j+1} c + b^{i+1} c^{j+1} a + c^{i+1} a^{j+1} b + c^{i+1} b^{j+1} a \bigr) \cdot (a+b+c)^k

Вообще, общая формула

\align{ f_m(x_1, x_2, \dotsc, x_m) &= \sum\limits_{\sigma \;\! \in \;\! \S_m} \, \sum\limits_{i_1=0}^\oo \sum\limits_{i_2=0}^\oo \dotsi \sum\limits_{i_{m-1}=0}^\oo \, \sum\limits_{k=0}^{\oo} x_{\sigma(1)}^{i_1+1} \cdot x_{\sigma(2)}^{i_2+1} \dotsm x_{\sigma(m-1)}^{i_{m-1}+1} \cdot x_{\sigma(m)} \cdot (x_1 + x_2 + \dotsc + x_m)^k \\ &= \frac{1}{1-\sum\limits_{k=1}^m x_k} \cdot \sum\limits_{\sigma \;\! \in \;\! \S_m} \, \Biggl( \prod\limits_{k=1}^{m-1} \frac{x_{\sigma(k)}}{1-x_{\sigma(k)}} \Biggr) \cdot x_{\sigma(m)} }

Пусть $X = \{x_1, x_2, \dotsc, x_n\}$ — множество из $n$ переменных. Определим

P_{n,~ m}(X) = \sum\limits_{1 \;\! \le \;\! j_1 < j_2 < \dotsb < j_m \le n} f_m (x_{j_1}, x_{j_2}, \dotsc, x_{j_m}) \quad\text{и}\quad Q_{n,~ m}(X) = \sum\limits_{1 \;\! \le \;\! j_1 < j_2 < \dotsb < j_m \le n} \frac{1}{1 - x_{j_1} - x_{j_2} - \dotsb - x_{j_m}}

Здесь $P_{n,~ m}(X)$ — сумма $f_m$ по всем $m$ -элементным подмножествам $X$ , $Q_{n,~ m}(X)$ — сумма $1 \Big/ \Bigl( 1 - \sum\limits_{k=1}^m x_{j_k} \Bigr)$ по тем же подмножествам $X$ , и $P_{n,~ 0}(X) = Q_{n,~ 0}(X) = 1$ по определению.

Пусть мы достаточно долго работаем с нашим самоорганизующимся списком. Длина списка $n$ . Тогда элемент $R_j$ будет находиться на позиции $m$ с предельной вероятностью

\prob(R_j ~\text{находится на позиции}~ m) = p_j \cdot P_{n-1,~ m-1} \bigl( \{p_1, p_2, \dotsc, p_{j-1}, p_{j+1}, p_{j+2}, \dotsc, p_n\} \bigr)

$P_{n-1,~ m-1}(X)$ — сумма $f_{m-1}$ по всем $(m-1)$ -элементным подмножествам $X$ , то есть по всем наборам из $m-1$ других элементов.

Предельная вероятность того, что $R_j$ находится на $m$ -м месте равна вероятности того, что непосредственно перед $R_j$ в списке находятся какие-то $m-1$ других элементов, причём порядок этих $m-1$ элементов соответствует тому, что они были запрошены после последнего запроса $R_j$ в определённом порядке.

Функция $f_m(\cdots)$ как раз перечисляет все последовательности запросов к этим $m-1$ элементам, в которых каждый из них встречается, и которые могли привести к тому, что они оказались перед $R_j$ в момент перед запросом $R_j$ .

Просуммировав этот факт для $m = 1, 2, \dotsc, n$ , получаем тождество

P_{n,~ n} + P_{n,~ n-1} + P_{n,~ n-2} + \dotsb + P_{n,~ 1} + P_{n,~ 0} = Q_{n,~ n}

Отсюда можно получить следующие тождества

P_{n,~ m} + \binom{n-m+1}{1} \cdot P_{n,~ m-1} + \dotsb + \binom{n}{m} \cdot P_{n,~ 0} = \sum\limits_{k=0}^m \binom{n-m+k}{k} \cdot P_{n,~ m-k} = Q_{n,~ m}

Q_{n,~ m} - \binom{n-m+1}{1} \cdot Q_{n,~ m-1} + \dotsb + (-1)^m \binom{n}{m} \cdot Q_{n,~ 0} = \sum\limits_{k=0}^m (-1)^k \binom{n-m+k}{k} \cdot Q_{n,~ m-k} = P_{n,~ m}

Следствие всех этих равенств и определений — важная формула

\sum\limits_{m=0}^n m \cdot P_{n,~ m} = n \cdot Q_{n,~ n} - Q_{n,~ n-1}

Вернёмся к нашему элементу $R_j$ . Найдем предельное среднее расстояние от $R_j$ до начала списка.

d_j = \sum\limits_{m=1}^n m \cdot \prob(R_j ~\text{находится на позиции}~ m) = \sum\limits_{m=1}^n m \cdot p_j \cdot P_{n-1,~ m-1} \bigl( \{p_1, p_2, \dotsc, p_{j-1}, p_{j+1}, p_{j+2}, \dotsc, p_n\} \bigr)

Применяем важную формулу и вычисляем

d_j = n - p_j \cdot \sum\limits_{\substack{1 \;\! \le \;\! i \le n \\ i \;\! \neq \;\! j}} \frac{1}{p_i + p_j}

Отсюда искомое предельное среднее количество сравнений

\expect C = \sum\limits_{j=1}^n p_j d_j = n - \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{p_i^2 + p_j^2}{p_i + p_j} = n - \sum\limits_{1 \;\! \le \;\! i < j \le n} \left(p_i + p_j - \frac{2 p_i p_j}{p_i + p_j} \right) = 1 + 2 \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{p_i \, p_j}{p_i + p_j}

Эвристика «Move to Front» — не просто академическое упражнение. Она лежит, например, в основе алгоритмов адаптивного сжатия (например, Burrows-Wheeler в bzip2), где частота символов пересчитывается на лету, или например в стратегиях кэширования, таких как Adaptive Replacement Cache.

Упражнения

Пусть все ключи последовательного поиска равновероятны. Найдите среднеквадратичное отклонение количества сравнений при успешном поиске в линейном списке с $n$ записями.

Вычислите среднее число сравнений при поиске в самоорганизующемся списке, если распределение ключей поиска

бинарное распределение, то есть $p_j = 1/2^j$ при $1 \le j < n$ и $p_n = 1/2^{n-1}$

Ответ

Нам нужно подставить значения $p_j$ в формулу $\expect C$ . Здесь $p_j = 1/2^j$ при $1 \le j < n$ и $p_n = 1/2^{n-1}$ .
$1 + 2 \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{p_i \, p_j}{p_i + p_j}$
Весь прикол задачи в вычислении суммы
$\sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{p_i \, p_j}{p_i + p_j}$
Я могу приблизить эту сумму другой суммой, с более удобными значениями с точностью до $O(n/2^n)$
$\sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{p_i \, p_j}{p_i + p_j} = \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{2^i + 2^j} + O \left(\frac{n}{2^n}\right)$
Составляем рекуррентное соотношение и получаем следующее равенство
$\sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{2^i + 2^j} = \left( \sum\limits_{k=1}^{n-1} \frac{1}{1+2^k} \right) \cdot \left( 1 + \frac{1}{2^n} \right) - \frac{n-1}{2^n}$

В итоге нам нужно посчитать, чему равно значение суммы
$\sum\limits_{k=1}^n \frac{1}{1+2^k}$
Используем $q$ -полигамма функцию
$\psi_q (z) = - \ln (1-q) + \ln q \cdot \sum\limits_{j=0}^\oo \frac{q^{j+z}}{1-q^{j+z}} \quad\text{при}~ 0 < q < 1$
Отсюда
$\sum\limits_{j=0}^{n-1} \frac{q^{j+z}}{1-q^{j+z}} = \frac{\psi_q (z) - \psi_q (z+n)}{\ln q}$

Пусть $q = 1/2$ . Тогда
$\sum\limits_{k=1}^n \frac{1}{1+2^k} = \sum\limits_{k=1}^n \frac{1}{1+q^{-k}} = \sum\limits_{k=1}^n \frac{q^k}{1+q^k}$
Разобьем искомую сумму на две
$\sum\limits_{k=1}^n \frac{q^k}{1+q^k} = \sum\limits_{k=1}^n \frac{q^k}{1-q^k} - 2 \sum\limits_{k=1}^n \frac{q^{2k}}{1-q^{2k}}$
Теперь, из представления $q$ -полигамма функции,
$\align{ \sum\limits_{k=1}^n \frac{q^k}{1-q^k} &= \sum\limits_{j=0}^{n-1} \frac{q^{j+1}}{1-q^{j+1}} = \frac{\psi_q (1) - \psi_q (1+n)}{\ln q} \\ \sum\limits_{k=1}^n \frac{q^{2k}}{1-q^{2k}} &= \sum\limits_{j=0}^{n-1} \frac{q^{2(j+1)}}{1-q^{2(j+1)}} = \frac{\psi_{q^2} (1) - \psi_{q^2} (1+n)}{\ln q^2} }$
Подставляем и получаем ответ
$\sum\limits_{k=1}^n \frac{q^k}{1+q^k} = \frac{\psi_q (1) - \psi_{q^2} (1) + \psi_{q^2} (1+n) - \psi_q (1+n)}{\ln q}$
Значит, для нашего случая, где $q=1/2$ , сумма равна
$\sum\limits_{k=1}^n \frac{1}{1+2^k} = \frac{\psi_{1/4} (1) - \psi_{1/4} (1+n) - \psi_{1/2} (1) + \psi_{1/2} (1+n)}{\ln 2}$

Теперь подставим в формулу суммы и получим точный ответ. Обращаю внимание на то, что в изначальном выражении сумма $\sum\limits_{k=1}^{n-1} \frac{1}{1+2^k}$ , а не $\sum\limits_{k=1}^n \frac{1}{1+2^k}$
$\align{ \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{p_i \, p_j}{p_i + p_j} &= \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{2^i + 2^j} + O \left( \frac{n}{2^n} \right) = \left( \sum\limits_{k=1}^{n-1} \frac{1}{1+2^k} \right) \cdot \left( 1 + \frac{1}{2^n} \right) - \frac{n-1}{2^n} + O \left( \frac{n}{2^n} \right) = \\ &= \frac{\psi_{1/4} (1) - \psi_{1/4} (n) - \psi_{1/2} (1) + \psi_{1/2} (n)}{\ln 2} \cdot \left( 1 + \frac{1}{2^n} \right) - \frac{n-1}{2^n} + O \left( \frac{n}{2^n} \right) }$
В пределе при $n \to \oo$ получим $\approx 0.7645$ .

Умножаем на $2$ , прибавляем $1$ и получаем ответ $2.529$ .
распределение Зипфа, то есть $p_j = 1/j H_n$ при $1 \le j \le n$

Ответ

Нам нужно подставить значения $p_j$ в формулу $\expect C$ . Здесь $p_j = 1/j \, H_n$ .
$1 + 2 \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{p_i \, p_j}{p_i + p_j} = 1 + \frac{2}{H_n} \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{i+j}$
Весь прикол задачи в вычислении суммы
$\sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{i+j}$
Рассмотрим сумму по всем парам
$\sum\limits_{i=1}^n \sum\limits_{j=1}^n \frac{1}{i+j} = 2 \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{i+j} + \sum\limits_{k=1}^n \frac{1}{2k} = 2 \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{i+j} + \frac{H_n}{2}$
Найдя значение суммы по всем парам мы найдём значение исходной суммы.

Пусть $s = i + j$ . Тогда $s$ меняется от $2$ до $2n$ . Теперь посмотрим, сколько пар $(i, j)$ дают данное значение $s$ . Если $s \le n+1$ , то $i$ может принимать любые значения от $1$ до $s-1$ , всего $s-1$ штук. Если $s > n+1$ , то $i$ может принимать любые значения от $s-n$ до $n$ , всего $2n-s+1$ штук.
$\sum\limits_{i=1}^n \sum\limits_{j=1}^n \frac{1}{i+j} = \sum\limits_{s=2}^{n+1} \frac{s-1}{s} + \sum\limits_{s=n+2}^{2n} \frac{2n-s+1}{s}$
Вычисляем сумму
$\sum\limits_{i=1}^n \sum\limits_{j=1}^n \frac{1}{i+j} = (n + 1 - H_{n+1}) + \bigl( - (n - 1) + (2n + 1) \cdot (H_{2n} - H_{n+1}) \bigr) = (2n+1) \, H_{2n} - (2n+2) \, H_n$

Теперь можно подставить и получить значение исходной суммы
$\sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{i+j} = \frac{1}{2} \cdot \left( \sum\limits_{i=1}^n \sum\limits_{j=1}^n \frac{1}{i+j} - \frac{H_n}{2} \right) = \frac{1}{2} \cdot \left( (2n+1) \, H_{2n} - (2n+2) \, H_n - \frac{H_n}{2} \right)$
Тогда ответ на задачу будет
$1 + \frac{2}{H_n} \sum\limits_{1 \;\! \le \;\! i < j \le n} \frac{1}{i+j} = 1 + \frac{1}{H_n} \cdot \left( (2n+1) \, H_{2n} - (2n+2) \, H_n - \frac{H_n}{2} \right) = \frac{(2n+1) \, H_{2n}}{H_n} - 2n - \frac{3}{2}$
распределение Парето, то есть $p_j = \bigl( j^\theta - (j-1)^\theta \bigr)/n^\theta$ при $1 \le j \le n$

Даны две невозрастающие последовательности чисел $x_1, x_2, \dotsc, x_n$ и $y_1, y_2, \dotsc, y_n$ .

Какая перестановка $\sigma \in \S_n$ делает сумму произведений $\sum\limits_{j=1}^n x_j \, y_{\sigma(j)}$ максимальной? А какая минимальной?

У нас есть $n$ условий, одновременное выполнение которых нужно проверить. Ну то есть нужно посчитать конъюнкцию всех $n$ условий. Понятно, что начав с начала, и дойдя до какого-то ложного условия, можно дальше не продолжать проверку.

Мы знаем, что проверка $j$ -го условия выполняется за время $T_j$ , и что это условие выполняется с вероятностью $p_j$ . Эта вероятность не зависит от результата проверки других условий. В каком порядке нужно проверять условия?

Нам нужно выполнить $n$ заданий. Выполнение $j$ -го задания занимает время $T_j$ . Крайний срок выполнения $j$ -го задания $D_j$ , то есть это задание нужно выполнить не позднее момента времени $D_j$ .

Какое расписание работ $a_1, a_2, \dotsc, a_n$ минимизирует максимальное опоздание, то есть величину

\max\limits \bigl( T_{a_1} - D_{a_1},~ T_{a_1} + T_{a_2} - D_{a_2},~ \dotsc,~ T_{a_1} + T_{a_2} + \dotsb + T_{a_j} - D_{a_j},~ \dotsc,~ T_{a_1} + T_{a_2} + \dotsb + T_{a_n} - D_{a_n} \bigr)