Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You could use a heap for this, but I think it would be overkill. It sounds like you're not going to have a lot of different values for the counts, and you'll have a lot of objects with each count. If that's true, then you only need thread the objects onto a list of objects with the same count. These lists are themselves arranged in a dequeue (or 'deque' as C++ insists on calling it).</p> <p>The key here is that you need to increment the count of all objects, and presumably you want that to be O(1) if possible, rather than O(N). And it is possible: the key is that each list's header contains also the difference of its count from the next smaller count. The header of the list with the smallest count contains a delta from 0, which is the smallest count. To increment the count of all objects, you only have to increase this single number by one.</p> <p>To set an object's count to 0, you remove the object from its list (which means you always need to refer to objects by their list iterator, or you need to implement your own intrusive linked list), and either (1) add it to the bottom list, if that list has a count of 0, or (2) create a new bottom list with a count of 0 containing only that object.</p> <p>The procedure for creating a new object is the same, except that you don't have to unlink it from its current list.</p> <p>To evict an object from memory, you choose the object at the head of the top list (which is the list with the largest count). If that list becomes empty, you pop it off the dequeue. If you need more memory, you can repeat this operation.</p> <p>So all operations, including "increment all counts", are O(1). Unfortunately, the storage overhead is two pointers per object, plus two pointers and an integer per unique count (at worst, this is the same as the number of objects, but presumably in practice it's much less). Since it's hard to imagine any other algorithm which uses less than one pointer plus a count for each object, this is probably not even a space-time tradeoff; the additional space requirements are minimal.</p>
    singulars
    1. This table or related slice is empty.
    1. PODetermining the best ADT for a priority queue with changeable elements (C++)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USrici
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PODetermining the best ADT for a priority queue with changeable elements (C++)
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COI'd upvote you but I cant yet ! What do you think of the method outlined here: http://stackoverflow.com/questions/2504178/lru-cache-design (took me some time to find it)
      singulars
      1. PO
      1. USLamar Latrell
    2. COThat method is the stripped-down version of my algorithm; the main difference is that it doesn't let you know how old the objects are (but maybe you don't care about that), and it's more precise. I've used my algorithm in a context where I was prepared to grow (or shrink) the cache based on demand, and where I wanted to automatically drop objects if they were too old, even if there was room to keep them. I prefer intrusive lists to hash tables, but tastes (and requirements) vary.
      singulars
      1. PO
      1. USrici
    3. COI dont need to know how old they are in absolute terms, only relative. It would be nice to be able to grow and shrink the cache eventually, but I'm not yet read up on how to query an OS for memory information, or indeed let it 'tell' my cache it's size. Bigger issues to tackle first. 'Intrusive-lists'>> ok, googling!
      singulars
      1. PO
      1. USLamar Latrell
 

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