Группировка и поиск идентичных элементов в списке кортежей?

Question

У меня есть несколько списков кортежей, как эти из них (они представляют собой координату):

a = [(100,100), (50,60)] 
b = [(100,50), (50,60)] 
c = [(100,100), (20,60)] 
d = [(70,100), (50,10)] 
e = [(100,80), (70,100)] 

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

Поскольку они являются координатами, X и Y для каждого кортежа не могут быть одинаковыми в другом кортеже (то есть X, но разные Y).

Для приведенного выше примера, я хотел бы, наконец, что-то вроде этого (в виде списка, но и более эффективным способом, если это возможно):

new_list1 = [a, b, c] 
new_list2 = [d, e] 

Есть ли более эффективный способ получить этот результат без индивидуального разбора между несколькими списками?

Answer 1

Хорошо, вот numpy Тактический векторный подход. Кажется разумно быстрым. Не тщательно проверены. Он явно предполагает, что в каждом списке есть два кортежа и каждый кортеж 2 координаты.

import time 
import numpy as np 

def find_chains_nmp(lists): 
    lists = np.asanyarray(lists) 
    lists.shape = -1,2 
    dtype = np.rec.fromrecords(lists[:1, :]).dtype 
    plists = lists.view(dtype) 
    lists.shape = -1, 2, 2 
    uniq, inv = np.unique(plists, return_inverse=True) 
    uniqf = uniq.view(lists.dtype).reshape(-1, 2) 
    inv.shape = -1, 2 
    to_flip = inv[:, 0] > inv[:, 1] 
    inv[to_flip, :] = inv[to_flip, ::-1].copy() 
    sl = np.lexsort(inv.T[::-1]) 
    sr = np.lexsort(inv.T) 
    lj = inv[sl, 0].searchsorted(np.arange(len(uniq)+1)) 
    rj = inv[sr, 1].searchsorted(np.arange(len(uniq)+1)) 
    mask = np.ones(uniq.shape, bool) 
    mask[0] = False 
    rooted = np.zeros(uniq.shape, int) 
    l, r = 0, 1 
    blocks = [0] 
    rblocks = [0] 
    reco = np.empty_like(lists) 
    reci = 0 
    while l < len(uniq): 
     while l < r: 
      ll = r 
      for c in rooted[l:r]: 
       if (rj[c]==rj[c+1]) and (lj[c]==lj[c+1]): 
        continue 
       connected = np.r_[inv[sr[rj[c]:rj[c+1]], 0], 
            inv[sl[lj[c]:lj[c+1]], 1]] 
       reco[reci:reci+lj[c+1]-lj[c]] = uniqf[inv[sl[lj[c]:lj[c+1]], :]] 
       reci += lj[c+1]-lj[c] 
       connected = np.unique(connected[mask[connected]]) 
       mask[connected] = False 
       rr = ll + len(connected) 
       rooted[ll:rr] = connected 
       ll = rr 
      l, r = r, rr 
     blocks.append(l) 
     rblocks.append(reci) 
     if l == len(uniq): 
      break 
     r = l + 1 
     rooted[l] = np.where(mask)[0][0] 
     mask[rooted[l]] = 0 
    return blocks, rblocks, reco, uniqf[rooted] 


# obsolete 
def find_chains(lists): 
    outlist = [] 
    outinds = [] 
    outset = set() 
    for j, l in enumerate(lists): 
     as_set = set(l) 
     inds = [] 
     for k in outset.copy(): 
      if outlist[k] & as_set: 
       outset.remove(k) 
       as_set |= outlist[k] 
       inds.extend(outinds[k]) 
     outset.add(j) 
     outlist.append(as_set) 
     outinds.append(inds + [j]) 
    outinds = [outinds[j] for j in outset] 
    del outset, outlist 
    result = [[lists[j] for j in k] for k in outinds] 
    return result, outinds 


if __name__ == '__main__': 
    a = [(100,100), (50,60)] 
    b = [(100,50), (50,60)] 
    c = [(100,100), (20,60)] 
    d = [(70,100), (50,10)] 
    e = [(100,80), (70,100)] 

    lists = [a, b, c, d, e] 
    print(find_chains(lists)) 



    lists = np.array(lists) 
    tblocks, lblocks, lreco, treco = find_chains_nmp(lists) 


    coords = np.random.random((12_000, 2)) 
    pairs = np.random.randint(0, len(coords), (12_000, 2)) 
    pairs = np.delete(pairs, np.where(pairs[:, 0] == pairs[:, 1]), axis=0) 
    pairs = coords[pairs, :] 
    t0 = time.time() 
    tblocks, lblocks, lreco, treco = find_chains_nmp(pairs) 
    t0 = time.time() - t0 
    print('\n\nproblem:') 
    print('\n\ntuples {}, lists {}'.format(len(coords), len(pairs))) 
    if len(pairs) < 40: 
     for k, l in enumerate(pairs): 
      print('[({:0.6f}, {:0.6f}), ({:0.6f}, {:0.6f})] ' 
        .format(*l.ravel()), end='' if k % 2 != 1 else '\n') 
    print('\n\nsolution:') 
    for j, (lists, tuples) in enumerate(zip(
      np.split(lreco, lblocks[1:-1], axis=0), 
      np.split(treco, tblocks[1:-1], axis=0))): 
     print('\n\ngroup #{}: {} tuples, {} list{}'.format(
      j + 1, len(tuples), len(lists), 
      's' if len(lists) != 1 else '')) 
     if len(pairs) < 40: 
      print('\ntuples:') 
      for k, t in enumerate(tuples): 
       print('({:0.6f}, {:0.6f}) '.format(*t), 
         end='' if k % 4 != 3 else '\n') 
      print('\nlists:') 
      for k, l in enumerate(lists): 
       print('[({:0.6f}, {:0.6f}), ({:0.6f}, {:0.6f})] ' 
         .format(*l.ravel()), end='' if k % 2 != 1 else '\n') 
    print('\n\ncomputation time', t0)