Найти все общие кортежи N размера в списке кортежей

Question

Я должен создать приложение, которое выполняет следующее (я должен только один раз разобрать данные и хранить их в базе данных):

Я дал K кортежи (с K над 1000000.) и каждого кортежа в виде

(UUID, (tuple of N integers)) 

Давайте предположим, что N равно 20 для каждого к-кортежа, и что каждые 20 размера кортеж отсортированы. Я сохранил все мои данные в базу данных в следующих двух формах (2 разных таблиц), так что я могу обрабатывать их более легко:

1. _id, UUID, tuple.as_a_string()
2. _id, UUID, 1st_elem, 2nd_elem, 3rd_3lem ... 20th_elem

цель состоит в том, чтобы найти все 10 размер кортежей из списка кортежей, таким образом, что каждый из этих кортежей существовать в более чем один 20 размере кортеж. **

Например, если нам даны два ING 20 размера кортежи:

(1, (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,161,17,18,19,20)) 
(2, (1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39)) 

общий кортеж: (1,3,5,7,9,11,13,15,17,19)

, который является 10-размера кортежа , так что получается нечто вроде следующего:

(1, 2, (1,3,5,7,9,11,13,15,17,19)) 

для того, чтобы достичь этого, что я сейчас делаю это (в Python 3):

• Создать набор с элементами 20 -si zed кортеж 1-й строки в базе данных.
• Создайте набор для каждой строки с элементами 20-размерного кортежа остальных строк в базе данных.
• Для каждого набора во втором списке множеств я пересекаюсь с первым набором.
• Затем я создаю комбинацию пересечения с 10 элементами (в Python это itertools.combinations (new_set, 10)), что дает мне результат, который я хочу.

Но эта процедура очень медленно. Даже используя многопроцессорную обработку, чтобы полностью использовать мои 8 ядер процессора, каждый компьютер для другого номера, он берет навсегда. У меня есть программа, работающая в течение 2 дней, и она только в 20%.

Есть ли у вас какие-либо идеи по оптимизации процесса? Будут ли массивы NumPy справляться со скоростью выполнения? Есть ли какой-либо способ в SQL рассчитать, что я хочу для каждой строки, даже по одной строке за раз?

Заранее спасибо.

Answer 1

Там, кажется, не будет много надежды на это: забывая combinations() часть, вам необходимо проверить пересечение каждой пары K кортежей. Есть choose(K, 2) = K*(K-1)/2 пар, поэтому с миллионом кортежей насчитывается около 500 миллиардов пар.

Один низкоуровневый трюк, который вы можете воспроизвести, состоит в том, чтобы представлять кортеж как целое, а не как набор, где бит 2**i устанавливается в целое число тогда и только тогда, когда i находится в кортеже. Поскольку вы сказали в комментариях, что кортеж не содержит дубликатов, а каждый элемент кортежа находится в range(1, 100), достаточно 100-битных целых чисел (его можно сократить до 99 бит, но не стоит беспокоить).

Дело в том, что побитовые «&» целых чисел идут намного быстрее, чем заданное пересечение. На моей коробке, примерно в 7 раз быстрее.Вот код, чтобы проиллюстрировать эту концепцию, и некоторые корявые результаты синхронизации (бег на машине делать много других вещей одновременно):

def build(K, values, N): 
    from random import sample 
    sets = [] 
    ints = [] 
    for i in range(K): 
     t = sample(values, N) 
     sets.append(set(t)) 
     ints.append(sum(1 << i for i in t)) 
    return sets, ints 

def run(K, values, N): 
    from time import time 
    as_sets, as_ints = build(K, values, N) 
    for meth, collection in [("sets", as_sets), 
          ("ints", as_ints)]: 
     s = time() 
     for i in range(K-1): 
      base = collection[i] 
      for j in range(i+1, K): 
       x = base & collection[j] 
     t = time() 
     print("K", K, meth, t-s) 

for K in 5000, 10000, 20000: 
    run(K, range(1, 100), 20) 

И выход:

K 5000 sets 7.322501182556152 
K 5000 ints 1.0357279777526855 
K 10000 sets 30.60071086883545 
K 10000 ints 4.150524377822876 
K 20000 sets 128.24610686302185 
K 20000 ints 15.933331727981567 

Обратите внимание, что, как и ожидалось, во время выполнения для любого подхода квадратично в K (так что удвоение K занимает примерно в 4 раза больше, а увеличение K в 10 раз увеличивает время выполнения в 10 раз ** 2 = 100).

В то время как пересечение происходит намного быстрее с помощью ints, определение мощности результата происходит медленнее. Есть много способов сделать это, но «лучшее» зависит от ожидаемого распределения и вашей толерантности к боли при кодировании ;-) Вот обзор major methods.

Answer 2

Похоже, что вы можете поместить кортежи в строки матрицы и составить карту из номеров строк в UUID. Тогда можно сохранить все кортежи в массиве numpy, поскольку элементы кортежей малы. numpy имеет код, способный вычислять пересечения между строками такого массива. Этот код генерирует комбинации для обработки сначала как кортежи, а затем выполняет сравнения.

from itertools import combinations 
import numpy as np 
from time import time 

minInt=1 
maxInt=100 
tupleSize=20 
intersectionSize=10 

K=100 
rows=np.zeros((K,tupleSize),dtype=np.int8) 
print ('rows uses', rows.nbytes, 'bytes') 

for i,c in enumerate(combinations(range(minInt,maxInt),tupleSize)): 
    if i>=K: 
     break 
    for j,_ in enumerate(c): 
     rows[i,j]=_ 

t_begin=time() 
for i in range(K-1): 
    for j in range(i+1,K): 
     intrsect=np.intersect1d(rows[i],rows[j],True) 
     if intrsect.shape[0]==intersectionSize: 
      print (i,j,intrsect) 
t_finish=time() 

print ('K=', K, t_finish-t_begin, 'seconds') 

Ниже приведены некоторые образцы измерений, сделанные на моем старом двухъядерном цуккете P4 дома.

строк использует 200 байт K = 10 +0,0009770393371582031 секунд

строки использует 1000 байт K = 50 0,0410161018371582 секунд

строк использует 2000 байт K = 100 0,15625 секунд

строки использует 10000 байт K = 500 3.610351085662842 секунды

строки используют 20000 байт K = 1000 14.931640863418579 секунд

строк использует 100000 байт K = 5000 379,5498049259186 секунд

Если запустить код на вашей машине вы можете экстраполировать. Я не знаю, сделает ли это ваш расчет допустимым или нет.

Возможно, я просто получу кучу отрицательных голосов!

Answer 3

Bill, я думаю, что это создает более случайный микс. Варианты ваших комбинаций систематически выбираются через выбор. При малом K размер пересечения близок к tupleSize.

choices = np.arange(minInt, maxInt) 
for i in range(K): 
    rows[i,:] = np.random.choice(choices, tupleSize, replace=False) 

Использование sets около 4 раза быстрее, чем np.intersect1d.

sets = [set(row) for row in rows] 
dd = collections.defaultdict(int) 
for i in range(K-1): 
    for j in range(i+1,K): 
     intrsect=sets[i].intersection(sets[j]) 
     dd[len(intrsect)] += 1 

Я переключился на сбор размера пересечения, поскольку он более интересен и менее чувствителен к стратегии итерации.

С К = 5000:

K= 5000 221.06068444252014 seconds 
{0: 77209, 1: 514568, 2: 1524564, 3: 2653485, 4: 3044429, 5: 2436717, 6: 1408293, 7: 596370, 8: 188707, 9: 44262, 10: 7783, 11: 1012, 12: 93, 13: 8} 

Меньшее время только на стадии создания sets; это очень быстро.

K= 5000 0.058181047439575195 46.79403018951416 seconds 
{0: 77209, 1: 514568, 2: 1524564, 3: 2653485, 4: 3044429, 5: 2436717, 6: 1408293, 7: 596370, 8: 188707, 9: 44262, 10: 7783, 11: 1012, 12: 93, 13: 8} 

для увеличения K

K= 10000 818.3419544696808 seconds 
{0: 309241, 1: 2058883, 2: 6096016, 3: 10625523, 4: 12184030, 5: 9749827, 6: 5620209, 7: 2386389, 8: 752233, 9: 176918, 10: 31168, 11: 4136, 12: 407, 13: 18, 14: 2} 
K= 10000 0.09764814376831055 151.11484718322754 seconds