Python：獲取陣列中的最大出現次數-有解無憂

我實作了代碼以嘗試在numpy array中獲得最大的出現次數。我對使用numba感到滿意，但有局限性。我想知道它是否可以改進為一般情況。

numba 實施

import numba as nb
import numpy as np
import collections

@nb.njit("int64(int64[:])")
def max_count_unique_num(x):
    """
    Counts maximum number of unique integer in x.

    Args:
        x (numpy array): Integer array.

    Returns:
        Int

    """
    # get maximum value
    m = x[0]
    for v in x:
        if v > m:
            m = v

    if m == 0:
        return x.size

    # count each unique value
    num = np.zeros(m   1, dtype=x.dtype)
    for k in x:
        num[k]  = 1
    # maximum count
    m = 0
    for k in num:
        if k > m:
            m = k
    return m

為了比較，我還實作了 numpy'sunique和collections.Counter

def np_unique(x):
    """ Counts maximum occurrence using numpy's unique. """
    ux, uc = np.unique(x, return_counts=True)
    return uc.max()


def counter(x):
    """ Counts maximum occurrence using collections.Counter. """
    counts = collections.Counter(x)
    return max(counts.values())

時間

編輯np.bincount：按照@MechanicPig 的建議添加以進行額外比較。

In [1]: x = np.random.randint(0, 2000, size=30000).astype(np.int64)
In [2]: %timeit max_count_unique_num(x)
30 μs ± 387 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
In [3]: %timeit np_unique(x)
1.14 ms ± 1.65 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
In [4]: %timeit counter(x)
2.68 ms ± 33.9 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [5]: x = np.random.randint(0, 200000, size=30000).astype(np.int64)
In [6]: %timeit counter(x)
3.07 ms ± 40.5 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [7]: %timeit np_unique(x)
1.3 ms ± 7.35 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
In [8]: %timeit max_count_unique_num(x)
490 μs ± 1.47 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
In [9]: x = np.random.randint(0, 2000, size=30000).astype(np.int64)
In [10]: %timeit np.bincount(x).max()
32.3 μs ± 250 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
In [11]: x = np.random.randint(0, 200000, size=30000).astype(np.int64)
In [12]: %timeit np.bincount(x).max()
830 μs ± 6.09 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

numba 實作的局限性非常明顯：只有當所有值x都是小的正數時效率才會int大大降低int；不適用于float負值。

有什么方法可以概括實作并保持速度？

更新
檢查源代碼后np.unique，一般情況下的實作可以是：

@nb.njit(["int64(int64[:])", "int64(float64[:])"])
def max_count_unique_num_2(x):
    x.sort()
    n = 0
    k = 0
    x0 = x[0]
    for v in x:
        if x0 == v:
            k  = 1
        else:
            if k > n:
                n = k
            k = 1
            x0 = v
    # for last item in x if it equals to previous one
    if k > n:
        n = k
    return n

timeit

In [154]: x = np.random.randint(0, 200000, size=30000).astype(np.int64)
In [155]: %timeit max_count_unique_num(x)
519 μs ± 5.33 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
In [156]: %timeit np_unique(x)
1.3 ms ± 9.88 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
In [157]: %timeit max_count_unique_num_2(x)
240 μs ± 1.92 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
In [158]: x = np.random.randint(0, 200000, size=300000).astype(np.int64)
In [159]: %timeit max_count_unique_num(x)
1.01 ms ± 7.2 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
In [160]: %timeit np_unique(x)
18.1 ms ± 395 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [161]: %timeit max_count_unique_num_2(x)
3.58 ms ± 28.7 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

所以：

如果 in 大整數x且大小不大，則max_count_unique_num_2節拍max_count_unique_num.
兩者max_count_unique_num和max_count_unique_num_2都明顯快于np.unique。
對上的小修改max_count_unique_num_2可以回傳出現次數最多的專案，即使所有專案的最大出現次數都相同。
max_count_unique_num_2x如果is 本身通過洗掉排序，甚至可以加速x.sort()。

uj5u.com熱心網友回復：

如果縮短代碼怎么辦：

@nb.njit("int64(int64[:])", fastmath=True)
def shortened(x):
    num = np.zeros(x.max()   1, dtype=x.dtype)
    for k in x:
        num[k]  = 1

    return num.max()

或并聯：

@nb.njit("int64(int64[:])", parallel=True, fastmath=True)
def shortened_paralleled(x):
    num = np.zeros(x.max()   1, dtype=x.dtype)
    for k in nb.prange(x.size):
        num[x[k]]  = 1

    return num.max()

并行化將勝過更大的資料大小。請注意，并行在某些運行中會得到不同的結果，如果可能，需要進行修復。

使用 Numba 處理浮點數（或負值）：

@nb.njit("int8(float64[:])", fastmath=True)
def shortened_float(x):
    num = np.zeros(x.size, dtype=np.int8)
    for k in x:
        for j in range(x.shape[0]):
            if k == x[j]:
                num[j]  = 1

    return num.max()

IMO，np.unique(x, return_counts=True)[1].max()是在非常快速的實作中同時處理整數和浮點數的最佳選擇。Numba 對于整數可能更快（它取決于資料大小，因為資料大小越大性能越弱；AIK，這是由于回圈本能而不是陣列），但是對于浮點數，如果可以的話，代碼必須在性能方面進行優化；但我不認為 N??umba 可以擊敗NumPy unique，尤其是當我們面對大資料時。

注意：np.bincount只能處理整數。

uj5u.com熱心網友回復：

您也可以在不使用 numpy 的情況下做到這一點。

arr = [1,1,2,2,3,3,4,5,6,1,3,5,7,1]
counts = list(map(list(arr).count, set(arr)))
list(set(arr))[counts.index(max(counts))]

如果你想使用 numpy 然后試試這個，

arr = np.array([1,1,2,2,3,3,4,5,6,1,3,5,7,1])
uniques, counts = np.unique(arr, return_counts = True)
uniques[np.where(counts == counts.max())]

兩者都做完全相同的作業。要檢查哪種方法更有效，只需執行此操作，

time_i = time.time()
<arr declaration> # Creating a new array each iteration can cause the total time to increase which would be biased against the numpy method. 
for i in range(10**5):
  <method you want>
time_f = time.time()

當我運行這個時，第一種方法得到 0.39 秒，第二種方法得到 2.69 秒。所以可以肯定地說第一種方法更有效。

uj5u.com熱心網友回復：

我想說的是，你的實作幾乎和numpy.bincount. 如果想讓它通用，可以考慮對原始資料進行編碼：

def encode(ar):
    # Equivalent to numpy.unique(ar, return_inverse=True)[1] when ar.ndim == 1
    flatten = ar.ravel()
    perm = flatten.argsort()
    sort = flatten[perm]

    mask = np.concatenate(([False], sort[1:] != sort[:-1]))
    encoded = np.empty(sort.shape, np.int64)
    encoded[perm] = mask.cumsum()
    encoded.shape = ar.shape

    return encoded

def count_max(ar):
    return max_count_unique_num(encode(ar))

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/473679.html

標籤：Python 麻木的表现柜台麻木

上一篇：不能將序列乘以非整數

下一篇：Chrome上的JS表排序失敗