Один интересный код-челлендж с Leetcode: поиск анаграмм в строке
На моих собеседованиях по программированию я часто использую упрощенную версию этой задачи с Leetcode.
Даны две строки
sиp, вернуть true, еслиsсодержит анаграммуp.
Мне нравится эта задача, потому что решение можно постепенно улучшать, и есть много чего обсудить. От алгоритмической сложности до оптимизации на уровне кэша процессора. Здесь я хочу рассказать, как решил эту задачу в первый раз.
Самое затратное решение
Первое решение, которое приходит в голову: давайте создадим список всех возможных
анаграмм, а затем просто проверим, есть ли одна из них в строке s. Звучит просто,
не так ли? Но есть несколько проблем с этим подходом. Во-первых, реализация эффективного алгоритма
для генерации всех возможных перестановок уже является достаточно сложной задачей. А во-вторых, временная сложность
итогового решения будет примерно O(s*p!). Факториал растет очень быстро: 3! == 6,
5! == 120, 10! == 3,628,800, и вы не захотите с этим иметь дело.
Первый шаг в правильном направлении
Первый шаг к более оптимальному решению — немного изменить способ восприятия задачи. Вместо
_вернуть true, если s содержит анаграмму _p* будем использовать *вернуть true, если s содержит подстроку с символами из строки p в любом порядке*. Это изменит наш способ мышления о проблеме и откроет больше решений.
Сортировка
Один из способов работы с неупорядоченными данными — сделать их упорядоченными нужным нам образом.
Поэтому мы сортируем символы в p, а затем сортируем все возможные подстроки длины p в s.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
if len(s) < len(p) or len(s) <1 or len(p)<1:
return result
p_len = len(p)
p_sorted = sorted(p)
for i in range(len(s)-p_len+1):
cur = sorted(s[i:i+p_len])
if cur == p_sorted:
result.append(i)
return result34 / 61 test cases passed.
Это работает, но очень медленно, и при отправке на Leetcode один из тестовых случаев завершился по времени. Временная сложность этого подхода составляет O(s*p*log(p)).
Подсчет
Хорошо. Сортировка строк была не самой лучшей идеей, но мы можем кое-чему научиться. Представьте, что у нас p = "appleappleapple", после сортировки мы получаем p = "aaaeeelllpppppp".
Мы можем представить эту строку как словарь { 'a': 3, 'e': 3, 'l': 3, 'p': 6 }. Мы можем представить любую строку подобным образом. Построение словаря — более простая операция, чем сортировка. Поэтому мы можем подсчитать количество символов в
подстроке и в p, а затем сравнить эти числа. В Python есть удобный помощник для упрощения этой задачи - collections.Counter.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
if len(s) < len(p) or len(s) <1 or len(p)<1:
return result
p_len = len(p)
p_counter = Counter(p)
cur = Counter(s[:p_len])
for i in range(len(s)-p_len+1):
cur = Counter(s[i:i+p_len])
if cur == p_counter:
result.append(i)
return result61 / 61 test cases passed, but took too long.
Мы снова “превысили время”, но на этот раз это было общее время для всех 61 тестов. Наше решение имеет сложность O(s*p), что, конечно, лучше, чем O(s*p*log(p)), но все еще не O(s).
Подсчет, но быстрее
Основная проблема предыдущего подхода заключается в том, что мы перестраиваем счетчик на каждой итерации. Мы рассматриваем подстроку как скользящее окно, поэтому нам нужно добавлять один символ спереди и удалять один сзади окна. Это позволит нам сохранять счетчик между итерациями.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
if len(s) < len(p) or len(s) <1 or len(p)<1:
return result
p_len = len(p)
p_counter = Counter(p)
cur = Counter(s[:p_len])
i = p_len-1
for i in range(len(p), len(s)):
if cur == p_counter:
result.append(i-p_len)
prev = s[i-p_len]
cur.subtract(prev)
cur.update(s[i])
if not cur.get(prev):
cur.pop(prev)
if cur == p_counter:
result.append(i-p_len+1)
return resultSuccess
Runtime: 426 ms, faster than 23.71% of Python3 online submissions for Find All Anagrams in a String.
Memory Usage: 15.2 MB, less than 33.09% of Python3 online submissions for Find All Anagrams in a String.
Мы наконец-то прошли тесты, но 23-й процентиль — не самый лучший результат. Давайте попробуем немного ускориться.
Сокращение издержек: счетчик
Может показаться, что мы достигли временной сложности O(s) и улучшить ее невозможно. Но на самом деле сложность все еще O(s*p) из-за cur == p_counter. Однако самая большая проблема заключается в том, что обновление счетчика — дорогостоящая операция. Чтобы подтвердить это, мы можем провести простые измерения:
>>> s = Solution()
>>> timeit('s.findAnagrams("abcabc","abc")', globals=globals())
11.242373244000191
>>> timeit('Counter("abc")', setup="", globals=globals())
1.417118921999645
>>> timeit('ll.append("a")', setup="ll = []", globals=globals())
0.07390610099992045
>>> c = Counter("abc")
>>> timeit('c.update("a")', globals=globals())
0.7364297260000967
>>> timeit('c.subtract("a")', globals=globals())
0.9186600939992786
>>> timeit('ca == cb', globals=globals())
0.09419484599857242
>>> timeit('ca.get("a")', globals=globals())
0.08134488799987594timeit измеряет, сколько секунд требуется для выполнения операции определенное количество раз. По умолчанию timeit выполняет один миллион итераций. s.findAnagrams("abcabc","abc") занимает:
- 1 раз, 1.42с или 12% времени, создание счетчика
- 6 раз, 0.919с*4 или 32.7% времени,
cur.subtract(prev) - 6 раз, 0.736с*4 или 26.2% времени,
cur.update(s[i]) - 6 раз, 0.08с*4 или 2.8% времени,
cur.get(prev) - 6 раз, 0.09с*4 или 3.2% времени,
cur == p_counter - 4 раза, 0.073с*4 или 2.5% времени,
list.append()
Счетчик потребляет ~60% времени выполнения. Но действительно ли нам нужен полноценный универсальный Counter, или мы можем использовать что-то более простое и быстрое? Задача имеет одно важное ограничение: s и p состоят из строчных английских букв. Это означает, что мы можем использовать список из 26 элементов, по одному для каждой английской буквы. Благодаря ascii стандарту коды этих букв последовательны, поэтому нам не нужен словарь для преобразования одной буквы в ее счетчик.
Я измерил производительность list с помощью timeit, чтобы подтвердить, что list быстрее, чем dict.
>>> timeit('l[10]+=1', setup="l = [0]*26", globals=globals())
0.0989342509983544
>>> timeit('l1==l2', setup="l1 = [0]*26; l2=[0]*26", globals=globals())
0.08017934499912371После замены Counter на list реализация выглядит следующим образом:
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s = s.encode("ascii")
p = p.encode("ascii")
result = []
if len(s) < len(p) or len(s) <1 or len(p)<1:
return result
p_len = len(p)
a = ord('a')
p_counter = [0]*26
for c in p:
p_counter[c - a] += 1
cur = [0]*26
for c in s[:p_len]:
cur[c - a] += 1
i = p_len-1
for i in range(len(p), len(s)):
if cur == p_counter:
result.append(i-p_len)
c = s[i]
prev = s[i-p_len]
cur[prev - a] -= 1
cur[c - a] += 1
if cur == p_counter:
result.append(i-p_len+1)
return resultИзменение сократило время выполнения на 65% (с 11,24с до 3,95с).
>>> timeit('s.findAnagrams("abcabc","abc")', globals=globals())
3.9490315559996816Удаление сравнения и достижение O(s)
Мы улучшили реализацию, но алгоритмическая сложность осталась прежней - O(s*p). В этом разделе мы удалим p из O(s*p) и дополнительно сократим издержки. Часть p скрыта в cur == p_counter.
Когда cur == p_counter истинно, разница между cur и p_counter дает список нулей. Мы можем использовать это себе во благо. Поскольку p_counter является константой, cur == p_counter можно заменить на (cur - p_counter) == (p_counter - p_counter), что можно заменить на (cur - p_counter) == [0]*26.
cur = [0]*26
for c in p:
cur[c - a] -= 1Теперь часть [0]*26 можно заменить счетчиком, который отслеживает количество нулей в cur. Мы можем реализовать трекер нулей, увеличивая счетчик нулей путем проверки значения счетчика буквы перед его обновлением.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s = s.encode("ascii")
p = p.encode("ascii")
result = []
if len(s) < len(p) or len(s) <1 or len(p)<1:
return result
p_len = len(p)
a = ord('a')
cur = [0]*26
for c in s[:p_len]:
cur[c - a] += 1
for c in p:
cur[c - a] -= 1
zeros = len([0 for i in cur if i == 0])
i = p_len-1
for i in range(len(p), len(s)):
if zeros == 26:
result.append(i-p_len)
c = s[i]
prev = s[i-p_len]
p_cur = cur[prev - a]
zeros += 1 if p_cur == 1 else 0
zeros += -1 if p_cur == 0 else 0
cur[prev - a] -= 1
c_cur = cur[c - a]
zeros += 1 if c_cur == -1 else 0
zeros += -1 if c_cur == 0 else 0
cur[c - a] += 1
if zeros == 26:
result.append(i-p_len+1)
return resultИ снова тест производительности:
>>> timeit('s.findAnagrams("abcabc","abc")', globals=globals())
6.378495043000001Выглядит так, словно мы все усложнили. Однако это не совсем так. Новая логика инициализации более затратная, и мы использовали простой тестовый случай. Давайте попробуем что-нибудь менее простое.
Тесты производительности
Чтобы сделать тесты более надежными, я написал небольшой скрипт и поместил один из самых сложных тестовых случаев из Leetcode в текстовый файл. В качестве тестового образца я выбрал тот, который вызвал тайм-аут в самой первой версии. Исходный код тестов производительности: perf_test.py и perf_input.txt
$ python3 content/posts/perf_test.py
SolutionSort: 12.7849 sec
SolutionCount: 7.9685 sec (-37.67% improvement)
SolutionFastCount: 0.0296 sec (-99.63% improvement)
SolutionList: 0.0119 sec (-59.82% improvement)
SolutionOs: 0.0101 sec (-15.24% improvement)Финальное решение в 1200 раз быстрее исходного.
Но на этом мы не останавливаемся.
Вот перевод:
Еще одна крошечная оптимизация
Теперь, когда мы работаем на уровне миллисекунд, мы можем начать оптимизировать небольшие операции, такие как prev - a. Мы можем убрать часть - a, создав список счетчиков с добавлением N элементов, чтобы операции cur[prev] попадали внутрь списка счетчиков. Это небольшое изменение дало еще 12%. Это приводит нас к 0,0089 мс вместо 12,9256, что в 1452 раза быстрее оригинальной версии.
SolutionSort: 12.9256 sec
SolutionCount: 7.9425 sec (-38.55% improvement)
SolutionFastCount: 0.0294 sec (-99.63% improvement)
SolutionList: 0.0120 sec (-59.20% improvement)
SolutionOs: 0.0101 sec (-15.66% improvement)
SolutionOs2: 0.0089 sec (-12.31% improvement)Альтернативный подход: хеширование
Есть как минимум еще один подход. Недавний кандидат, которого я интервьюировал, предложил подход, при котором вообще не нужно считать символы. Кандидат предложил использовать хеш-функцию, не зависящую от порядка символов, так что вместо подсчета мы будем вычислять хеш-значения для подстроки и p, а затем просто сравнивать два числа.
Однако есть один недостаток, по крайней мере, в Python: по мере роста длины p растет и хеш, что приводит к более дорогим математическим операциям.
>>> timeit('50357543 * 9')
0.013241855999996943
>>> timeit('6634282395641056463368422676523964230824061054656696147421638381867962461616370766912810646544439112552112104094315979216387096611584409353999775 * 9')
0.09212760000002618Тест Leetcode не проходит даже раньше первой версии. Но вот результаты тестов производительности:
SolutionSort: 12.9363 sec
SolutionCount: 8.1108 sec (-37.30% improvement)
SolutionFastCount: 0.0293 sec (-99.64% improvement)
SolutionList: 0.0118 sec (-59.69% improvement)
SolutionOs: 0.0099 sec (-15.86% improvement)
SolutionOs2: 0.0089 sec (-10.81% improvement)
SolutionHash: 0.3288 sec (3607.15% degradation)Примечание: SolutionHash медленнее оптимального, но все еще примерно в 24,5 раза быстрее, чем SolutionCount.
Заключение
Особо нечего заключать. Я просто хотел показать, как решал эту сложную задачу шаг за шагом, когда впервые с ней столкнулся. И было интересно наблюдать, как небольшими изменениями улучшается производительность во время написания поста.