11
\$\begingroup\$

It was a part of my coding challenge and the last one, but I failed because it failed to yield a result in two seconds for some of sample inputs (out of six samples, three passed but three failed for not meeting the time constraint).

Basically, you are supposed to find the maximum deviation from given number of consecutive integers. There are two inputs; the first argument is an array of integers and the second argument is the number of consecutive integers. And you print the maximum deviation. For example, if you have [10, 1, 5, 2, 6, 3] and 3 as arguments, the output should be 9 since [10, 1, 5] would yield the maximum deviation of 9 (10-1).

Can this be refactored to be faster?

def find_deviation(integers, range)
  max = 0
  (0..integers.size-range).each do |n|
    array = integers.slice(n, range)
    diff = array.max - array.min
    max = diff if diff > max
  end
  puts max
end
\$\endgroup\$
7
  • 1
    \$\begingroup\$ link to the code challenge to get the samples? \$\endgroup\$
    – tokland
    Commented Feb 16, 2014 at 11:19
  • \$\begingroup\$ @tokland, I don't have the access to the samples and I can't go back to the challenge once it's done. \$\endgroup\$
    – yangtheman
    Commented Feb 17, 2014 at 8:32
  • \$\begingroup\$ @yangtheman, ok, but at least a link? is it a public challenge? \$\endgroup\$
    – tokland
    Commented Feb 17, 2014 at 17:10
  • 1
    \$\begingroup\$ There's a discrepancy between your explanation and your code. You wrote that the maximum deviation for [10,1,5] is 5, because 10 - 5 = 5. However you compute the difference between the max and the min, which would be 10 - 1 = 9, and I think that's what you're really looking for. \$\endgroup\$
    – To마SE
    Commented Feb 19, 2014 at 9:44
  • \$\begingroup\$ @tokland, no, it wasn't a public challenge, so that's I can't share a link nor I can go back to the challenge. \$\endgroup\$
    – yangtheman
    Commented Feb 20, 2014 at 16:46

1 Answer 1

10
\$\begingroup\$

Some notes:

  • find_deviation(v, d): Try to write more meaningful names for variables. Specially, I'd give a plurar name to v, since it's a collection.

  • max = 0, each, inline if: All of this denote you think in imperative terms. Some notes on functional programming with Ruby.

I'd write, with a functional approach:

def find_deviation(values, m)
  values.each_cons(m).map { |xs| xs.max - xs.min }.max
end

Now, this function has exactly the same time complexity than yours (though it may be faster or slower depending on how Ruby works). The complexity is: len(values) = n -> O(n*m). Note that you can use Enumerable#minmax to avoid one traversal, but it's still the same complexity.

To make it faster here's an idea, even though it's not trivial to implement: use a structure with O(log n) times for insertion/deletion/max/min (a binary search tree is ideal for this) to hold values of the sliding window, this way the overall complexity is O(nlog m). I guess some of the tests have big values of m so the trivial approach O(nm) is too slow.

[edit] Just for fun, I wrote a O(n log m) implementation in Haskell (I found no BST gem for Ruby):

deviation :: (Num a, Ord a) => [a] -> Int -> a 
deviation [] _ = 0
deviation xs m = maximum $ [Tree.maximum w - Tree.minimum w | w <- windows]
  where
    windows = scanl shift (Tree.fromList $ take m xs) (zip xs (drop m xs))
    shift window (old, new) = Tree.insert (Tree.delete window old) new
\$\endgroup\$
5
  • \$\begingroup\$ Yeah, I don't think you can get away from having to examine all elements in the array. I don't know if implementing my own way of finding max and min would be faster than using Ruby's min and max method. I guess the key is not creating subset of arrays, but to operate on the given array (thus using binary search on sliding window). Let me see if I can test this hypothesis. \$\endgroup\$
    – yangtheman
    Commented Feb 17, 2014 at 8:56
  • \$\begingroup\$ I did some research of my own and updated my question. What do you think? \$\endgroup\$
    – yangtheman
    Commented Mar 3, 2014 at 20:16
  • \$\begingroup\$ "you would still need to operate on all subsets of the given array, and it would be the slowest" -> no, in my second suggestion you'd use trees, not arrays, so sorting/inclusion/removal operations would be logarithmic (nearly linear for all practical purposes). \$\endgroup\$
    – tokland
    Commented Mar 3, 2014 at 21:30
  • \$\begingroup\$ I see. Would it work even if given argument is an array? I don't know Haskell, but if given argument is an array, there is no other way around having to work with subsets of the given array? \$\endgroup\$
    – yangtheman
    Commented Mar 3, 2014 at 22:06
  • \$\begingroup\$ No, arrays may have some operations O(1), but most definitely not all three you need here. Check for example for Python: wiki.python.org/moin/TimeComplexity#list \$\endgroup\$
    – tokland
    Commented Mar 3, 2014 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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