1

我想使用 bisect （如此处所示，在第二个答案中：Does python have a sorted list?），但我没有使用数字列表，而是有一个对象列表。具体来说，来自此类的对象：https ://networkx.github.io/documentation/latest/_modules/networkx/classes/graph.html

我希望列表保持图表按节点数排序。如果我将这些图推送到列表中，它看起来像是以任意方式插入的，（如果我多次运行它，它会在运行之间发生变化）。

是否有每个类可以定义的“排序”函数，在应用排序时将使用它（如其他语言中的运算符覆盖）？

import bisect
import networkx as nx

L=[]
G1 = nx.Graph()
G2 = nx.Graph()

G1.add_edges_from([(1,2),(1,3),(2,3),(3,4),(4,5),(4,6),(5,6),(4,7),(7,8),(7,9),(8,9)])
print 'G1', G1.number_of_nodes()
G2.add_edges_from([(1,2),(1,3)])
print 'G2', G2.number_of_nodes()

bisect.insort(L,G1)
bisect.insort(L,G2)

print 'L0 ', L[0].number_of_nodes()
print 'L1' ,L[1].number_of_nodes()

如果有其他方法可以做到这一点，那就太好了。

谢谢

4

1 回答 1

2

您的列表有点随意的顺序是由于对象是按id排序的（它是从 CPython 中对象的 RAM 地址派生的），除非它们提供了一些其他方式来定义排序。

解决问题的简单方法是简单地使用内置list.sort方法（或函数），作为关键函数参数sorted传递。key=len

但是，如果你想使用bisect来维护一个排序列表，你也可以这样做，但是你的类需要定义富比较方法。

您可以将这些方法添加到您的图形类中，但将新类定义为包装器可能更容易（也更简洁）。

这是一个包装内置list类型的简单示例。它定义了一个私有方法_cmp来执行基于长度的比较，并且富比较“魔术”方法调用_cmp. 为了提高效率，应该直接定义丰富的比较方法，以避免调用另一个方法，但使用_cmp更容易阅读（和编写:)）。

import bisect

class MyList(object):
    def __init__(self, data):
        self.data = data

    def __repr__(self):
        return 'MyList({0!r})'.format(self.data)

    def _cmp(self, other):
        return len(self.data) - len(other.data)

    #Rich comparison methods
    def __lt__(self, other):
        return self._cmp(other) < 0

    def __le__(self, other):
        return self._cmp(other) <= 0

    def __eq__(self, other):
        return self._cmp(other) == 0

    def __ne__(self, other):
        return self._cmp(other) != 0

    def __ge__(self, other):
        return self._cmp(other) >= 0

    def __gt__(self, other):
        return self._cmp(other) > 0


data = (
    [50, 60],
    [10, 20, 30],
    [1, 2, 3, 4, 5],
    [5, 6],
    [7, 8, 9, 10],
)

blist = []
for seq in data:
    a = MyList(seq)
    bisect.insort(blist, a)
    print(a)
    print(blist)
    print()

输出

MyList([50, 60])
[MyList([50, 60])]

MyList([10, 20, 30])
[MyList([50, 60]), MyList([10, 20, 30])]

MyList([1, 2, 3, 4, 5])
[MyList([50, 60]), MyList([10, 20, 30]), MyList([1, 2, 3, 4, 5])]

MyList([5, 6])
[MyList([50, 60]), MyList([5, 6]), MyList([10, 20, 30]), MyList([1, 2, 3, 4, 5])]

MyList([7, 8, 9, 10])
[MyList([50, 60]), MyList([5, 6]), MyList([10, 20, 30]), MyList([7, 8, 9, 10]), MyList([1, 2, 3, 4, 5])]

您可能想看看heapq：您可能会发现它比bisect. heapq如果定义了丰富的比较方法，将（当然）使用它们。

于 2016-01-27T09:45:09.800 回答