Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><strong>Method 1</strong></p> <p>Since k is small, you can use the tournament method to find the kth largest. This method is described in Knuth's Art of Programming, Volume 3, Page 212.</p> <p>First create a tournament on n-k+2 elements. Something like a knockout tennis tournament. First you split into pairs and compare the members of the pairs (as if those two played a match and one lost). Then the winners, you split in to pairs again and so on, till you have a winner. You can view it as a tree, with the winner at the top.</p> <p>This takes n-k+1 compares exactly.</p> <p>Now the winner of these n-k+2 cannot be your kth largest element. Consider its path P up the tournament.</p> <p>Of the remaining k-2 now pick one, and follow that up the path P which will give you a new largest. Basically you sort of redo the tournament with the previous winner being replaced by one of the k-2 elements. Let P be the path of the new winner. Now pick another from the k-3 and follow the new path up and so on.</p> <p>At the end after you exhaust the k-2, replace the largest with -infinity and the largest of the tournament will be the kth largest. The elements you have thrown away are the top k-1 elements.</p> <p>This takes at most <code>n - k + (k-1) [log (n-k+2)]</code> comparisons to find the top k. It uses O(n) memory though. </p> <p>In terms of number of compares this should likely beat any selection algorithms.</p> <p><strong>Method 2</strong></p> <p>As an alternative, you can maintain a min-heap of k elements.</p> <p>First insert k elements. Then for each element of array, if it is less than the min element of the heap, throw it away. Otherwise, delete-min of the heap and insert the element from the array.</p> <p>At the end, the heap will contain the top k elements. This will take <code>O(n log k)</code> compares.</p> <p>Of course, if n is small, just sorting the array should be good enough. The code will be simpler too.</p>
    singulars
    1. This table or related slice is empty.
    1. POOptimal algorithm for returning top k values from an array of length N
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POOptimal algorithm for returning top k values from an array of length N
      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. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHuh? -> Now the winner of these n-k+2 cannot be your largest element
      singulars
      1. PO
      1. USP i
    2. CO@Ohmu: Typo. Kth largest... Corrected.
      singulars
      1. PO
      1. This table or related slice is empty.
    3. COHas anyone got some code for this? It is time I got a hold of Knuth's book...
      singulars
      1. PO
      1. USP i
 

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