python - まばらなリストにランダムな 1 を入力する

Question

ランダムな場所にいくつかの 1 を含むリストを作成する必要があります。次の方法で乱数のリストを正常に作成できます。

from random import randint
l = [randint(0,1023) for _ in range(0,10)]

l で指定された位置に 1 を含むリストを作成するにはどうすればよいですか?

Answer 1

アルゴリズムのベンチマークを行うために、ランダムな場所に 10 ～ 40 個の l を含む 0 の大きなリストを作成する必要があります。

これはあなたのために働くかもしれませんか？

import random

zeros = [0] * 1024
ones = [1] * random.randint(10, 40)
l =  zeros + ones
random.shuffle(l)

# the list l contains many zeros and 10 - 40 1's in random places.

where_the_ones_are = [i for i, x in enumerate(l) if x == 1] 

Answer 2

まばらなリスト

「疎リスト」についての私の理解では、ほとんどの (たとえば、95% 以上の) 値はゼロになり、メモリ効率の理由から、これらを格納したくないということです( cf. Sparse array )。

リスト内包表記

リスト内包表記を使用すると、条件式の解決( foo if condition else bar ) を使用して、その位置に 1 があるか 0 があるかを判断できます。例えば：

In [1]: from random import randint

In [2]: l = [randint(0,1023) for _ in range(0,10)]

In [3]: l
Out[3]: [987, 356, 995, 192, 21, 22, 1013, 375, 796, 339]

In [4]: 1 if 987 in l else 0
Out[4]: 1

In [5]: 1 if 988 in l else 0
Out[5]: 0

これは、質問で言及した 2 番目のリストにデータを入力する必要がないことを意味します。

1 if index in l else 0

辞書理解

または、辞書内包表記を使用することもできます。これはより読みやすいと思います：

In [1]: from random import randint
In [2]: l = {randint(0, 1023): 1 for _ in xrange(0, 10)}

これにより、次のような辞書が生成されます。

In [3]: l
Out[3]: 
{216: 1,
 381: 1,
 384: 1,
 392: 1,
 396: 1,
 472: 1,
 585: 1,
 630: 1,
 784: 1,
 816: 1}

次に、デフォルト値 0 を指定して要素にアクセスします。要求された位置の値が設定されている場合は、次のように取得されます。

In [4]: l.get(216, 0)
Out[4]: 1

値が設定されていない場合は、ゼロが返されます。

In [5]: l.get(217, 0)
Out[5]: 0

ポジションのリストを取得するには:

In [6]: l.keys()
Out[6]: [384, 392, 472, 630, 216, 585, 396, 381, 784, 816]

上記のアプローチの両方の欠陥

randint(0, 1023)は同じ数を複数回発行する可能性があり、衝突が発生し、必要な数よりも少ない数になる可能性があります。

すべてを結び付ける

class簡単に (再) 使用できるように、辞書ベースの実装を でラップします。

from random import randint


class RandomSparseList(object):
    def __init__(self, size, min_bits, max_bits):
        self.size = int(size)
        self.bits = {}
        self.bits_set = randint(min_bits, max_bits)
        while self.bits_set > len(self.bits):
            self.bits[randint(0, self.size)] = 1 

    def __len__(self):
        return self.size

    def __getitem__(self, index):
        if index < 0 or index >= self.size:
            raise IndexError
        return self.bits.get(int(index), 0)

    def __iter__(self):
        for i in xrange(self.size):
            yield self.__getitem__(i)

    def __contains__(self, index):
        return index in self.bits

    def __repr__(self):
        return '[{}]'.format(', '.join(str(x) for x in self))

    def set_bits(self):
        return self.bits.keys()

使用例

classこれをファイルに入れました：

In [1]: from random_sparse_list import RandomSparseList

インスタンスを作成します。

In [2]: rsl = RandomSparseList(1024, 10, 40)

リストの長さを確認します。

In [3]: len(rsl)
Out[3]: 1024

どのビットが設定されていますか?

In [4]: rsl.set_bits()
Out[4]: 
[523,
 400,
 285,
 158,
 419,
 434,
 701,
 67,
 843,
 846,
 591,
 720,
 470,
 864,
 912,
 739,
 996,
 485,
 489,
 234,
 1005,
 573,
 381,
 784]

24: それは確かに 10 ～ 40 の範囲です。

ランダムアクセス：

In [5]: rsl[523]
Out[5]: 1

In [6]: rsl[524]
Out[6]: 0

ビットは設定されていますか？

In [7]: 400 in rsl
Out[7]: True

In [8]: 401 in rsl
Out[8]: False

リストの反復:

In [9]: for index, value in enumerate(rsl):
   ...:     if value:
   ...:         print '{} found at index {}'.format(value, index)
   ...:         
1 found at index 67
1 found at index 158
1 found at index 234
1 found at index 285
1 found at index 381
1 found at index 400
1 found at index 419
1 found at index 434
1 found at index 470
1 found at index 485
1 found at index 489
1 found at index 523
1 found at index 573
1 found at index 591
1 found at index 701
1 found at index 720
1 found at index 739
1 found at index 784
1 found at index 843
1 found at index 846
1 found at index 864
1 found at index 912
1 found at index 996
1 found at index 1005

文字列表現:

In [10]: rsl
Out[10]: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

ノート

ベースのset実装はさらにメモリ効率が高くなりますが、上記のdict0は、および以外の (ランダムまたはその他の) 値を含むように簡単に変更できます1。

アップデート

この質問と、標準のスパース実装の欠如に触発されて、チーズ ショップにsparse_listlist実装を追加しました 。でインストールすると、実装がはるかに簡単になります。pip install sparse_listRandomSparseList

from sparse_list import SparseList
from random import randint


class RandomSparseList(SparseList):
    def __init__(self, size, min_bits, max_bits):
        super(RandomSparseList, self).__init__(size, 0)
        self.bits = randint(min_bits, max_bits)
        while self.bits > len(self.elements):
            self.elements[randint(0, self.size)] = 1

これは上記の例とまったく同じように機能しますが、拡張スライスなどの追加機能がいくつかあります。GitHubでソースを読む (そして貢献する) ことができます。

Answer 3

これが私の解決策です。位置と 1 の数はどちらもランダムです。アルゴリズムが機能するかどうかを確認するために、ones 配列に位置があります。

from random import randint

MAX_NUMS=1000
#big array of 0s
arr = [0] * MAX_NUMS

#How many 1s do you want?
numOnes=randint(10, 40)
ones=[1]*numOnes

#Fill array with random postions 
for i in range(0,numOnes-1):
        ones[i] =  randint(0,MAX_NUMS-1)
print ones

#Set arr to 1 for each random postion
for pos in ones:
        arr[pos]=1
print arr