4

Python でインクリメンタルな Numpy 配列の必要性に出くわしました。何も見つからないので、それを実装しました。私の方法が最善の方法なのか、それとも他のアイデアを思い付くことができるのか疑問に思っています.

したがって、問題は、サイズが事前に知られていない2D配列（プログラムはnD配列を処理する）を持っており、可変量のデータを配列に一方向に連結する必要があることです（私がしたとしましょうnp.vstak を何度も呼び出します)。データを連結するたびに、配列を取得し、軸 0 に沿って並べ替え、その他の操作を行う必要があるため、配列の長いリストを作成してから、リストを一度に np.vstak することはできません。メモリ割り当てはコストがかかるため、インクリメンタル配列に目を向けました。ここでは、必要なサイズよりも大きな数量の配列のサイズをインクリメントし (50% のインクリメントを使用します)、割り当ての数を最小限に抑えます。

これをコード化しました。次のコードで確認できます。

class ExpandingArray:

    __DEFAULT_ALLOC_INIT_DIM = 10   # default initial dimension for all the axis is nothing is given by the user
    __DEFAULT_MAX_INCREMENT = 10    # default value in order to limit the increment of memory allocation

    __MAX_INCREMENT = []    # Max increment
    __ALLOC_DIMS = []       # Dimensions of the allocated np.array
    __DIMS = []             # Dimensions of the view with data on the allocated np.array (__DIMS <= __ALLOC_DIMS)

    __ARRAY = []            # Allocated array

    def __init__(self,initData,allocInitDim=None,dtype=np.float64,maxIncrement=None):
        self.__DIMS = np.array(initData.shape)

        self.__MAX_INCREMENT = maxIncrement
        if self.__MAX_INCREMENT == None:
            self.__MAX_INCREMENT = self.__DEFAULT_MAX_INCREMENT

        # Compute the allocation dimensions based on user's input
        if allocInitDim == None:
            allocInitDim = self.__DIMS.copy()

        while np.any( allocInitDim < self.__DIMS  ) or np.any(allocInitDim == 0):
            for i in range(len(self.__DIMS)):
                if allocInitDim[i] == 0:
                    allocInitDim[i] = self.__DEFAULT_ALLOC_INIT_DIM
                if allocInitDim[i] < self.__DIMS[i]:
                    allocInitDim[i] += min(allocInitDim[i]/2, self.__MAX_INCREMENT)

        # Allocate memory 
        self.__ALLOC_DIMS = allocInitDim
        self.__ARRAY = np.zeros(self.__ALLOC_DIMS,dtype=dtype)

        # Set initData 
        sliceIdxs = [slice(self.__DIMS[i]) for i in range(len(self.__DIMS))]
        self.__ARRAY[sliceIdxs] = initData

    def shape(self):
        return tuple(self.__DIMS)

    def getAllocArray(self):
        return self.__ARRAY

    def getDataArray(self):
        """
        Get the view of the array with data
        """
        sliceIdxs = [slice(self.__DIMS[i]) for i in range(len(self.__DIMS))]
        return self.__ARRAY[sliceIdxs]

    def concatenate(self,X,axis=0):
        if axis > len(self.__DIMS):
            print "Error: axis number exceed the number of dimensions"
            return

        # Check dimensions for remaining axis 
        for i in range(len(self.__DIMS)):
            if i != axis:
                if X.shape[i] != self.shape()[i]:
                    print "Error: Dimensions of the input array are not consistent in the axis %d" % i
                    return

        # Check whether allocated memory is enough 
        needAlloc = False
        while self.__ALLOC_DIMS[axis] < self.__DIMS[axis] + X.shape[axis]:
            needAlloc = True
            # Increase the __ALLOC_DIMS 
            self.__ALLOC_DIMS[axis] += min(self.__ALLOC_DIMS[axis]/2,self.__MAX_INCREMENT)

        # Reallocate memory and copy old data 
        if needAlloc:
            # Allocate 
            newArray = np.zeros(self.__ALLOC_DIMS)
            # Copy 
            sliceIdxs = [slice(self.__DIMS[i]) for i in range(len(self.__DIMS))]
            newArray[sliceIdxs] = self.__ARRAY[sliceIdxs]
            self.__ARRAY = newArray

        # Concatenate new data 
        sliceIdxs = []
        for i in range(len(self.__DIMS)):
            if i != axis:
                sliceIdxs.append(slice(self.__DIMS[i]))
            else:
                sliceIdxs.append(slice(self.__DIMS[i],self.__DIMS[i]+X.shape[i]))

        self.__ARRAY[sliceIdxs] = X
        self.__DIMS[axis] += X.shape[axis]

このコードは、vstack/hstack のいくつかのランダムなサイズの連結よりもかなり優れたパフォーマンスを示しています。

私が疑問に思っているのは、それが最善の方法ですか? これをすでにnumpyで行うものはありますか?

さらに、np.array のスライス代入演算子をオーバーロードできると便利です。これにより、ユーザーが実際の次元の外側に何かを代入するとすぐに ExpandingArray.concatenate() が実行されます。そのようなオーバーロードを行う方法は？

テスト コード: vstack とメソッドを比較するために使用したコードもここに投稿します。最大長 100 のデータのランダムなチャンクを合計します。

import time

N = 10000

def performEA(N):
    EA = ExpandingArray(np.zeros((0,2)),maxIncrement=1000)
    for i in range(N):
        nNew = np.random.random_integers(low=1,high=100,size=1)
        X = np.random.rand(nNew,2)
        EA.concatenate(X,axis=0)
        # Perform operations on EA.getDataArray()
    return EA

def performVStack(N):
    A = np.zeros((0,2))
    for i in range(N):
        nNew = np.random.random_integers(low=1,high=100,size=1)
        X = np.random.rand(nNew,2)
        A = np.vstack((A,X))
        # Perform operations on A
    return A

start_EA = time.clock()
EA = performEA(N)
stop_EA = time.clock()

start_VS = time.clock()
VS = performVStack(N)
stop_VS = time.clock()

print "Elapsed Time EA: %.2f" % (stop_EA-start_EA)
print "Elapsed Time VS: %.2f" % (stop_VS-start_VS)
4

2 に答える 2

2

これらの最も一般的な設計パターンは、小さな配列にリストを使用することだと思います。確かに、動的なサイズ変更などを行うことができます (クレイジーなことをしたい場合は、サイズ変更配列メソッドも使用できます)。どのくらいの大きさになるかわからない場合は、常にサイズを 2 倍にするのが典型的な方法だと思います。もちろん、配列がどれだけ大きくなるかわかっている場合は、前もってすべてを割り当てるのが最も簡単です。

def performVStack_fromlist(N):
    l = []
    for i in range(N):
        nNew = np.random.random_integers(low=1,high=100,size=1)
        X = np.random.rand(nNew,2)
        l.append(X)
    return np.vstack(l)

展開する配列が役立つユースケースがいくつかあると確信していますが (たとえば、追加する配列がすべて非常に小さい場合)、このループは上記のパターンで処理したほうがよいようです。最適化は主に、すべてをコピーする必要がある頻度に関するものであり、このようなリスト (リスト自体以外) を実行するのは、ここで 1 回だけです。そのため、通常ははるかに高速です。

于 2013-02-22T15:18:24.433 に答える
2

同様の問題に直面したとき、私は ndarray.resize() ( http://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.resize.html#numpy.ndarray.resize )を使用しました。ほとんどの場合、再割り当てとコピーを完全に回避します。それがより高速であることが証明されるとは保証できませんが (おそらくそうなるでしょう)、非常に単純です。

2 番目の質問については、拡張目的でスライスの割り当てをオーバーライドすることはお勧めできません。その演算子は、既存のアイテム/スライスに割り当てるためのものです。それを変更したい場合、場合によってはどのように動作させたいかがすぐにはわかりません。たとえば、次のようになります。

a = MyExtendableArray(np.arange(100))
a[200] = 6  # resize to 200? pad [100:200] with what?
a[90:110] = 7  # assign to existing items AND automagically-allocated items?
a[::-1][200] = 6 # ...

私の提案は、スライスの割り当てとデータの追加は別々にしておくべきだということです。

于 2013-02-22T15:36:13.457 に答える