2

Pythonで特定の範囲（たとえば0から10）の整数の小さなセットを表す最も効率的な方法を探しています。この場合、効率とは、（ソートされていないリストからの）高速な構築、高速なクエリ（各セットでのいくつかのクエリ）、およびソートされたバージョンの適度に高速な構築（おそらく10セットに1回程度）を意味します。先験的に、候補者はPythonの組み込みセットタイプ（高速クエリ）、ソートされた配列（おそらく構築が高速ですか？）、またはビット配列（Cにいる場合はすべて高速です...）を使用していますが、Pythonがその効率的（？））。どれを選ぶべきかアドバイスはありますか？

ありがとう。

4

4 に答える 4

1

私はビットマップを使用して、「セット」のメンバーをint...に格納します。これは、この場合の組み込み型よりも実際には高速である可能性がありますが、setテストはしていません。それは間違いなくより少ないストレージを必要とするでしょう。

アップデート

現在、完全なセットのような実装を行い、Pythonの組み込みクラスに対してベンチマークを行う時間はありませんが、これが私の提案を示す実用的な例であると私は信じています。ご同意いただけると思いますが、コードはかなり高速で、メモリ効率も高いように見えます。

Pythonのほぼ透過的な「無制限」の長整数機能を考えると、書き込まれる内容は、必要以上に広い範囲の整数値で自動的に機能しますが、そうすると少し遅くなる可能性があります。;）

class BitSet(object):
    def __init__(self, *bitlist):
        self._bitmap = 0
        for bitnum in bitlist:
            self._bitmap |= (1 << bitnum)

    def add(self, bitnum):
        self._bitmap |= (1 << bitnum)

    def remove(self, bitnum):
        if self._bitmap & (1 << bitnum):
            self._bitmap &= ~(1 << bitnum)
        else:
            raise KeyError

    def discard(self, bitnum):
       self._bitmap &= ~(1 << bitnum)

    def clear(self):
        self._bitmap = 0

    def __contains__(self, bitnum):
        return bool(self._bitmap & (1 << bitnum))

    def __int__(self):
        return self._bitmap

if __name__ == '__main__':

    bs = BitSet()

    print '28 in bs:', 28 in bs
    print 'bs.add(28)'
    bs.add(28)
    print '28 in bs:', 28 in bs

    print
    print '5 in bs:', 5 in bs
    print 'bs.add(5)'
    bs.add(5)
    print '5 in bs:', 5 in bs

    print
    print 'bs.remove(28)'
    bs.remove(28)
    print '28 in bs:', 28 in bs
于 2012-06-13T22:02:32.077 に答える
0

私のアドバイスは、ビルトインに固執することset()です。組み込みの C コードに勝るパフォーマンスの Python コードを作成することは非常に困難です。組み込みの C コードに依存している場合、構築の速度と検索の速度が最も速くなります。

並べ替えられたリストの場合、組み込みの並べ替え機能を使用するのが最善の策です。

x = set(seq) # build set from some sequence
lst = sorted(x)  # get sorted list from set

一般に、Python では、記述するコードが少ないほど高速になります。Python の組み込み C 基盤に依存できるほど、高速になります。解釈された Python は、多くの場合、C コードよりも 20 倍から 100 倍遅く、ビルトイン機能を意図したとおりに使用するよりも優れているほど賢くなることは非常に困難です。

セットが常に [0, 10] の範囲の整数であることが保証されていて、メモリ フットプリントをできるだけ小さくしたい場合は、整数内のビット フラグが適しています。

pow2 = [2**i for i in range(32)]

x = 0  # set with no values
def add_to_int_set(x, n):
    return x | pow2[n]

def in_int_set(x, n):
    return x & pow2[n]

def list_from_int_set(x):
    return [i for i in range(32) if x & pow2[i]]

これは実際には組み込みset()関数を使用するよりも遅いに違いありませんが、各セットが単なるintオブジェクトになることはわかっています: 4 バイトと Python オブジェクトのオーバーヘッドです。

文字通り何十億も必要な場合arrayは、Python リストの代わりに NumPy を使用してスペースを節約できます。NumPyarrayは裸の整数を格納するだけです。実際、NumPy には 16 ビットの整数型があるため、セットが実際に [0, 10] の範囲にしかない場合は、NumPy を使用してストレージ サイズをそれぞれ 2 バイトまで減らすことができますarray。

http://www.scipy.org/FAQ#head-16a621f03792969969e44df8a9eb360918ce9613

于 2012-06-13T21:57:26.010 に答える
0

この場合、True/False 値のリストを使用できます。で使用されるハッシュ テーブルsetは同じことを行いますが、ハッシュ、バケット割り当て、衝突検出のオーバーヘッドが含まれます。

myset = [False] * 11
for i in values:
    myset[i] = True
mysorted = [i for i in range(11) if myset[i]]

いつものように、自分の状況でどのように機能するかを知るために、自分で時間を計る必要があります。

于 2012-06-13T22:12:04.540 に答える