Need for speed - array operations

Discussion in 'Ruby' started by Chris Lervag, Apr 29, 2011.

  1. Chris Lervag

    Chris Lervag Guest

    Hi,

    Im working on a library to decode medical image files, and some of these
    files are encoded as 'PALETTE COLOR', which means you have a lookup
    table for red, green and blue pixel values. The final RGB pixel array is
    constructed by hitting the lookup table with the original pixel values.
    In my implementation I am using an iterator, and it is kinda slow. I
    cant spot an obvious way to improve on it though, so I thought I'd put
    the question out here and see if any of you more experienced Rubyists
    can suggest a more efficient way of doing this.

    Thanks,
    Chris

    Example code:
    # Set up example arrays to test the algorithm:
    lookup_values = Array.new
    lookup_values << Array.new(256, 0)
    lookup_values << Array.new(256, 1)
    lookup_values << Array.new(256, 2)
    pixels = Array.new(258000, rand(256))
    rgb = Array.new(pixels.length*3)

    # The PALETTE transformation algorithm:
    pixels.each_index do |i|
    rgb[i*3] = lookup_values[0][pixels]
    rgb[(i*3)+1] = lookup_values[1][pixels]
    rgb[(i*3)+2] = lookup_values[2][pixels]
    end

    --
    Posted via http://www.ruby-forum.com/.
     
    Chris Lervag, Apr 29, 2011
    #1
    1. Advertising

  2. Chris Lervag

    Ralf Mueller Guest

    On 04/29/2011 10:54 AM, Chris Lervag wrote:
    > Hi,
    >
    > Im working on a library to decode medical image files, and some of these
    > files are encoded as 'PALETTE COLOR', which means you have a lookup
    > table for red, green and blue pixel values. The final RGB pixel array is
    > constructed by hitting the lookup table with the original pixel values.
    > In my implementation I am using an iterator, and it is kinda slow. I
    > cant spot an obvious way to improve on it though, so I thought I'd put
    > the question out here and see if any of you more experienced Rubyists
    > can suggest a more efficient way of doing this.
    >
    > Thanks,
    > Chris
    >
    > Example code:
    > # Set up example arrays to test the algorithm:
    > lookup_values = Array.new
    > lookup_values<< Array.new(256, 0)
    > lookup_values<< Array.new(256, 1)
    > lookup_values<< Array.new(256, 2)
    > pixels = Array.new(258000, rand(256))
    > rgb = Array.new(pixels.length*3)
    >
    > # The PALETTE transformation algorithm:
    > pixels.each_index do |i|
    > rgb[i*3] = lookup_values[0][pixels]
    > rgb[(i*3)+1] = lookup_values[1][pixels]
    > rgb[(i*3)+2] = lookup_values[2][pixels]
    > end
    >

    You might try narray: http://narray.rubyforge.org/. It's available as a gem.

    ralf
     
    Ralf Mueller, Apr 29, 2011
    #2
    1. Advertising

  3. On Fri, Apr 29, 2011 at 1:05 PM, Ralf Mueller <> wrote:
    > On 04/29/2011 10:54 AM, Chris Lervag wrote:
    >>
    >> Hi,
    >>
    >> Im working on a library to decode medical image files, and some of these
    >> files are encoded as 'PALETTE COLOR', which means you have a lookup
    >> table for red, green and blue pixel values. The final RGB pixel array is
    >> constructed by hitting the lookup table with the original pixel values.
    >> In my implementation I am using an iterator, and it is kinda slow. I
    >> cant spot an obvious way to improve on it though, so I thought I'd put
    >> the question out here and see if any of you more experienced Rubyists
    >> can suggest a more efficient way of doing this.
    >>
    >> Thanks,
    >> Chris
    >>
    >> Example code:
    >> # Set up example arrays to test the algorithm:
    >> lookup_values =3D Array.new
    >> lookup_values<< =A0Array.new(256, 0)
    >> lookup_values<< =A0Array.new(256, 1)
    >> lookup_values<< =A0Array.new(256, 2)
    >> pixels =3D Array.new(258000, rand(256))
    >> rgb =3D Array.new(pixels.length*3)
    >>
    >> # The PALETTE transformation algorithm:
    >> pixels.each_index do |i|
    >> =A0 rgb[i*3] =3D lookup_values[0][pixels]
    >> =A0 rgb[(i*3)+1] =3D lookup_values[1][pixels]
    >> =A0 rgb[(i*3)+2] =3D lookup_values[2][pixels]
    >> end
    >>

    > You might try narray: http://narray.rubyforge.org/. It's available as a g=

    em.

    Not so fast. There is room for optimization even in this
    implementation. We can shave off over 12% with a pure Ruby solution:

    13:18:20 Temp$ ruby19 lv.rb
    user system total real
    old prep 0.000000 0.000000 0.000000 ( 0.000000)
    old 1.812000 0.000000 1.812000 ( 1.806000)
    new prep 0.000000 0.000000 0.000000 ( 0.001000)
    new 1.016000 0.047000 1.063000 ( 1.060000)

    https://gist.github.com/948178

    Kind regards

    robert


    --=20
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
     
    Robert Klemme, Apr 29, 2011
    #3
  4. Chris Lervag

    Chris Lervag Guest

    Robert,
    I've implemented your tweaked solution and indeed it runs significantly
    faster! In retrospect it looks so obvious, almost embarrasing!

    Thanks a million, your effort is appreciated!

    Ralf,
    yes I am aware of NArray, and probably that will be the optimal
    solution. At some stage I will probably use it, however, at least for
    now, I want to avoid external dependencies and just go with a pure Ruby
    solution.

    Thanks,
    Chris

    --
    Posted via http://www.ruby-forum.com/.
     
    Chris Lervag, Apr 29, 2011
    #4
  5. Chris Lervag

    Chris Lervag Guest

    Just a bit of an update:
    Turns out the each_with_index iterator is INSANELY slow on ruby1.8 on
    large arrays, so I had to use each_index instead and pixels instead
    of pix.

    Still a happy ending though!

    Chris

    --
    Posted via http://www.ruby-forum.com/.
     
    Chris Lervag, Apr 29, 2011
    #5
  6. Pirogov Eugene, May 17, 2011
    #6
  7. On 05/17/2011 01:26 PM, Pirogov Eugene wrote:
    > I'm experience the loss of speed in NArrays. Did you guys tried benching
    > a simple access to an element in NArray?
    >
    > My benches show dramatical slowdown comparing to a Ruby built-in Array.
    > I already filled an issue here:
    > https://github.com/masa16/narray/issues/8.
    >


    It's too simple a benchmark to demonstrate the efficiency of narray.
    What it's measuring is access time from ruby. For the first two cases,
    the number in the ruby array is a fixnum (shifted by one bit and or-ed
    with 0x01) that can simply be returned with no modification, as a 32 or
    64 bit VALUE (ruby's basic data type). In the third case, the number is
    stored as an 8 bit signed int, which has to be converted to VALUE by
    sign extending, shifting, and or-ing.

    As soon as you start measuring operations whose inputs and outputs are
    both NArrays (especially large ones), you'll see the speed...
     
    Joel VanderWerf, May 17, 2011
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ham

    I need speed Mr .Net....speed

    Ham, Oct 28, 2004, in forum: ASP .Net
    Replies:
    6
    Views:
    2,359
    Antony Baula
    Oct 29, 2004
  2. efiedler
    Replies:
    1
    Views:
    2,089
    Tim Ward
    Oct 9, 2003
  3. Jesus M. Salvo Jr.
    Replies:
    2
    Views:
    4,285
    robert
    Feb 11, 2006
  4. Replies:
    2
    Views:
    2,316
    Howard
    Apr 28, 2004
  5. Momo

    Speed of BitSet operations

    Momo, Jun 6, 2007, in forum: Java
    Replies:
    5
    Views:
    407
    Roedy Green
    Jun 15, 2007
Loading...

Share This Page