-1
\$\begingroup\$

I acknowledge that this exact question was asked here. I was working on the same problem from the same website. I had the same question and consulted the above as a reference, however with respect to the person answering the question, it is the wrong answer. That is why I decided to restart this thread.

Problem

With an array of integer elements, I have to consider all sequences of d consecutive elements. For every sequence (there can be almost 100k of them) I must find the difference between the highest and lowest values in that sequence. All of this has to be accomplished in under 2 seconds.

This was the first solution that came to my mind, but as expected it couldn't find the solution in less than 2 seconds for some test cases.

def find_deviation(v,d)
  v.each_cons(d).to_a.map { |array|array.max - array.min}.max}
end

The answer given in that thread was

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

At first glance, that code looks nearly identical to mine, only with different variable names.

This puzzle had some pretty stringent data constraints

v: Array of integers

d: Integer value with the length of the sequence

  1. The array will contain up to 100,000 elements
  2. All elements in the array are integers in the range [1,2 ^ 31 - 1]
  3. The value of d is less than the length of the array.
  4. The algorithm has to solve in less than 2 seconds

In my solution, I'm using the each_cons method then mapping it.

The complexity is at least \$O(n^2)\$, which means this method will take way too long to solve.

With an array of 100,000 elements, and taking each_cons of more than 50,000 and then mapping them, this might take hours to solve.

I've tried generating random numbers like this.

v = 100000.times.map {(1..2**32-1).to_a.sample}
d = 97,854

and it will literally never finish.

Basically, I'm trying to find the bottlenecks in this code. I must be doing something wrong.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you missed the second half of the answer you linked, where it's suggested to use a binary search tree for fast min/max/insert/delete. \$\endgroup\$ – mjolka Sep 24 '14 at 4:27
4
\$\begingroup\$

First, don't use those functions to create the array, it takes forever because you are depleting the memory of the computer that way.

Use something like this:

v = Array.new(100000).map {rand (2**32-1)}

That is, v is a new array of size 100000, where each element is set to a random number between 0 and 232-1.

For d, don't put commas in the integer, just d=97854. (EDIT: or use _ as mentioned in by Devon in the comments)

As for a fast way to get the difference in the array, that's probably the core of the quiz, so I won't provide code. Hint: code it like you would do manually: check the max/min of the first interval and modify the max/min depending on the element in the array that you gain/lose when you shift the begining/ending of the interval. Sorry if I'm cryptic in the explanation; this is supposed to be only a hint!

\$\endgroup\$
  • 1
    \$\begingroup\$ Array.new(100000){ rand 2**32-1 } \$\endgroup\$ – Nakilon Sep 25 '14 at 9:59
  • \$\begingroup\$ Thank you, that hint should be enough to help me solve this. \$\endgroup\$ – Johnson Sep 25 '14 at 16:58
  • 1
    \$\begingroup\$ By the way, Ruby Style Guide says that you should separate large numbers with underscores. See github.com/bbatsov/ruby-style-guide#underscores-in-numerics \$\endgroup\$ – Devon Parsons Sep 26 '14 at 13:43
0
\$\begingroup\$

Based on Array#[] and Enumerable#each_cons I think the first one is faster since the last one should create a new enumerable object for each loop. Also instead of transverse each sub-array twice for min and for max I prefer to use Enumerable#minmax so the code should looks like:

def find_deviation(values, m)
  step = 0
  temp_results = []
  length = values.length
  while(step < length) do
    minmax = values[step, step = step + m].minmax
    temp_results << minmax[1] - minmax[0]
  end
  temp_results.max
end

I run some benchmarks for both your original method and my method:

a. my method

                 user     system      total        real
step 10     29.070000   0.000000  29.070000 ( 29.073000)
step 100     2.920000   0.000000   2.920000 (  2.921683)
step 1000    0.300000   0.000000   0.300000 (  0.295665)
step 10000   0.030000   0.000000   0.030000 (  0.035206)

b. your method

step 10      0.280000   0.000000   0.280000 (  0.286872)
step 100     1.770000   0.000000   1.770000 (  1.767475)
step 1000   16.390000   0.000000  16.390000 ( 16.398964)

It is still running for an 10000 step...

So I guess the best option is to mix both methods and use your original method for small steps and my method for big steps

\$\endgroup\$
  • \$\begingroup\$ Alright, I think I understand now. So for smaller arrays I should use my method and for larger arrays, use yours? That's what I understand from your benchmark tests. \$\endgroup\$ – Johnson Sep 25 '14 at 16:57
  • \$\begingroup\$ Let me try to explain, the values size is not important, the important is the m param, for small m your method is ok, for big m my method is ok \$\endgroup\$ – Aguardientico Sep 25 '14 at 16:58
  • \$\begingroup\$ Yeah, I just figured that out through testing. I'm going to use my method for small m and your method for big m and run benchmark tests again. \$\endgroup\$ – Johnson Sep 25 '14 at 17:03

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.