Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I wrote a zscore algorithm in Ruby that runs fine, but is incredibly slow when I have 8000+ entries to score. Can anyone help me figure out a way to improve my code, please?

module Enumerable  
  def mean
    reduce(:+).to_f / length
  end

  def sample_variance
    sum = inject(0){ |acc, i| acc + (i - mean)**2 }
    1 / length.to_f * sum
  end

  def standard_deviation
    Math.sqrt(sample_variance)
  end

  def zscore
    if standard_deviation.zero?
      Array.new(length, 0)
    else
      collect { |v| (v - mean) / standard_deviation } 
    end
  end
end

The float is giving every score an accuracy of up to 17 decimal places. Would making it only 8 decimal places speed things up?

EDIT: Here is an updated version of the algorithm given the advice received in this thread.

class Array
  def mean(len=self.length)
    reduce(:+).to_f / len
  end

  def sample_variance
    len = length
    m = mean(len)
    sum = reduce { |acc, i| acc + (i - m)**2 }
    sum.to_f / len
  end

  def standard_deviation
    Math.sqrt(sample_variance)
  end

  def zscore
    stdev = standard_deviation
    m = mean
    stdev.zero? ? Array.new(length, 0) : collect { |v| (v - m) / stdev }
  end
end
share|improve this question
    
If that is a sample variance (as opposed to a population variance), you need to divide by n-1 (not n) for it to be an unbiased estimator (though in this case the difference is negligible). Also, I suggest you write that sum / (length + 1.0). –  Cary Swoveland May 21 at 8:38
    
@CarySwoveland I'm not a very mathy person...would you be so kind as to explain why I need to do sum/(length + 1.0) for sample variance? Thanks! Also, this is a population variance as I am running it on all records. –  DaniG2k May 21 at 12:16
    
Unfortunately, it's a mathy answer. I think sum.to_f / len reads better than 1 / len.to_f * sum. –  Cary Swoveland May 21 at 16:28

1 Answer 1

up vote 4 down vote accepted

The problem is here: collect { |v| (v - mean) / standard_deviation }. standard_deviation is constant but, being inside a block, it is called on each iteration. Set the value to a local variable before. As noted by Flambino, the same principle applies to sample_variance (which uses mean inside a block).

In a functional language (where immutability is honored) the compiler would be able to do the right thing, but not in an imperative language plagued with side-effects like Ruby.

Some additional notes to your code:

  • module Enumerable: But you call .length, which is not a method that an enumerable is required to implement. Consider adding them to Array (which includes Enumerable).

  • reduce and then inject. I'd use just one of the alias.

share|improve this answer
    
I actually just noticed this before you wrote it. Setting standard_deviation to a variable at the beginning of the zscore method makes this run blazingly fast. Thanks –  DaniG2k May 18 at 21:39
1  
@DaniG2k You can do the same local var trick with mean in your zscore and sample_variance methods. Not as big a boost as storing standard_deviation, but the principle's the same –  Flambino May 18 at 21:42
    
@tokland I'm confused: the reduce method should be called on an Enumerable but length should be called on an Array. Which is better to use? –  DaniG2k May 18 at 21:53
1  
@DaniG2k: Array includes Enumerable. –  tokland May 18 at 21:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.