Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><strong>Without any further assumption on the operations you are going to do</strong>, you can't achieve better performance than with a <code>PriorityQueue</code> or another O(log(n))-insert collection (TreeSet , for example, but you lose the O(1)-peek). As you correctly assumed <code>Collections.min(Collection, Comparator)</code> is a linear operation.</p> <p><strong>But</strong> it depends on how often you need to change the ordering: for example if you only need to change it once in a while and still keep a "standard" ordering, <code>min()</code> is a viable option, but if you need to switch ordering completely then you will probably be better off with reordering the queue/set (that is, traversing and adding all the elements in a new one), tough at a O(nlog(n)) cost. Using <code>Collections.sort(List, Comparator)</code> may be effective if you need a lot of reordering compared to inserts, but requires you to use a <code>List</code>.</p> <p>Of course if you can make somewhat strong assumptions on the types of sorting you will need (for example, if it can be restricted to a part of the data) you could write your own collection.</p> <p><strong>Edit:</strong> So you have a (more or less) finite number of orderings (never mind that it's the same type of comparison over different fields, it's different Comparators and that's what matters)? If that's the case, you can probably achieve best performance by using m queues that reference the same objects, each using a different comparator (the simplest method, really). This way you have:</p> <ul> <li>constant time access</li> <li>O(m*logn(n)) inserts (to insert in every queue)</li> <li>O(m*n) removals (to remove from every queue)</li> <li>no ordering costs (as it's handled by the inserts)</li> <li>slightly larger memory cost (probably negligible)</li> <li>additional O(n*log(n)) cost the first time a particolar ordering is requested</li> </ul> <p>Supposing a value of m orders of magnitude smaller than n, this is comparable to optimal (single-ordering PriorityQueue) performance. For convenience, you can wrap this into a custom collection that takes a Comparator parameter on retrieval operations, and use it as a key for an HashMap of all the PriorityQueues.</p> <p><strong>Edit #2:</strong> In that case, there is no better solution than running min() on every retrieval (unless you can make assumptions on the changes of the data); this also means that it's better to just use an ArrayList as the collection, since it has basically the lowest possible cost on every operation and you will not benefit from PriorityQueue's natural ordering anyway. You will end up with linear cost on retrieval (for min) and constant on insertion and deletion: this is optimal as there is no sorting algorithm that has less than Ω(n) and Θ(nlog n) anyway.</p> <p>As a side note, ordered collections work on the assumption that values will not change after insertion; this is because there is no cost-effective way to monitor the changes nor to reorder them "in place".</p>
    singulars
    1. This table or related slice is empty.
    1. PORetrieve Least Element, Elements are Dynamically-Ordered
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USViruzzo
    1. USViruzzo
    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. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI'm not really looking for better performance than PriorityQueue, _if_ PriorityQueue will work given a dynamic ordering. Your second paragraph is a little hard to follow. Could you summarise in light of edits 1&2? Thanks
      singulars
      1. PO
      1. USAaron J Lang
    2. CO@AaronJLang see edit
      singulars
      1. PO
      1. USViruzzo
    3. COYour solution is ingenious, but I still don't think I've explained myself properly. The comparator is singular and constant. It assesses the same fields every time. However, the values in those fields (ie the state of the elements) change over time.
      singulars
      1. PO
      1. USAaron J Lang
 

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