Databases
StackOverflow2013
Postsdbo
POEfficient way of keeping numbers in order
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POEfficient way of keeping numbers in order
    text
    copied!<p>This is a problem that could apply to any language, but I'll use python to show it.</p> <p>Say you have a list of numbers, <code>ls = [0,100,200,300,400]</code></p> <p>You can insert an element at any index, but the elements must always stay in numerical order. Duplicates are not allowed.</p> <p>For example, <code>ls.insert(2, 150)</code> results in <code>ls = [0,100,150,200,300,400]</code>. The elements are in the correct order, so this is correct. </p> <p>However, <code>ls.insert(3, 190)</code> results in <code>ls = [0,100,200,190,300,400]</code>. This is incorrect.</p> <p><strong>For any index <code>i</code>, what is the best number <code>x</code> to use in <code>ls.insert(i,x)</code> to minimize the number of sorts?</strong></p> <p>My first intuition was to add half the difference between the previous and next numbers to the previous one. So to insert a number at index 3, <code>x</code> would equal 200 + (300-200), or 250. However this approaches the asymptote far too quickly. When the differences get too close to 0, I could restore the differences by looping through and changing each number to produce a larger difference. I want to choose the best number for <code>x</code> so to minimize the number of times I need to reset.</p> <p><strong>EDIT</strong></p> <p>The specific problem I'm applying this to is a iOS app with a list view. The items in the list are represented in a Set, and each object has an attribute orderingValue. I can't use an Array to represent the list (due to issues with cache-server syncing), so I have to sort the set each time I display the list to the user. In order to do this, the orderingValue must be stored on the ListItem object.</p> <p>One additional detail is, due to the nature of the UI, the user is probably more likely to add an item to the top or bottom of the list rather than insert it in the middle.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

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