Python-сообщество

Cyxapeff · Март 11, 2007 20:06:58

Как в питоне 2.2 просто отсортировать по ключу?
В 2.4 и 2.5 делаю так: mass.sort(key=operator.attrgetter(“Date”))
а в 2.2 attrgetter функции нету (((. Или надо свою писать?

Cyxapeff · Март 11, 2007 20:18:06

sorry. уже нашёл.
def sortby(somelist, n):
nlist = [(x, x) for x in somelist]
nlist.sort()
return

Tmr · Март 13, 2007 16:15:35

Свою написать несложно:
my_attrgetter = lambda attr: lambda obj, attr=attr: getattr(obj, attr)
lst =
get_count = my_attrgetter('count')
print get_count(lst)(3) # количество троек в lst
Если getter используется только один раз, функцию можно не именовать:
class s(object):
def __init__(self, s):
self.s = s
def __repr__(self):
return self.s
mass =
print mass
mass.sort(key=lambda obj: getattr(obj, “s”))
print mass
Но работать в версии ниже 2.4 не будет: раньше параметра key для sort не было. Однако вполне можно обойтись и без этого параметра:
mass =
mass.sort(cmp = lambda x, y: cmp(x.s, y.s))
print mass

Последний вариант будет работать значительно (возможно на порядки) быстрее и экономичнее по расходу памяти чем привденный тобой вариант с использованием временного списка.

Cyxapeff · Март 15, 2007 19:51:19

спасибо за исчерпывающий ответ.

xonix · Март 16, 2007 21:03:18

Tmr
Но работать в версии ниже 2.4 не будет: раньше параметра key для sort не было. Однако вполне можно обойтись и без этого параметра:
mass = [s('aaaa'), s('aa'), s('aaa'), s('aaaaa'), s('a')]
mass.sort(cmp = lambda x, y: cmp(x.s, y.s))
print mass
Последний вариант будет работать значительно (возможно на порядки) быстрее и экономичнее по расходу памяти чем привденный тобой вариант с использованием временного списка.

Здесь вот ой как не факт… key всегда экономичнее чем cmp, потому что функция вызывается многократно для каждого элемента а key только единожды, а вариант Cyxapeff'a больше соответствует подходу key (Кстати, это отражено в стандартной доке)

Отредактировано (Март 16, 2007 21:04:24)

Tmr · Март 19, 2007 11:42:24

xonix
Здесь вот ой как не факт… key всегда экономичнее чем cmp, потому что функция вызывается многократно для каждого элемента а key только единожды, а вариант Cyxapeff'a больше соответствует подходу key (Кстати, это отражено в стандартной доке)

Не совсем понял о чем речь… Функция, создаваемая функцией передаваемой как параметр key, тоже вызывается для каждого элемента, чтобы получить значение атрибута.
Анализ выполнения функции:

def sortby(somelist, n):
nlist = [(x, x) for x in somelist]
nlist.sort()
return

Память:
1. Первой строкой формируется второй список по длине равный исходному. Расход памяти уже в 2 раза больше.
2. Последней строкой формируется и возврашяется, как результат, третий список по длине равный исходному.
Итого, используется памяти = n*size*3, где n - кол. элементов списка, size - размер элемента
Я не знаю какое кол-во дополнительной памяти использует метод sort, и здесь допускаю, что он не использует дополнительной памяти.
Получается, что памяти используется в 3 раза больше, чем при простом вызове sort.

Производительность:
sortby = sort + время на выделение памяти для первого и второго списка + n * 2 * время формирования одного элемента списка конструкцией for,
где sort - время сортировки, n - кол-во элементов

sort(cmp = lambda x, y: cmp(x.s, y.s)) = sort + n * cmp, где sort - время сортировки, n - кол-во элементов, cmp - время работы функции cmp, причем она же (так или иначе) вызывается внутри функции sort при обычной сортировке, поэтому фактически это время здесь эквивалентно времени вызова пустой функции с параметрами x.s, y.s.

Разве это не в разы!?

Возможно, я в чем-то ошибся, если это так, поправьте меня.

ЗЫ
Можно, как вариант ещё и так сделать:

mass1 = sorted(mass, key=lambda obj: getattr(obj, “s”))

Отредактировано (Март 19, 2007 17:31:20)

xonix · Март 20, 2007 04:02:19

В том то и дело, что key вызывается 1 раз для каждого элемента (т.е. сложность ~n*Сложность(key)). А функция cmp вызывается единожды для КАЖДОГО СРАВНЕНИЯ, коих будет ~n*n => сложность будет ~n*n*Сложность(cmp). Хотя тут я наврал слегка. n*n это при сортировке пузырьком, при быстрой сортировке и сортировке слиянием будет ~n*ln(n). Но все рано ассимптотика будет n против n * ln n в лучшем случае.

Striver · Март 20, 2007 06:02:52

Посмотрел на теоретические споры, решил всё-таки проверить. Итак:

from time import time
from random import randint
N=1000

class s(object):
def __init__(self, s):
self.s = s
def __repr__(self):
return self.s

def sort1(somelist):
nlist =
nlist.sort()
return

def sort2(somelist):
somelist.sort(cmp = lambda x, y: cmp(x.s, y.s))
return somelist

list1=
for i in xrange(N):
list1.append(s(randint(0,1000000)))
list2=list1

time1=time()
sort1(list1)
print ‘Time sort1 = ’, time()-time1

time2=time()
sort2(list2)
print ‘Time sort2 = ’, time()-time2

Результаты:

N=1000
Time sort1 =  0.0
Time sort2 =  0.0160000324249

N=10000
Time sort1 =  0.0469999313354
Time sort2 =  0.156000137329

N=100000
Time sort1 =  0.93700003624
Time sort2 =  2.29699993134

N=1000000
Time sort1 =  530.907000065
Time sort2 =  243.906000137

При N=1000000 мой бедный компутер (память = 256Мб) постоянно жевал жесткий диск и делал вид, что сейчас умрёт, причем свопил он при обоих сортировках, но хорошо заметно, что использование двух лишних списков в первой сортировке играет свою фатальную роль. Общий же вердикт видимо такой: при N<100000 выгоднее использовать первый метод, а при бОльших N НЕОБХОДИМО проводить собственные тесты, т.к. результат сильно зависит от памяти, процессора, скорости жесткого диска, версии Python и т.д.

Tmr · Март 20, 2007 18:27:12

Striver, спасибо за эксперимент!

xonix
В том то и дело, что key вызывается 1 раз для каждого элемента (т.е. сложность ~n*Сложность(key)). А функция cmp вызывается единожды для КАЖДОГО СРАВНЕНИЯ, коих будет ~n*n => сложность будет ~n*n*Сложность(cmp). Хотя тут я наврал слегка. n*n это при сортировке пузырьком, при быстрой сортировке и сортировке слиянием будет ~n*ln(n). Но все рано ассимптотика будет n против n * ln n в лучшем случае.

Это действительно так, но поскольку внутри sort, очевидно, все равно вызыается cmp, то при использовании анонимной функции для вызова cmp, время работы sort увеличивется на <сложность sort> * (<время для передачи параметров функции и возвращения результата> + <время обращения к атрибутам объекта>). Для не очень больших величин этим можно пренебречь, но оказывается, к сожалению, не в Python…
Суть кода в 2-х словах: для 2-х списков из N элементов для каждй пары вызывается cmp(a, b) и lambda a1,a2: cmp(a1, a2), и вычисляется соотношение времени затраченного на эти вызовы.

from time import time
from random import randint, sample
from os import linesep

def random_s(size):
return s(''.join(sample('qwertyuioplkjhgfdsazxcvbn', size)))

def random_s_list(list_size, s_size):
return

def dumb_map(funct, lst1, lst2):
for l1 in lst1:
for l2 in lst2:
funct(l1, l2)

def test_cmp(lst1, lst2):
time1=time()
dumb_map(cmp, lst1, lst2)
time1=time()-time1
print ‘Time cmp = ’, time1
time2=time()
f = lambda a1,a2: cmp(a1, a2)
dumb_map(f, lst1, lst2)
time2=time()-time2
print ‘Time lambda: cmp = ’, time2
if time1 > 0:
print ‘Ratio = ’, time2/time1, linesep
else:
print ‘Ratio = ’, time2, linesep
#—————————
class s(object):
def __init__(self, s):
self.s = s
def __repr__(self):
return self.s

N=500
for z in xrange(4):
N = N*2
print ‘N = ’, N
test_cmp(random_s_list(N, 10), random_s_list(N, 10))

Результат:

N =  1000
Time cmp =  4.64099979401
Time lambda: cmp =  10.0780000687
Ratio =  2.17151487093 

N =  2000
Time cmp =  18.5780000687
Time lambda: cmp =  40.2029998302
Ratio =  2.1640111789 

N =  4000
Time cmp =  73.625
Time lambda: cmp =  160.780999899
Ratio =  2.18378268114 

N =  8000
Time cmp =  298.094000101
Time lambda: cmp =  655.421999931
Ratio =  2.19870913104

Такое соотношение очень существенно! По неопытности я об этом не догадался…
Не поленился, написал аналогичный код в делфи. С отключенной оптимизацией, с передачей параметров по значению (параметры копируются в стек) код дает соотношение для вызова функции по ссылке (процедурный аналог lambda) очень близкое к 1. Хотя, если написать вызовы функций через диспинтерфейсы (прокси-классы), как вероятно происходит вызов в Python, то результат скорее всего будет близок. Вот такие вот вызовы функций в языках с динамической типизацией…
Если кто-то заметит ошибку в рассуждениях - напишите, пож.

Dimka665 · Окт. 10, 2008 12:56:10

ясен пень, что с лямбдой медленнее.
ее лучше с функциями высокого порядка использовать.

Python-сообщество

Уведомления

#1 Март 11, 2007 20:06:58

python 2.2 и сортировка

#2 Март 11, 2007 20:18:06

python 2.2 и сортировка

#3 Март 13, 2007 16:15:35

python 2.2 и сортировка

#4 Март 15, 2007 19:51:19

python 2.2 и сортировка

#5 Март 16, 2007 21:03:18

python 2.2 и сортировка

#6 Март 19, 2007 11:42:24

python 2.2 и сортировка

#7 Март 20, 2007 04:02:19

python 2.2 и сортировка

#8 Март 20, 2007 06:02:52

python 2.2 и сортировка

#9 Март 20, 2007 18:27:12

python 2.2 и сортировка

#10 Окт. 10, 2008 12:56:10

python 2.2 и сортировка

Board footer