5

私はPythonで中央値の中央値アルゴリズムのこの実装を作成しましたが、正しい結果を出力していないようです。また、線形の複雑さも感じられません。どこで軌道に乗ったのでしょうか。

def select(L):
    if len(L) < 10:
        L.sort()
        return L[int(len(L)/2)]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        print(subList)
    Meds.append(select(subList))
    L2 = select(Meds)
    L1 = L3 = []
    for i in L:
        if i < L2:
            L1.append(i)
        if i > L2:
            L3.append(i)
    if len(L) < len(L1):
        return select(L1)
    elif len(L) > len(L1) + 1:
        return select(L3)
    else:
        return L2

この関数は次のように呼び出されます。

L = list(range(100))
shuffle(L)
print(select(L))

LE：ごめんなさい。GetMedは、リストを並べ替えてlen（list）の要素を返すだけの関数でした。そこで選択する必要がありました。今すぐ修正しましたが、それでも間違った出力が得られます。インデントに関しては、コードはエラーなしで機能し、何も問題はありません：-??

LE2：私は（現在のLに対して）50を期待しています、それは私に30から70までの出力を与えます、それ以上でもそれ以下でもありません（まだ）

LE3：どうもありがとうございました、それは今それが機能するトリックをしました。混乱していますが、この方法と、単純に配列を並べ替えて結果を出力する単純な方法とを比較しようとしています。さて、これまで読んだことから、selectメソッドの時間計算量はO（n） DeterministicSelectionであるはずです。おそらくPython開発者が行った最適化と競合することはできませんが、私が得たよりも近い結果を期待していました。たとえば、リストの範囲を10000000に変更すると、selectは84.10837116255952秒で結果を出力し、sortandreturnメソッドは18.92556029528825でそれを行います。このアルゴリズムを高速化するための良い方法は何ですか？

4

2 に答える 2

5

1）コードのインデントが間違っている場合は、次のことを試してください。

def select(L):
    if len(L) < 10:
        L.sort()
        return L[int(len(L)/2)]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        print(subList)
        Meds.append(select(subList))
    L2 = select(Meds)
    L1 = L3 = []
    for i in L:
        if i < L2:
            L1.append(i)
        if i > L2:
            L3.append(i)
    if len(L) < len(L1):
        return select(L1)
    elif len(L) > len(L1) + 1:
        return select(L3)
    else:
        return L2

2）使用するメソッドは中央値を返しません。中央値からそれほど遠くない数値を返すだけです。中央値を取得するには、疑似中央値よりも大きい数を数える必要があります。過半数が大きい場合は、疑似中央値よりも大きい数でアルゴリズムを繰り返します。それ以外の場合は、他の数で繰り返します。

def select(L, j):
    if len(L) < 10:
        L.sort()
        return L[j]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        Meds.append(select(subList, int((len(subList)-1)/2)))
    med = select(Meds, int((len(Meds)-1)/2))
    L1 = []
    L2 = []
    L3 = []
    for i in L:
        if i < med:
            L1.append(i)
        elif i > med:
            L3.append(i)
        else:
            L2.append(i)
    if j < len(L1):
        return select(L1, j)
    elif j < len(L2) + len(L1):
        return L2[0]
    else:
        return select(L3, j-len(L1)-len(L2))

警告：そうではありL = M = []ませんL = []M = []

于 2012-05-29T22:58:36.163 に答える
3

以下は私のPYTHONの実装です。速度を上げるには、代わりにPYPYを使用することをお勧めします。

SPEEDについての質問： 列あたり5つの数値の理論速度は約10Nなので、最適速度が約4Nであるのに対し、2倍の速度で列あたり15の数値を使用します。しかし、私は最先端のソリューションの最適な速度について間違っている可能性があります。私自身のテストでは、私のプログラムはsort（）を使用したプログラムよりもわずかに高速に実行されます。確かに、あなたのマイレージは変わるかもしれません。

Pythonプログラムが「median.py」であると仮定すると、それを実行する例は「python./median.py100」です。速度ベンチマークについては、検証コードをコメントアウトして、PYPYを使用することをお勧めします。

#!/bin/python
#
# TH @stackoverflow, 2016-01-20, linear time "median of medians" algorithm
#
import sys, random


items_per_column = 15


def find_i_th_smallest( A, i ):
    t = len(A)
    if(t <= items_per_column):
        # if A is a small list with less than items_per_column items, then:
        #     1. do sort on A
        #     2. return the i-th smallest item of A
        #
        return sorted(A)[i]
    else:
        # 1. partition A into columns of items_per_column items each. items_per_column is odd, say 15.
        # 2. find the median of every column
        # 3. put all medians in a new list, say, B
        #
        B = [ find_i_th_smallest(k, (len(k) - 1)/2) for k in [A[j:(j + items_per_column)] for j in range(0,len(A),items_per_column)]]

        # 4. find M, the median of B
        #
        M = find_i_th_smallest(B, (len(B) - 1)/2)

        # 5. split A into 3 parts by M, { < M }, { == M }, and { > M }
        # 6. find which above set has A's i-th smallest, recursively.
        #
        P1 = [ j for j in A if j < M ]
        if(i < len(P1)):
            return find_i_th_smallest( P1, i)
        P3 = [ j for j in A if j > M ]
        L3 = len(P3)
        if(i < (t - L3)):
            return M
        return find_i_th_smallest( P3, i - (t - L3))


# How many numbers should be randomly generated for testing?
#
number_of_numbers = int(sys.argv[1])


# create a list of random positive integers
#
L = [ random.randint(0, number_of_numbers) for i in range(0, number_of_numbers) ]


# Show the original list
#
print L


# This is for validation
#
print sorted(L)[int((len(L) - 1)/2)]


# This is the result of the "median of medians" function.
# Its result should be the same as the validation.
#
print find_i_th_smallest( L, (len(L) - 1) / 2)
于 2016-01-20T22:04:26.347 に答える