Hi
is it really so, that (internally) unshift replaces every item of the
array???
benchmarking it seems to allow that conclusion: Time depends on the length
of the array (in Ruboto)
Is there a nice lib/gem for real (one direction and double linked) lists?
- And (all sort of) ready-to-use trees?
My monkeys want to have fun too 
thx Berg
Shift and unshift work off the left side of the array, just like the
similar commands do in Bash, Bourne Shell, and many other shells
(which is where, I believe, the naming came from). Pop and push work
on the right side of the array to do the same thing. So pop and push
work on the end with the highest index, where shift and unshift work
on the end with the lowest index. Shift was originally used as a
convenient way to process arguments off the function or script
argument list without having to state the identifier. No, I cannot
recall why that was a nice thing to do, but I think in earlier days it
turned out to be convenient.
As Ruby tries, more than most with success, to be congruent, you'll
probably find shift and unshift, as well as pop and push to be used
the same way with other containers or sequential data structures in
Ruby.
On Wed, Jul 27, 2016 at 3:05 PM, A Berger <aberger7890@gmail.com> wrote:
Hi
is it really so, that (internally) unshift replaces every item of the
array???
benchmarking it seems to allow that conclusion: Time depends on the length
of the array (in Ruboto)Is there a nice lib/gem for real (one direction and double linked) lists?
- And (all sort of) ready-to-use trees?
My monkeys want to have fun toothx Berg
Unsubscribe: <mailto:ruby-talk-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-talk>
push and unshift - im asking what can not be found in the docs...
Did anyone run a benchmark with (the newest) MRI?
Thx Berg
Hi
is it really so, that (internally) unshift replaces every item of the
array???
benchmarking it seems to allow that conclusion: Time depends on the length
of the array (in Ruboto)
​It may well be the case, in Ruboto. Those sorts of details are
implementation-specific; i.e. not specified as part of the Ruby language
itself (timing and algorithmic concerns rarely are.)​
Is there a nice lib/gem for real (one direction and double linked) lists?
- And (all sort of) ready-to-use trees?
My monkeys want to have fun too
​I couldn't say; normally Arrays and Structs work well enough for me (in
CRuby/MRI).​
thx Berg
​Cheers
On 28 July 2016 at 08:05, A Berger <aberger7890@gmail.com> wrote:
--
Matthew Kerwin
http://matthew.kerwin.net.au/
Shift and unshift work off the left side of the array, just like the
similar commands do in Bash, Bourne Shell, and many other shells
(which is where, I believe, the naming came from). Pop and push work
on the right side of the array to do the same thing. So pop and push
work on the end with the highest index, where shift and unshift work
on the end with the lowest index.
​That's correct. The issue is that when operating on the left side of the
array (the "head"), you may have to copy all subsequent elements of the
array left or right one position. A clever implementation may implement
`shift` by incrementing the array pointer, thus relieving the need to move
each subsequent element left one position. However this isn't always
implemented, or even necessarily possible. Thus it's an implementation
detail (not specified by Ruby, and potentially different from
implementation to implementation).​
Shift was originally used as a
convenient way to process arguments off the function or script
argument list without having to state the identifier. No, I cannot
recall why that was a nice thing to do, but I think in earlier days it
turned out to be convenient.
​Back in the good old days function parameters were `push`ed onto the call
stack; however the parameter list is a (FIFO) queue, not a (LIFO) stack, so
to retrieve them in order you had to `shift` them off again.
While the details of the call stack are quite safely abstracted these days,
the paradigm of treating args/params as a list remains; especially in older
languages like Perl. Thus, in Perl, one can either splat the elements of
the argument list using parallel assignment {my ($a,$b,$c) = @_}, or shift
the elements off the args list as required {my $a=shift, $b=shift, $c=shift}
(N.B. if no list is passed to 'shift', it shifts from '@_' by default).​
As Ruby tries, more than most with success, to be congruent, you'll
probably find shift and unshift, as well as pop and push to be used
the same way with other containers or sequential data structures in
Ruby.
​Certainly it works on some list-like data structures (Array, Hash); it's
not generalised to Enumerable, though. I wouldn't say that Ruby tries to be
congruent; rather that it tries to make sense.
Cheers
On 28 July 2016 at 08:29, Xeno Campanoli <xeno.campanoli@gmail.com> wrote:
--
Matthew Kerwin
http://matthew.kerwin.net.au/
push and unshift - im asking what can not be found in the docs...
Did anyone run a benchmark with (the newest) MRI?
Thx Berg
On 28 July 2016 at 09:02, A Berger <aberger7890@gmail.com> wrote:
~~~
$ cat bm.rb
require 'benchmark'
puts RUBY_DESCRIPTION
n = 10_000_000
Benchmark.bm(20) do |x|
a = [0] * n
b = [0] * n
x.report('pop') { n.times { a.pop } }
x.report('shift') { n.times { b.shift } }
end
$ ruby-trunk bm.rb
ruby 2.4.0dev (2016-07-07 trunk 55602) [x86_64-linux]
user system total real
pop 0.500000 0.000000 0.500000 ( 0.493228)
shift 0.490000 0.000000 0.490000 ( 0.496545)
$ ruby2.3 bm.rb
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-linux]
user system total real
pop 0.460000 0.010000 0.470000 ( 0.471049)
shift 0.480000 0.000000 0.480000 ( 0.485684)
$ ruby2.2 bm.rb
ruby 2.2.5p319 (2016-04-26 revision 54774) [x86_64-linux]
user system total real
pop 0.500000 0.000000 0.500000 ( 0.508665)
shift 0.520000 0.000000 0.520000 ( 0.525314)
$ jruby bm.rb
jruby 9.0.5.0 (2.2.3) 2016-04-20 fffffff OpenJDK 64-Bit Server VM 24.95-b01
on 1.7.0_101-b00 +jit [linux-amd64]
user system total real
pop 0.370000 0.000000 0.370000 ( 0.334230)
shift 0.340000 0.000000 0.340000 ( 0.321069)
$ jruby-trunk bm.rb
jruby 9.1.3.0-SNAPSHOT (2.3.0) 2016-07-07 6902d10 OpenJDK 64-Bit Server VM
24.95-b01 on 1.7.0_101-b00 +jit [linux-x86_64]
user system total real
pop 0.400000 0.000000 0.400000 ( 0.362148)
shift 0.390000 0.000000 0.390000 ( 0.365059)
$
~~~
So, seems alright to me. What benchmark are you using?
Cheers
--
Matthew Kerwin
http://matthew.kerwin.net.au/
I haven't used it a lot but I was impressed by this gem for efficient,
immutable data structures: https://github.com/hamstergem/hamster
Robert
On Wed, Jul 27, 2016 at 7:22 PM, Matthew Kerwin <matthew@kerwin.net.au> wrote:
On 28 July 2016 at 09:02, A Berger <aberger7890@gmail.com> wrote:
push and unshift - im asking what can not be found in the docs...
Did anyone run a benchmark with (the newest) MRI?
Thx Berg~~~
$ cat bm.rb
require 'benchmark'puts RUBY_DESCRIPTION
n = 10_000_000
Benchmark.bm(20) do |x|
a = [0] * n
b = [0] * n
x.report('pop') { n.times { a.pop } }
x.report('shift') { n.times { b.shift } }
end$ ruby-trunk bm.rb
ruby 2.4.0dev (2016-07-07 trunk 55602) [x86_64-linux]
user system total real
pop 0.500000 0.000000 0.500000 ( 0.493228)
shift 0.490000 0.000000 0.490000 ( 0.496545)
$ ruby2.3 bm.rb
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-linux]
user system total real
pop 0.460000 0.010000 0.470000 ( 0.471049)
shift 0.480000 0.000000 0.480000 ( 0.485684)
$ ruby2.2 bm.rb
ruby 2.2.5p319 (2016-04-26 revision 54774) [x86_64-linux]
user system total real
pop 0.500000 0.000000 0.500000 ( 0.508665)
shift 0.520000 0.000000 0.520000 ( 0.525314)
$ jruby bm.rb
jruby 9.0.5.0 (2.2.3) 2016-04-20 fffffff OpenJDK 64-Bit Server VM
24.95-b01 on 1.7.0_101-b00 +jit [linux-amd64]
user system total real
pop 0.370000 0.000000 0.370000 ( 0.334230)
shift 0.340000 0.000000 0.340000 ( 0.321069)
$ jruby-trunk bm.rb
jruby 9.1.3.0-SNAPSHOT (2.3.0) 2016-07-07 6902d10 OpenJDK 64-Bit Server VM
24.95-b01 on 1.7.0_101-b00 +jit [linux-x86_64]
user system total real
pop 0.400000 0.000000 0.400000 ( 0.362148)
shift 0.390000 0.000000 0.390000 ( 0.365059)
$
~~~So, seems alright to me. What benchmark are you using?
Cheers
--
Matthew Kerwin
http://matthew.kerwin.net.au/Unsubscribe: <mailto:ruby-talk-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-talk>
thanks for your answers!
(Matthew: Could you show it with push+unshift - sure, you will not run out
of mem 
Berg
​You have to be careful when benchmarking growing functions like
push/unshift, because of the way MRI allocates more space than is
immediately required for an array. Notice how pushing onto an empty array
takes the same time as pushing onto a very large array; but unshifting onto
a very large array is actually faster than unshifting onto an empty one.
On 28 July 2016 at 17:06, A Berger <aberger7890@gmail.com> wrote:
thanks for your answers!
(Matthew: Could you show it with push+unshift - sure, you will not run out
of mem
Berg
~~~
$ cat bm2.rb
require 'benchmark'
puts RUBY_DESCRIPTION
n = 10_000_000
Benchmark.bm(20) do |x|
a =
b =
x.report('push') { n.times { a.push 0 } }
x.report('unshift') { n.times { b.unshift 0 } }
end
Benchmark.bm(20) do |x|
a = [0] * n
b = [0] * n
x.report('push 2') { n.times { a.push 0 } }
x.report('unshift 2') { n.times { b.unshift 0 } }
end
Benchmark.bm(20) do |x|
a = [0] * (n * 3)
b = [0] * (n * 3)
x.report('push 4') { n.times { a.push 0 } }
x.report('unshift 4') { n.times { b.unshift 0 } }
end
$ ruby2.3 bm2.rb
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-linux]
user system total real
push 0.610000 0.010000 0.620000 ( 0.633040)
unshift 0.860000 0.020000 0.880000 ( 0.881495)
user system total real
push 2 0.610000 0.010000 0.620000 ( 0.635371)
unshift 2 0.760000 0.010000 0.770000 ( 0.771234)
user system total real
push 4 0.600000 0.000000 0.600000 ( 0.637529)
unshift 4 0.650000 0.020000 0.670000 ( 0.674283)
$
~~~
This suggests that when an unshift causes an overflow, MRI allocates a
bunch of space to the left of the array (meaning the next however many
unshifts don't require a reallocation). Of course that wouldn't always
work, so it would sometimes have to relocate the entire array in memory.
I'm just speculating based on the benchmark numbers, though; it might not
work that way at all.
Cheers
--
Matthew Kerwin
http://matthew.kerwin.net.au/
I'm just speculating based on the benchmark numbers, though; it might not
work that way at all.
Nice work, though!
Hi
Thanks for the insight(s)
  - many methods cant handle nil
  - more benchmark-details than I were thinking of 
- Nice that it is optimized in MRI !
cheers
Berg
