-1

繰り返しを処理するリスト交差アルゴリズムを python で書き留めようとしています。私はPythonとプログラミングの初心者なので、これが非効率的に聞こえたら許してください。ここで、L1 と L2 は問題の 2 つのリストで、L は交差セットです。

  1. L1 を反復する
  2. L2 を繰り返す
  3. 要素が L1 と L2 にある場合
  4. Lに追加します
  5. L1 と L2 から削除します。
  6. L を繰り返す
  7. 要素を L1 と L2 に戻す

これが Mathematica 内でリストの交差を評価するために使用されるアルゴリズムではないことは 100% 確信していますが、これ以上効率的なアルゴリズムを思い付くことはできません。その過程で L1 と L2 を変更したくないので、交差点を両方のリストに追加し直します。何か案は？リスト以外の組み込み関数/データ型を使用したくないので、インポートセットなどはありません。私に関する限り、これはアルゴリズムと実装の演習であり、プログラミングの演習ではありません。

4

6 に答える 6

3

より高速なソリューションは次のとおりです。

def intersect_sorted(a1, a2):
  """Yields the intersection of sorted lists a1 and a2, without deduplication.

  Execution time is O(min(lo + hi, lo * log(hi))), where lo == min(len(a1),
  len(a2)) and hi == max(len(a1), len(a2)). It can be faster depending on
  the data.
  """
  import bisect, math
  s1, s2 = len(a1), len(a2)
  i1 = i2 = 0
  if s1 and s1 + s2 > min(s1, s2) * math.log(max(s1, s2)) * 1.4426950408889634:
    bi = bisect.bisect_left
    while i1 < s1 and i2 < s2:
      v1, v2 = a1[i1], a2[i2]
      if v1 == v2:
        yield v1
        i1 += 1
        i2 += 1
      elif v1 < v2:
        i1 = bi(a1, v2, i1)
      else:
        i2 = bi(a2, v1, i2)
  else:  # The linear solution is faster.
    while i1 < s1 and i2 < s2:
      v1, v2 = a1[i1], a2[i2]
      if v1 == v2:
        yield v1
        i1 += 1
        i2 += 1
      elif v1 < v2:
        i1 += 1
      else:
        i2 += 1

O(min(n + m, n * log(m)))n が長さの最小値で、m が最大値である時間で実行されます。両方のリストを同時に繰り返し処理し、最初のできるだけ多くの要素をスキップします。

分析はこちらから入手できます: http://ptspts.blogspot.ch/2015/11/how-to-compute-intersection-of-two.html

于 2015-11-27T18:49:50.157 に答える
2

を繰り返し、毎回L1すべてを繰り返すL2と、二次時間がかかります。これを改善する唯一の方法は、すべてのL2. (最後に重複を削除する同様の問題がありLます。)

setfor L2(および for )を使用する場合L、もちろん各in L2ステップは一定時間であるため、アルゴリズム全体は線形です。また、を使用する代わりに、独自のハッシュ テーブル実装をいつでも構築できますset。しかし、それは大変な作業です。

二分探索木、または並べ替えられたリストとbinary_find関数だけでも、O(N log N) で実行できます。そして、それbinary_findは自分で書く方がはるかに簡単です。そう：

S2 = sorted(L2)
L = [element for element in L1 if binary_find(element, S2)]
S = remove_adjacent(sorted(L))

または、さらに簡単に、L1 も並べ替えると、必要ありませんremove_adjacent。

S1, S2 = sorted(L1), sorted(L2)
L = []
for element in S1:
    if binary_find(element, S2) and (not L or L[-1] != element):
        L.append(element)

いずれにせよ、これは O(N log N) です。ここで、N は長いリストの長さです。比較すると、元は O(N^2) で、他の答えは O(N^3) です。もちろん、もう少し複雑ですが、理解するのは非常に簡単です。

追加のビルトインを使用したくない場合でも、標準ライブラリからのものを使用したくないと想定しているため、 binary_find(および、該当する場合は)を記述する必要があります。remove_adjacentしかし、それは本当に簡単です。例えば：

def binary_find(element, seq):
    low, high = 0, len(seq), 
    while low != high:
        mid = (low + high) // 2
        if seq[mid] == element:
            return True
        elif seq[mid] < element:
            low = mid+1
        else:
            high = mid
    return False

def remove_adjacent(seq):
    ret = []
    last = object()
    for element in seq:
        if element != last:
            ret.append(element)
        last = element
    return ret

sortedorを使いたくない場合でもlist.sort、独自のソートを非常に簡単に作成できます。

于 2013-02-13T01:58:15.853 に答える
1

どうですか：

  1. L1 を繰り返す
  2. L2 を繰り返す
  3. (L1 と L2 に) あり、L にない場合 -> L に追加

特に効率的ではありませんが、コードでは次のようになります (ポイントを強調するために繰り返しています)。

>>> L1 = [1,2,3,3,4]
>>> L2 = [2,3,4,4,5]
>>> L = list()
>>> for v1 in L1:
        for v2 in L2:
            if v1 == v2 and v1 not in L:
                L.append(v1)
>>> L
[2,3,4]

要素がすでに L にあるかどうかを確認し、そうでない場合は L に追加するだけで、L1 と L2 からの削除を回避できます。その場合、L1 と L2 に繰り返しがあっても問題ありません。

于 2013-02-13T01:23:02.157 に答える
1

編集：タイトルを間違って読み、ビルトイン部分をざっと読みました。とにかくここに残します。他の誰かを助けるかもしれません。

setタイプを使用してこれを実現できます。

>>> a = [1,2,3,4]
>>> b = [3,4,5,6]
>>> c = list(set(a) & set(b))
>>> c
[3, 4]
于 2013-02-13T01:23:48.217 に答える
0
  1. 一時的なリストを作成します。
  2. 2 つのリストのいずれかを繰り返します。どちらでも構いません。
  3. すべての要素について、その要素が他のリスト ( if element in list2) に存在し、まだ一時リストにないかどうかを確認します (同じ構文)。
  4. 両方の条件が true の場合は、それを一時リストに追加します。

解決策を投稿するのは残念ですが、正直なところ、私のテキストよりも読みやすいです。

def intersection(l1, l2):
    temp = []

    for item in l1:
        if item in l2 and item not in temp:
            temp.append(item)

    return temp
于 2013-02-13T01:26:28.607 に答える