3

クラスで学んだばかりの rselect アルゴリズムを実装しようとしています。ただし、実装のどこが間違っているのかわかりません。これが私のコードです。*編集 * : David の回答で提供された情報を使用してみましたが、コードはまだ奇妙に動作します。改訂されたコードは次のとおりです。

def rselect(seq,length,i):# i is the i'th order statistic.
    if len(seq)<=1:return seq
    lo,pi,hi,loc_pi= random_partition(seq
    if loc_pi==i:return pi 
    if loc_pi>i:return rselect(lo,loc_pi-1,i) 
    elif loc_pi<i:return rselect(hi,length-loc_pi,i-loc_pi)#
from random import choice  
def random_partition(seq):
    pi =choice(seq)
    #print 'pi',pi
    loc_pi=seq.index(pi)
    print 'Location',loc_pi
    lo=[x for x in seq if x<=pi]
    hi=[x for x in seq if x>pi]
    return lo,pi,hi,len(lo)+1   #--A

def test_rselect(seq,i):
    print 'Sequence',seq
    l=len(seq)
    print 'Statistic', rselect(seq,l,i)

ただし、出力は時と場合によって異なります。私はアルゴリズムと python の両方の初心者です。私が間違っている場所についての助けをいただければ幸いです。編集: コードを実行するたびに、i 番目の次数統計の値が異なります。これは私の問題です。たとえば、以下のコードを実行すると、次のようになります。

Revised Output:
/py-scripts$ python quicksort.py
Sequence [54, -1, 1000, 565, 64, 2, 5]
Statistic Location 1
-1
@ubuntu:~/py-scripts$ python quicksort.py
Sequence [54, -1, 1000, 565, 64, 2, 5]
Statistic Location 5
Location 1
Location 0
-1

予想される出力: ここで i 次の統計を見つけることを期待しています。

したがって

test_rselect([54,-1,1000,565,64,2,5],2)常にStatisticとして返さ5れます。

この実装で私が間違っている場所での助けは役に立ちます..ありがとう!!
編集 2 : アルゴリズムを分析しようとしてから、 A とマークされた行でピボットの場所 (loc_pi)を返す方法にエラーがあると思います。上記のプログラムの次の一連のイベントを考慮してください。

test_rselect( [ 55, 900, -1,10, 545, 250], 3) // call to input array 

calls rselect ([ 55, 900, -1,10, 545, 250],6,3)

    1st  call to random_partition:
        pi=545 and loc_pi=4
        lo=[55,-1,10,250,545]
        hi=[900]
    return to rselect function (lo,545,hi,6)
    here loc_pi>i: so rselect(lo,5,3)// and discard the hi part

    2nd recursive call to rselect:
    2nd recursive call to random_partition:
        call random_partition on (lo) // as 'hi' is discarded
        pi=55 loc_pi=0
        lo=[-1,10,55]
        hi=[250,545]
        return to rselect(lo,55,hi,4)
        here loc_pi>i: rselect(lo,3,3)// The pivot element is lost already as it is in 'hi' here!!

正しいo/pを取得するために、ピボット要素の位置を返す方法についての助けがあれば助かります。私が間違っている場所とそれを修正する方法を明確に説明する答えのために、報奨金を設定します（学ぶことを楽しみにしているので、素晴らしいヒントを歓迎します:)） 。素晴らしい回答をお待ちしております！

4

3 に答える 3

2

アルゴリズムの問​​題は、 の決定ですloc_pi。たとえば、 で 1000 が最初piに選択された場合を考えてみましょうloc_pi=seq.index(pi)。その場合、loc_pi1000 はシーケンスのインデックス 2 にあるため 2 に等しくなり、関数は 1000 を返します。これは順序統計 2 ではないことがわかっています。

loc_piしたがって、ランダムに選択された のインデックスに基づいて決定できないことがわかっていpiます。結局のところ、そのリストは任意の順序になっています。その位置は何の意味もありません。loc_piその値に対して実際に取得しようとしているのは、選択した pi を下回っているそのサブリスト内の要素の数です。そしてありがたいことに、それは簡単に入手できます！行を変更するだけです：

    return lo,pi,hi,loc_pi

に

    return lo,pi,hi,len(lo) + 1

そして、それが正確かつ一貫して機能することがわかります!

dynamic-oit-vapornet-c-913:test dgrtwo$ python test21.py
Sequence [54, -1, 1000, 565, 64, 2, 5]
Statistic pi 565
Location 3
pi 5
Location 5
pi -1
Location 0
pi 2
Location 0
2
dynamic-oit-vapornet-c-913:test dgrtwo$ python test21.py
Sequence [54, -1, 1000, 565, 64, 2, 5]
Statistic pi -1
Location 1
pi 54
Location 0
pi 5
Location 2
pi 2
Location 0
2

ETA: また、入力シーケンスに関係がある場合、書かれたアルゴリズムが常に機能するとは限らないことにも注意してください。いくつかの例を試してみると、私の言いたいことがわかるでしょう。それを解決する簡単な方法があり、あなたが理解できると確信しています。

于 2012-05-15T18:43:06.810 に答える
1

主要なエラー（ピボットを返す方法など）はないと思います。これは、1つずつ（または2つでも）混乱しているだけです。さらに、iと比較するつもりだと思います。 1ではなくrselectの最初の行。

これが私の見解ですが、可能な限り変更はありません。

def rselect(seq,length,i):# i is the i'th order statistic.
    if len(seq)<=i:return seq
    lo,pi,hi,loc_pi= random_partition(seq)
    if loc_pi==i:return pi 
    if loc_pi>i:return rselect(lo,loc_pi,i) 
    elif loc_pi<i:return rselect(hi,length-(loc_pi+1),i-(loc_pi+1))
from random import choice  
def random_partition(seq):
    pi =choice(seq)
    lo=[x for x in seq if x<=pi]
    hi=[x for x in seq if x>pi]
    return lo,pi,hi,len(lo)-1

編集：重複する要素がある場合に機能するバージョンは次のとおりです。さて、もう少し変更しなければならなかったので、自分で簡単にするために、わかりにくいものをいくつか取り出しました。

def rselect(seq,i):# i is the i'th order statistic.
    if len(seq)<=i:return seq
    lo,pi,hi= random_partition(seq)
    if i < len(lo):return rselect(lo,i) 
    if i < len(seq)-len(hi): return pi 
    return rselect(hi,i-(len(seq)-len(hi)))
from random import choice
def random_partition(seq):
    pi =choice(seq)
    lo=[x for x in seq if x<pi]
    hi=[x for x in seq if x>pi]
    return lo,pi,hi

def test_rselect(seq,i):
    print 'Sequence',seq
    stat=rselect(seq,i)
    print 'Statistic', stat
于 2012-05-31T08:37:35.003 に答える
1

変更する場合:

return lo,pi,hi,len(lo)+1

に：

return lo,pi,hi,len(lo)

次のように、閉じ括弧を追加し)て、構文エラーが修正されるようにします。

lo,pi,hi,loc_pi= random_partition(seq)

エントリが繰り返されていないシーケンスに対しては確実に機能します。

for i in xrange(1,8):
    print rselect([54,-1,1000,565,64,2,5],7,i),
#Output:
-1 2 5 54 64 565 [1000]

これは期待される出力です。

私の主なアドバイスは、スタイルのガイドラインに従ってコーディングを試みることだと思います! あなたのコードは一目で読むのがかなり難しいです!

パラメータlengthは冗長であるため、完全に削除できます。また、最後のエントリが単一の値リストとして返されることもあるので、それを変更しました (ただし、空のリストを渡すとフォールオーバーすることがわかりますが、おそらく大したことではありません)。次のコードは、もう少し読みやすい形式で、繰り返し入力できるように修正されています。

from random import choice, shuffle

def rselect(seq, i):
    lo, hi, pi, loc_pi = random_partition(seq)
    if loc_pi == i or (min(lo) == max(lo) and not hi):
        return pi
    elif loc_pi > i:
        return rselect(lo, i)
    elif loc_pi < i:
        return rselect(hi, i - loc_pi)

def random_partition(seq):
    pi = choice(seq)
    lo = [x for x in seq if x <= pi]
    hi = [x for x in seq if x > pi]
    return lo, hi, pi, len(lo)

#this is a nice way to test it:
cat = range(1,21)
for i in xrange(1,21):
    shuffle(cat)
    print rselect(cat,i),

#Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
于 2012-05-25T18:22:25.137 に答える