[Performance/Python2.7]: La meilleure façon de trier une liste énorme (plus 100,000) objet python

Question

J'ai une méthode me retourne un générateur, en gros je récupère une liste énorme d'objets, par exemple:

def get_persons(self):
    # par exemple 
    persons_db = self.get_persons_db()
    for person in persons_db:
         yield person

Je voudrai savoir s'il y'a un moyen pour trier le générateur a la volée ou s'il y'a une méthode a appliquer sur le générateur genre mon_generateur.sort( cmp=cmp), au lieu de reboucler une deuxième fois sur la liste?

Comments

quelles caractéristiques ont tes objets? car en fonction de ça (s'ils sont déjà un peu trié, ou compplètement dans le désordre) tu pourrais appliquer l'algo de tri le plus optimal, il ne suffit pas de se jeter sur sorted et le travail est fait, il faudrait en savoir un peu plus pour utiliser la fonction de tri adéquate.

Car les algos de tri dépendent de tes données, python ne peut pas deviner tout seul

---

@boblinux: C'est typiquement le genre de réponse anti-pythonique. En python, on ne cherche généralement pas à savoir ce genre de chose, et on n'a que peu de moyens de contrôler ce qui se passe sous le capot, en fait. D'ailleurs, tu proposerais quoi comme fonction de tri, à part sorted ou sort ?

Sinon, ça tombe bien, python optimise justement le tri pour le genre de cas que tu cite.

Answer 1

Pour trier un générateur, pas d'autre moyen que de le transformer en liste, vu que le tri à la volée est impossible. Tu peux utiliser sorted par exemple.

Dans le cas où tu n'as pas besoin de tous les éléments, mais juste des k premiers dans l'ordre, il est possible d'utiliser heapq.nlargest() par exemple.

EDIT : Vu ton code, persons_db est déja une liste, alors pourquoi ne pas la trier avant de la transformer en générateur ? Ça peut être rendu optionnel si nécessaire.

Aussi, si tes données proviennent d'une DB, peut-être est-il judicieux de trier les données directement au niveau de la DB.

Comments

Merci pour ta réponse.

Je préfère utiliser sort() que sorted pour des raisons de performance

Oui effectivement, vaut mieux traiter les données dans les couches basses (au niveau de la BDD), c'est ce que je comptais faire, juste je me suis dit peut être un ça été fait par un dev python pour pousser les performances au bout.

---

Pour un générateur, je ne pense pas que ça fasse une différence, puisqu'il faut de toute façon construire la liste, et sorted est bien plus naturel à utiliser dans ce cas.

---

Le mieux est bien d’avoir une liste triée provenant de la BDD. L’utilisation du module heapq est peut-être un bon palliatif. Voici l’article de Sam et Max qui en parle.