Saya memiliki sampel besar (M) array boolean dengan panjang 'N'. Jadi ada 2^N array boolean unik yang mungkin. Saya ingin tahu berapa banyak array yang merupakan duplikat satu sama lain dan membuat histogram.

Salah satu kemungkinan adalah membuat bilangan bulat unik (a[0] + a[1]*2 + a[3]*4 + ...+a[N]*2^(N-1)) untuk setiap larik unik dan histogram bilangan bulat itu.

Tapi ini akan menjadi O(M*N). Apa cara terbaik untuk melakukan ini?

1
PyariBilli 27 November 2021, 09:32
Itu sangat tergantung pada output Anda. Menyimpan kombinasi 2^N membakar memori Anda dengan cepat untuk nilai N yang besar. Dalam hal ini sebaiknya gunakan np.histogram. Mungkin hanya sebagian kecil saja yang ada di arr. Dalam hal ini Anda tidak perlu bekerja dengan 2^N item dan menggunakan np.bincount. Tidak ada cara yang lebih baik daripada melakukan (a[0] + a[1]*2 + a[3]*4 + ...+a[N]*2^(N-1) dan numpy.ravel_multi_index benar-benar melakukannya pada intinya. Tetapi jika Anda menyukai sesuatu yang lebih berkinerja, coba numexpr
 – 
mathfux
27 November 2021, 12:47

2 jawaban

Jawaban Terbaik

numpy.ravel_multi_index dapat melakukan ini untuk Anda :

arr = np.array([[True, True, True], 
              [True, False, True], 
              [True, False, True], 
              [False, False, False], 
              [True, False, True]], dtype=int)
nums = np.ravel_multi_index(arr.T, (2,) * arr.shape[1])
>>> nums
array([7, 5, 5, 0, 5], dtype=int64)

Dan karena Anda membutuhkan histogram, gunakan

>>> np.histogram(nums, bins=np.arange(2**arr.shape[1]+1))
(array([1, 0, 0, 0, 0, 3, 0, 1], dtype=int64), 
 array([0, 1, 2, 3, 4, 5, 6, 7, 8]))

Opsi lain adalah menggunakan np.unique:

>>> np.unique(arr, return_counts=True, axis=0)
(array([[0, 0, 0],
        [1, 0, 1],
        [1, 1, 1]]),
 array([1, 3, 1], dtype=int64))
1
mathfux 27 November 2021, 12:25

Dengan operasi vektor, pembuatan kunci jauh lebih cepat daripada a[0] + a[1]x2 + a[3]x4 + ...+a[N]*2^(N-1). Saya pikir itu bukan solusi yang lebih baik... dalam kasus apa pun Anda hampir harus "membaca" satu kali setiap nilai, dan ini memerlukan langkah MxN.

N = 3
M = 5
sample = [
    np.array([True, True, True]),
    np.array([True, False, True]),
    np.array([True, False, True]),
    np.array([False, False, False]),
    np.array([True, False, True]),
]

multipliers = [2<<i for i in range(N-2, -1, -1)]+[1]

buckets = {}
buck2vec = {}
for s in sample:
    key = sum(s*multipliers)
    if key not in buckets:
        buckets[key] = 0
        buck2vec[key] = s
    buckets[key]+=1
    
for key in buckets:
    print(f"{buck2vec[key]} -> {buckets[key]} occurency")

Hasil:

[False False False] -> 1 occurency
[ True False  True] -> 3 occurency
[ True  True  True] -> 1 occurency
-1
Massimo Rebuglio 27 November 2021, 11:28