変数格納について

Question

私はProject Eulerの第4の問題の最適化されたソリューションを書き終えました。私がアルゴリズムを実装している間、私は設計上の選択に対して内部的な衝突を経験しました。オペレーションのプロダクトを将来の参照のために自身の変数に格納するか、それを変数として格納せずに、必要に応じて2つのオペランドの積を再現するかは不明でした。

product = x * y 
if (checkPalindrome(product) and product > largest_product): 
    largest_product = product 

オペランドは「製品」に格納され、次の行で参照されます。私が持っている好奇心は、製品への参照が必要なときはいつでも、製品を再現する場合と比較して、これがより良い方法であると考えられるかどうかです。このように：

if (checkPalindrome(x * y) and x * y > largest_product): 
    largest_product = x * y 

実装のこの違いは、スケーリング時にスペースや時間パフォーマンスに差が生じることはありますか？

Answer 1

実際には、最初のアプローチが最適です。ここから、小さな整数を掛けているので、後のアプローチでそれほど大きな影響を与えません。しかし、これをループの中で実行すると、製品数の計算のために、それは実際に結びつき、影響を与えます。

ループが10個あるとします。 2番目のアプローチでは、1回の乗算にO（1）時間かかる場合。したがって、ループ内では、このような計算が2つあるため、O（2）回かかります。そのようなループの数が10の場合、O（20）回あります。

if (checkPalindrome(x * y) and x * y > largest_product): # O(1) 
    largest_product = x * y  # O(1) 
# total O(2) for two calculations 

しかし、最初のアプローチでは、あなたが一度だけ計算を行っていることから、算出された値を利用し、後の工程では、それだけで計算中、唯一のO（1）時間がかかります。しかし、時間がない、あなたが条件チェックのためにそれを参照する間。このようなループを10回実行すると、O（10）回分になります。したがって、あなたはあなたの時間の50％を節約しています。

product = x * y # O(1) for one calculation 
if (checkPalindrome(product) and product > largest_product): 
    largest_product = product 

はい、メモリが制約の場合は、変数を格納するためにメモリが必要な場合があります。その場合、2番目のアプローチを考えるかもしれません。または、計算の単一の点がある場合、その場合、2番目の方法を使用することをお勧めします。しかし、メモリが制約される最初のケースでは、変数を格納するだけでは大量のメモリを必要としません。だから、とにかく、私は最初のものを見つけました（毎回計算するのではなく、一度計算してください）。

Answer 2

Pythonでの算術は特に高速ではありませんので、同じ計算を複数回実行しない方がよいでしょう。ところで、最大の製品を「手で」決定するのではなく、組み込みのmax機能でそれを実行できます。

また、product = x * yを避けて多くのRAMを節約していないことにも言及してください。コードはまだx * yの結果を保持するためにintオブジェクトを作成しなければならず、そのオブジェクトを名前にバインドしても多くのRAMを消費しません。 OTOHは、同じ計算を3回実行するだけでなく、結果を格納するために3つのオブジェクトを作成（およびリサイクル）する必要があることを意味します。

Other languages have "variables", Python has "names"をご覧ください。この重要なトピックの詳細な調査については、SOベテランのNed Batchelderによって書かれたFacts and myths about Python names and valuesを参照してください。

Answer 3

数値は、その長さに比例した量のストレージを消費します（プリントアウト時）。適度な大きさの数字の場合、20桁までは、この効果に全く気付かない可能性があります。あなたが巨大な数字（数千桁）またはそれらの多くを持っていない限り、あなたはその効果に気づかない可能性があります。

2つの数字の乗算には、研究の積極的な領域がありますが、これらの目的のために、最長の数字の長さの2乗に比例した時間が必要です（ifそれらは長さにおいて同様である）。しかし、あなたが巨大な数字を持っていない限り、あなたはこの効果に気づかない可能性があります。

他の人も見てきたように、乗算はPythonでは高速ではないので、それは懸念事項です。

私は、明確なものを書いておき、パフォーマンスに問題が発生したときにそのパフォーマンスの問題を解決することをお勧めします。