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

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

0 голосов
/ 24 марта 2011

Я столкнулся со странным поведением при работе со списками в 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. Таким образом, первоначальное упорядочение с помощью sorted (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))

Ответы [ 3 ]

3 голосов
/ 24 марта 2011

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

print sorted(set(tuple(sorted(x)) for x in L))
1 голос
/ 24 марта 2011

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

0 голосов
/ 24 марта 2011

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

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

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

...