Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>First, your criterion for an unboxed data structure is probably a bit mislead. Unboxed values <em>must</em> be strict, and they have nothing to do with immutability. The solution I'm going to propose is immutable, lazy, and boxed. Also, I'm not sure in what way you are wanting construction and querying to be O(1). The structure I'm proposing is lazily constructed, but because it's potentially unbounded, its full construction would take infinite time. Querying the structure will take O(k) time for any particular key of size k, but of course the value you're looking up may take further time to compute.</p> <p>The data structure is a lazy trie. I'm using Conal Elliott's MemoTrie library in my code. For genericity, it takes functions instead of lists for the weights and values.</p> <pre><code>knapsack :: (Enum a, Num w, Num v, Num a, Ord w, Ord v, HasTrie a, HasTrie w) =&gt; (a -&gt; w) -&gt; (a -&gt; v) -&gt; a -&gt; w -&gt; v knapsack weight value = knapsackMem where knapsackMem = memo2 knapsack' knapsack' 0 w = 0 knapsack' i 0 = 0 knapsack' i w | weight i &gt; w = knapsackMem (pred i) w | otherwise = max (knapsackMem (pred i) w) (knapsackMem (pred i) (w - weight i)) + value i </code></pre> <p>Basically, it's implemented as a trie with a lazy spine and lazy values. It's bounded only by the key type. Because the entire thing is lazy, its construction before forcing it with queries is O(1). Each query forces a single path down the trie and its value, so it's <strike>O(1) for a bounded key size</strike> O(log n). As I already said, it's immutable, but not unboxed.</p> <p>It will share all work in the recursive calls. It doesn't actually allow you to print the trie directly, but something like this should not do any redundant work:</p> <pre><code>mapM_ (print . uncurry (knapsack ws vs)) $ range ((0,0), (i,w)) </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POEfficient table for Dynamic Programming in Haskell
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJake McArthur
    1. USJake McArthur
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POEfficient table for Dynamic Programming in Haskell
      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. COO(1) for bounded key size is cute, but its really O(log n), no? Which is better to note, since O(2^n) is also O(1) for bounded n :-)
      singulars
      1. PO
      1. USsclv
    2. COIf you want to be pedantic, it's O(k), for k being the size of the key. Since the keys in this case are probably machine ints or something, k is actually a constant, not merely bounded. Also, it's O(1) in the number of elements if you ignore the key size, which is how we normally measure containers. It's unfair to say that a trie is O(log n) when we also say a balanced tree is O(log n). If we considered the key size, the balanced tree would actually be O(k log n), and if we considered the k factor to be logarithmic in the number of elements as you suggest, a tree would be O(log n log n).
      singulars
      1. PO
      1. USJake McArthur
    3. COOk. My dander is up now :-). MemoTrie converts words/ints/integers to little-endian lists of bits. The bits function produces a list that is length O(log n). cf: http://codepad.org/BlRqzJKL. There are trie representations possible that aren't like this. The one Conal uses, for good reason (to handle, e.g., unbounded Integers), however *is* like this.
      singulars
      1. PO
      1. USsclv
 

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