タプルのリスト内の同じ要素をグループ化して検索する？

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] 

がより効率的な方法があります複数のリスト間で1対1の解析を行わずにこの結果を得ることができますか？

Answer 1

ここをクリックしてnumpy tastic vectorisedアプローチです。合理的に速いと思われる。しかし、徹底的にテストされていない。 explicitlは、各リストに2つのタプルがあり、各タプルに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)