Como obter o indice de item de menor valor em um dict?

[Fábio Barrionuevo]

Boa tarde pessoal,

Estou implementando o algoritmo de Dijsktra, 

que ja está funcional.

percebi que na minha implementação,

o algoritmo demora muito tempo no metodo abaixo.

alguem conhece alguma forma mais eficiente de se obter o indice do primeiro menor valor de um dict python?

    def retorna_indice_menor_valor_do_dicionario_se_indice_pertencer_a_lista(qnt_vertices,lista, dicionario):

            menor = 99999999

            # -1 se nao achou menor valor

            indice= -1

            for i in xrange(0,  qnt_vertices):

                if  dicionario[i] < menor and i in lista:

                    menor =  dicionario[i]

                    indice = i

            return indice

Obrigado a todos.

--
Fábio C. Barrionuevo da Luz
Acadêmico de Sistemas de Informação na Faculdade Católica do Tocantins - FACTO
Palmas - Tocantins - Brasil - América do Sul

[Christian S. Perone]

min(dicionario, key=dicionario.get) ?

2012/5/25 Fábio Barrionuevo <bna...@gmail.com>

--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com

--
"Forgive, O Lord, my little jokes on Thee, and I'll forgive Thy great big joke on me."
http://pyevolve.sourceforge.net/wordpress/

[Alysson Bruno]

Além da dica do Perone, seu algoritmo não está otimizado. Se vc já guarda o indice do menor valor, não precisa guardar o valor em si. Ou seja, retire o menor e onde precisa do valor dele (no if) use dicionario[indice].

paz e amor (love and peace),

Alysson Bruno
Palmas(TO)
Brasil

http://abruno.com

Meu alterego Escritor: Leia alguns contos que escrevo, não esqueça de me dar sua opinião: http://goo.gl/Wjn4p

2012/5/25 Fábio Barrionuevo <bna...@gmail.com>

[Rafael Sachetto]

2012/5/25 Christian S. Perone <christia...@gmail.com>

min(dicionario, key=dicionario.get) ?

Mesmo assim, ainda seria uma busca sequencial. Já que o dicionário é uma hash que nao possui nenhuma ordenação.

O algortitmo de Dijsktra funciona muito melhor utilizando uma fila de prioriadades, que já existe em python (http://docs.python.org/library/heapq.html)

--
Rafael Sachetto Oliveira

[Leandro Lameiro]

Oi Fábio,

Você pode iterar só sobre a sua lista ao invés de todos os nós do seu dict. Isso vai te poupar vários "i in lista", que pode ser uma operação cara dependendo do tamanho do seu grafo.

def retorna_indice_menor_valor_do_dicionario_se_indice_pertencer_a_lista(qnt_vertices,lista, dicionario):
    menor = 99999999
    # -1 se nao achou menor valor
    indice= -1

    for i in lista:
        if  dicionario[i] < menor:

            menor =  dicionario[i]
            indice = i
    return indice

Depois, se ainda for preciso otimizar, você pode passar o controle do loop pro nível do C, ao invés do Python, mais ou menos como o Christian sugeriu, assim:

def get_second_element_of_tuple(the_tuple):
    return the_tuple[1]

min_key, value = min( ((i, dicionario[i]) for i in lista), key=get_second_element_of_tuple )

Mas aí já estamos no mundo da micro-otimização, tenho certeza que tem algo melhor que isso a ser feito, olhando para o programa todo, como o Rafael sugere.

2012/5/25 Rafael Sachetto <rsac...@gmail.com>

--
Best regards,
Leandro Lameiro

Blog: http://lameiro.wordpress.com
Twitter: http://twitter.com/lameiro

[Reginaldo Silva]

Primeiramente, devo dizer que sou a favor de reinventar a roda, desde que seja para fins educacionais.

O Richard Feynman, prêmio nobel de física, já dizia: "What I cannot create, I do not understand".

Então, se você está implementando Dijkstra para um exercício ou para auto engrandecimento, vá fundo.

Caso contrário, use a biblioteca networkx, que tem implementações bem eficientes de Dijkstra e outros algoritmos relacionados a grafos.

O site da networkx é http://networkx.lanl.gov/

Abraço,

Reginaldo

2012/5/25 Rafael Sachetto <rsac...@gmail.com>

[Fábio Barrionuevo]

Christian, meu conhecimento em python ainda é pequeno, realmente não conhecia essa forma de obter a chave do valor minimo.

Leandro, sua dica de otimização fez meu algoritmo rodar 6x mais rápido...

Reginaldo, minha implementação é para fins aprendizagem mesmo.

Obrigado a todos pelas respostas.

att