Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If there were a way to generate all combinations in O(1), you could do this in O(r) just by generating and filtering. Assuming <code>itertools.combinations</code> has an O(1) <code>next</code>, there are at most r-1 values to skip over, so the worst case is r-1 times O(1), right?</p> <p>Jumping ahead a bit to avoid confusion, I don't think there is an O(1) implementation of <code>combinations</code>, and therefore this is <em>not</em> O(r). But is there anything possible that <em>is</em>? I'm not sure. Anyway…</p> <p>So:</p> <pre><code>def nonconsecutive_combinations(p, r): def good(combo): return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1)) return filter(good, itertools.combinations(p, r)) r, n = 2, 4 print(list(nonconsecutive_combinations(range(1, n+1), r)) </code></pre> <p>This prints:</p> <pre><code>[(1, 3), (1, 4), (2, 4)] </code></pre> <hr> <p>The <code>itertools</code> documentation doesn't guarantee that <code>combinations</code> has an O(1) <code>next</code>. But it seems to me that if there is a possible O(1) algorithm, they'd use it, and if there isn't, you're not going to find one.</p> <p>You can read <a href="http://hg.python.org/cpython/file/3.3/Modules/itertoolsmodule.c#l2289" rel="nofollow">the source code</a>, or we could time it… but we're going to do that, let's time the whole thing.</p> <p><a href="http://pastebin.com/ydk1TMbD" rel="nofollow">http://pastebin.com/ydk1TMbD</a> has my code, and thkang's code, and a test driver. The times it's printing are the cost of iterating the entire sequence, divided by the length of the sequence.</p> <p>With <code>n</code> ranging from 4 to 20 and <code>r</code> fixed at 2, we can see that the times for both go down. (Remember, the <em>total</em> time to iterate the sequence is of course going up. It's just sublinear in <code>the total length</code>) With <code>n</code> ranging from 7 to 20 and <code>r</code> fixed at 4, the same is true.</p> <p>With <code>n</code> fixed at 12 and <code>r</code> ranging from 2 to 5, the times for both go up linearly from 2 through 5, but they're much higher for 1 and 6 than you'd expect.</p> <p>On reflection, that makes sense—there are only 6 good values out of 924, right? And that's why the time per <code>next</code> was going down as <code>n</code> went up. The total time is going up, but the number of values yielded is going up even faster.</p> <p>So, <code>combinations</code> doesn't have an O(1) <code>next</code>; what it does have is something complicated. And my algorithm does not have an O(r) <code>next</code>; it's also something complicated. I think the performance guarantees would be a lot easier to specify over the whole iteration than per <code>next</code> (and then it's easy to divide by the number of values if you know how to calculate that).</p> <p>At any rate, the performance characteristics are exactly the same for the two algorithms I tested. (Oddly, switching the wrapper <code>return</code> to <code>yield from</code> made the recursive one faster and the filtering one slower… but it's a small constant factor anyway, so who cares?)</p>
    singulars
    1. This table or related slice is empty.
    1. POGenerating non-consecutive combinations
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USabarnert
    1. USabarnert
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    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
    1. COThanks, I need to try it out and think more about your claim. Actually now that I see your good, it is potentially Omega(r^2) (and so Omega(n^2)) even if underlying generator is O(1), isn't it? Still, more thought(from me) is required.
      singulars
      1. PO
      1. USKnoothe
    2. CO@Knoothe: Would it help if I used `timeit` to demonstrate how the time grows with n and with r?
      singulars
      1. PO
      1. USabarnert
    3. COI will try it out on my workloads, but I do need this to be as fast as I can make it. My current solution is based on the filtering, and that does not seem sufficient, based on the perf measurements I have done.
      singulars
      1. PO
      1. USKnoothe
 

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