2

Pythonスクリプトのリストにそれぞれ2セットの数字があります。最初のリストの各数値について、2番目の数値のいずれかがそれよりも大きいかどうかを確認する必要があります。n2がn1よりも大きかった回数だけが必要です。（たとえば、numset1is[7,2]とnumset2is[6,9]の場合、必要なのは3つだけです）現在、これを実行しています。各n1を調べて、各n2がそれよりも大きいかどうかを確認します。

possibilities = [(n1<n2) for n1 in numset1 for n2 in numset2]
numPossibilities = sum(possibilities)

現在、これは私のスクリプトの中で最も遅い部分です。特に、より大きなデータセット（数千の数値を含むnumset1とnumset2）を処理する場合はそうです。これをより効率的にする方法があると確信していますが、方法がわかりません。

4

3 に答える 3

3

並べ替えnumset2てから繰り返しますが、たとえば、bisectモジュールをnumset1使用してバイナリ検索を使用します：http： //docs.python.org/2/library/bisect.htmlnumset2

import bisect
# your code here
numset2.sort()
L = len(numset2)
numPossibilities = sum([bisect.bisect_right(numset2,n1) < L for n1 in numset1])

また、元のコードは2番目の文で要求したものを計算しないことに注意してください。の各要素について、基準に一致する要素があるかどうかではなく、この要素よりも大きい要素の数をnumset1合計します。numset2

元のコードと一致させるには、次のようにします。

numPossibilities = sum([L - bisect.bisect_right(numset2,n1) for n1 in numset1])
于 2012-12-07T00:51:02.510 に答える
2

問題は、の各組み合わせを反復処理する必要があることです。組み合わせが(n1, n2)ありますlen(numset1) * len(numset2)。これは、非常に大きい場合にnumset1非常にnumset2大きくなります。

別の言い方をすれば、アルゴリズムの実行時間はO（n ^ 2）です（len(numset1)がほぼ等しい場合len(numset2)。その実行時間をより速くしましょう。:-)

リストを並べ替えると、これがはるかに簡単になります。numset1では、並べ替えてみましょうnumset2。

>>> numset1.sort()
>>> numset2.sort()

numset1ここで、 （と呼ぶn1）の最小要素と（と呼ぶ）numset2の最小要素を比較しn2ます。が小さい場合、それよりも大きい要素n1があることがわかります。が小さい場合、の要素はそれよりも小さいことがわかります。len(numset2)numset2n2numset1

これはPythonリストのO（n）操作であるため、リストの先頭から実際に要素を削除する必要はありません。代わりに、各リストのどこにいるかを追跡し、繰り返します。

>>> n1_idx, n2_idx, accumulator = 0, 0, 0
>>> while n1_idx < len(numset1) and n2_idx < len(numset2):
        if numset1[n1_idx] < numset2[n2_idx]:
            accumulator += len(numset2) - n2_idx
            n1_idx += 1
        else:
            n2_idx += 1

この操作の最後に、リストの並べ替えにO（nlog（n））時間を費やし、反復を行うためにO（n）時間を費やしたため、全体的な実行時の複雑さはO（nlog（n））になります。

それと、ペアaccumulatorの数があります。(n1, n2)n1 < n2

于 2012-12-07T01:03:26.477 に答える
0

これがかなり効率的な実装であるべきものです：

def get_possibilities(numset1, numset2):
    sortset1 = sorted(numset1)
    sortset2 = sorted(numset2)
    total = 0
    i2 = 0
    for i1, n1 in enumerate(sortset1, 1):
        while sortset2[i2] <= n1:
            i2 += 1
            if i2 >= len(sortset2):
                # reached end of i2, so just return total now
                return total
            # current from sortset2 is greater than from sortset1 so far
            total += i1
    # all remaining elements of sortset2 greater than all elements of sortset1
    total += (len(sortset2) - i2 - 1) * len(sortset1)
    return total

これは、各セットを1回だけ繰り返します。これは、実行する前にセットをソートすることによって実行されます。これにより、ロジックの改善が可能になります。これは、sortset2at indexのi2要素がatindexの要素よりも大きい場合、以前のインデックスのすべての要素よりも大きいためです。sortset1i1sortset1

于 2012-12-07T01:17:17.607 に答える