3

我正在尝试实现我刚刚在课堂上学到的 rselect 算法。但是，似乎无法弄清楚我在实施中哪里出错了。这是我的代码。*编辑 * ：我尝试使用大卫回答中提供的信息，但我的代码仍然很奇怪。这是修改后的代码：

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)应该一直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. 例如，考虑第一个pi选择1000 的情况loc_pi=seq.index(pi)。在这种情况下，loc_pi将等于 2，因为 1000 在序列的索引 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

如果你改变：

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 回答
1

我不认为有任何主要错误（在你如何返回枢轴或其他方面），这只是很多一个（甚至两个）的混淆，另外我认为你的意思是与 i 比较rselect 的第一行，而不是 1。

这是我的看法，尽可能少的改变：

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 回答