7

これまでに遭遇したことのない問題について考えており、使用する最も効率的なアルゴリズムを決定しようとしています。

要素の各ペアを使用して、並べ替えたい値を計算しながら、2 つのリストを繰り返し処理しています。私の最終的な目標は、トップ 20 の結果を取得することです。結果を 3 番目のリストに格納し、そのリストを絶対値で並べ替え、単純に上位 20 をスライスすることもできますが、これは理想的ではありません。

これらのリストは非常に大きくなる可能性があるため、理想的には上位 20 の絶対値のみを保存し、新しい上位値が計算されるときに古い値を削除したいと考えています。

これをPythonで実装する最も効率的な方法は何ですか?

4

4 に答える 4

11

見てみましょうheapq.nlargest：

heapq.nlargest(n, iterable[, key])

iterableで定義されたデータセットからn 個の最大要素を含むリストを返します。keyが指定されている場合、イテラブル内の各要素から比較キーを抽出するために使用される 1 つの引数の関数を指定します。key=str.lowersorted(iterable, key=key, reverse=True)[:n]

于 2013-06-25T14:47:52.927 に答える
1

サイズが 20 のタプルのリストを、計算の最小結果未満で初期化し、2 つのインデックスを -1 にします。結果を計算すると、結果のペアのインデックスとともに結果リストに追加され、値のみでソートされ、リストが長さ 20 にトリミングされます。長さ 21 のリストのみをソートするので、かなり効率的です。

于 2013-06-25T14:51:16.093 に答える
1

最良の回答はすでに選択されていることは承知していますが、教育目的のために、私の回答も検討してください。

タイプミスがないことを願っています：

def some_name(list_a, list_b):
    if len(list_a) != len(list_b):
        raise Exception("Too bad")
    result_list = []
    for result in (list_a[i] + list_b[i] for i in range(len(list_a))):
        if len(result_list) >= 20:
            if result_list[0] > result:
                continue
            result_list = result_list[1:]
        result_list.append(result)
        result_list.sort()

そして、いくつかのリファクタリングの後-それはほとんどのことheapq.nlargestを行います（もちろん、ここでは結果を自分でソートしておく必要があります）：

def some_name(list_a, list_b):
    if len(list_a) != len(list_b):
        raise Exception("Too bad")
    result_list = []
    for result in (list_a[i] + list_b[i] for i in range(len(list_a))):
        result_list.append(result)
        result_list.sort()
        result_list = result_list[-20:]
于 2013-06-25T15:05:19.457 に答える