Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The definition of big-O notation is that its argument is a function (<em>f(x)</em>) that, as the variable in the function (<em>x</em>) tends to infinity, there exists a constant <em>K</em> such that the objective cost function will be smaller than <em>Kf(x)</em>. Typically <em>f</em> is chosen to be the smallest such simple function such that the condition is satisfied. (It's pretty obvious how to lift the above to multiple variables.)</p> <p>This matters because that <em>K</em> — which you aren't required to specify — allows a whole multitude of complex behavior to be hidden out of sight. For example, if the core of the algorithm is O(n<sup>2</sup>), it allows all sorts of other O(1), O(logn), O(n), O(nlogn), O(n<sup>3/2</sup>), etc. supporting bits to be hidden, <em>even if for realistic input data those parts are what actually dominate.</em> That's right, it can be completely misleading! (Some of the fancier bignum algorithms have this property for real. Lying with mathematics is a wonderful thing.)</p> <p>So where is this going? Well, you can assume that <code>int</code> is a fixed size easily enough (e.g., 32-bit) and use that information to skip a lot of trouble and allocate <em>fixed size</em> arrays of flag bits to hold all the information that you really need. Indeed, by using two bits per potential value (one bit to say whether you've seen the value at all, another to say whether you've printed it) then you can handle the code with fixed chunk of memory of 1GB in size. That will then give you enough flag information to cope with as many 32-bit integers as you might <em>ever</em> wish to handle. (Heck that's even practical on 64-bit machines.) Yes, it's going to take some time to set that memory block up, but it's constant so it's formally O(1) and so drops out of the analysis. Given that, you then have constant (but whopping) memory consumption and linear time (you've got to look at each value to see whether it's new, seen once, etc.) which is exactly what was asked for.</p> <p>It's a dirty trick though. You could also try scanning the input list to work out the range allowing less memory to be used in the normal case; again, that adds only linear time and you can strictly bound the memory required as above so that's constant. Yet more trickiness, but formally legal.</p> <hr> <p>[EDIT] Sample <em>C</em> code (this is not C++, but I'm not good at C++; the main difference would be in how the flag arrays are allocated and managed):</p> <pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; // Bit fiddling magic int is(int *ary, unsigned int value) { return ary[value&gt;&gt;5] &amp; (1&lt;&lt;(value&amp;31)); } void set(int *ary, unsigned int value) { ary[value&gt;&gt;5] |= 1&lt;&lt;(value&amp;31); } // Main loop void print_repeats(int a[], unsigned size) { int *seen, *done; unsigned i; seen = calloc(134217728, sizeof(int)); done = calloc(134217728, sizeof(int)); for (i=0; i&lt;size; i++) { if (is(done, (unsigned) a[i])) continue; if (is(seen, (unsigned) a[i])) { set(done, (unsigned) a[i]); printf("%d ", a[i]); } else set(seen, (unsigned) a[i]); } printf("\n"); free(done); free(seen); } void main() { int a[] = {1,0,-2,4,4,1,3,1,-2}; print_repeats(a,sizeof(a)/sizeof(int)); } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POFinding repeating signed integers with O(n) in time and O(1) in space
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDonal Fellows
    1. USDonal Fellows
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFinding repeating signed integers with O(n) in time and O(1) in space
      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. COThis is all far easier than pre-calculating the first 4 billion primes…
      singulars
      1. PO
      1. USDonal Fellows
    2. COI had to give your answer an up vote. Can you implement your idea in a C++ function now? That's what the problem asks for.
      singulars
      1. PO
      1. USApshir
    3. COThe magic constant, `134217728`, should be instantly recognizable as 128M. (Thank goodness for `dc`…)
      singulars
      1. PO
      1. USDonal Fellows
 

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