2

定義: 配列A(a1,a2,...,an)は、それらが同じサイズで、～から～までのすべての場合>=よりも大きいB(b1,b2,...bn)a_i>=b_ii1n.

例えば：

[1,2,3] >= [1,2,0]
[1,2,0] not comparable with [1,0,2]
[1,0,2] >= [1,0,0]

多数のそのような配列 (約 10000 ですが、それ以上になる可能性があります) で構成されるリストがあります。配列の要素は正の整数です。このリストから、少なくとも 1 つの他の配列よりも大きいすべての配列を削除する必要があります。Bつまり、そのようなものが存在する場合A >= Bは削除しAます。

これが非常に遅い私の現在のO(n^2)アプローチです。すべての配列を他のすべての配列と単純に比較し、それが大きい場合は削除します。高速化する方法はありますか。

import numpy as np
import time
import random

def filter_minimal(lst):
    n = len(lst)
    to_delete = set()
    for i in xrange(n-1):
        if i in to_delete:
            continue
        for j in xrange(i+1,n):
            if j in to_delete: continue
            if all(lst[i]>=lst[j]):
                to_delete.add(i)
                break
            elif all(lst[i]<=lst[j]):
                to_delete.add(j)
    return [lst[i] for i in xrange(len(lst)) if i not in to_delete]


def test(number_of_arrays,size):
    x = map(np.array,[[random.randrange(0,10) for _ in xrange(size)] for i in xrange(number_of_arrays)])
    return filter_minimal(x)

a = time.time()
result = test(400,10)
print time.time()-a
print len(result)

numpy.allPS組み込みのpythonの代わりに使用するとall、プログラムが劇的に遅くなることに気付きました。その理由は何ですか？

4

2 に答える 2

1

まさにあなたが求めているものではないかもしれませんが、これで始められるはずです。

import numpy as np
import time
import random

def compare(x,y):
    #Reshape x to a higher dimensional array
    compare_array=x.reshape(-1,1,x.shape[-1])
    #You can now compare every x with every y element wise simultaneously
    mask=(y>=compare_array)
    #Create a mask that first ensures that all elements of y are greater then x and
    #then ensure that this is the case at least once.
    mask=np.any(np.all(mask,axis=-1),axis=-1)
    #Places this mask on x
    return x[mask]

def test(number_of_arrays,size,maxval):
    #Create arrays of size (number_of_arrays,size) with maximum value maxval.
    x = np.random.randint(maxval, size=(number_of_arrays,size))
    y=  np.random.randint(maxval, size=(number_of_arrays,size))
    return compare(x,y)

print test(50,10,20)
于 2013-02-20T15:07:21.870 に答える
0

まず、目的を注意深く確認する必要があります。削除されたアレイであっても、他のアレイのいずれかであるアレイを削除するのは本当ですか？たとえば、A>BおよびC>AおよびB= Cの場合、Aのみを削除する必要がありますか、それともAとCの両方を削除する必要がありますか？INCOMPATIBLE配列のみを削除する必要がある場合、それははるかに難しい問題です。アレイのセットの異なるパーティションに互換性がある可能性があるため、これは非常に難しい問題です。そのため、最大の有効なパーティションを見つけるという問題があります。

簡単な問題を想定すると、問題を定義するためのより良い方法は、少なくとも1つの要素<他のすべての配列の対応する要素を持つすべての配列を保持することです。（難しい問題では、これは他のKEPT配列の対応する要素です。これについては考慮しません。）

ステージ1

この問題を解決するには、配列を列に配置してから、配列のキーと各配列の行の位置へのマッピング（POSITIONリスト）を維持しながら、各行を並べ替えます。たとえば、次のようなステージ1の結果になる可能性があります。

行1：BCDAE
行2：CAEBD
行3：EDBCA

つまり、最初の要素（行1）の配列Bの値は> = C、C>=Dなどです。

ここで、この行列の最後の列（例では{EDA}）を並べ替えて繰り返します。各項目について、その要素がその行の前の要素よりも小さいかどうかを確認します。たとえば、行1で、E <Aかどうかを確認します。これが当てはまる場合は、すぐに戻って結果を保持します。たとえば、E_row1 <A_row1の場合、配列Eを保持できます。行の値が等しい場合にのみ、ステージ2テストを実行する必要があります（以下を参照）。

示されている例では、E、D、Aを保持します（上記のテストに合格している限り）。

ステージ2

これにより、BとCが残ります。それぞれのPOSITIONリストを並べ替えます。たとえば、これにより、Bの最小位置の行が行2であることがわかります。次に、Bと、最小行のその下にあるすべての配列、ここでは行2を直接比較します。このような配列はDだけです。 BとDを直接比較します。これは、行3でB <Dであることを示しています。したがって、BはDと互換性があります。アイテムが最小位置より下のすべての配列と互換性がある場合は、それを保持します。Bを保持します。

ここで、Cに対して同じことを行います。Cの場合、直接比較する必要があるのは1つだけで、Aを使用します。CがAを支配するため、Cを保持しません。

最後の列に表示されなかったアイテムをテストすることに加えて、ステージ1で等しいアイテムをテストする必要があることに注意してください。たとえば、行1のD = A = Eを想像してください。この場合、直接比較する必要があります。最後の列の配列を含むすべての等式に対して。したがって、この場合、EをAに、EをDに直接比較します。これは、EがDを支配していることを示しているため、Eは保持されません。

最終的な結果は、A、B、およびDを保持することです。CとEは破棄されます。

このアルゴリズムの全体的なパフォーマンスは、ステージ1ではn2 * log n + {n下限、ステージ2ではn * log n-上限}です。したがって、最大実行時間はn2 * log n + nlognであり、最小実行時間はn2lognです。 +n。アルゴリズムの実行時間はn-cubedn3であることに注意してください。各行列（n * n）を比較し、各比較はn要素の比較= n * n*nであるため。

一般に、これはブルートフォースアプローチよりもはるかに高速です。ほとんどの時間は、多かれ少なかれ避けられないタスクである、元のマトリックスのソートに費やされます。並べ替えの代わりに優先度付きキューを使用することでアルゴリズムを改善できる可能性がありますが、結果のアルゴリズムははるかに複雑になることに注意してください。

于 2013-02-20T19:38:59.987 に答える