Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Ruby Programming Language

Enumerable#serially - those nifty functions w/o memory footprint


Hello,

I've seen many people write things like:

(1..1000000).to_a. # anything that is a huge enumerable can work as an example
  collect{|x| num_appearances(x)}.select{|x|
x.is_norwegian?}.collect{|x| x.paycheck}.each{|x| p x}

I almost wrote something like that myself today.

The problem, of course, is the huge memory footprint - collect,
select, collect each creates a new temporary array to store the
results in.

Here's a solution to that problem, exchanging it for a bit of speed
(anything that uses those methods could obviously live with that,
otherwise another language or method would be used):

module Enumerable
  def serially(&b)
    self.collect{|x| *([x].instance_eval(&b)}
  end
end

Just beware not to use it with sort or any of the "!" methods or with
sort or sort_by.

Aur

Sorry, found a bug, I'll need to make it into this:

module Enumerable
  def serially(&b)
    a = []
    self.each{|x| t = ([x].instance_eval(&b); a << b[0] unless b.empty?}
    # notice, relevance to "it" discussion that's currently going on, just btw
  end
end

On 5/30/07, SonOfLilit <sonofli@gmail.com> wrote:

On 30.05.2007 15:35, SonOfLilit wrote:

> Hello,

> I've seen many people write things like:

> (1..1000000).to_a. # anything that is a huge enumerable can work as an
> example
>  collect{|x| num_appearances(x)}.select{|x|
> x.is_norwegian?}.collect{|x| x.paycheck}.each{|x| p x}

Just guessing what all this does, but there is of course the obvious
solution:

some_large_enum.each do |x|
   x = num_appearances(x)
   p x.paycheck if x.norwegian?
end

> I almost wrote something like that myself today.

> The problem, of course, is the huge memory footprint - collect,
> select, collect each creates a new temporary array to store the
> results in.

Yes, that's really an issue.

> Here's a solution to that problem, exchanging it for a bit of speed
> (anything that uses those methods could obviously live with that,
> otherwise another language or method would be used):

> module Enumerable
>  def serially(&b)
>    self.collect{|x| *([x].instance_eval(&b)}
>  end
> end

> Just beware not to use it with sort or any of the "!" methods or with
> sort or sort_by.

I am not exactly sure I understand what this is supposed to do. This
isn't even compiling properly.

Regards

        robert

On Wed, May 30, 2007 at 10:46:33PM +0900, SonOfLilit wrote:
> Sorry, found a bug, I'll need to make it into this:

> module Enumerable
>  def serially(&b)
>    a = []
>    self.each{|x| t = ([x].instance_eval(&b); a << b[0] unless b.empty?}
>    # notice, relevance to "it" discussion that's currently going on, just
>    btw
>  end
> end

Somehow I don't think you tested this :-)

* You have mismatched parentheses
* You assign to t, but never use the value
* you call b twice, once with no arguments, and once with 0 as an argument
* b is a block, but you call #empty? on it

Can you give an example of how this is supposed to be used?

Brian.

I think I get his point. I wrote a little lib to try out my
interpretation of what he is trying to do.

a = (1..20)

b = a.serially do
     select do |x|
         if x > 10
             true
         else
             false
         end
     end
     collect do |x|
         "0x" + x.to_s
     end
     select do |x|
         if x == "0x15"
             false
         else
             true
         end
     end
end

puts b

# generates

0x11
0x12
0x13
0x14
0x16
0x17
0x18
0x19
0x20

The lib is at

http://xtargets.com/snippets/posts/show/69

--
Brad Phelan
http://xtargets.com/snippets

A quick profile with ruby-prof find the above technique about 10 times
slower in 50000 elements than for the traditional method.

--
Brad Phelan
http://xtargets.com

This little bit of code has got me interested. Turns out I can create a
version with comparable time execution by slicing the the input
enumerable into memory friendly chunks and then performing all
operations on those chunks. This kind of reminds me of C++
expression templating tricks

See the link

http://xtargets.com/snippets/posts/show/69

for the latest highspeed version and the ruby-prof results

--
Brad Phelan
http://xtargets.com

module Enumerable
 def serially(&b)
   a = []
   self.each{|x| t = [x].instance_eval(&b); a << t[0] unless t.empty?}
   a
 end
end

p (0..20).serially{select{|x| x>10}.collect{|x|"0x" <<
x.to_s}.select{|x| x != "0x15"}}

#=> ["0x11", "0x12", "0x13", "0x14", "0x16", "0x17", "0x18", "0x19", "0x20"]

The original version was written in another computer, and re-typing
wuthout testing took it's toll. I'm really sorry for wasting all of
your times.

On the other hand, I seem to have inspired someone to think of a
really clever hack, that is exactly orthogonal to my method:

While I call all methods on each member of the enumerable,
incrementally building the results array (a bit like using Generator
iterators, but without the continuations :P), Brad evaluates each
function in the chain on 100 members at a time, building the array for
the next function. If he'd use slices of size 1, our code would be
very similar in idea. My attempt to combine our methods ended in
finding that my installed Enumerable implementation is braindead,
probably a collision between the 1.8.5 and 1.8.2 ruby versions
installed here. I don't care enough to go into it right now.

Profiling data is on the way and will be here soon.

Aur

On 5/30/07, Brad Phelan <phe@tttech.ttt> wrote:

Following is ruby-prof output. First, a few words:

4.75 against 1.56 isn't too good, but it isn't ten times slower. I
think it can be excused (and maybe the code can be optimized a bit) in
cases where you'd process huge lists with ruby of all languages.

This is the code used to profile:

require 'rubygems'
require 'ruby-prof'

module Enumerable
 def serially(&b)
   a = []
   self.each{|x| t = [x].instance_eval(&b); a << t[0] unless t.empty?}
   a
 end
end

# Profile the code
result = RubyProf.profile{
 a = (1..50000)
 b = a.serially{select{|x| x>280}.collect{|x|"0x" <<
x.to_s}.select{|x| x != "0x15"}}

}

# Print a graph profile to text
printer = RubyProf::GraphPrinter.new(result)
printer.print(STDOUT, 0)

result = RubyProf.profile{
 a = (1..50000)
 b = a.select{|x| x>280}.collect{|x|"0x" << x.to_s}.select{|x| x != "0x15"}

}

# Print a graph profile to text
printer = RubyProf::GraphPrinter.new(result)
printer.print(STDOUT, 0)

  %total   %self     total      self    children             calls   Name
--------------------------------------------------------------------------- -----
                      0.16      0.16      0.00         49720/49720
Array#select
   3.37%   3.37%      0.16      0.16      0.00               49720     String#==
--------------------------------------------------------------------------- -----
                      0.19      0.19      0.00         49720/49720
Array#collect
   4.00%   4.00%      0.19      0.19      0.00               49720     String#<<
--------------------------------------------------------------------------- -----
                      4.75      0.79      3.96                 1/1
Enumerable#serially
 100.00%  16.63%      4.75      0.79      3.96                   1
Range#each
                      3.46      1.01      2.45         50000/50000
Kernel#instance_eval
                      0.18      0.18      0.00         49720/49720     Array#[]
                      0.15      0.15      0.00         50000/50000
Array#empty?
                      0.17      0.17      0.00         49720/49720     Array#<<
--------------------------------------------------------------------------- -----
                      3.46      1.01      2.45         50000/50000
Range#each
  72.84%  21.26%      3.46      1.01      2.45               50000
Kernel#instance_eval
                      1.08      0.65      0.43         50000/50000
Array#collect
                      1.37      1.02      0.35       100000/100000
Array#select
--------------------------------------------------------------------------- -----
                      0.24      0.24      0.00         49720/49720
Array#collect
   5.05%   5.05%      0.24      0.24      0.00               49720
Fixnum#to_s
--------------------------------------------------------------------------- -----
                      0.19      0.19      0.00         50000/50000
Array#select
   4.00%   4.00%      0.19      0.19      0.00               50000     Fixnum#>
--------------------------------------------------------------------------- -----
                      4.75      0.00      4.75                 1/1     #toplevel
 100.00%   0.00%      4.75      0.00      4.75                   1
Enumerable#serially
                      4.75      0.79      3.96                 1/1
Range#each
--------------------------------------------------------------------------- -----
                      1.37      1.02      0.35       100000/100000
Kernel#instance_eval
  28.84%  21.47%      1.37      1.02      0.35              100000
Array#select
                      0.16      0.16      0.00         49720/49720     String#==
                      0.19      0.19      0.00         50000/50000     Fixnum#>
--------------------------------------------------------------------------- -----
                      0.15      0.15      0.00         50000/50000
Range#each
   3.16%   3.16%      0.15      0.15      0.00               50000
Array#empty?
--------------------------------------------------------------------------- -----
                      1.08      0.65      0.43         50000/50000
Kernel#instance_eval
  22.74%  13.68%      1.08      0.65      0.43               50000
Array#collect
                      0.19      0.19      0.00         49720/49720     String#<<
                      0.24      0.24      0.00         49720/49720
Fixnum#to_s
--------------------------------------------------------------------------- -----
                      0.18      0.18      0.00         49720/49720
Range#each
   3.79%   3.79%      0.18      0.18      0.00               49720     Array#[]
--------------------------------------------------------------------------- -----
                      0.17      0.17      0.00         49720/49720
Range#each
   3.58%   3.58%      0.17      0.17      0.00               49720     Array#<<
--------------------------------------------------------------------------- -----
 100.00%   0.00%      4.75      0.00      4.75                   1     #toplevel
                      4.75      0.00      4.75                 1/1
Enumerable#serially

Thread ID: 1020900
  %total   %self     total      self    children             calls   Name
--------------------------------------------------------------------------- -----
                      0.16      0.16      0.00         49720/49720
Array#select
  10.00%  10.00%      0.16      0.16      0.00               49720     String#==
--------------------------------------------------------------------------- -----
                      0.14      0.14      0.00         49720/49720
Array#collect
   8.75%   8.75%      0.14      0.14      0.00               49720     String#<<
--------------------------------------------------------------------------- -----
                      0.41      0.22      0.19                 1/1
Enumerable#select
  25.62%  13.75%      0.41      0.22      0.19                   1
Range#each
                      0.19      0.19      0.00         50000/50000     Fixnum#>
--------------------------------------------------------------------------- -----
                      0.24      0.24      0.00         49720/49720
Array#collect
  15.00%  15.00%      0.24      0.24      0.00               49720
Fixnum#to_s
--------------------------------------------------------------------------- -----
                      0.19      0.19      0.00         50000/50000
Range#each
  11.88%  11.88%      0.19      0.19      0.00               50000     Fixnum#>
--------------------------------------------------------------------------- -----
                      0.41      0.00      0.41                 1/1     #toplevel
  25.62%   0.00%      0.41      0.00      0.41                   1
Enumerable#select
                      0.41      0.22      0.19                 1/1
Range#each
--------------------------------------------------------------------------- -----
                      0.38      0.22      0.16                 1/1     #toplevel
  23.75%  13.75%      0.38      0.22      0.16                   1
Array#select
                      0.16      0.16      0.00         49720/49720     String#==
--------------------------------------------------------------------------- -----
                      0.81      0.43      0.38                 1/1     #toplevel
  50.62%  26.88%      0.81      0.43      0.38                   1
Array#collect
                      0.14      0.14      0.00         49720/49720     String#<<
                      0.24      0.24      0.00         49720/49720
Fixnum#to_s
--------------------------------------------------------------------------- -----
 100.00%   0.00%      1.60      0.00      1.60                   1     #toplevel
                      0.41      0.00      0.41                 1/1
Enumerable#select
                      0.81      0.43      0.38                 1/1
Array#collect
                      0.38      0.22      0.16                 1/1
Array#select

On 30.05.2007 21:54, SonOfLilit wrote:

You are changing subject in between:  Originally you started out with
memory consumption being the issue.  Now you talk about speed.  Your
solution is neither fast nor easy on the memory.  For speed see the
benchmark below.  It's not easy on the memory because you still create a
*ton* of temporary one element arrays (four per iteration if I'm not
mistaken) - this avoids the single large copy but allocating and GC'ing
all these temporaries imposes a significant overhead.  The obvious and
simple solution here is to do it all in *one* iteration.  So why invent
something new if there is an easy and efficient solution available?

Kind regards

        robert

10:38:35 [Temp]: ./ser.rb
Rehearsal --------------------------------------------------
classic          3.359000   0.000000   3.359000 (  3.338000)
serially        13.719000   0.016000  13.735000 ( 13.747000)
serially!       13.328000   0.000000  13.328000 ( 13.361000)
inject           4.297000   0.000000   4.297000 (  4.339000)
each             3.297000   0.000000   3.297000 (  3.273000)
---------------------------------------- total: 38.016000sec

                      user     system      total        real
classic          3.203000   0.000000   3.203000 (  3.265000)
serially        12.891000   0.000000  12.891000 ( 13.233000)
serially!       12.438000   0.000000  12.438000 ( 12.617000)
inject           3.937000   0.000000   3.937000 (  3.985000)
each             2.937000   0.000000   2.937000 (  3.008000)

[ ser.rb ]
#!ruby

require 'benchmark'

ITER = 10

module Enumerable
  def serially(&b)
    a = []
    each{|x| t = [x].instance_eval(&b); a << t[0] unless t.empty?}
    a
  end
end

a = (1..50000)

Benchmark.bmbm(15) do |bench|
  bench.report("classic") do
    ITER.times do
      # a = (1..50000)
      b = a.select {|x| x>280}.collect{|x|"0x" << x.to_s}.select{|x| x != "0x15"}
   end
  end

  bench.report("serially") do
    ITER.times do
      # a = (1..50000)
      b = a.serially { select {|x| x>280}.collect{|x|"0x" << x.to_s}.select{|x| x != "0x15"} }
   end
  end

  bench.report("serially!") do
    ITER.times do
      # a = (1..50000)
      b = a.serially { select {|x| x>280}.collect! {|x|"0x" << x.to_s}.select {|x| x != "0x15"} }
   end
  end

  bench.report("inject") do
    ITER.times do
      # a = (1..50000)
      b = a.inject([]) do |acc, x|
        if x > 280
          x = "0x" << x.to_s
          acc << x unless x == "0x15"
        end
        acc
      end
    end
  end

  bench.report("each") do
    ITER.times do
      # a = (1..50000)
      b = []
      a.each do |x|
        if x > 280
          x = "0x" << x.to_s
          b << x unless x == "0x15"
        end
      end
    end
  end
end

> You are changing subject in between:  Originally you started out with
> memory consumption being the issue.  Now you talk about speed.  Your
> solution is neither fast nor easy on the memory.  For speed see the
> benchmark below.  It's not easy on the memory because you still create a
> *ton* of temporary one element arrays (four per iteration if I'm not
> mistaken) - this avoids the single large copy but allocating and GC'ing
> all these temporaries imposes a significant overhead.  The obvious and
> simple solution here is to do it all in *one* iteration.  So why invent
> something new if there is an easy and efficient solution available?

I can get comparable results for my solution

Rehearsal --------------------------------------------------
serially         7.410000   0.120000   7.530000 (  7.731576)
classic          5.890000   0.080000   5.970000 (  6.123102)
---------------------------------------- total: 13.500000sec

                      user     system      total        real
serially         6.500000   0.000000   6.500000 (  6.581172)
classic          3.160000   0.010000   3.170000 (  3.199095)

See http://xtargets.com/snippets/posts/show/69 for details

What kills me and makes the final overhead is a fast way to
*non-recursively* flatten an array of arrays. My solution
is

    def self.flatten(o)
        length = o.inject(0) {|m,i|m+i.length}
        out = Array.new(length)
        base = 0
        o.each do |sub|
            top = base + sub.length
            out[base..top]=sub
            base = top
        end

    end

It is much faster than the inject and concat simple
method but still too slow.

Any ideas ( apart from code it in C )

Brad

On 31.05.2007 11:05, Brad Phelan wrote:

Even without flattening you won't beat #each:

13:19:42 [Temp]: ./ser.rb
Rehearsal -----------------------------------------------------
classic             3.188000   0.000000   3.188000 (  3.392000)
serially           12.968000   0.031000  12.999000 ( 13.770000)
serially!          12.563000   0.000000  12.563000 ( 13.187000)
serially_chunk      3.578000   0.000000   3.578000 (  3.628000)
serially_chunk_rk   3.594000   0.000000   3.594000 (  3.643000)
inject              4.015000   0.016000   4.031000 (  4.124000)
each                2.922000   0.016000   2.938000 (  3.091000)
------------------------------------------- total: 42.891000sec

                         user     system      total        real
classic             3.110000   0.000000   3.110000 (  3.237000)
serially           12.515000   0.000000  12.515000 ( 12.973000)
serially!          12.000000   0.031000  12.031000 ( 12.471000)
serially_chunk      2.938000   0.000000   2.938000 (  3.140000)
serially_chunk_rk   3.172000   0.000000   3.172000 (  3.331000)
inject              3.781000   0.000000   3.781000 (  3.839000)
each                2.891000   0.000000   2.891000 (  2.956000)

:-)

        robert

[ ser.rb ]
#!ruby

require 'benchmark'

ITER = 10

module Enumerable
  def serially(&b)
    a = []
    each{|x| t = [x].instance_eval(&b); a << t[0] unless t.empty?}
    a
  end
end

require 'enumerator'

class Serializer

    attr_accessor :obj

    def collect(*args, &block)
        @obj.collect!(*args, &block)
    end

    def select(*args, &block)
        @obj = @obj.select(*args, &block)
    end

   def self.flatten(o)
       length = o.inject(0) {|m,i|m+i.length}
       out = Array.new(length)
       base = 0
       o.each do |sub|
           top = base + sub.length
           out[base..top]=sub
           base = top
       end

   end
end

module Enumerable

   def flatten
       length = @obj.inject(0) {|m,i|m+i.length}
       out = Array.new(length)
       base = 0
       @obj.each do |sub|
           out[base..base+sub.length]=sub
           base = base + sub.length
       end

   end
   def serially_chunk(slice=50, &b)
        t = []
        o = Serializer.new
        self.each_slice(slice) do |x|
            o.obj = x
            o.instance_eval(&b)
            t << o.obj
        end
        Serializer.flatten t
    end

   def serially_chunk_rk(slice=50, &b)
        t = []
        o = Serializer.new
        each_slice(slice) do |x|
            o.obj = x
            o.instance_eval(&b)
            t.concat o.obj
        end
        t
    end
end

a = (1..50000)

Benchmark.bmbm(15) do |bench|
  bench.report("classic") do
    ITER.times do
      # a = (1..50000)
      b = a.select {|x| x>280}.collect{|x|"0x" << x.to_s}.select{|x| x != "0x15"}
   end
  end

  bench.report("serially") do
    ITER.times do
      # a = (1..50000)
      b = a.serially { select {|x| x>280}.collect{|x|"0x" << x.to_s}.select{|x| x != "0x15"} }
   end
  end

  bench.report("serially!") do
    ITER.times do
      # a = (1..50000)
      b = a.serially { select {|x| x>280}.collect! {|x|"0x" << x.to_s}.select {|x| x != "0x15"} }
   end
  end

  bench.report("serially_chunk") do
    ITER.times do
      # a = (1..50000)
      b = a.serially_chunk(1000) do
          select {|x| x > 280}
          collect do |x|
            "0x" << x.to_s
          end
          select {|x| x != "0x15"}
      end
   end
  end

  bench.report("serially_chunk_rk") do
    ITER.times do
      # a = (1..50000)
      b = a.serially_chunk_rk(1000) do
          select {|x| x > 280}
          collect do |x|
            "0x" << x.to_s
          end
          select {|x| x != "0x15"}
      end
   end
  end

  bench.report("inject") do
    ITER.times do
      # a = (1..50000)
      b = a.inject([]) do |acc, x|
        if x > 280
          x = "0x" << x.to_s
          acc << x unless x == "0x15"
        end
        acc
      end
    end
  end

  bench.report("each") do
    ITER.times do
      # a = (1..50000)
      b = []
      a.each do |x|
        if x > 280
          x = "0x" << x.to_s
          b << x unless x == "0x15"
        end
      end
    end
  end
end

Now who's changing the subject? Of course if you fold all your desired
operations into a single each block it will be faster. The question
is can you find a pattern that differs marginally from the classic
pattern but is faster and more memory efficient.

As I pointed out in a previous post C++ expression templates are
used to effect the optimisation that is being talked about here
in C++. Perhapps an on the fly code generation trick to generate
this optimal each block is worth it if the data size is large
enough.

B

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc