Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If you only need the top 10 values, then you'd waste a lot of time sorting every single number.</p> <p>Just go through the list of numbers and keep track of the top 10 largest values seen so far. Update the top ten as you go through the list, and print them out when you reach the end.</p> <p>This will mean you only need to make a single pass through the file (ie time complexity of theta(n))</p> <p><strong>A simpler problem</strong></p> <p>You can look at your problem as a generalization of finding the maximum value in a list of numbers. If you're given <code>{2,32,33,55,13, ...}</code> and are asked to find the largest value, what would you do? The typical solution is to go through the list, while remembering the largest number encountered so far and comparing it with the next number. </p> <p>For simplicity, let's assume we're dealing with positive numbers.</p> <pre><code>Initialize max to 0 0 &lt; 2, so max = 2 2 &lt; 32, so max = 32 32 &lt; 33, so max = 33 33 &lt; 55, so max = 55 55 &gt; 13, so max = 55 ... return max </code></pre> <p>So you see, we can find the max in a single traversal of the list, as opposed to any kind of comparison sort.</p> <p><strong>Generalizing</strong></p> <p>Finding the <strong>top 10</strong> values in a list is very similar. The only difference is that we need to keep track of the top 10 instead of just the max (top 1).</p> <p>The bottom line is that you need some container that holds 10 values. As you're iterating through your giant list of numbers, the only value you care about in your size-10-container is the minimum. That's because this is the number that would be replaced if you've discovered a new number that deserves to be in the top-10-so-far.</p> <p>Anyway it turns out that the data structure best fit for finding mins quickly is a min heap. But I'm not sure if you've learned about heaps yet, and the overhead of using a heap for 10 elements could possibly outweigh its benefits. </p> <p>Any container that holds 10 elements and can obtain the min in a reasonable amount of time would be a good start.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow can I sort 1 million numbers, and only print the top 10 in Python?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USpepsi
    1. USpepsi
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow can I sort 1 million numbers, and only print the top 10 in Python?
      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 does risk being 10x slower which may mean 10 milliseconds instead of 1 millisecond. but it could mean 10 seconds instead of 1 second.
      singulars
      1. PO
      1. USrobert king
    2. COif you want to the top K values, then this is O(KN) (depending on how you keep track of the top 10), check http://en.wikipedia.org/wiki/Selection_algorithm, something such as median of medians is O(N)
      singulars
      1. PO
      1. USrobert king
    3. CO@robertking : In the OP's problem, k is given as a constant 10, which is why I simplified it to theta(n). If we actually care about a generic algorithm for the top k values, we can use a heap of size k to track the top k values, reducing it to theta(n*lg(k)). This is likely what heapq does as well. But who knows, maybe the overhead of managing a heap is greater than the overhead of traversing a size 10 array. You'd have to profile it to find out.
      singulars
      1. PO
      1. USpepsi
 

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