Implementação em Python do algoritmo “median of medians”
Eu escrevi essa implementação do algoritmo mediano de medianas em python, mas não parece produzir o resultado certo, e também não parece ser uma complexidade linear para mim, alguma idéia de onde eu saí da pista?
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
A função é chamada assim:
L = list(range(100))
shuffle(L)
print(select(L))
LE: Desculpe. GetMed era uma função que simplesmente classificava a lista e retornava o elemento em len (lista), deveria ter sido selecionado lá, eu o consertei agora, mas ainda assim recebo as saídas erradas. Quanto ao recuo, o código funciona sem erro, e não vejo nada de errado com isso: - ??
LE2: Estou esperando 50 (para o atual L), me dá saídas de 30 a 70, nem mais nem menos (ainda)
LE3: Muito obrigado, o truque funcionou agora. Porém, estou confuso, estou tentando fazer uma comparação entre esse método e o ingênuo, onde eu simplesmente classifico a matriz e envio os resultados. Agora, pelo que li até agora, a complexidade de tempo do método select deve ser O (n)Seleção Determinista. Embora eu provavelmente não possa competir com a otimização que os desenvolvedores python fizeram, esperava resultados mais próximos do que consegui, por exemplo, se eu alterar o intervalo da lista para 10000000, selecione as saídas como resultado em 84.10837116255952 segundos enquanto o método de classificação e retorno faz isso em 18.92556029528825. Quais são algumas boas maneiras de tornar esse algoritmo mais rápido?