title: intersection of 100*100 elements and any suggestion for a better data structure?
body: <p>okay heres the problem!<br/>
  i have created a dictionary something like this</p>
  
  <pre><code>a={'t1':[{seta1},{seta2},{seta3},{seta4}],
     't2':[{setb1},{setb2},{setb3},{setb4}],
      .
      .
      .
     't100':[{setz1},{setz2},{setz3},{setz4}]}
  </code></pre>
  
  <p>where 't1','t2',....,'t100' are the timestamps and {set1},{set2},{set3},{set4} are the disjoint sets of clusters at those respective timestamps.</p>
  
  <p>now i want to find intersections of each and every set set with every other set across timestamps.
  i.e., assuming    </p>
  
  <pre><code>b={}   # is my resulting dictionary
  </code></pre>
  
  <p>Initially b is empty so 'b' contains entire a['t1'] with key 't1'<br/></p>
  
  <pre><code>b['t1']=a['t1'] #isn't this a deep copy? cos i replicating the values. Is there a way to achieve a shallow copy? thought of using .copy() and .update() method but couldn't figure out any possible way.
  </code></pre>
  
  <p>as the iterations goes on, I find the intersections and update the resulting dictionary as follows.</p>
  
  <pre><code>k=[i&amp;j for i in a[key1] for j in b[key2]]
  
  #if intersections between a and b are empty sets, then i will create 'key1' in b and put the corresponding value of key1 in b
  #if key1 is already present in b, then i will append the a[key1] value into b[key1] and remove the corresponding value from a[key1]
  
  #if the intersections are found, and the length of each intersection is &gt;2, i will do something like this
  b[key2+','+key1] not in b.keys(): 
    b[key2+','+key1]=[] #b[t1,t2]=non-empty intersections whose length is &gt;2
  b[key2+','+key1]=k #where k holds the intersection and the empty sets and intersections with length one are removed before this stage    
  </code></pre>
  
  <p>suppose that i have each seta1, seta2, seta3 etc.,. having 100 elements each<br/>
  then isn't finding intersections very intensive? (100*100) is there any efficient way to find intersections easily? How to cut down the intensity? I believe I read somewhere that worst case scenario of intersection is </p>
  
  <pre><code>     O(len(s)*len(t))
  </code></pre>
  
  <p>to sum it up:</p>
  
  <ul>
  <li>to find intersection in an easier way? is numpy's intersect1d better than this?</li>
  <li>is there possibly a better data structure for computation? (i thought heap would be the choice, but again after every insertion the heap tree should be rearranged to attain "parental dominance property". any other suggestion?)</li>
  <li>to achieve a shallow copy of a particular key-value pair from one dictionary to another.</li>
  </ul>
  
  <p>any help would be very much appreciated.! :)
  thanks in adv.! :) :)</p>