immutabe.Seq with constant time append

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

immutabe.Seq with constant time append

mikael.staldal
I am looking for an implementation of scala.collection.immutabe.Seq with constant time append operation.

List is not sufficient since its append is linear time.

Should I use Vector, or is there any other alternative? Vector seems a bit overkill for my use case. I don't need an IndexedSeq, I am only reading the elements in sequence (using foreach() or iterator()).

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: immutabe.Seq with constant time append

Alexandru Nedelcu-4
You can also use `Queue`, which has constant time append (`enqueue`) and amortized constant time`dequeue`. It's OK most of the time, unless you need indexing.

So if you want some sort of immutable buffer `Queue` is often better in terms of performance than `Vector`.

--
Alexandru Nedelcu
alexn.org



On Mon, Dec 5, 2016, at 11:12, [hidden email] wrote:
I am looking for an implementation of scala.collection.immutabe.Seq with constant time append operation.

List is not sufficient since its append is linear time.

Should I use Vector, or is there any other alternative? Vector seems a bit overkill for my use case. I don't need an IndexedSeq, I am only reading the elements in sequence (using foreach() or iterator()).


--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Aw: [scala-user] immutabe.Seq with constant time append

Dennis Haupt-2
In reply to this post by mikael.staldal
can't you use list and then just iterator over it in reverse order?
 
Gesendet: Montag, 05. Dezember 2016 um 10:12 Uhr
Von: [hidden email]
An: scala-user <[hidden email]>
Betreff: [scala-user] immutabe.Seq with constant time append
I am looking for an implementation of scala.collection.immutabe.Seq with constant time append operation.

List is not sufficient since its append is linear time.

Should I use Vector, or is there any other alternative? Vector seems a bit overkill for my use case. I don't need an IndexedSeq, I am only reading the elements in sequence (using foreach() or iterator()).
 

 

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: immutabe.Seq with constant time append

mikael.staldal
Isn't reverse iteration over a List quite inefficient?

On Monday, December 5, 2016 at 12:08:46 PM UTC+1, Dennis Haupt wrote:
can't you use list and then just iterator over it in reverse order?
 
Gesendet: Montag, 05. Dezember 2016 um 10:12 Uhr
Von: <a href="javascript:" target="_blank" gdf-obfuscated-mailto="p-YCr9vdBAAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">mikael....@...
An: scala-user <<a href="javascript:" target="_blank" gdf-obfuscated-mailto="p-YCr9vdBAAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">scala...@...>
Betreff: [scala-user] immutabe.Seq with constant time append
I am looking for an implementation of scala.collection.immutabe.Seq with constant time append operation.

List is not sufficient since its append is linear time.

Should I use Vector, or is there any other alternative? Vector seems a bit overkill for my use case. I don't need an IndexedSeq, I am only reading the elements in sequence (using foreach() or iterator()).
 

 

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="javascript:" target="_blank" gdf-obfuscated-mailto="p-YCr9vdBAAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">scala-user+...@googlegroups.com.
For more options, visit <a href="https://groups.google.com/d/optout" target="_blank" rel="nofollow" onmousedown="this.href=&#39;https://groups.google.com/d/optout&#39;;return true;" onclick="this.href=&#39;https://groups.google.com/d/optout&#39;;return true;">https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: immutabe.Seq with constant time append

Jasper-M
I think the reverse iterator first reverses the list and then returns a normal iterator over that reversed list. So that is more or less ~2n complexity (but not O(n²) as a naive solution would be), which is probably the best you're going to get.

Op woensdag 7 december 2016 14:48:13 UTC+1 schreef [hidden email]:
Isn't reverse iteration over a List quite inefficient?

On Monday, December 5, 2016 at 12:08:46 PM UTC+1, Dennis Haupt wrote:
can't you use list and then just iterator over it in reverse order?
 
Gesendet: Montag, 05. Dezember 2016 um 10:12 Uhr
Von: [hidden email]
An: scala-user <[hidden email]>
Betreff: [scala-user] immutabe.Seq with constant time append
I am looking for an implementation of scala.collection.immutabe.Seq with constant time append operation.

List is not sufficient since its append is linear time.

Should I use Vector, or is there any other alternative? Vector seems a bit overkill for my use case. I don't need an IndexedSeq, I am only reading the elements in sequence (using foreach() or iterator()).
 

 

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit <a href="https://groups.google.com/d/optout" rel="nofollow" target="_blank" onmousedown="this.href=&#39;https://groups.google.com/d/optout&#39;;return true;" onclick="this.href=&#39;https://groups.google.com/d/optout&#39;;return true;">https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: immutabe.Seq with constant time append

杨 Yang博 Bo
In reply to this post by Dennis Haupt-2
A Queue is simply a combination of a List and a reversed List

在 2016年12月5日星期一 UTC+8下午7:08:46,Dennis Haupt写道:
can't you use list and then just iterator over it in reverse order?
 
Gesendet: Montag, 05. Dezember 2016 um 10:12 Uhr
Von: <a href="javascript:" target="_blank" gdf-obfuscated-mailto="p-YCr9vdBAAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">mikael....@...
An: scala-user <<a href="javascript:" target="_blank" gdf-obfuscated-mailto="p-YCr9vdBAAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">scala...@...>
Betreff: [scala-user] immutabe.Seq with constant time append
I am looking for an implementation of scala.collection.immutabe.Seq with constant time append operation.

List is not sufficient since its append is linear time.

Should I use Vector, or is there any other alternative? Vector seems a bit overkill for my use case. I don't need an IndexedSeq, I am only reading the elements in sequence (using foreach() or iterator()).
 

 

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="javascript:" target="_blank" gdf-obfuscated-mailto="p-YCr9vdBAAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">scala-user+...@googlegroups.com.
For more options, visit <a href="https://groups.google.com/d/optout" target="_blank" rel="nofollow" onmousedown="this.href=&#39;https://groups.google.com/d/optout&#39;;return true;" onclick="this.href=&#39;https://groups.google.com/d/optout&#39;;return true;">https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: immutabe.Seq with constant time append

Odd Möller
Perhaps https://github.com/Sciss/FingerTree would fit the bill?

On Mon, Jan 2, 2017 at 6:59 AM, 杨博 <[hidden email]> wrote:
A Queue is simply a combination of a List and a reversed List

在 2016年12月5日星期一 UTC+8下午7:08:46,Dennis Haupt写道:
can't you use list and then just iterator over it in reverse order?
 
Gesendet: Montag, 05. Dezember 2016 um 10:12 Uhr
Von: [hidden email]
An: scala-user <[hidden email]>
Betreff: [scala-user] immutabe.Seq with constant time append
I am looking for an implementation of scala.collection.immutabe.Seq with constant time append operation.

List is not sufficient since its append is linear time.

Should I use Vector, or is there any other alternative? Vector seems a bit overkill for my use case. I don't need an IndexedSeq, I am only reading the elements in sequence (using foreach() or iterator()).
 

 

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: immutabe.Seq with constant time append

Sannah Ziama
In reply to this post by mikael.staldal
Not exactly what you want but close: prepend to an immutable list and then reverse it in the end. 

On Monday, December 5, 2016 at 1:12:25 AM UTC-8, [hidden email] wrote:
I am looking for an implementation of scala.collection.immutabe.Seq with constant time append operation.

List is not sufficient since its append is linear time.

Should I use Vector, or is there any other alternative? Vector seems a bit overkill for my use case. I don't need an IndexedSeq, I am only reading the elements in sequence (using foreach() or iterator()).

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Loading...