ビットマスキングでデータギャップを見つける

Question

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

私は考えていたかもしれませんが、比較的速くなければならないのは、利用可能な数字の1と欠損の0を含むビット配列として完全な集合を表現することです。したがって、上記は[1,1,1,0,0,0,1,1,1,1]のようになります。次に、すべての位置が1になるまで、指定された長さの配列を完全なセットでXORマスクするウィンドウ関数を実行することができます。これは、およそ〜O（n）のシーケンス全体にわたる単一パスと、各走行でマスキングする。

は、ここで私が思い付くことをどうにか何：

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秒）のためにかなり速いです。私はこれをより速くする方法と大きなセットでより効率的にする方法についてのヒントを感謝します。ありがとう！

Answer 1

隣接する数値の差異を見つけて、十分な差異を探します。 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のイディオムを学ぶ。私たちは、直接反復を好む、と私たちは本当のboolean型を持っている。）

Answer 2

それはあなたが後にしている効率だ場合、私は一緒に何かをしたいです（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])) 

Answer 3

でした...しかし、何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 

EDIT：OPの希望に合わせて調整されます。

Answer 4

これらは、入力リストの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)] 

注これらは発電機であり、消費することメモリはほとんどありません。 テストデータセットでこれらがどのように機能するかを知りたいです。

Answer 5

あなたはXORとシフトを使用することができ、おおむねO（n）時間で実行されます。

しかし、実際には、インデックス（ある最小長を超えるすべてのギャップのハッシュリスト）を作成する方が良い方法かもしれません。

（ビットマスクではなく）これらの整数のシーケンスで開始すると仮定すると、単純にシーケンスを歩いてインデックスを作成します。ギャップよりも大きいギャップが見つかると、そのギャップサイズを辞書に追加します（必要に応じて空のリストとしてインスタンスを作成し、シーケンスにオフセットを追加します）。

最後に、あなたのシーケンス内のギャップ（あなたの希望のしきい値よりも大きい）

このアプローチの素晴らしい点は、ベースリストを変更するときにこのインデックスを維持できるはずだということです。したがって、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()関数「二分」ビルトインを中心に構築される可能性があります。