2

n個のリストからすべての可能な組み合わせを計算し、最小二乗差が最小の組み合わせを維持するための非常に効率的な方法を探しています。

私はすでにそれを行うコードを持っていますが、それが数百万の組み合わせになると、物事は遅くなります。

Candidates_lenには、[[500、490、510、600] [300、490、520] [305、497、515]]などの長さのリストのリストが含まれます。candidates_nameに は、[['a'、 ' b'、' c'、' d'] ['mi'、' mu'、' ma'] ['pi'、' pu'、' pa']]

両方のリストにはn個のリストがあります。

#    Creating the possible combinations and store the lists of lengths in vector r
r=[[]]
for x in candidates_len:
    r = [ i + [y] for y in x for i in r ]
#Storing the names of the combinations and store the lists of identifiers in vector z
z=[[]]
for x in candidates_name:
    z = [ i + [y] for y in x for i in z ]          
#Calculating distances and storing the minimum one
min_index = 0
min_dist = 0
list_best = []
for index, item in enumerate(r):
    n = 0
    dist = 0
    while n < len(candidates_len):
        for i in range(n,len(candidates_len)):
            dist = dist + (item[n]-item[i])**2
        n=n+1
    if index==0:
            min_dist = dist
            min_index = index
            list_best.append(item)
    elif dist < min_dist:
        min_dist = dist
        min_index = index
        list_best = []
        list_best.append(z[index])
least_combination = min_index

ハードケース： http： //pastebin.com/BkVQTQWK

ここにいくつかのテスト時間があります。1分かそこら以下に入るのが良いでしょう。それが可能かどうかはわかりませんが。

combinations time(s)
77760   1.255663
41184   1.580333
69120   6.214786
8960   1.131834
537600  14.855361
89100   1.264126
16384   3.247404
4199040 666.853284
226800   3.935878
9289728 679.064149
4

2 に答える 2

5

ここでの私の最初の考えは、あなたが必要のないリストを構築するのに非常に多くの時間を費やしているということです。少なくとも、それらを廃棄すると、物事がはるかに簡単になりますが、実際に物事が速くなるという保証はありません。

r = itertools.product(*candidates_len)
z = itertools.product(*candidates_name)

min_dist = None
for item, names in itertools.izip(r, z):
  dist = 0
  for n in range(len(item)):
    for i in range(n, len(item)):
      dist += (item[n]-item[i])**2
  if min_dist is None or dist < min_dist:
    min_dist = dist
    best = item, names

print(best)

テストデータでは、明示的なリストがギガバイトのメモリを消費しています。どれだけかはわかりません。私の貧弱な4GBのラップトップは、zリストの生成が完了する前にスワップスラッシュ地獄に入り、すべてが遅くなりました。セットアップ部分がない場合よりも、操作全体にかかる時間は短くなりitertoolsます。たとえば、16GBのRAMを搭載したマシンではおそらくそうではありませんが、それでも、メモリが必要ない場合は、なぜメモリを使用するのでしょうか。

私の次の考えは、あなたがしているのは、一連のアレイでLSDを計算することだけだということです。小さなアレイの巨大なアレイがありますか？もしそうなら、あなたはそれらのジャグを外すことができますか（例えば、それらにNoneを記入する）そしてnumpy全部を。一方、大きな配列の配列の場合は、配列のリスト（または上記のようにイテレーター）がnumpy必要になる可能性があるため、少なくとも1つの次元をベクトル化できます。

いずれにせよ、ベクトル化は、大きな配列に対する単純な操作を伴うものを最適化するための鍵であり、numpy多くの場合、エキスパートのC++およびFortranおよびプラットフォーム固有のアセンブリコーダーが手動で行う可能性のあるものよりも優れています。

コードを熟考することも、アルゴリズムを深いレベルで理解しようとすることもなく、私の最初の試みは、r（上記のコードのように）シーケンスとして生成することですが、numpy行ベクトル（のようなものmatrix(x, dtype=int) for x in itertools.product(*candidates_len)）を生成することです。次に、それぞれの差を計算してから、下の三角形の2乗を合計しitemますitem - item.T（これは、方法を理解するために調べる必要があります）。そもそも下の三角形だけを計算する方法を考え出すことで、おそらくパフォーマンスをさらに向上させることができます。これに対する典型的なトリックは、ベクトル化された演算の一部として下三角和を対角線に入れる方法を理解することです。次に、対角線を抽出するだけですが、それが常に適切であるとは限りません。放送ドキュメントを参照してください明示的な行列を作成せずに内部ループをベクトル化する方法に関するいくつかのアイデア。最後に、全体から3D配列を作成して（個々のアイテムを固定幅にパディングすることを意味する場合があります）、操作全体をベクトル化する方法があるかどうかを確認します。（メモリ使用numpy量は、値全体ではなく各値に4バイトを割り当てるだけでよいので、それほど悪くはありませんPyObject…しかし、それでも十分に悪いので、得るよりも多くを失う可能性があります。）これがすべて少しなら申し訳ありません漠然としていますが、うまくいけば、実験を始めるのに十分です。

もう1つの考えは、おそらくこれを並列化できるということです。その膨大なリストを処理するのに十分なメモリを備えたマシンであれば、少なくとも4つのコアが搭載されていると思います。そして、完全に独立した操作の長いシーケンスがあります。これは、並列化するのが世界で最も簡単なことです。最初のステップとして、を作成しmultiprocessing.Pool、作業を直接行うのではなく、外側のループにジョブをプールに送信させます。ジョブが小さすぎるため、頭上で溺れていることに気付くでしょうが、いつでもN個のアイテムをまとめて（明示的に、またはドキュメントのgrouperレシピを参照してitertools）、ジョブを「ループ」にすることができます。これらのN個のアイテムを超えて、最小LSDのアイテムを返します。」（最適なNを見つけるには、多少の調整が必要になる場合があります。）これはトップレベルと一緒に行うこともできます。numpy、x軸に沿って巨大な配列をチャンクに分割し、それらをジョブとしてファームアウトすることによって。

もう1つの考え：アルゴリズムはN * Mの積で始まり、各要素の長さはNです。次に、各要素について、2回ループします。したがって、可能な限り最高のパフォーマンスはO（N ^ 3 * M）になります。これは本当に正しいアルゴリズムですか？もしそうなら、あなたは実際にあなたのアルゴリズムからN ^ 3 * Mのパフォーマンスを得ていますか？どちらかの質問に対する答えが「いいえ」の場合、それをマイクロ最適化しようとしてはいけません。適切にコーディングされた最も効率的なアルゴリズムを実際に入手した場合にのみ、ベクトル化、過剰な作業の回避、タイトループのC ++およびFortranへの移行などを行う価値があります。それ以外の場合は、戻って「しかし、前回のテスト実行の4倍の大きさにすると、それでも爆発します。」

于 2012-12-05T20:16:22.477 に答える
2

私が最初にすることは、これをできるだけ多くNumpy配列に入れることです。Numpyの配列ベースの操作は、多かれ少なかれC速度で実行されます。そもそも、これの多くはNumpyで実行できるようです...

それでも血が流れない場合は、コードのプロファイルを作成し、Cythonでボッテルネック用の関数を作成します。リスト/配列に静的型を置くことができると仮定すると、Pythonicの世界にとどまりたいのであれば、Cythonがおそらく最善の策になるでしょう。私は個人的に、Cythonを使用したいくつかのボトルネックの100倍のスピードアップを見てきました。

これは、ドキュメントからのCythonによる画像畳み込みの例です。

于 2012-12-05T20:20:13.570 に答える