Ускорение процесса добавления списка с помощью операторов if else
У меня есть список, содержащий строки, представляющие собой комбинацию «A», «B» и «C».
Например:
abc_list = ["AB", "AC", "AB", "BC", "BB", ...]
Теперь я хочу создать новый список, который снова переводит каждый элемент в «A», «B» и «C» с помощью простого правила.
Правило следующее:
Если элемент "AA", "AB" или "BA", то новый элемент строки должен стать "A". Если элемент «BB», «AC» или «CA», то новый элемент строки должен стать «B». Если элемент "CC", "CB" или "BC", то новый элемент строки должен стать "C".
Таким образом, новый список становится:
new_abc_list = ["A", "B", "A", "C", "B", ...]
На данный момент я делаю это следующим образом, но у меня есть ощущение, что это можно сделать намного эффективнее.
new_abc_list = []
for element in abc_list :
if element == "AA":
new_abc_list .append("A")
elif element == "AB":
new_abc_list .append("A")
elif element == "BA":
new_abc_list .append("A")
elif element == "CB":
new_abc_list .append("C")
elif element == "CC":
new_abc_list .append("C")
elif element == "BC":
new_abc_list .append("C")
else:
new_abc_list .append("B")
return new_abc_list
Каков более эффективный способ сделать это?
Ответы 1
Это выглядит как хорошая работа для словаря и понимания списка:
mapper = {"AA": "A", "AB": "A", "BA": "A", "CB": "C", "CC": "C", "BC": "C"}
abc_list = ["AB", "AC", "AB", "BC", "BB"]
# find the value from key, default to 'B' if not found
new_abc_list = [mapper.get(x, 'B') for x in abc_list]
Выход:
['A', 'B', 'A', 'C', 'B']
Сложность будет O(n), так как поиск по словарю - O(1). Напротив, исходный код должен проверять все значения, пока не найдет совпадение для каждого элемента в цикле.
тайминги
На 500 тыс. предметов (abc_list = ["AB", "AC", "AB", "BC", "BB"] * 100_000) с 6 тестами:
# dictionary with list comprehension
27.8 ms ± 1.94 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# dictionary with for loop and append
56.4 ms ± 12.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# loop with tests
84.8 ms ± 11.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
в худшем случае: 500 000 элементов, не соответствующих ни одному тесту (abc_list = ['ZZ']*500_000):
# dictionary with list comprehension
35.1 ms ± 4.08 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# dictionary with for loop and append
48.2 ms ± 2.62 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# loop with tests
124 ms ± 20.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Я имею в виду, исходный код также O (N).
@juanpa.arrivillaga не с точки зрения соответствия значений, ему нужно проверить все if/elif до совпадения, поэтому наихудшая сложность — это O(n*m), где m — количество возможных тестов.
Но возможное количество тестов постоянно. Временная сложность этого кода O(N). Может быть более высокий постоянный фактор, но алгоритмически они эквивалентны.
Получение словарного значения O(1), с циклом это O(m), так что есть коэффициент m ускорения.
@juanpa.arrivillaga Я добавил несколько таймингов, чтобы поддержать это. (Еще более лучшим сравнением было бы добавление дополнительных тестов).
Эти тайминги вообще не демонстрируют то, что вы утверждаете, они просто демонстрируют, что подход со словарем быстрее, что не то же самое, что алгоритмически быстрее. Чтобы попытаться подтвердить ваше утверждение эмпирически, вам нужно будет показать, как масштабируется алгоритм, и в одном случае он будет масштабироваться линейно, а в другом — полиномиально. Но вы обнаружите, что оба масштабируются линейно, потому что они оба O (N).
По сути, работа, выполняемая внутри цикла в обоих случаях, является постоянным временем. Это не O(M), M не может варьироваться. Итак, позвольте мне выразить это по-другому: в вашем анализе что такое М?
Что ж, я думаю, что мы должны здесь не согласиться (или, может быть, мы говорим о разных вещах здесь). Словарный подход - O (1 * N) и цикл O (M * N). Как упоминалось в моем комментарии, чтобы действительно протестировать масштабирование на M (количество условий), нам нужно было бы увеличить количество условий (чего я не делал). Конечно, в обоих случаях цикл будет состоять из N элементов.
*Но это не то, как работает анализ алгоритмов. Вы не можете масштабировать количество ветвей, это не вход для алгоритма! Извините, но это очень принципиально. Оба подхода являются O (N).
M/1 - это то, что я назвал n/1 в ответе, количество тестов
Количество тестов является постоянным, алгоритмически вы можете выбрать постоянное число, при котором для любого заданного ввода время, необходимое для выполнения этого, будет меньше этого постоянного числа. Единственная переменная в обоих случаях — это длина входного списка, и оба алгоритма линейно масштабируются на этом входе.
Итак, мы не брали об одном и том же. И я хочу сказать, что подход со словарем улучшается в цикле. Чем больше тестов у вас есть, тем хуже они будут работать, в то время как использование словаря находит правильное значение напрямую.
Тогда вы не говорите об алгоритмической сложности, например. НА). Я не пытаюсь быть сложным, но ваше утверждение об алгоритме O(M*N) просто неверно. Действительно, все алгоритмы в ваших таймингах имеют одинаковую временную сложность. Но, конечно, это не значит, что все они имеют одинаковую скорость. Опять же, это очень важно для анализа алгоритмов.
Я не вижу причин, по которым количество тестов не может быть переменной. Если OP решит добавить больше категорий элементов, потребуется больше тестов, и код будет медленнее. Тем не менее, вы правы для фиксированного количества тестов, алгоритмическая сложность обоих подходов линейно зависит от количества элементов (я никогда не утверждал обратного);)
Да, извините, это была ошибка. Исправленный.