Databases
StackOverflow2013
Postsdbo
POfastest way to get n lowest from array
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POfastest way to get n lowest from array
    primarykey
    data
    text
    <p>I need to find n lowest (which are not 0) from array of doubles (let's call the array <em>samples</em>). I need to do this many times in a loop, thus the speed of execution is crucial. I tried first sorting the array and then taking the first 10 values (which are not 0), however, although Array.Sort is said to be fast, it became the bottleneck:</p> <pre><code>const int numLowestSamples = 10; double[] samples; double[] lowestSamples = new double[numLowestSamples]; for (int count = 0; count &lt; iterations; count++) // iterations typically around 2600000 { samples = whatever; Array.Sort(samples); lowestSamples = samples.SkipWhile(x =&gt; x == 0).Take(numLowestSamples).ToArray(); } </code></pre> <p>Thus I tried a different, but less clean solution, by first reading in the first n values, sorting them, then looping through all other values in <em>samples</em> checking if the value is smaller than the last value in the sorted <em>lowestSamples</em> array. If the value is lower then replace it with the one in the array and sort the array again. This turned out to be approximately 5 times faster:</p> <pre><code>const int numLowestSamples = 10; double[] samples; List&lt;double&gt; lowestSamples = new List&lt;double&gt;(); for (int count = 0; count &lt; iterations; count++) // iterations typically around 2600000 { samples = whatever; lowestSamples.Clear(); // Read first n values int i = 0; do { if (samples[i] &gt; 0) lowestSamples.Add(samples[i]); i++; } while (lowestSamples.Count &lt; numLowestSamples) // Sort the array lowestSamples.Sort(); for (int j = numLowestSamples; j &lt; samples.Count; j++) // samples.Count is typically 3600 { // if value is larger than 0, but lower than last/highest value in lowestSamples // write value to array (replacing the last/highest value), then sort array so // last value in array still is the highest if (samples[j] &gt; 0 &amp;&amp; samples[j] &lt; lowestSamples[numLowestSamples - 1]) { lowestSamples[numLowestSamples - 1] = samples[j]; lowestSamples.Sort(); } } } </code></pre> <p>Although this works relatively fast, I wanted to challenge anyone to come up with an even faster and better solution.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USRoger Saele
    1. USRoger Saele
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POfastest way to get n lowest from array
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POfastest way to get n lowest from array
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POfastest way to get n lowest from array
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI wonder if maintaining a min-heap is a good solution here.
      singulars
      1. POfastest way to get n lowest from array
      1. USChaosPandion
    2. COChaosPandion: Beat me by 5 seconds ;)
      singulars
      1. POfastest way to get n lowest from array
      1. USrobbrit
    3. COIf this is something that is called once is the performace gain worth the extra work / complexity (in terms of code maintainability)?
      singulars
      1. POfastest way to get n lowest from array
      1. USJake1164
 

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