Need for speed - array operations

C

Chris Lervag

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
 
R

Ralf Mueller

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
 
R

Robert Klemme

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/
 
C

Chris Lervag

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
 
C

Chris Lervag

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
 
J

Joel VanderWerf

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...
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,906
Latest member
SkinfixSkintag

Latest Threads

Top