アルゴリズムのすばらしさを覗く--配列の中で最小のK個数を探す&pythonの中で最大のスタックを巧みに使う

原文は私のブログのホームページで発表して、転載して出典を明記して下さい
前言
小さなアルゴリズムや大きなシステムにかかわらず、スタックは常にあるシーンでプログラマーが好むデータ構造であるが、pythonでは、データ構造の極めて柔軟性のため、list、tuple、dictは多くの場合、他のデータ構造をシミュレートすることができ、Queueライブラリはスタックとキューを提供し、優先キュー(最小スタックと類似)、heapqは最小スタック、ツリーを提供している.チェーンテーブルのポインタはpythonで最も一般的な変数とすることができるので、pythonは大きいほうがいいです.のpythonを使用すると、プログラマーを複雑なデータ構造から解放し、アルゴリズムに重点を置くことができます.さて本題に戻ります.
タイトル
先日1つのとても経典のアルゴリズムのテーマを見ました:n個の整数を入力して、その中の最小のk個の数を探し出します
解決策
このテーマ自体は難しくありませんが、このブログではpythonの中で最も多くの使用とこのテーマの解法のまとめに重点を置いています.
一.ツールバーの
この考え方は最も簡単であるべきで,配列全体を並べ替え,その後前のk個のデータを取り出せばよいが,このアルゴリズムの時間複雑度はnlog(n)であり,ここでは高速並べ替えを示す.コードは次のとおりです.

def partition(alist, start, end):
    if end <= start:
        return
    base = alist[start]
    index1, index2 = start, end
    while start < end:
        while start < end and alist[end] >= base:
            end -= 1
        alist[start] = alist[end]
        while start < end and alist[start] <= base:
            start += 1
        alist[end] = alist[start]
    alist[start] = base
    partition(alist, index1, start - 1)
    partition(alist, start + 1, index2)


def find_least_k_nums(alist, k):
    length = len(alist)
    if not alist or k <=0 or k > length:
        return None
    start = 0
    end = length - 1
    partition(alist, start, end)
    return alist[:k]




if __name__ == "__main__":
    l = [1, 9, 2, 4, 7, 6, 3]
    min_k = find_least_k_nums(l, 7)
    print min_k

二.クイックソートの考え方
この解法は第1の解法の上の1種の改善で、急速な順序付けの思想はみんなすでに知っていて、今私達は最小のk個数しか必要としないので、もし私達がある急速な順序付けの中で、選択した基準木の大きさはちょうど配列全体の第kの小さいデータで、それでは今回の順序付けが完成した後に、この基準数の前のデータは私たちが必要としている(彼らは秩序化していないが)、この方法は同じように配列を変えたが、時間の複雑さをO(n)に圧縮することができ、多くは言わないで、直接コードを上げることができる.

def partition(alist, start, end):
    if end <= start:
        return
    base = alist[start]
    index1, index2 = start, end
    while start < end:
        while start < end and alist[end] >= base:
            end -= 1
        alist[start] = alist[end]
        while start < end and alist[start] <= base:
            start += 1
        alist[end] = alist[start]
    alist[start] = base
    return start


def find_least_k_nums(alist, k):
    length = len(alist)
    #if length == k:
    # return alist
    if not alist or k <=0 or k > length:
        return
    start = 0
    end = length - 1
    index = partition(alist, start, end)
    while index != k:
        if index > k:
            index = partition(alist, start, index - 1)
        elif index < k:
            index = partition(alist, index + 1, end)
    return alist[:k]




if __name__ == "__main__":
    l = [1, 9, 2, 4, 7, 6, 3]
    min_k = find_least_k_nums(l, 6)
    print min_k

三.さいだいスタック
上記の方法は配列の構造を変更し、数字の順序を必要とせずに使用すると時間の複雑さが良好に得られるが、数字が非常に多く、一度にメモリをロードすることが不可能になったり、メモリの消費が大きすぎたりすると、上記の方法は実行できなくなり、Kサイズのデータコンテナを作成して最小のK個数を格納することができる.次に配列全体を巡回し、各数値とコンテナの最大数を比較します.この数がコンテナの最大値より大きい場合は、巡回を続けます.そうしないと、この数値でコンテナの最大値を置き換えます.この方法の理解も非常に簡単で、容器の選択については、多くの人が最初に反応するのが最大の山ですが、pythonの中で最大の山はどのように実現しますか?最小スタックを実現したheapqライブラリを借りることができます.1つの配列では、各数が逆になると、最大数が最小数になり、数字全体の順序が変化するため、配列の各数字に逆を取ることができ、最小スタックを借りて、最後に結果を返すときに逆を取ることができます.コードは以下の通りです.

import heapq
def get_least_numbers_big_data(self, alist, k):
    max_heap = []
    length = len(alist)
    if not alist or k <= 0 or k > length:
        return
    k = k - 1
    for ele in alist:
        ele = -ele
        if len(max_heap) <= k:
            heapq.heappush(max_heap, ele)
        else:
            heapq.heappushpop(max_heap, ele)

    return map(lambda x:-x, max_heap)


if __name__ == "__main__":
    l = [1, 9, 2, 4, 7, 6, 3]
    min_k = get_least_numbers_big_data(l, 3)

まとめ
前の2つの方法は、データ量が小さい場合に配列構造の変更を許可すれば使用できますが、ビッグデータシーンでは配列構造を変更せずに3つ目の方法を使用できます.