python - 从 Python 的嵌套列表中删除反向重复项可以节省时间吗？

Question

我有一个包含数百万个其他列表的嵌套(使用元组 atm)。对于每个列表，一个元素只能包含一次。我认为每个列表都是唯一的，所以我需要它们全部，但我最近意识到我的嵌套列表包含这样的对:

listA = ('77', '131', '212', '69')
listB = ('69', '212', '131', '77')

虽然 listA 和 listB 是唯一的，但其中一个只是另一个的反转副本。我需要保留每一个独特的组合，因为顺序很重要。

listC = ('131', '69', '77', '212')

因此，listC 虽然使用相同的元素，但由于顺序而被认为是唯一的，因此需要保留。

如果删除所有重复项，我可以将嵌套列表减少很多(大约一半)，但我找不到一种方法来以省时的方式做到这一点。

因为最好在将这些反向重复项添加到我的嵌套列表之前消除它们，所以下面我包含了用于创建列表的类。

class Graph(object):

    def __init__(self, graph_dict=None):
        """ Initializes a graph object.
            If no dictionary or None is given,
            an empty dictionary will be used. """
        if graph_dict == None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    def find_all_paths(self, start_vertex, end_vertex, path=[]):
        """ Find all paths from start_vertex to end_vertex in graph """
        graph = self.__graph_dict
        path = path + [start_vertex]        
        if start_vertex == end_vertex:
            return [path]
        if start_vertex not in graph:
            return []
        paths = []
        for vertex in graph[start_vertex]:
            if vertex not in path:
                extended_paths = self.find_all_paths(vertex, end_vertex, path)
                for p in extended_paths:
                    if len(p) >= 2:
                        p = tuple(p)
                        paths.append(p)
        return paths

graph = Graph(vertexGraphDict)
nestedList= graph.find_all_paths(begin, end)

vertexGraphDict 只是一个以顶点为键的字典，其值是它所连接的其他顶点的列表。

我尝试使用以下方法消除反向重复项:

reversedLists = []
for item in nestedLists:
    if item in reversedLists:
        nestedLists.remove(item)
    else:
        revItem = item[::-1] 
        reversedLists.append(revItem)

这个方法非常慢。在删除类中的 p = tuple(p) 行后，我还尝试了 revItem = list(reversed(item)) ；也很慢。在列表生成过程中尝试这些方法可以节省总体时间，但不会加快消除过程，而这是关键。

Answer 1

您可以构建一个 OrderedDict ，仅当最后一项低于第一项时，键为逆序元组，值是元组本身，然后获取列表OrderedDict 的值:

from collections import OrderedDict
l = [
    ('77', '131', '212', '69'),
    ('69', '212', '131', '77'),
    ('1', '2', '3', '4'),
    ('4', '1', '2', '3'),
    ('4', '3', '2', '1')
]
list(OrderedDict((t[::-1] if t[-1] < t[0] else t, t) for t in l).values())

或者，如果您使用的是 Python 3.7 或更高版本，其中字典键是有序的，则可以使用字典代替 OrderedDict:

list({t[::-1] if t[-1] < t[0] else t: t for t in l}.values())

这将返回:

[('69', '212', '131', '77'), ('4', '3', '2', '1'), ('4', '1', '2', '3')]