Одновременный перебор пар: как выбрать между сортировкой и хешом на почти отсортированных данных
Есть два больших списка идентификаторов, оба отсортированы по возрастанию и содержат уникальные значения: a длины n и b длины m. Нужно получить отсортированный список общих идентификаторов. Рассматриваются три реализации:
# A: два указателя
def common_a(a, b):
i = j = 0
out = []
while i < len(a) and j < len(b):
if a[i] == b[j]:
out.append(a[i]); i += 1; j += 1
elif a[i] < b[j]:
i += 1
else:
j += 1
return out
# B: множество
def common_b(a, b):
sb = set(b)
return [x for x in a if x in sb]
# C: вложенный поиск
def common_c(a, b):
return [x for x in a if x in b]
Что верно про эти три варианта?
- Все три варианта эквивалентны по времени: `in` по отсортированному списку в C выполняется двоичным поиском за O(log m), поэтому C отличается от A и B только константой
- B строго лучше A: построение множества обходится в O(1) на элемент и не требует лишней памяти, а два указателя дают O(n log m) из-за постоянных сравнений на каждом шаге
- A — O(n + m) времени и O(1) дополнительной памяти сверх ответа; B — O(n + m) времени, но O(m) дополнительной памяти; C — O(n·m), потому что `in` по списку линеен
- A даёт O(n·m), потому что при несовпадении каждый указатель может пройти весь чужой список целиком; линейный результат дают только B и C