Databases
StackOverflow2013
Postsdbo
POHow can I ensure amortized O(n) concatenation from Data.Vector?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow can I ensure amortized O(n) concatenation from Data.Vector?
    primarykey
    data
    text
    <p>I have an application where it is efficient to use Vectors for one part of the code. However, during the computation I need to keep track of some of the elements. I have heard that you can get O(n) amortized concatenation from Data.Vectors (by the usual array growing trick) but I think that I am not doing it right. So lets say we have the following setup:</p> <pre><code>import Data.Vector((++),Vector) import Prelude hiding ((++)) import Control.Monad.State.Strict data App = S (Vector Int) add :: Vector Int -&gt; State App () add v1 = modify (\S v2 -&gt; S (v2 ++ v1)) </code></pre> <p>Does <code>add</code> run in amortized O(n) time in this case? If not, how can I make <code>add</code> do that (do I need to store an <code>(forall s. MVector s Int)</code> in the State?). Is there a more efficient way of implementing <code>add</code>?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USHaskellElephant
    1. USHaskellElephant
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow can I ensure amortized O(n) concatenation from Data.Vector?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow can I ensure amortized O(n) concatenation from Data.Vector?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow can I ensure amortized O(n) concatenation from Data.Vector?
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO@hvr: No that is not what I want. I am pretty sure I am not doing it correctly in my question. However, I don't know the Data.Vector library that well and although the documentation `(++)` only states that it is *O(m+n)* worst case, it might still have *O(n)* amortized runtime.
      singulars
      1. POHow can I ensure amortized O(n) concatenation from Data.Vector?
      1. USHaskellElephant
    2. COSo I hate it when people on StackOverflow answer questions with questions, but I'm about to do it :P - Why do you think you're doing it "wrong"? I assume you're using `State` for some reason unrelated to this question, so if you strip the `State`-related stuff away it's clear you're not doing anything crazy: <!-- language: lang-hs --> add :: Vector Int -> Vector Int -> Vector Int add v1 v2 = v1 ++ v2 - You noticed the docs say it runs in *O(n + m)* time; what led you to believe it should run faster?
      singulars
      1. POHow can I ensure amortized O(n) concatenation from Data.Vector?
      1. USmergeconflict
    3. COWrong might be too strong, I just wanted to say that I realize that add might end up being `O(n^2)* worst case. Also note that although something might run in *O(n+m)* worst case, it might run in *O(n)* amortized, the reason why I thought that could be achieved is that MVector can grow, (http://hackage.haskell.org/packages/archive/vector/0.9/doc/html/Data-Vector-Storable-Mutable.html#g:8), and the think I heard it somewhere. The reason I included State, and I know it is unclear, is that it is what I am doing in my application and it is not totally unrelated since I might store some other type.
      singulars
      1. POHow can I ensure amortized O(n) concatenation from Data.Vector?
      1. USHaskellElephant
 

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