141

Python で整数のビット数をすばやくカウントする方法が必要です。私の現在の解決策は

bin(n).count("1")

しかし、これを行うより速い方法があるかどうか疑問に思っていますか?

PS: (私は大きな 2D バイナリ配列を数値の 1 つのリストとして表し、ビットごとの操作を行っています。これにより、時間が数時間から数分に短縮されます。そして、これらの余分な分を取り除きたいと思います。

編集：1.それはpython 2.7または2.6でなければなりません

小さい数値の最適化は明確なボトルネックではないため、それほど重要ではありませんが、いくつかの場所で10 000 +ビットの数値があります

たとえば、これは 2000 ビットの場合です。

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
4

12 に答える 12

137

任意の長さの整数の場合、bin(n).count("1")純粋な Python で見つけることができる最速のものです。

私は Óscar と Adam のソリューションを適応させて、それぞれ 64 ビットと 32 ビットのチャンクで整数を処理しようとしました。どちらも少なくとも 10 倍は遅くなりましbin(n).count("1")た (32 ビット バージョンでは、約半分の時間がかかりました)。

一方、gmpy popcount()は の約 1/20 の時間かかりましたbin(n).count("1")。したがって、gmpy をインストールできる場合は、それを使用してください。

コメントの質問に答えるには、バイトの場合はルックアップ テーブルを使用します。実行時に生成できます。

counts = bytes(bin(x).count("1") for x in range(256))  # py2: use bytearray

または、文字通り定義するだけです：

counts = (b'\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08')

次に、0 ≤ x ≤ 255counts[x]で 1 のビット数を取得します。x

于 2012-03-22T22:46:15.433 に答える
36

次のアルゴリズムを適用できます。

def CountBits(n):
  n = (n & 0x5555555555555555) + ((n & 0xAAAAAAAAAAAAAAAA) >> 1)
  n = (n & 0x3333333333333333) + ((n & 0xCCCCCCCCCCCCCCCC) >> 2)
  n = (n & 0x0F0F0F0F0F0F0F0F) + ((n & 0xF0F0F0F0F0F0F0F0) >> 4)
  n = (n & 0x00FF00FF00FF00FF) + ((n & 0xFF00FF00FF00FF00) >> 8)
  n = (n & 0x0000FFFF0000FFFF) + ((n & 0xFFFF0000FFFF0000) >> 16)
  n = (n & 0x00000000FFFFFFFF) + ((n & 0xFFFFFFFF00000000) >> 32) # This last & isn't strictly necessary.
  return n

これは 64 ビットの正の数に対して機能しますが、簡単に拡張でき、引数の対数に応じて (つまり、引数のビット サイズに比例して) 操作の数が増加します。

これがどのように機能するかを理解するために、64 ビット文字列全体を 64 個の 1 ビット バケットに分割すると想像してください。各バケットの値は、バケットに設定されているビット数と同じです (ビットが設定されていない場合は 0、1 ビットが設定されている場合は 1)。最初の変換は同様の状態になりますが、それぞれ 2 ビット長の 32 個のバケットがあります。これは、バケットを適切にシフトし、それらの値を追加することによって実現されます (バケットをまたがるキャリーは発生しないため、1 回の追加ですべてのバケットが処理されます。n ビットの数値は常に、数値 n をエンコードするのに十分な長さです)。さらに変換すると、1 つの 64 ビット長のバケットに到達するまで、指数関数的に増加するサイズのバケット数が指数関数的に減少する状態になります。これにより、元の引数に設定されたビット数が得られます。

于 2012-03-22T20:48:53.973 に答える
20

この投稿で説明されているように、人口カウント アルゴリズムの Python 実装を次に示します。

def numberOfSetBits(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

で動作し0 <= i < 0x100000000ます。

于 2012-03-22T20:09:27.893 に答える
10

この投稿によると、これはハミング重みの最速の実装の 1 つと思われます(約 64KB のメモリを使用することを気にしない場合)。

#http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable
POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcount32_table16(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff])

Python 2.x では、 に置き換える必要がrangeありxrangeます。

編集

より良いパフォーマンスが必要な場合 (そして数値が大きな整数である場合)、GMPライブラリを見てください。これには、さまざまなアーキテクチャ用の手書きのアセンブリ実装が含まれています。

gmpyGMP ライブラリをラップする C コードの Python 拡張モジュールです。

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024
于 2012-03-22T20:19:37.627 に答える
2

あなたは Numpy が遅すぎると言いました。個々のビットを保存するために使用していましたか？ビット配列として int を使用するという考えを拡張し、それらを格納するために Numpy を使用しないのはなぜですか?

n ビットをceil(n/32.)32 ビット int の配列として格納します。次に、int を使用するのと同じ (よく似た) 方法で numpy 配列を操作できます。これには、それらを使用して別の配列にインデックスを付けることが含まれます。

アルゴリズムは基本的に、各セルに設定されたビット数を並列に計算し、各セルのビット数を合計します。

setup = """
import numpy as np
#Using Paolo Moretti's answer http://stackoverflow.com/a/9829855/2963903
POPCOUNT_TABLE16 = np.zeros(2**16, dtype=int) #has to be an array

for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcount32_table16(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff])

def count1s(v):
    return popcount32_table16(v).sum()

v1 = np.arange(1000)*1234567                       #numpy array
v2 = sum(int(x)<<(32*i) for i, x in enumerate(v1)) #single int
"""
from timeit import timeit

timeit("count1s(v1)", setup=setup)        #49.55184188873349
timeit("bin(v2).count('1')", setup=setup) #225.1857464598633

驚いたことに、C モジュールを書くことを誰も勧めませんでした。

于 2014-05-03T06:01:53.220 に答える
-2

最初の表現は、1または0のいずれかであるintのリストのリストであることがわかります。単にその表現でそれらを数えます。

整数のビット数はPythonでは一定です。

ただし、設定されたビット数をカウントする場合、最も速い方法は、次の擬似コードに準拠したリストを作成することです。[numberofsetbits(n) for n in range(MAXINT)]

これにより、リストを生成した後、一定時間のルックアップが提供されます。これの適切な実装については、@PaoloMorettiの回答を参照してください。もちろん、これをすべてメモリに保持する必要はありません。ある種の永続的なKey-Valueストア、またはMySqlを使用することもできます。（別のオプションは、独自の単純なディスクベースのストレージを実装することです）。

于 2012-03-22T20:04:16.987 に答える