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\$
  • 1
    \$\begingroup\$ link to the code challenge to get the samples? \$\endgroup\$ – tokland Feb 16 '14 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 Feb 17 '14 at 8:32
  • \$\begingroup\$ @yangtheman, ok, but at least a link? is it a public challenge? \$\endgroup\$ – tokland Feb 17 '14 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 Feb 19 '14 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 Feb 20 '14 at 16:46
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\$
  • \$\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 Feb 17 '14 at 8:56
  • \$\begingroup\$ I did some research of my own and updated my question. What do you think? \$\endgroup\$ – yangtheman Mar 3 '14 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 Mar 3 '14 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 Mar 3 '14 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 Mar 3 '14 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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