Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If your problem demands that:</p> <ul> <li>you store your elements fully sorted in an actual C/C++ array, and</li> <li>you maintain your items in sorted order at all times,</li> </ul> <p>then you've painted yourself into a corner: your requirements spell "insertion sort".</p> <p>No matter what algorithm or auxiliary datastructure you choose, inserting a new element in the middle will require you to move the larger elements up by an index, and deleting any element (except the largest) will require you to move the larger elements down by an index. Since an insertion sort does exactly that, without any additional logic or datastructure, you might as well use it.</p> <p>The only exception is if your comparison is particularly expensive. If that is the case, then you can use a <a href="http://en.wikipedia.org/wiki/Binary_search_algorithm" rel="nofollow noreferrer">binary search</a> to find your insertion point (instead of comparing your new element against each old element as you move it). However, you will still need to move all elements larger than the mutation point, so you will never be able to improve your performance past O(N) (although a bulk data move should be pretty fast...).</p> <p>Also, you should evaluate your requirements: if you know that <code>N &lt; 256</code>, and the worst case of inserting an object in position <code>0</code> is fast enough for your application, you should stop there. There's no point in making things more complicated than necessary, to save time you don't need.</p> <hr> <p>On the other hand, if:</p> <ul> <li>you don't actually need to keep all elements fully sorted at all times, and</li> <li>what you <em>do</em> actually need is to repeatedly find and remove the largest/smallest element in the array</li> </ul> <p>then what you need is called a <a href="http://en.wikipedia.org/wiki/Priority_queue" rel="nofollow noreferrer">priority queue</a>, and you can implement it (in memory-efficient, in-place fashion) by using an <a href="http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node5.html" rel="nofollow noreferrer">implicit heap</a>. Implicit heap operations are O(log N), and typically have a good performance factor; even for <code>N = 255</code>, this can make a big difference in worst-case performance.</p>
    singulars
    1. This table or related slice is empty.
    1. POSorted insertion into small (255 element) list
      singulars
      1. PTQuestion
    1. PTAnswer
    1. UScomingstorm
    1. UScomingstorm
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POSorted insertion into small (255 element) list
      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. CO@commingstorm: I highly appreciate your mentioning of an implicit heap. That is exactly the *kind* of suggestions I was looking for - even though evaluation of the hint may or may not be the final solution.
      singulars
      1. PO
      1. USArne
    2. COInvestigating the implicit heap, I bet it has been mentioned before but without the explicit naming. Kudos to who-ever it was!
      singulars
      1. PO
      1. USArne
 

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