2

一連の数字で特定の長さの不連続 (ギャップ) を見つけるという問題に直面しています。したがって、たとえば、[1,2,3,7,8,9,10]と のギャップが与えられた場合、length=3が見つかります[4,5,6]。ギャップが の場合、length=4何も見つかりません。もちろん、実際のシーケンスはもっと長くなります。この問題はかなりの数の投稿で見てきましたが、さまざまなアプリケーションと可能な実装がありました。

私がうまくいくと思った方法の 1 つは、完全なセットを、使用可能な番号の 1 と欠落の 0 を含むビット配列として表すことです。したがって、上記は のようになります[1,1,1,0,0,0,1,1,1,1]。次に、すべての位置が 1 になるまで、指定された長さの配列を完全なセットで XOR マスクするウィンドウ関数を実行する可能性があります。各実行でのマスキング。

これが私が思いついたものです：

def find_gap(array, start=0, length=10):
    """
    array:  assumed to be of length MAX_NUMBER and contain 0 or 1 
            if the value is actually present
    start:  indicates what value to start looking from
    length: what the length the gap should be
    """

    # create the bitmask to check against
    mask = ''.join( [1] * length )

    # convert the input 0/1 mapping to bit string
    # e.g - [1,0,1,0] -> '1010'
    bits =''.join( [ str(val) for val in array ] )

    for i in xrange(start, len(bits) - length):

        # find where the next gap begins
        if bits[i] != '0': continue

        # gap was found, extract segment of size 'length', compare w/ mask
        if (i + length < len(bits)):
            segment = bits[i:i+length]

            # use XOR between binary masks
            result  = bin( int(mask, 2) ^ int(segment, 2) )

            # if mask == result in base 2, gap found
            if result == ("0b%s" % mask): return i

    # if we got here, no gap exists
    return -1

これは、約 100k (< 1 秒) でかなり高速です。大規模なセットでこれをより速く/より効率的にする方法についてのヒントをいただければ幸いです。ありがとう！

4

5 に答える 5

2

隣接する数値の違いを見つけて、十分な大きさの違いを探します。2 つのリスト (最初の数字以外のすべての数字と最後の数字以外のすべての数字) を作成し、それらをペアで減算することによって違いを見つけます。zip値をペアにするために使用できます。

def find_gaps(numbers, gap_size):
    adjacent_differences = [(y - x) for (x, y) in zip(numbers[:-1], numbers[1:])]
    # If adjacent_differences[i] > gap_size, there is a gap of that size between
    # numbers[i] and numbers[i+1]. We return all such indexes in a list - so if
    # the result is [] (empty list), there are no gaps.
    return [i for (i, x) in enumerate(adjacent_differences) if x > gap_size]

(また、いくつかの Python イディオムを学んでください。私たちは直接反復を好み、真のブール型を使用しています。)

于 2010-12-07T10:01:43.590 に答える
2

XOR とシフトを使用することができ、おおよそ O(n) 時間で実行されます。

ただし、実際には、インデックス (最小長よりも大きいすべてのギャップのハッシュ リスト) を作成する方が適切な方法である可能性があります。

これらの整数のシーケンス (ビットマスクではなく) から開始すると仮定すると、シーケンスを単純にたどってインデックスを作成します。しきい値より大きいギャップを見つけたら、そのギャップ サイズをディクショナリに追加します (必要に応じて空のリストとしてインスタンス化し、シーケンスにオフセットを追加します。

最後に、シーケンス内のすべてのギャップ (目的のしきい値より大きい) のリストが表示されます。

このアプローチの良い点の 1 つは、ベース リストを変更するときに、このインデックスを維持できることです。したがって、インデックスの構築に費やされた O(n*log(n)) の初期時間は、後続のクエリとインデックスの更新の O(log(n)) コストによって償却されます。

を構築するための非常に大雑把な関数を次に示しgap_index()ます。

def gap_idx(s, thresh=2):
    ret = dict()
    lw = s[0]  # initial low val.
    for z,i in enumerate(s[1:]):
        if i - lw < thresh:
            lw = i
            continue
        key = i - lw
        if key not in ret:
            ret[key] = list()
        ret[key].append(z)
        lw = i
    return ret

insort()データセットとインデックスの両方を維持するクラスは、組み込みの「bisect」モジュールとその機能を中心に構築するのが最適です。

于 2010-12-08T10:21:49.737 に答える
1

これらは、入力リストの単一のウォークを提供します。

指定された長さのギャップ値のリスト:

from itertools import tee, izip
def gapsofsize(iterable, length):
    a, b = tee(iterable)
    next(b, None)
    return ( p for x, y in izip(a, b) if y-x == length+1 for p in xrange(x+1,y) )

print list(gapsofsize([1,2,5,8,9], 2))

[3, 4, 6, 7]

すべてのギャップ値:

def gaps(iterable):
    a, b = tee(iterable)
    next(b, None)
    return ( p for x, y in izip(a, b) if y-x > 1 for p in xrange(x+1,y) )

print list(gaps([1,2,4,5,8,9,14]))

[3, 6, 7, 10, 11, 12, 13]

ベクトルとしてのギャップのリスト:

def gapsizes(iterable):
    a, b = tee(iterable)
    next(b, None)
    return ( (x+1, y-x-1) for x, y in izip(a, b) if y-x > 1 )

print list(gapsizes([1,2,4,5,8,9,14]))

[(3, 1), (6, 2), (10, 4)]

これらはジェネレーターであり、メモリをほとんど消費しないことに注意してください。これらがテスト データセットでどのように機能するかを知りたいです。

于 2010-12-07T10:51:00.343 に答える
1

aix が行ったこととほとんど同じですが、必要な長さのギャップのみを取得します。

def findGaps(mylist, gap_length, start_idx=0):
    gap_starts = []
    for idx in range(start_idx, len(mylist) - 1):
        if mylist[idx+1] - mylist[idx] == gap_length + 1:
            gap_starts.append(mylist[idx] + 1)

    return gap_starts

編集：OPの希望に合わせて調整。

于 2010-12-07T10:28:16.430 に答える
1

あなたが求めているのが効率である場合、私は次の行に沿って何かをします（xシーケンス番号のリストはどこにありますか）：

for i in range(1, len(x)):
  if x[i] - x[i - 1] == length + 1:
    print list(range(x[i - 1] + 1, x[i]))
于 2010-12-07T10:18:39.753 に答える