После просмотра образцов кода из RosettaCode и грамотного программирования я все еще смущен тем, как реализовать memoization для проблемы, которую я делаю.Выполнение заметок
В задаче, я выполнить магии() формулу, аналогичную последовательности Коллатца по количеству, и в конечном итоге последовательность либо дает 1,2 или 3.
, например, он может пойти:
123849 -> 2342453 -> 1233453 ->3
Я хотел бы сохранить значения после того, как вычислил их, так что, когда я выполняю magic() при увеличении числа больших чисел, время выполнения уменьшается. Так, например, после магии (123849), я хотел бы хранить 123849, 2342453 и 1233453. Если какое-либо из этих чисел появится в будущем, вместо того, чтобы выполнять магическую функцию, он немедленно выдает 3.
ones=[]
twos=[]
threes=[]
def magic(x):
# Memoization
if ones.count(x)>0: return 1
if twos.count(x)>0: return 2
if threes.count(x)>0: return 3
sequence=[]
<generate magic sequence, add each value to sequence>
# Add each sequence to the appropriate list
if final_value==1: ones.extend(sequence)
if final_value==2: twos.extend(sequence)
if final_value==3: threes.extend(sequence)
return final_value
Мой вопрос: есть ли лучший (более эффективный/быстрый) способ реализации этой мемуаризации? Могу ли я использовать списки вместо dicts?
- Я прочел следующее: What is memoization and how can I use it in Python? и понял, что вы обычно должны использовать dicts. Мне просто интересно, существует ли большая разница между использованием списков и dicts для memoization.