Databases
StackOverflow2013
Postsdbo
PONeat way of computing functions on key-value pairs
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PONeat way of computing functions on key-value pairs
    primarykey
    data
    text
    <p>Suppose you have a have list with key - value pairs. Neither keys, nor values, nor the pair are required to be unique.</p> <p>The following example</p> <pre><code>a -&gt; 1 b -&gt; 2 c -&gt; 3 a -&gt; 3 b -&gt; 1 </code></pre> <p>would be valid.</p> <p>Now suppose I want to associate to any key value pair (k->v) another value V, which has the following properties:</p> <ul> <li>it is the same for two pairs, if their keys are identical</li> <li>it is uniquely determined by the set of key-value pairs in the entire list</li> </ul> <p>This sounds abstract, but for example the sum, the maximum and counting function qualify as examples</p> <pre><code> Pair SUM MAX COUNT a -&gt; 1 4 3 2 b -&gt; 2 3 2 2 c -&gt; 3 3 3 1 a -&gt; 3 4 3 2 b -&gt; 1 3 2 2 </code></pre> <p>I am looking for a fast methods/data structures to compute such functions on the entire list.</p> <p>If the keys can be sorted, one can simply sort the list, then iterate through the sorted list, and compute the function V in each block with identical keys.</p> <p>I am asking whether there are nice methods to do this, if the values are not comparable or one does not want to change the order of the entries.</p> <p>Some thoughts:</p> <ol> <li>Of course, one could apply a hash function to the keys, in order to obtain sortable keys.</li> <li>Of course, one could also store the original position of each pair, then do the sorting, then compute the function, and finally undo the sorting.</li> </ol> <p>So essentially the question is already answered. However, I am interested in whether there are more elegant solutions maybe using some adapt data structure</p> <p>EDIT: To clarify Sunny Agrawal comment, what I mean by associate. Well this is also part of the question on how to nicely arrange the data structure. In my example, I would get another list/map with (k->v) as key and V as value. However, it might make sense to not arrange the data that way. I require, that V is stored in such a way that for given k it needs constant time to obtain V.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USwood
    1. USwood
    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
    1. VO
      singulars
      1. PONeat way of computing functions on key-value pairs
      1. This table or related slice is empty.
      1. VTDownMod
    1. CO..in which language?
      singulars
      1. PONeat way of computing functions on key-value pairs
      1. USChris Mantle
    2. COwhat do you mean by associate with the key value pairs ? one solution is to maintain a another DS is parallel which is a map containing the key as original Data and value is a structure of Min, Max, Count, Sum, Avg etc and you update the structure for each key as you add
      singulars
      1. PONeat way of computing functions on key-value pairs
      1. USSunny Agrawal
    3. COIt is not about language, but about the structure. So be it java or c++, or c#. The answer should not depend on that
      singulars
      1. PONeat way of computing functions on key-value pairs
      1. USwood
 

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