Implementacja algorytmu „mediany median” w Pythonie
Napisałem tę implementację mediany algorytmu median w Pythonie, ale wydaje się, że nie daje prawidłowego wyniku, a także nie wydaje mi się liniową złożonością, jakimkolwiek pomysłem, gdzie poszedłem poza ścieżkę?
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
Funkcja nazywa się tak:
L = list(range(100))
shuffle(L)
print(select(L))
LE: Przepraszam. GetMed to funkcja, która po prostu posortowała listę i zwróciła element na len (lista), powinna być tam zaznaczona, naprawiłem ją teraz, ale nadal otrzymuję nieprawidłowe wyniki. Jeśli chodzi o wcięcia, kod działa bezbłędnie i nie widzę w tym nic złego: - ??
LE2: Spodziewam się 50 (dla obecnego L), daje mi to wyniki od 30 do 70, nie więcej (jeszcze)
LE3: Dziękuję bardzo, że to działa teraz. Jestem jednak zdezorientowany, próbuję dokonać porównania między tą metodą a tą naiwną, gdzie po prostu sortuję tablicę i wypisuję wyniki. Teraz, z tego, co przeczytałem do tej pory, złożoność czasowa wybranej metody powinna wynosić O (n)Wybór deterministyczny. Chociaż prawdopodobnie nie mogłem konkurować z programistami optymalizującymi Pythona, spodziewałem się bliższych wyników niż ja, na przykład, jeśli zmienię zakres listy na 10000000, wybierz wynik, uzyskując wynik 84.10837116255952 sekundy podczas metody sortowania i powrotu robi to w 18.92556029528825. Jakie są dobre sposoby na przyspieszenie tego algorytmu?