6

整数の2つのソートされたリストがあります。最初のリストと2番目のリストから、それぞれ特定の距離内にある整数のすべてのペアを見つけたいと思います。

素朴なアプローチは、各ペアをチェックすることであり、結果としてO（N ^ 2）時間が発生します。O（N * logN）またはそれより短い方法でそれを行う方法があると確信しています。

Pythonでは、単純なO（N ^ 2）アプローチは次のとおりです。

def find_items_within(list1, list2, within):
    for l1 in list1:
        for l2 in list2:
            if abs(l1 - l2) <= within:
                yield (l1, l2)

pythonicの答えのための追加のポイント。

アプリケーションノート

この小さなパズルの目的を指摘したかっただけです。ドキュメントを検索していて、ある用語が別の用語から一定の距離内にあるすべての出現箇所を見つけたいと思っています。最初に両方の用語の用語ベクトルを見つけ、次に以下で説明するアルゴリズムを使用して、それらが互いに所定の距離内にあるかどうかを判断できます。

4

7 に答える 7

7

ペアがあり、それらすべてを譲る必要がO(n^2)あるため、それを上手く行う方法はありません。O(n^2)within = infinity

これらのペアの数を見つけることは別の話でありe、十分な各要素の最初のインデックスを見つけることによって行うことができますwithin-e < arr[idx]。インデックスidxは、たとえば二分探索を使用して効率的に見つけることができます。これにより、これらのペアの数O(nlogn)を見つけるためのソリューションが得られます。

また、線形時間（）で実行することもできます。最初の範囲が見つかっO(n)た後、すべての要素に対してバイナリ検索を実行する必要がないため、他の範囲について（その場合は）、実際に反復する必要があることに注意してください。線形時間計算量を取得するために、2つのポインターと「決して振り返らない」リスト。[a,b][a',b']a>a'b>=b'

擬似コード:(線形時間解の場合）

numPairs <- 0
i <- 0
a <- 0
b <- 0
while (i < list1.length):
  while (a < i && list1[i] - list2[a] > within):
      a <- a+1
  while (b < list2.length && list2[b] - list1[i] < within):
      b <- b+1
  if (b > a):
      numPairs <- numPairs + (b-a)
  i <- i+1
return numPairs

（最初の疑似コードからいくつかの修正を行いました-最初のコードは単一のリスト内の範囲内のペアの数を見つけることを目的としていたため-2つのリスト間で一致しませんでした、申し訳ありません）

于 2012-11-29T14:17:00.620 に答える
6

このコードはO（n * log（n）+ m）です。ここで、mは回答のサイズです。

def find_items_within(l1, l2, dist):
    l1.sort()
    l2.sort()
    b = 0
    e = 0
    ans = []
    for a in l1:
        while b < len(l2) and a - l2[b] > dist:
            b += 1
        while e < len(l2) and l2[e] - a <= dist:
            e += 1
        ans.extend([(a,x) for x in l2[b:e]])
    return ans

最悪の場合、それは可能ですm = n*nが、答えがすべての可能なペアのほんの小さなサブセットである場合、これははるかに高速です。

于 2012-11-29T15:49:39.387 に答える
2

ここにあなたが与えたのと同じインターフェースを持つ何かがあります：

def find_items_within(list1, list2, within):
    i2_idx = 0
    shared = []
    for i1 in list1:
        # pop values to small
        while shared and abs(shared[0] - i1) > within: 
            shared.pop(0)
        # insert new values 
        while i2_idx < len(list2) and abs(list2[i2_idx] - i1) <= within:
            shared.append(list2[i2_idx])
            i2_idx += 1
        # return result
        for result in zip([i1] * len(shared), shared):
            yield result

for item in find_items_within([1,2,3,4,5,6], [3,4,5,6,7], 2):
    print item

あまり美しくはありませんが、list1の長さとアイテムごとの共有ペアのリスト（ドロップおよび追加される要素が平均して一定であるO(N*M)場合）のトリックを実行する必要があります。NMshared

于 2012-11-29T14:41:42.390 に答える
0

これはうまくいくようです：

from itertools import takewhile
def myslice(lst,start,stop,stride=1):
    stop = len(lst) if stop is None else stop
    for i in xrange(start,stop,stride):
        yield lst[i]

def find_items_within(lst1,lst2,within):
    l2_start = 0
    for l1 in lst1:
        try:
            l2_start,l2 = next( (i,x) for i,x in enumerate(myslice(lst2,l2_start,None),l2_start) if abs(l1-x) <= within )
            yield l1,l2
            for l2 in takewhile(lambda x:(abs(l1-x) <= within), myslice(lst2,l2_start+1,None)):
                yield l1,l2
        except StopIteration:
            pass


x = range(10)
y = range(10)
print list(find_items_within(x,y,2.5))
于 2012-11-29T14:29:23.803 に答える
0

リスト内の値の分布によっては、ビニングを使用して処理を高速化できる場合があります。すべての値が含まれる範囲（min(A+B), max(A+B)）を取得し、その範囲を距離と同じサイズのビンに分割しDます。再検討します。次に、すべてのペアを見つけるには、ビン内または隣接するビン内の値を比較するだけで済みます。値が多くのビンに分割されている場合、これはM*N比較を回避する簡単な方法です。

実際には同じくらい簡単かもしれない別のテクニック：一種の有界線形スキャンを実行します。最初からリストAとリストBのインデックスを維持します。各反復で、インデックスをリストAに進め（最初の要素から開始）、この要素をA0と呼びます。次に、インデックスをリストBに進めます。A0-D未満のBの最後の値を覚えておいてください（これは、次の反復で開始する場所です）。ただし、A0-DとA0 + Dの間の値を見つけている間は、前進し続けてください。これらは、探しているペアです。Bの値がA0+Dより大きくなるとすぐに、この反復を停止して次の反復を開始します— 1つの要素をさらにAに進め、Bが<A0-Dであった最後の場所からBのスキャンを開始します。

平均して、要素ごとに一定数の近くのペアがある場合、これはO（M + N）である必要があると思いますか？

于 2012-11-29T14:35:44.700 に答える
0

このメソッドは、キーがの可能な値であり、その値がその値の距離内にあるlist2値のリストであるディクショナリを使用します。list1list2

def find_items_within(list1, list2, within):
    a = {}
    for l1 in list1:
        for i in range(l1-within, l1+within+1):
            if i not in a:
                a[i] = []
            a[i].append(l1)
    for l2 in list2:
        if l2 in a:
            for l1 in a[l2]:
                yield(l1, l2)

これの複雑さはちょっと間抜けです。サイズMのlist1とサイズNのlist2で、サイズWの範囲内の場合、O（log（M * W）*（M * W + N））になります。実際には、小さいWではかなりうまくいくと思います。

ボーナス：これはソートされていないリストでも機能します。

于 2012-11-29T14:43:00.783 に答える
0

「スキャンライン」手法を使用して、線形時間（ ）からすべての間隔にlist2ある整数を見つけることができます（ネストされた間隔をカウントするためのすべての重複する間隔とサブO（n ^ 2）アルゴリズムを見つける方法を参照してください）。[x - within, x + within]xlist1O(n)

対応する間隔を列挙するには、時間がlist1必要です。ここで、は間隔の数です。つまり、全体的なアルゴリズムは次のとおりです。O(m)mO(n*m)

from collections import namedtuple
from heapq import merge

def find_items_within(list1, list2, within):
    issorted = lambda L: all(x <= y for x, y in zip(L, L[1:]))
    assert issorted(list1) and issorted(list2) and within >= 0

    # get sorted endpoints - O(n) (due to list1, list2 are sorted)
    Event = namedtuple('Event', "endpoint x type")
    def get_events(lst, delta, type):
        return (Event(x + delta, x, type) for x in lst)
    START, POINT, END = 0, 1, 2 
    events = merge(get_events(list1, delta=-within, type=START),
                   get_events(list1, delta=within, type=END),
                   get_events(list2, delta=0, type=POINT))

    # O(n * m), m - number of points in `list1` that are 
    #               within distance from given point in `list2`
    started = set() # started intervals
    for e in events:  # O(n)
        if e.type is START: # started interval
            started.add(e.x) # O(m) is worst case (O(1) amortized)
        elif e.type is END: # ended interval
            started.remove(e.x)  # O(m) is worst case (O(1) amortized)
        else:  # found point
            assert e.type is POINT
            for x in started:  # O(m)
                yield x, e.x

で重複する値を許可するにはlist1; xにそれぞれのインデックスを追加し、セットの代わりにEvent辞書を使用することができます。index -> xstarted

于 2012-11-29T22:35:07.307 に答える