terça-feira, fevereiro 06, 2007

Ordenando listas no python2.3 e inferiores

Ordenação simples

Um objeto to tipo 'list' possui um método chamado 'sort' que faz a ordenação 'in-place' (resultado na própria variável) do objeto.

Descrição do método:

L.sort([cmpfunc]) -- sort *IN PLACE*; if given, cmpfunc(x, y) -> -1, 0, 1'

Exemplo:

>>> lista = ['a', 'c', 'b']
>>> lista.sort()
>>> lista
['a', 'b', 'c']
>>>


Ordenação simples inversa


Para ordenar uma lista do maior para o menor item temos o método 'reverse', que trabalha de maneira análoga ao método 'sort'.

Exemplo:

>>> lista.reverse()
>>> lista
['c', 'b', 'a']
>>>

Ordenação de lista de dicionários por uma chave

O metodo 'sort' aceita uma função de comparação como paramêtro. Essa função caso seja informada será utilizada para comparar os itens da lista e resolver qual item prioridade na ordem sobre os demais.

Para que o método ordene a lista se baseando na chave dos dicionários a função criada sobrescreve a função 'bulti-in' 'cmp' do python.

A função 'cmp' como podemos ver abaixo, compara dois objetos recebidos como paramêtro retornando um inteiro que informa qual dos itens é maior ou se os dois são iguais. Baseado no resultado da função 'cmp' a função 'sort' ira ordenar a lista.

Descrição do método:

'cmp(x, y) -> integer\n\nReturn negative if xy.'

Em nosso exemplo desejamos ordenar a lista utilizando como base a chave (coluna) '2' do dicionário e assim a definimos.

Quando a função 'sort' estiver interando sobre a lista, ela vai passar cada item encontrado para a nossa função sort modificada 'mycmp' que por sua vez irá chamar a funcao 'cmp' passando como paramêtro o valor das chaves no dicionário pelo qual desejamos ordenar.

>>> lista = [{1: 'b', '2': 'b'}, {1: 'c', '2': 'a'}]
>>>
... def mycmp(a, b):
... print a
... print b
... return cmp(a.get('2'), b.get('2'))
...
>>> lista.sort(mycmp)
>>> lista
[{1: 'b', '2': 'b'}, {1: 'c', '2': 'a'}]

Também podemos utilizar 'lambda' para criar uma função anônima. O resultado é o mesmo, talvez com alguma variação de performance.

lista.sort(lambda x,y: cmp(a.get('2'), b('2')))

Ordenar listas de dicionários de acordo com uma ou mais chaves escolhidas

A função abaixo recebe dois paramêtros, a lista que se deseja ordenar e a lista de chaves que devem ditar a ordenação.

>>> lista = [{1: 1, '2': 'b', '3': 0}, {1: 1, '2': 'a', '3': -1}, {1: 0, '2': 'd', '3': 5}]
>>> def sort_list(l, sort_keys):
... def mycmp(a, b):
... k1 = map(lambda x: a.get(x), sort_keys)
... k2 = map(lambda x: b.get(x), sort_keys)
... return cmp(k1, k2)
...
... l.sort(mycmp)
... return l
...
>>> sort_list('1', lista, ['2', '1'])
[{1: 1, '3': -1, '2': 'a'}, {1: 1, '3': 0, '2': 'b'}, {1: 0, '3': 5, '2': 'd'}]

Criamos uma função 'closure' chamada 'mycmp', que como no exemplo anterior será passada para a função 'sort'. Dentro da funcao 'mycmp' é onde temos a diferença básica em relacao a função anterior. Ao invés de dizer qual o resultado de cada dicionário que ele deve utilizar para ordenar, passamos duas listas com os valores das colunas pelas quais desejamos ordenar.

Novamente, o 'sort' utlizando a funcao 'cmp' irá decidir qual dos dois objetos deve ter a preferência e assim ordenar a lista de dicionários de acordo com as colunas que especificamos.

Atenção, alguns módulos como por exemplo 'mxDatetime' sobrescrevem o método sort para que funcionem a seu gosto. Isso pode fazer com o que o método 'cmp' que estiver no namespace local não seja o 'cmp' original, caso você utilize algum módulo onde isso acontece o sort não irá funcionar corretamente. Neste caso deveremos importar a função 'cmp' diretamente das funções 'bulti-in' ou melhor do namespace '__builtin__'.

Detalhe sobre a implementação do método sort

O algoritmo de 'sort' utilizado no python é um tando diferente dos algoritmos tradicionais, um tipo de mergesort com algumas coisas a mais.

Retirado dos fontes do python listsort.txt:

"This describes an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it ). It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.

In a nutshell, the main routine marches over the array once, left to right, alternately identifying the next run, then merging it into the previous runs "intelligently". Everything else is complication for speed, and some hard-won measure of memory efficiency.
"

26 comentários:

buy viagra disse...

, alternately identifying the next run, then merging it into the previous runs "intelligently". Everything else is complication for speed, and some hard-won measure of memory efficiency."

Anônimo disse...

generic viagra 50mg buy viagra online from canada - viagra dosage in 24 hours

Anônimo disse...

viagra 50mg viagra online usa - buy viagra online with a mastercard

Anônimo disse...

generic viagra viagra for pulmonary hypertension - buy viagra online without

Anônimo disse...

viagra online without prescription can buy viagra us - viagra dosage vs cialis dosage

Anônimo disse...

buy soma online no prescription salzarex generic soma - soma special order services

Anônimo disse...

buy soma online buy soma online with prescription - soma junebug bar

Anônimo disse...

buy soma online medication like soma - buy soma safely online

Anônimo disse...

soma drug buy soma online florida - soma gym

Anônimo disse...

cheap tramadol no prescription tramadol withdrawal klonopin - tramadol addiction and withdrawal

Anônimo disse...

tramadol 50mg where to buy tramadol in the usa - tramadol 7171

Anônimo disse...

xanax online xanax online legal - urine drug test detection times xanax

Anônimo disse...

buy tramadol buy tramadol valium online - tramadol withdrawal itching

Anônimo disse...

xanax online cost generic xanax without insurance - xanax xr high

Anônimo disse...

where to buy tramadol online buy tramadol online without prescriptions - tramadol 50 mg back pain

Anônimo disse...

buy tramadol online buyers of tramadol - buy tramadol online usa cheap

Anônimo disse...

http://landvoicelearning.com/#74967 tramadol use for withdrawal symptoms - tramadol with acetaminophen dosage

Anônimo disse...

buy tramadol online 8 50 mg tramadol - buy tramadol online cod

Anônimo disse...

http://buytramadolonlinecool.com/#30807 buy tramadol echeck - tramadol 200 mg no prescription

Anônimo disse...

buy tramadol no rx tramadol for dogs kidney failure - tramadol ingredients 50 mg

Anônimo disse...

http://buytramadolonlinecool.com/#28875 tramadol no high - order tramadol online sweden

Anônimo disse...

buy klonopin online can overdose klonopin - klonopin e 64

Anônimo disse...

buy tramadol online purchase tramadol online cod - tramadol for dogs an 627

Anônimo disse...

buy klonopin online cheap klonopin withdrawal memory loss - buy klonopin cheap

Anônimo disse...

Thе ωrite-up provides proѵen
beneficial to us. It’s vегy educatіonal and you're simply obviously really knowledgeable of this type. You have exposed my own sight for you to different views on this particular subject matter together with intriquing, notable and strong content material.
My site ... buy ambien

Anônimo disse...

Your οwn repοrt features establiѕheԁ hеlpful to
us. It’s extгеmelу еԁucational and
you're simply certainly really experienced in this area. You possess opened my own face to various thoughts about this specific topic together with intriguing and reliable content material.
Also visit my weblog ; viagra