Мой код Python проходит простые тесты, но не расширенные из-за ограничений производительности

Question

Я учу себя кодировать с Python и некоторое время я заканчиваю ката (в основном 7 кю) на Codewars. Когда я пытался подняться на уровень после 6 кю ката , насколько я знаю, это было достигнуто:

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

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

Примечания:

Используется широкий диапазон символов, и некоторые из них могут отображаться неправильно в вашем браузере. Ваше решение должно быть линейным с точки зрения длины строки, чтобы пройти последний тест. Примеры:

"Hello World" -> ["H", "e", "", "W", "r", "l", "d"]

" Codewars "-> [" C "," o "," d "," e "," w "," a "," r "," s "]

" woowee "- -> []

"wwoooowweeee" -> []

"racecar" -> ["e"]

"Mamma" -> ["M "]

" Мама "-> [" М "," м "]

Следующие Python 3.6.0 тестовые пробы кода:

def function_name(s):
    result = []
    lengthS = len(s)
    dictResult = {}

    for item in s[-1:(-1 * lengthS - 1):-1]:
        numLetters = 0
        for number in range(lengthS):
            if item == s[number]:
                numLetters = numLetters + 1
        if numLetters % 2 != 0:
            dictResult[item] = numLetters

    for key in list(dictResult.keys())[-1:(-1 * (len(list(dictResult))) - 1):-1]:
        result.append(key)

    return result

Сбой при запуске полного цикла тестов из-за:

Тайм-аут выполнения (12000 мс)

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

Ясно, что мой код не оптимизирован по производительности. Прочитайте некоторые статьи об алгоритмах, и я подозреваю, что моему коду не хватает производительности из-за для l oop в другой для l oop, что является операцией сложности O (n²). И вот где я застрял на некоторое время. Я не уверен, что это единственный фрагмент кода, который нужно изменить, и если это так - просто не могу понять, как это можно сделать.

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

Answer 1

Согласно вашей заметке:

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

• Я буду публиковать только узкие места, остальные это зависит от вас, чтобы выяснить. Ваш код имеет

  for number in range(lengthS):
          if item == s[number]:
              numLetters = numLetters + 1
  

, что в основном означает, что вы просматриваете всю строку и проверяете, где существуют все символы item, и собираете счет. Это делает ваш код квадратичным c по своей природе (O (n ^ 2)), потому что для каждого символа в строке выполняется полное сканирование, делающее асимптотически n ^ 2 шагов.

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

for item in s[-1:(-1 * lengthS - 1):-1]:
        numLetters = 0
        for number in range(lengthS):
            if item == s[number]:
                numLetters = numLetters + 1
        if numLetters % 2 != 0:
            dictResult[item] = numLetters

на

for item in s[-1:(-1 * lengthS - 1):-1]:
        dictResult[item] = dictResult.get(item,0) + 1

Это позволит собрать все подсчеты для определенного символа за один проход, сделав его O (n) по своей природе.

• Второе наблюдение, которое я обнаружил, заключается в том, что нет смысла (или какого-либо преимущества) в обходе строки в обратном направлении, как показано ниже:

  for item in s[-1:(-1 * lengthS - 1):-1]:
  

  Вместо этого вы можете попробуйте просто зациклить их один за другим, как показано ниже:

  for item in s:
      dictResult[item] = dictResult.get(item,0) + 1
  

• В-третьих, нужно посмотреть, действительно ли вам нужны item в dictResult, если их число четное. Если на каком-либо этапе итерации счет какого-либо персонажа окажется четным, вы можете просто удалить его из dictResult. Таким образом, в dictResult ключи будут иметь нечетные ключи. Это также делает ваш код более эффективным (иногда значительным). Обратите внимание, что ключи с нечетным значением в dictResult не будут упорядочены с точки зрения порядка символов, в которых ожидается вывод. Я оставляю это как упражнение для вас, чтобы разобраться.

Обновление:

Кажется, что из Python3 .7, клавиши В словаре хранятся в том порядке, в котором они вставлены. Таким образом, сравнительно легко сопоставить порядок вывода.

Правильный фрагмент кода:

def odd_one_out(s):
    result = []
    dictResult = {}

    for item in s:
        dictResult[item] = dictResult.get(item,0) + 1
        if dictResult[item] % 2 == 0:
            dictResult.pop(item)
    return list(dictResult.keys())

Answer 2

Вы правы, выяснив, что именно O (n ^ 2) вызывает ошибку превышения лимита времени.

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

Это значительно сократит время выполнения.

Вы правы с точки зрения сложности пространства.

Answer 3

Здесь я даю компактное решение, используя немного знаний python и его стандартной библиотеки:

Это работает для python> = 3.7, потому что до этого Счетчик не был определен как упорядоченный

from collections import Counter
def function_name(s):
    count = Counter(s)
    answer = [c for c, num in count.items() if num % 2]
    return answer

В других версиях небольшое изменение, принимая символы по порядку из строки:

from collections import Counter
def function_name(s):
    count = Counter(s)
    answer = [c for c in s if count[c] % 2]
    return answer

Answer 4

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

пример:

my_counter = {}
for letter in s:
    my_counter[letter] = my_counter.get(letter, 0) + 1 

Поскольку вам не нужно полное решение, я позволю вам разобраться с остальными. Надеюсь, это поможет.

do c из get (): https://docs.python.org/3/library/stdtypes.html?highlight=get#dict .get