Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I don't know if this can be done in linear time. It is straightforward to do it in O(n·log n) time if there are n triplets in the input. Here is a sketch of a method, in a not-necessarily-preferred form of implementation:</p> <ol> <li><p>Make an array of markers M, initially all clear. </p></li> <li><p>Create an array and make a copy of the input, sorted first on the middle element and then by the third element whenever middle elements are equal. (Time is O(n·log n) so far.)</p></li> <li><p>For each distinct middle value, make a BST (binary search tree) with key = third element. (Time is O(n·log n) again.)</p></li> <li><p>Make a hash table keyed by middle values, with data pointing at appropriate BST's. That is, given a middle value y and third element z, in time O(1) we can get to the BST for triplets whose middle value is y; and from that, in time O(log n) can find the triplet with third-element value closest to z.</p></li> <li><p>For each triplet t = (x,y,z) in turn, if marker is not yet set use the hash table to find the BST, if any, corresponding to x. In that BST, find the triplet u with third element closest to z. If difference is less than 10, set the markers for t and u. (Time is O(n·log n) again.)</p></li> <li><p>Repeat steps 2–5 but with BST's based on first element values rather than middle value, and lookups in step 5 based on y rather than x. (Although the matching-relations are symmetric, so that we can set two markers at each cycle in step 5, some qualifying triplets may end up not marked; ie, they are in tolerance but more distant than the nearest-match that is found. It would be possible to mark all of the qualifying triplets in step 5, but that would increase worst-case time from O(n·log n) to O(n²·log n).)</p></li> <li><p>For each marker that is set, output the corresponding triplet.</p></li> </ol> <p>Overall time: O(n·log n). The same time can be achieved without building BST's but instead using binary searches within subranges of the sorted arrays.</p> <p><em>Edit:</em> In python, one can build structures usable with <em><a href="http://docs.python.org/2/library/bisect.html" rel="nofollow">bisect</a></em> as illustrated below in excerpts from an ipython interpreter session. (There may be more efficient ways of doing these steps.) Each data item in dictionary <code>h</code> is an array suitable for searching with <code>bisect</code>.</p> <pre><code>In [1]: from itertools import groupby In [2]: a=[(0,1,10), (1,2,20), (2,3,25), (0,1,15), (1,4,40), (1,4,33), (3,3,17), (2,1,19)] In [3]: b=sorted((e[1],e[2],i) for i,e in enumerate(a)); print b [(1, 10, 0), (1, 15, 3), (1, 19, 7), (2, 20, 1), (3, 17, 6), (3, 25, 2), (4, 33, 5), (4, 40, 4)] In [4]: h={k:list(g) for k,g in groupby(b,lambda x: x[0])}; h Out[4]: {1: [(1, 10, 0), (1, 15, 3), (1, 19, 7)], 2: [(2, 20, 1)], 3: [(3, 17, 6), (3, 25, 2)], 4: [(4, 33, 5), (4, 40, 4)]} </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POHow to remove lines from a large file
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJames Waldby - jwpat7
    1. USJames Waldby - jwpat7
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow to remove lines from a large file
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks. Any idea how to do this in python? Maybe bisect and a sorted list could replace the BSTs?
      singulars
      1. PO
      1. USphoenix
    2. CO@phoenix, added example
      singulars
      1. PO
      1. USJames Waldby - jwpat7
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload