[#5322] O(1) performance for insertions/deletions at the front of an Array/String — Eric Mahurin <eric_mahurin@...>
I just did some benchmarks on push, pop, shift, and unshift
24 messages
2005/07/01
[#5338] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Mathieu Bouchard <matju@...>
2005/07/02
On Fri, 1 Jul 2005, Eric Mahurin wrote:
[#5348] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Eric Mahurin <eric_mahurin@...>
2005/07/02
--- Mathieu Bouchard <matju@artengine.ca> wrote:
[#5357] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Mathieu Bouchard <matju@...>
2005/07/03
On Sat, 2 Jul 2005, Eric Mahurin wrote:
[#5359] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Eric Mahurin <eric_mahurin@...>
2005/07/03
--- Mathieu Bouchard <matju@artengine.ca> wrote:
[#5361] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Mathieu Bouchard <matju@...>
2005/07/03
On Sun, 3 Jul 2005, Eric Mahurin wrote:
[#5362] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Eric Mahurin <eric_mahurin@...>
2005/07/03
--- Mathieu Bouchard <matju@artengine.ca> wrote:
[#5365] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Yukihiro Matsumoto <matz@...>
2005/07/04
Hi,
[#5367] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Eric Mahurin <eric_mahurin@...>
2005/07/04
--- Yukihiro Matsumoto <matz@ruby-lang.org> wrote:
[#5368] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Yukihiro Matsumoto <matz@...>
2005/07/04
Hi,
[#5372] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Florian Gro<florgro@...>
2005/07/04
Yukihiro Matsumoto wrote:
[#5375] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Eric Mahurin <eric_mahurin@...>
2005/07/04
--- Florian Gro<florgro@gmail.com> wrote:
[#5379] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Nikolai Weibull <mailing-lists.ruby-core@...>
2005/07/04
Eric Mahurin wrote:
[#5380] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Eric Mahurin <eric_mahurin@...>
2005/07/04
--- Nikolai Weibull
[#5381] Re: O(1) performance for insertions/deletions at the front of an Array/String
— Nikolai Weibull <mailing-lists.ruby-core@...>
2005/07/04
Eric Mahurin wrote:
[#5388] Problem with socket communications on Windows — "Jim McMaster" <jim.mcmaster@...>
I recently installed PGP 9.0 on my Windows XP SP2 machine. At that point,
5 messages
2005/07/05
[#5391] Object#=~ — Ryan Davis <ryand-ruby@...>
Since Rexexp#=~ and String#=~ return nil if they fail to match,
12 messages
2005/07/06
[#5396] Re: Object#=~
— Yukihiro Matsumoto <matz@...>
2005/07/06
Hi,
[#5397] Re: Object#=~
— "daz" <dooby@...10.karoo.co.uk>
2005/07/06
[#5401] Re: Object#=~
— Yukihiro Matsumoto <matz@...>
2005/07/06
Hi,
[#5402] Re: Object#=~
— Eric Mahurin <eric_mahurin@...>
2005/07/06
--- Yukihiro Matsumoto <matz@ruby-lang.org> wrote:
[#5409] socket.c - s_recvfrom — Zach Dennis <zdennis@...>
If I am reading s_recvfrom correctly in can throw an error which kills
4 messages
2005/07/07
[#5420] Sydney Developer Preview 1 released — Evan Webb <evanwebb@...>
Sydney, an experimental ruby interpreter, has been released!
15 messages
2005/07/11
[#5424] Re: [ANN] Sydney Developer Preview 1 released
— Evan Webb <evanwebb@...>
2005/07/12
Thanks everyone for the feedback so far!
[#5425] Re: [ANN] Sydney Developer Preview 1 released
— Yukihiro Matsumoto <matz@...>
2005/07/12
Hi,
[#5426] Re: [ANN] Sydney Developer Preview 1 released
— Evan Webb <evanwebb@...>
2005/07/12
The MD5 sum is 53d1bde4542365caf4849c56e6274617.
[#5427] Re: [ANN] Sydney Developer Preview 1 released
— nobuyoshi nakada <nobuyoshi.nakada@...>
2005/07/12
Hi,
[#5430] Re: [ANN] Sydney Developer Preview 1 released
— Evan Webb <evanwebb@...>
2005/07/12
On 7/12/05, nobuyoshi nakada <nobuyoshi.nakada@ge.com> wrote:
[#5436] Re: [ANN] Sydney Developer Preview 1 released
— nobu.nokada@...
2005/07/12
Hi,
[#5437] Re: [ANN] Sydney Developer Preview 1 released
— Evan Webb <evanwebb@...>
2005/07/13
Hello,
[#5445] GC tweak — Stefan Kaes <skaes@...>
I have found that the performance of current garbage collector
11 messages
2005/07/13
[#5451] bug in pstore (ruby 1.8.2) on Windows ( Win XP) ? — noreply@...
Bugs item #2101, was opened at 2005-07-14 15:30
5 messages
2005/07/14
[#5470] Bogus age value from Etc — Daniel Berger <Daniel.Berger@...>
Hi all,
5 messages
2005/07/15
[#5471] make fail; ruby v182 not finding readline ? — OpenMacNews <OpenMacNews@...>
hi all,
6 messages
2005/07/15
[#5476] Bug in ruby's command line parsing — Lothar Scholz <mailinglists@...>
Hello,
9 messages
2005/07/16
[#5479] Re: Bug in ruby's command line parsing
— Doug Kearns <dougkearns@...>
2005/07/16
On Sat, Jul 16, 2005 at 10:11:34AM +0900, Lothar Scholz wrote:
[#5492] ruby ( v183) bcc32: using Socket.new with timeout -> files not closed — noreply@...
Bugs item #2131, was opened at 2005-07-19 17:34
9 messages
2005/07/19
[#5498] Re: [ ruby-Bugs-2131 ] ruby ( v183) bcc32: using Socket.new with timeout -> files not closed
— "daz" <dooby@...10.karoo.co.uk>
2005/07/21
[#5499] Re: [ ruby-Bugs-2131 ] ruby ( v183) bcc32: using Socket.new with timeout -> files not closed
— "H.Yamamoto" <ocean@...2.ccsnet.ne.jp>
2005/07/21
[#5513] Re: [ ruby-Bugs-2131 ] ruby ( v183) bcc32: using Socket.new with timeout -> files not closed
— "daz" <dooby@...10.karoo.co.uk>
2005/07/24
Re: O(1) performance for insertions/deletions at the front of an Array/String
From:
Mathieu Bouchard <matju@...>
Date:
2005-07-02 00:35:31 UTC
List:
ruby-core #5338
On Fri, 1 Jul 2005, Eric Mahurin wrote: > 3. unshift has O(1) performance when you unshift no more than > the amount you have shifted. I'd assume it just decremented > the start of array pointer. When you unshift more than you > shifted, it is O(n), physically moving the data to the right. The O(n) problem happens because when unshift is physically moving the data to the right, it does it by a fixed number of elements. Instead, it should do it by a percentage of the current size, which is would make it an amortized O(1). The actual percentage used has influence on the time constant. I agree that Ruby should do it in amortized O(1). > c. if shifts/unshifts can be made just as fast as pushes/pops, > you could cut the average time in half for random insertions > and deletions. This is a bright idea! I vote for it! ,-o--------o--------o--------o-. ,---. irc.freenode.net #dataflow | | The Diagram is the Program tm| | ,-o-------------o--------------o-. `-o------------o-------------o-' | | Mathieu Bouchard (Montr饌l QC) | | t駘駱hone:+1.514.383.3801`---' `-o-- http://artengine.ca/matju -'