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

Question

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

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

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

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

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

如果我删除所有重复项，我可以将我的嵌套列表减少很多（大约一半），但我找不到一种节省时间的方法。

因为最好在将这些颠倒的重复项添加到我的嵌套列表之前将其删除，下面我包含了我用来制作列表的 class。

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)

这个方法很慢。在删除 class 中的行 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())

这个returns:

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

Answer 2

我的方法是将每个元组切换到一个列表，反转它，将它切换回一个元组，如果它是列表的一部分，则从列表中删除（反转的）元组。

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

for t in l:
    lr = list(t)
    lr.reverse()
    tr = tuple(lr)
    if tr in l:
        l.remove(tr)

print(l)

我不知道这会计算多快，但输出就在这里。

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

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

Save time removing reversed duplicates from a nested list in Python?

python

reverse

list

duplicates

detection