Vadim
Ноя. 22, 2010 15:42:17
Понадобилось мне отсортировать обьекты, а list.sort() меня не устраивает, подскажите, код, приведенный ниже, хоть и рабочий но вызывает у меня опасения, может в нем можно что-то конструктивно подкорректировать
def swap(a, b):
c = a
a = b
b = c
return a, b
def getbest(population, metric = 0):
sigma = max(population[:len(population) - metric])
population[len(population)-1- metric], population[population.index(sigma)] = swap(population[len(population)-1-metric], population[population.index(sigma)])
if metric + 1 < len(population):
getbest(population, metric+1)
return population
Zubchick
Ноя. 22, 2010 15:58:54
1. весь свап заменяется на
a, b = b, a
2. у вас N рекурсивных вызывов getbest внутри которых просмотр массива из ~ N/2 элементов (сначала просмотр N, затем уменьшается каждый шаг на 1, тоесть в среднем N/2) и того N*N/2 ~ O(N^2) )сложность же быстрой сортировки (тоже ркурсивный алгоритм) в среднем O(N*logN). Так что я прям не знаю чем вас не устроил стандартный сорт :)
Vadim
Ноя. 22, 2010 16:04:40
Свал не уменьшится, просто пропадет 6 символов, но и на том спасибо =)
Про сложность это да, но проблема в том что мне надо написать именно такую сортировку =(
Андрей Светлов
Ноя. 22, 2010 16:23:38
Вы помните, что максимальная глубина стека по умолчанию - 1000?
А вызов - довольно дорогая операция? В Питоне сложность кода считают именно по количеству необходимых вызовов.
Простым циклом было бы быстрее - это все же не функциональный язык программирования с tail recursion optimization.
list.sort, равно как и sorted - не подошли по объективным причинам?
population == population
Второй вариант пишется проще а работает быстрее
Vadim
Ноя. 22, 2010 18:30:52
Нет, по субьективным, попросил друг написать пример рекурсивной функции.
За условие спасибо большое, я долго изворачивался чтоб оно работало нормально =)
Глубина стека в данном случае не важна, важна сама структура программы, вообще говоря я хотел писать это на Turbo Delphi, так как-то нагляднее выходит, но он настоял на пайтоне.
Ещё раз спасибо =)