Архитектура
Два решения через trie, одно через двоичный поиск.
Все решения используют один и тот же протокол:
make(seq)
- строит поисковую таблицу читая последовательность префиксов seq
;
prefix_len(table, s)
- возвращает длину префикса из таблицы; если префикса нет, возвращает -1;
save(table, f)
- сохраняет таблицу в файл;
load(f)
- читает таблицу из файла.
save/load
удобны для тестирования. Данных много, строить каждый раз таблицу с нуля накладно.
Тестовые данные
Алгоритмы оцениваются по времени построения таблицы, объёму получившейся таблицы на диске и в памяти, по времени одного запроса. Тестировались два разных набора префиксов: один из соседнего ответа, второй более случайный. Генератор для второго:
import itertools
import random
import sys
s = int(sys.argv[1])
n = int(sys.argv[2])
p = float(sys.argv[3])
b = int(sys.argv[4])
random.seed(s)
while b > 0:
for c in itertools.product('0123456789', repeat=n):
if b <= 0:
break
if random.random() < p:
print(''.join(c))
b -= len(c)
n += 1
Этот код порождает префиксы с общим числом символов около 150 миллионов:
$ python gen-random-prefixes.py 42 2 0.25 150_000_000
01
03
07
09
10
12
13
16
19
23
...
65427578
65427584
65427589
65427590
65427591
65427592
65427595
65427598
65427599
65427601
Миллион запросов порождает этот код:
import itertools
import random
import sys
s = int(sys.argv[1])
n1 = int(sys.argv[2])
n2 = int(sys.argv[3])
k = int(sys.argv[4])
random.seed(s)
for _ in range(k):
n = random.randrange(n1, n2)
print(''.join(random.choices('0123456789', k=n)))
$ python gen-random-requests.py 4242 7 11 1000000
1632504174
1131266
90208566
3316448741
94987864
41454832
0375100555
749931845
5314923
151098151
...
69074190
97368304
8460381
8414310892
9293950
184240618
7116417498
162559013
787488982
297770516
Решения
Универсальное trie
Trie - дерево, каждый узел словарь словарей: {символ: словарь для поддерева}. Нам интересны не любые префиксы, а только те что попадают в строку полностью. Например: префикс 44 не соответствует строке 456. Они совпадают по первому символу, но это не подходит. Поэтому в словарях специально помечены символы, которые завершают префикс: в словаре для этих символов храниться ключ - пустая строка.
Trie строится за линейное время от общего числа символов в префиксах. Поиск префикса для строки делается за длину строки. Сложность обозначим O(N); O(r) где N - число символов во всех префиксах, r - длина строки в запросе.
def make(seq):
trie = {}
for s in seq:
node = trie
for c in s:
# move to child
node = node.setdefault(c, {})
# mark last node as end of string
node[''] = None
return trie
def prefix_len(trie, s):
node = trie
j = -1
for i, c in enumerate(s):
# node is marked as end of string
if '' in node:
j = i
# move to child if present
node = node.get(c)
if node is None:
break
else:
# node is marked as end of string
if '' in node:
j = len(s)
return j
Упакованное trie
Универсальное trie тратит много памяти. Хотя память линейная, константа велика. Известно что алфавит - цифры, можно заменить словари на массивы из десяти элементов. Эти массивы можно собрать в один большой массив. Там есть ещё тонкости, но я их опускаю. Сложность не меняется по сравнению с универсальным trie.
ARRAY_TYPE = 'Q'
ABSENT = 1 << (array.array(ARRAY_TYPE).itemsize * 8) - 1
EMPTY = (ABSENT, ) * 10
def make(seq):
trie = array.array(ARRAY_TYPE, [0] * 2)
for s in seq:
# trie root node
p = 0
for i in map(int, s):
# this is a leaf (no subtree)
if trie[p] < 2:
# allocate new node
trie[p] |= len(trie)
trie.extend(EMPTY)
# move to ith child
p = (trie[p] & ~1) + i
# mark child present
if trie[p] == ABSENT:
trie[p] = 0
# mark last node as end of string
trie[p] |= 1
return trie
def prefix_len(trie, s):
p = 0
j = -1
for k, i in enumerate(map(int, s)):
# node is marked as end of string
if trie[p] & 1 != 0:
j = k
# this is a leaf (no subtree)
if trie[p] < 2:
break
# move to child
p = (trie[p] & ~1) + i
# if child is absent
if trie[p] == ABSENT:
break
else:
# node is marked as end of string
if trie[p] & 1 != 0:
j = len(s)
return j
Двоичный поиск
Все префиксы распределяются в списки по длине. Каждый список сортируется. При поиске префикса в каждом списке делается двоичный поиск. Сложность хуже чем у trie: O(N·log N); O(r·log N). Зато константы лучше: обработка trie буквально посимвольная, со списками можно работать как c едиными объектами.
def make(seq):
table = []
for s in seq:
n = len(s)
if n >= len(table):
table.extend([] for _ in range(n - len(table) + 1))
table[n].append(s)
for row in table:
row.sort()
return table
def prefix_len(table, s):
for n in range(min(len(s) + 1, len(table)))[::-1]:
row = table[n]
s_n = s[:n]
i = bisect.bisect_left(row, s_n)
if i < len(row) and row[i] == s_n:
return n
return -1
Сравнение
Все три решения тестировались, все они возвращают одинаковые ответы.
- Время построения таблицы включает построение таблицы в памяти и запись её на диск с помощью
pickle
.
- Место на диске в комментариях не нуждается.
- Для измерения места в памяти программа считывала таблицу с диска и останавливалась в ожидании ввода. Пока она висела я смотрел сколько памяти занимает процесс.
- Время загрузки таблицы с диска включает загрузку, исполнение одного запроса, выход из программы. Один запрос ничего не занимает, очистка памяти для универсального trie1 заметна, я её проигнорировал.
- Время одного запроса мерялось хитро: запускались прогоны с миллионом запросов и с двумя миллионами. Разница времён делилась на миллион, получалось время одного запроса. Вычитание удаляет время загрузки и обработки первого миллиона запросов. Оставшееся время приходится на второй миллион.
data_150.txt
В каком-то смысле это вырожденный тест: префиксы числа в дапазоне [1, 16839793].
|
Универсальное trie |
Упакованное trie |
Двоичный поиск |
Время построения таблицы |
28 с |
56 с |
11 c |
Место на диске |
136 MB |
135 MB |
174 MB |
Место в памяти |
4800 MB |
139 MB |
1200 MB |
Время загрузки таблицы с диска |
9.2 с |
0.2 с |
1.6 с |
Время одного запроса |
3.2·10-6 с |
5.0·10-6 с |
5.1·10-6 с |
Случайные префиксы
|
Универсальное trie |
Упакованное trie |
Двоичный поиск |
Время построения таблицы |
46 с |
70 с |
13 c |
Место на диске |
187 MB |
582 MB |
207 MB |
Место в памяти |
6100 MB |
586 MB |
1400 MB |
Время загрузки таблицы с диска |
19.0 с |
0.6 с |
1.9 с |
Время одного запроса |
3.8·10-6 с |
5.5·10-6 с |
9.3·10-6 с |
Выводы
Все варианты выполняют запрос быстрее десяти микросекунд. То есть, сто тысяч запросов в секунду или быстрее. Учтите что в это время входит ввод данных и вывод результата. Это очень быстро.
Время построения таблиц от десяти секунд до минуты. Эта операция делается один раз для списка префиксов, надо потерпеть. Зато потом запросы будут обрабатываться очень быстро.
Место в памяти велико - от сотен мегабайт до единиц гигабайт. Это понятно учитывая что мы храним поисковую структуру для ста пятидести миллионов элементов, а язык - Питон, возможности низкоуровневой оптимизации ограничены. Упакованное trie всего в три раза больше исходных данных, а его можно сжать ещё в два раза сравнительно просто.
Время загрузки с диска приемлемо для упакованного trie и двоичного поиска. Две секунды и сервис готов к работе.
Исходные коды можно найти в репозитории trie2.