Сэкономить время, удалив обратные дубликаты из вложенного списка в Python? - PullRequest
Новая
       33

Сэкономить время, удалив обратные дубликаты из вложенного списка в Python?

1 голос
/ 27 марта 2019

У меня есть вложенное, содержащее миллионы других списков (с использованием кортежей 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)

Этот метод очень медленный. Я также попробовал revItem = list (полностью измененный (элемент)) после удаления строки p = tuple (p) в моем классе; очень медленно. Использование этих методов во время создания списка экономит время в целом, но не ускоряет процесс исключения, что является ключевым.

Ответы [ 2 ]

3 голосов
/ 27 марта 2019

Вы можете построить OrderedDict с ключом, являющимся кортежем в обратном порядке, только если последний элемент ниже, чем первый элемент, и значением является сам кортеж, а затем получить список значений * 1002.*: 

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 или более поздние версии, в которых упорядочены ключи dict, вы можете использовать dict вместо 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')]
0 голосов
/ 27 марта 2019

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

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')]
...