Python: неожиданный порядок в списках

Question

Я столкнулся со странным поведением при работе со списками в Python. Я реализовал метод, который возвращает список списков целых чисел; в частности, это циклы в графе, каждый из которых включает три узла:

simple_cycles = compute_cycles(graph)

Это возвращает мне что-то вроде этого:

[[40000,20000,30000],[700,500,600],[600,500,700],..]

Теперь мне нужно (1) упорядочить каждый список в списке, и после этого мне нужно (2) удалить дубликаты из всего списка и (3) мне нужно снова отсортировать весь этот список. Тогда желаемый результат может выглядеть следующим образом:

[[500,600,700],[20000,30000,40000]]

Задача (1) достигается путем сортировки внутренних списков до их возвращения через compute_cycles. Задачи (2) и (3) получаются путем выполнения следующей строки:

cycles = dict((x[0], x) for x in simple_cycles).values()

Это работает для первого обработанного графика. Каждый следующий график дает сбой, потому что порядок во внутренних списках иногда неправильный. Я дважды попробовал последнюю строку исходного кода, и второй результат оказался не таким, как ожидалось. Например, я получил как х во втором запуске:

[29837921, 27629939, 27646591]

вместо

[27629939, 27646591, 29837921]

Это приводит к выбору 29837921 в качестве ключа в словаре вместо 27629939. Таким образом, первоначальное упорядочение с сортировкой (x) уже кажется ложным. Но почему?

Я пытался воспроизвести это поведение вне моей программы, но не могу. В моем приложении я анализирую документ XML следующим образом:

detector = MyParser()
handler = MyHandler()
handler.subscribe(detector.update)
detector.parse(filename, handler)

..

def parse(self, infile, handler):
  parser = etree.XMLParser(target=handler)
  etree.parse(infile, parser)

При выполнении, например,

detector = MyParser()
handler = MyHandler()
handler.subscribe(detector.update)
detector.parse(filename, handler)
detector.parse(filename, handler)

тогда заказ второго прогона является неожиданным.

Я знаю, что мой пример исходного кода не подходит для воспроизведения его самостоятельно, но, возможно, я упускаю некоторые элементарные элементы Python при работе со списками.

Обновить

Вот создание списков:

from networkx import dfs_successors

def compute_cycles(graph):
  cycles = []
  for node in graph.nodes():
    a = graph.successors(node);
    for a_node in a:
      b = graph.successors(a_node)
      for next_node in b:
        c = graph.successors(next_node);
        if len(c) > 1:
          if c[0] == node:
            cycles.append(sorted([node, a_node, next_node]))
          elif c[1] == node:
            cycles.append(sorted([node, a_node, next_node]))
        else:
          if c == node:
            cycles.append(sorted([node, a_node, next_node]))
        #fi
      #rof
    #rof
  #rof
  return cycles

Обновить

Если сделал большую ошибку: я перезаписал __repr__ функция моего объекта Node, используемого в графе, так что он возвращает целое число. Может быть, сортировка не удалась, потому что я имею дело с реальными объектами, а не с целыми числами. Я изменил свой звонок на sort функционировать так:

cycles.append(sorted([node, a_node, next_node], key=lambda revision: revision.rev.revid))

Я должен посмотреть, если это имеет значение. Класс узла определяется следующим образом:

class Node(object):
  def __init__(self, revision, revision_hash):
    self.rev = revision
    self.revhash = revision_hash

  def __repr__(self):
    return repr((self.rev.revid))

Answer 1

Моя проблема наконец-то решена. Потому что я помещаю объекты в списки вместо простых IntegersЯ должен был использовать sort метод следующим образом:

sorted([node, a_node, next_node], key=lambda revision: revision.rev.revid))

Здесь я обращаюсь к переменной-члену, содержащей Integer, который уже был возвращен __str__, Однако неявное преобразование при сортировке не было стабильным.

Answer 2

Я не понимаю, почему вы используете dict,

print sorted(set(tuple(sorted(x)) for x in L))

Answer 3

Словари не обязательно соблюдают порядок. Им разрешено это менять. Поместите это в интерпретатор: {'a': 1, 'b': 2, 'c': 3}, я получил {'a': 1, 'c': 3, 'b': 2},