Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>if I understand you correctly you need to find k highest numbers that can be produced by multiplying together 1, 2 or 3 elements from your list, and all the values are floating point numbers between 0 and 1.</p> <p>It is clear that you only need to consider the k highest numbers from the list. The rest can be discarded straight away. You can use your O(n log k) algorithm to get them, again in sorted order (I assume your list isn't preordered). To simplify the problem, you can now take their logarithms and try to maximize the sums of the numbers instead of the original problem of maximizing the products. This might speed up little.</p> <p>Now (considering the logarithmic presentation), all your numbers are negative, so adding more of them together will just create more and more negative numbers.</p> <p>Let's call the k highest numbers A1...Ak. We can reduce the problem further now assuming that there exists also number A0, that has the value 0 in the log representation and 1 in the original representation; then the problem is to enumerate the first k 3-tuples (x,y,z in {A0,...,Ak}) with the constraint that x &geq; y &geq; z and that z &lt; A0. Let's denote 3-tuple by [i,j,n] and the sum of the elements in this tuple by S[i,j,n]. The first element to be reported is obviously [0,0,1], i.e. , which corresponds in the original problem formulation to the singleton #1 value on the list.</p> <p>We use a max-heap as in the original formulation; we push the triples to the heap, using their sums (S[...]) as the ordering key. The algorithm starts by pushing [0,0,0] to the heap. Then:</p> <pre><code>answer = [] for m in 0 .. k: top = heap.pop() answer.append(sum(top)) (i,j,n) = top # explode the tuple if (n &lt; k - 1): heap.push((i,j,n+1)) if (j == n): heap.push((i,j+1,j+1)) if (i == j): heap.push((i+1,i+1,i+1)) </code></pre> <p>At the end, answer contains k + 1 elements, the first one of them is [0,0,0] which must be discarded.</p> <p>Let be given as -1, -3, -8, -9. Then the algorithm proceeds like this:</p> <pre><code>Heap Top Rest (shown in order) [ 0, 0, 0] | [ 0, 0,-1] | [ 0,-1,-1] [-1,-1,-1] [ 0,-1,-1] | [-1,-1,-1] [ 0,-1,-3] [ 0,-3,-3] [-1,-1,-1] | [-1,-1,-2] [ 0,-1,-3] [-1,-2,-2] [-2,-2,-2] [ 0,-3,-3] [-1,-1,-2] | [ 0,-1,-3] [-1,-1,-3] [-1,-2,-2] [-2,-2,-2] [ 0,-3,-3] [ 0,-1,-3] | [-1,-1,-3] [ 0,-1,-4] [-1,-2,-2] [-2,-2,-2] [ 0,-3,-3] [-1,-1,-3] | [ 0,-1,-4] [-1,-1,-4] [-1,-2,-2] [-2,-2,-2] [ 0,-3,-3] [ 0,-1,-4] | [-1,-2,-2] [-1,-1,-4] [ 0,-1,-5] [-2,-2,-2] [ 0,-3,-3] ... etc. </code></pre> <p>The nice thing about this algorithm is that it doesn't enumerate duplicates and the heap size is O(k); to see why, observe that the algorithm adds on every iteration the maximum of elements on the heap (often less), so after k iterations there cannot be more than 2k elements in the heap.</p> <p>This gives then running time O(n log k + k log k) = O((n + k) log k).</p>
    singulars
    1. This table or related slice is empty.
    1. POgenerate top k values
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAntti Huima
    1. USAntti Huima
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POgenerate top k values
      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. VTAcceptedByOriginator
    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. COwow..that was cool!
      singulars
      1. PO
      1. USuser352951
    2. COHmm there is likely a bug in the iteration algorithm ... It can be still linear time but the iteration order is not that simple because the might be ordered (a1,a1), (a1,a2), (a1,a3), (a2,a2), (a1,a4) --- I'll update the answer tomorrow
      singulars
      1. PO
      1. USAntti Huima
    3. COyes, was thinking the same..probably can't do without a heap but i like the log optimization
      singulars
      1. PO
      1. USuser352951
 

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