Блог

Я хотел бы найти эффективный способ извлечения всех элементов в массиве, которые соответствуют определенному шаблону.

Например, учитывая, что у меня есть:

• массив M , состоящий из подмассивов разных размеров:

     M = [[0, 1],
         [3, 2, 4],
         [3, 8],
         [9],
         [0, 2],
         [3, 1],
         [0, 3],
         [2, 4],
         [3, 7]]
    

• Шаблон подмассивов. Например, [[a, b], [a, c], [a, d]] совпадения [[0, 1], [0, 2], [0, 3]] .

Как я могу вернуть все элементы M , которые соответствуют шаблону?

До сих пор я использовал for циклы для поиска подходящих элементов, но этот наивный подход оказывается очень дорогостоящим, когда шаблон имеет более 2 подмассивов.

Пример:

 M = [[0, 1], [3, 2, 4], [3, 8], [9], [0, 2], [3, 1], [0, 3], [2, 4], [3, 7]]

# pattern with 3 sub-arrays -> [[a, b], [a, c], [a, d]]

for i, arr1 in enumerate(M):
    for j, arr2 in enumerate(M):
        for k, arr3 in enumerate(M):
            if i != j != k:
                if len(arr1) == len(arr2) == len(arr3) == 2:
                    a1, a2, a3 = arr1[0], arr2[0], arr3[0]
                    b, c, d = arr1[1], arr2[1], arr3[1]
                    if a1 == a2 == a3 and b < c < d:
                        print arr1, arr2, arr3
  

Вывод:

 [0,1], [0,2], [0,3]
[3,1], [3,7], [3,8]
  

Поскольку на каждый вложенный массив приходится дополнительный вложенный цикл, временная сложность этого метода ( O(n^k) где k — количество вложенных массивов) становится проблемой.

Возможно ли ускорить этот процесс? Если да, то как?

Во-первых, прежде чем перейти к numpy, давайте посмотрим на ваши условия. Вам требуется, чтобы вложенные массивы имели только два элемента. Итак, давайте предварительно отфильтруем ваш массив:

 M = [m for m in M if len(m) == 2]
  

Теперь вы проверяете a1 == a2 == a3 and b < c < d , но каждая возможная перестановка b , c , d отображается в последовательности. Так что на самом деле, если вы найдете какой-либо b != c != d для данного a , вы можете изменить его в правильном порядке, зная, что этот порядок в конечном итоге появится.

Поэтому очень простой способ справиться с этим — создать сопоставление словаря a со всеми возможными вариантами для b , c , d , отфильтровать их по минимальному количеству «подмассивов», которые вы хотите, отсортировать их и вычислить все возможные комбинации:

 # set removed duplicates automatically
options = collections.defaultdict(set)

for a, b in (m for m in M if len(m) == 2):  # Use a generator to filter on-the-fly
    options[a].add(b)

for a, bcd in options.items():
    # sort (combinations automatically filters too-short bins)
    for b, c, d in itertools.combinations(sorted(bcd), 3):
        print(f'[{a}, {b}], [{a}, {c}], [{a}, {d}]')
  

Это решение, вероятно, алгоритмически оптимально. Он выполняет один проход по исходному списку для выявления потенциальных шаблонов, а затем выполняет ровно одну итерацию для каждого шаблона. Единственное, чего здесь потенциально не хватает, это то, что дубликаты полностью устраняются. Вы можете обрабатывать дубликаты, используя collections.Counter вместо set .