0

私はPythonを使用して作業しています。

言葉で質問があります。たとえば、query = [hello、tree、blue]

ドキュメントが含まれる単語ごとに選択したので、単語ごとにリストを作成します。各位置はドキュメントの1つです。まあ言ってみれば：

list_query[0]=[1,4,5]
list_query[1]=[5,8]
list_query[2]=[4,5,8]

したがって、結果を取得する必要があります= [5]

でも、交差点を使ってやりたくないです。反復、i、jを使用してそれを行う必要があります。

hello:
      i
      |
      1    4    5
tree:
      5    8
      |
      j

i = 0から始めて、list_query [0] [i] == list_query [1] [j]かどうかを比較し、そうであれば、その番号をリストに追加する必要があります。そうでない場合は、両方のイテレータの数を減らして、これらのリストとクエリの残りの要素を交差させた結果を繰り返す必要があります。しかし、親切にそれを行う方法を見つけてください、そしてそれは私を怒らせています。

だから誰かが私を助けることができれば...事前に感謝します。

4

2 に答える 2

0

パフォーマンスよりもコードの単純さに最も関心がある場合は、リストの内容を繰り返し交差させることはそれほど難しくありません。

def intersect(query_lists):
    # initialize to first result set
    combined_results = query_lists[0]

    # filter out values missing in any other result set
    for query in query_lists[1:]:
        combined_results = filter(lambda i: i in query, combined_results)

    # turn nested generators into a list
    return list(combined_results)

setこれは、リストではなくインスタンスを使用するとはるかに高速になりますが、インスタンスを使用している場合は、組み込みの交差メソッドを使用するだけで、手動で行う必要はありません。

また、リストを組み合わせ、組み合わせた結果を並べ替えてからスキャンして、元のリストとまったく同じ回数重複する値を見つけることで、ほぼ同じスピードアップを実現できます。ただし、入力セットに重複がある可能性がある場合、これは機能しません。

入力リストがそれぞれソートされていることがわかっている場合は、最初の値がすべて同一であるかどうかを確認し、最大の値よりも小さい値を拒否できます。ただし、サブリストを自分で並べ替えるとパフォーマンス上の利点の一部が失われるため、サブリストが並べ替えられていない場合は、実行する価値がない可能性があります。

于 2012-10-27T15:45:37.250 に答える
0

あなたはもうかなり遠いところにいるように感じます。実装をお見せすることもできますが、アルゴリズムについてはすでに説明しているので、自分で実装するのは難しいことではありません。しかし、おそらくあなたは自分の説明に自信がないでしょう。

クエリなどについて必要のない情報を省き、ゆっくりと正確に説明を述べさせていただきます。事前にソートされたリストが2つあり、それらの共通部分を見つけたいと思います。a = [1, 4, 5, 7, 8]リスト、、、、およびb = [5, 8, 9]で始まる、少し完全な例と、最初は図から除外する空の出力リストを使用して、図を適合させます。i=0j=0out = []

i = 0
a = 1 4 5 7 8

j = 0
b = 5 8 9

まず、それらが等しいかどうかを確認します。a[i]そうではないので、との最小値を取りb[j]ます。この場合、、、なのでa[i] == 1、b[j] == 5インクリメントしたいと思いますi。

i =   1
a = 1 4 5 7 8

j = 0
b = 5 8 9

同じ手順を実行して、iもう一度インクリメントします。

i =     2
a = 1 4 5 7 8

j = 0
b = 5 8 9

今では状況が異なります。a[i]とb[j]は同じなので、その値を出力リストに追加し、両方の値をインクリメントします。

i =       3
a = 1 4 5 7 8

j =   1
b = 5 8 9

out = 5

続けます。再び未満a[i]です...b[j]

i =         4
a = 1 4 5 7 8

j =   1
b = 5 8 9

そして、値は同じなので、その値をに追加しout、インクリメントiしてj...

i =           5
a = 1 4 5 7 8

j =     2
b = 5 8 9

out = 5 8

しかし今、私たちはそれを見つけますi == len(a)。したがって、アルゴリズムが終了したことがわかります。

これで、必要な変数とロジックがどのように機能するかを確立するために必要なすべてが揃いました。alist 、list b、index i、index j、 listが必要outです。i == len(a)またはのいずれかで停止するループを作成し、j == len(b)そのループ内で、とa[i]の同等性をテストしb[j]ます。それらが等しい場合は、との両方をインクリメントしi、jに追加a[i]しoutます。それらが等しくない場合は、かどうかをテストしa[i] < b[j]ます。そうである場合は、インクリメントしますi; それ以外の場合は、インクリメントしますj。

これにより、2つのリスト間の共通部分が決まります。これを最初と2番目のリストに適用し、次に結果を3番目のリストに適用し、次にその結果を4番目のリストに適用する必要があります。

于 2012-10-27T16:00:50.107 に答える