Python实现的＆QUOT;中位数＆QUOT的中位数;算法 [英] Python implementation of "median of medians" algorithm
问题描述
我已经写了这个实现在python中位数算法的位数，但它似乎并没有输出正确的结果呢，它也似乎没有线性的复杂性给我，我哪里偏离了轨道的任何想法？
I've written this implementation of the median of medians algorithm in python, but it doesn't seem to output the right result, and it also does not seem of linear complexity to me, any idea where I went off track ?
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
该函数的调用像这样：
The function is called like so:
L = list(range(100))
shuffle(L)
print(select(L))
LE：对不起。 GetMed是一个函数，只是排序的名单，并在LEN（名单）返回的元素，它应该已经选择在那里，我不动它了，但我仍然得到错误的输出。至于压痕时，code工作无差错，我看不妥的地方： - ??
LE: Sorry. GetMed was a function that simply sorted the list and returned the element at len(list), it should've been select there, I fixed it now, but still I get the wrong outputs. As for the indentation, the code works without error, and I see nothing wrong with it :-??
LE2：我期待50（当前L），它给了我输出从30到70，不多不少（但）
LE2: I'm expecting 50 (for the current L), it gives me outputs from 30 to 70, no more no less (yet)
LE3：非常感谢你，说这样做是现在工作的伎俩。我很迷惑，虽然，我试图使这一方法进行了比较，并天真的，在这里我简单排序的数组并输出结果。现在，从我至今读，选择方法的时间复杂度应为O（n）的确定性选择。虽然我可能无法与优化Python开发人员没有竞争，我没有想到更接近的结果比我得到的，例如，如果我更改列表的范围为10000000，选择输出的结果84.10837116255952秒而排序和返回方法确实它18.92556029528825。有什么好的办法，使这个算法快？
LE3: Thank you very much, that did the trick it works now. I'm confuse though, I'm trying to make a comparison between this method, and the naive one, where I simply sort the array and output the results. Now, from what I read so far, the time complexity of the select method should be O(n) Deterministic Selection. Although I probably can't compete with the optimisation python developers did, I did expect closer results than I got, for example, if I change the range of the list to 10000000, select outputs the result in 84.10837116255952 seconds while the sort and return method does it in 18.92556029528825. What are some good ways to make this algorithm faster?
推荐答案
1）你的code缩进是错误的，试试这个：
1) Your code indentation is wrong, try this:
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）使用不返回值的方法，它仅仅返回一个数是不那么远的中位数。要获得中位数，你需要算多少数大于你的伪中间，如果多数会更大，大于伪中值，否则重复与其他数字号码重复的算法。
2) The method you use does not return the median, it just return a number which is not so far from the median. To get the median, you need to count how many number are greater than your pseudo-median, if a majority is greater, repeat the algorithm with the numbers greater than the pseudo-median, else repeat with the other numbers.
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 = []
这篇关于Python实现的＆QUOT;中位数＆QUOT的中位数;算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
