Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.ruby > #3689 > unrolled thread

Need for speed - array operations

Back to article view | Back to comp.lang.ruby

Contents

  Need for speed - array operations Chris Lervag <chris.lervag@gmail.com> - 2011-04-29 03:54 -0500
    Re: Need for speed - array operations Ralf Mueller <ralf.mueller@zmaw.de> - 2011-04-29 06:05 -0500
      Re: Need for speed - array operations Robert Klemme <shortcutter@googlemail.com> - 2011-04-29 06:23 -0500
    Re: Need for speed - array operations Chris Lervag <chris.lervag@gmail.com> - 2011-04-29 09:05 -0500
    Re: Need for speed - array operations Chris Lervag <chris.lervag@gmail.com> - 2011-04-29 16:45 -0500
    Re: Need for speed - array operations Pirogov Eugene <iamexile@gmail.com> - 2011-05-17 15:26 -0500
      Re: Need for speed - array operations Joel VanderWerf <joelvanderwerf@gmail.com> - 2011-05-17 16:23 -0500

#3689 — Need for speed - array operations

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[i]]
  rgb[(i*3)+1] = lookup_values[1][pixels[i]]
  rgb[(i*3)+2] = lookup_values[2][pixels[i]]
end

-- 
Posted via http://www.ruby-forum.com/.

[toc] | [next] | [standalone]

#3694

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[i]]
>    rgb[(i*3)+1] = lookup_values[1][pixels[i]]
>    rgb[(i*3)+2] = lookup_values[2][pixels[i]]
> end
>
You might try narray: http://narray.rubyforge.org/. It's available as a gem.

ralf

[toc] | [prev] | [next] | [standalone]

#3695

On Fri, Apr 29, 2011 at 1:05 PM, Ralf Mueller <ralf.mueller@zmaw.de> 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 = 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[i]]
>>   rgb[(i*3)+1] = lookup_values[1][pixels[i]]
>>   rgb[(i*3)+2] = lookup_values[2][pixels[i]]
>> end
>>
> You might try narray: http://narray.rubyforge.org/. It's available as a gem.

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


-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

#3698

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

[toc] | [prev] | [next] | [standalone]

#3731

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[i] instead 
of pix.

Still a happy ending though!

Chris

-- 
Posted via http://www.ruby-forum.com/.

[toc] | [prev] | [next] | [standalone]

#4691

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.

-- 
Posted via http://www.ruby-forum.com/.

[toc] | [prev] | [next] | [standalone]

#4694

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.ruby

csiph-web