5

私は10^18のオーダーの数を処理しなければならないパズルをやっています。ただし、Pythonはすべての領域で非常に大きな数を処理できるわけではありません。

具体的には、a = 1000000000000000000（10 ^ 18）を割り当て、基本的な算術計算（+、-、/、*）を実行すると、それに応答します。ただし、range（）で使用するとOverflowErrorが表示されます

>>> a = 1000000000000000000
>>> a/2
500000000000000000L
>>> a*2
2000000000000000000L
>>> a+a
2000000000000000000L
>>> a*a
1000000000000000000000000000000000000L
>>> range(a)

Traceback (most recent call last):
  File "<pyshell#5>", line 1, in <module>
    range(a)
OverflowError: range() result has too many items
>>> xrange(a)

Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    xrange(a)
OverflowError: Python int too large to convert to C long

Python2.7を使用しました。

  1. どうすればそのようなケースを処理できますか？、そのような数字を保持しているパズルに対処するための最良の方法は何ですか？（チュートリアル/本のリファレンスをいただければ幸いです）
  2. Pythonがrange（）/ xrange（）でそれを処理できない理由

inbuild関数を使用してPython2.7でそれを実行したいと思います。それは不可能ですか？

4

2 に答える 2

10

Python 2.x では、rangeCxrangeでの作業に制限されてlongおり、大きな整数はそれには大きすぎます。rangeこの制限は、との実装の選択によるものですxrange。

range()Python 3.x ではこの制限がなくなり、非常に大きな整数で実行できるようになりました。

>>> range(2**128)
range(0, 340282366920938463463374607431768211456)

Python 3の公式の変更リストには、次のように書かれています。

range()xrange()は、任意のサイズの値で機能することを除いて、以前と同じように動作するようになりました。後者はもうありません。

Python 2.x では、range()関数はリストを返しました。明らかに、非常に大きな範囲のすべての要素にメモリを割り当てることは期待できません。xrange()関数はオブジェクトを返しますxrange。ドキュメントでは、「実際にはすべてを同時に格納することなく、対応するリストと同じ値を生成する不透明なシーケンス型」と説明されています。ドキュメントには、次のように書かれています。

xrange()シンプルで高速であることを目的としています。実装では、これを達成するために制限が課される場合があります。Python の C 実装では、すべての引数がネイティブ C の long (「短い」Python 整数) に制限されており、要素数がネイティブ C の long に収まる必要もあります。

これは、Python 2.x の制限を説明しています。

非常に大きな範囲に対する新しい Python 3 サポートで何ができるかはよくわかりません。たとえば、これを試すことはお勧めしません。

2**128 in range(2**128)

それは長い間実行されます。

コメントで、大きな数までカウントするコードを書いていることを示しています。次のようなコードを使用して、Python で簡単にこれを行うことができます。

i = 0
while i<N:
    doSomething(i)
    i += 1

しかし、 がN大きい場合、これには非常に長い時間がかかることがわかります。あなたの質問によるNと、オーダー 2 18の値に対してそれを回避する方法はありません。

于 2012-01-23T13:06:06.217 に答える
1

あなたの問題は、Python 2.7 の range() が範囲内のすべての値の明示的なリストを構築することです。そのようなリストを構築するのに十分なリソースがありません。

Python 3 はこの動作を修正し、必要に応じて値のみを計算します...あたかもジェネレーター式によるかのように。

Python 2 の xrange() 関数は、値を登録するように制約されているため、役に立ちません。これは、Python 2 が自明ではない数値に対する range() の巨大なオーバーヘッドを回避するための妥協案でした。

1 つのアプローチは、任意の整数を反復処理する独自のジェネレーターを定義することです。次のようなものです。

def genrange(min,max,stride=1):
    val=min
    while val<max:
        yield val
        val+=stride

ただし、これはおそらくより大きなスキームの間違いであると思います.32ビット整数のすべての値を反復処理するのに十分な処理リソースを持っている可能性は低いため. (32 ビット) レジスタ。そもそも範囲に依存しない問題に対処するためのより良い方法があると思います。

于 2012-01-23T13:12:40.460 に答える