Я пытаюсь выяснить, какова временная сложность этого кода, который решает проблему скользящего максимума

Я пробовал использовать 2 вложенных цикла, но это было бы сложнее O (n * k), и я думаю, что приведенный ниже код менее сложный

   res=[]
  for i in 0..(array.length-k) do 
   res <<  array.slice(i,k).sort[-1]
  end
  return res 
  

Я хочу знать, какова сложность используемых методов по умолчанию (Ruby) и как они влияют на сложность этого цикла. Спасибо

Вот Enumerator решение, которое кажется самым быстрым для больших наборов данных (k> ~ 65)

 def sliding_max(arr,k)
  a = arr.dup
  b = a.shift(k)
  max_n = n = b.max
  Enumerator.new do |y|
    y << max_n
    loop do 
      break if a.empty?
      b.<<(a.shift)
      max_n = b.max if b.shift == max_n || b.last > max_n
      y << max_n 
    end
  end.to_a    
end
  

Здесь мы вычисляем max только в том случае, если число, удаленное из массива, было равно max или добавляемое значение больше текущего максимума.

Вот еще один тест, который показывает, как меняется относительная эффективность по мере k увеличения размера каждого фрагмента.

 require 'benchmark'

def test(arr, k)
  puts "Testing for k = #{k}"
  Benchmark.bm(11) do |x|
  

     x.report("Wonder Boy") {
      res=[]
      for i in 0..(arr.length-k) do
        res << arr.slice(i,k).max
      end
      res
    }
  

     x.report("Tadman") { arr.each_cons(k).map(amp;:max) }
  

     x.report("Cary") {
      (k..arr.size-1).each_with_object([arr.first(k).max]) do |i,a|
        mx = a.last
        a << (arr[i-k] < mx ? [mx, arr[i]] : arr[i-k 1, k]).max
      end
    }
  

     x.report("Engineer 1") {
      a = arr.dup
      b = a.shift(k)
      max_n = n = b.max
      Enumerator.new do |y|
        y << max_n
        loop do 
          break if a.empty?
          b.<<(a.shift)
          max_n = b.max if b.shift == max_n || b.last > max_n
          y << max_n 
        end
      end.to_a    
    }
  

     x.report("Engineer 2") {
      a = arr.dup
      b = a.shift(k)
      max_n = n = b.max
      Enumerator.new do |y|
        y << max_n
        loop do 
          break if a.empty?
          b.<<(a.shift)
          max_n = (b.shift == max_n) ? b.max : [max_n, b.last].max
          y << max_n 
        end
      end.to_a    
    }
  end
end
  

 arr = 10000.times.map { rand(100) } 
arr.first(4)
  #=> [61, 13, 41, 82]
  

 test(arr, 3)
Testing for k = 3
                  user     system      total        real
Wonder Boy    0.021185   0.004539   0.025724 (  0.025695)
Tadman        0.004801   0.000000   0.004801 (  0.004809)
Cary          0.004542   0.000000   0.004542 (  0.004568)
Engineer 1    0.003998   0.000000   0.003998 (  0.004005)
Engineer 2    0.003427   0.000000   0.003427 (  0.003438)
  

 test(arr, 10)
Testing for k = 10
                  user     system      total        real
Wonder Boy    0.003102   0.000000   0.003102 (  0.003105)
Tadman        0.003205   0.000012   0.003217 (  0.003225)
Cary          0.003286   0.000000   0.003286 (  0.003292)
Engineer 1    0.003387   0.000000   0.003387 (  0.003397)
Engineer 2    0.003092   0.000000   0.003092 (  0.003100)
  

 test(arr, 30)
Testing for k = 30
                  user     system      total        real
Wonder Boy    0.011111   0.000000   0.011111 (  0.011139)
Tadman        0.010568   0.000000   0.010568 (  0.010572)
Cary          0.004292   0.000000   0.004292 (  0.004301)
Engineer 1    0.004197   0.000000   0.004197 (  0.004203)
Engineer 2    0.003759   0.000000   0.003759 (  0.003766)
  

 test(arr, 100)
Testing for k = 100
                  user     system      total        real
Wonder Boy    0.007409   0.000035   0.007444 (  0.007437)
Tadman        0.005771   0.000914   0.006685 (  0.006703)
Cary          0.002773   0.000000   0.002773 (  0.002782)
Engineer 1    0.003213   0.000000   0.003213 (  0.003222)
Engineer 2    0.003138   0.000005   0.003143 (  0.003150)
  

 test(arr, 1000)
Testing for k = 1000
                  user     system      total        real
Wonder Boy    0.019694   0.000000   0.019694 (  0.019696)
Tadman        0.031178   0.012383   0.043561 (  0.043571)
Cary          0.005782   0.000000   0.005782 (  0.005788)
Engineer 1    0.002446   0.000000   0.002446 (  0.002431)
Engineer 2    0.002395   0.000000   0.002395 (  0.002396)
  

Наиболее показательным результатом почти наверняка является результат для k = 100 .

Часто помогает начать с сокращения кода до самого необходимого:

 (array.length-k).times.map |i|
  array.slice(i,k).max
end
  

Где sort здесь можно убрать, сделав линейное время для этой операции. Обычно sort считается O(log n).

В конечном счете это O (n²), если только вы не сможете исключить внутренний или внешний цикл.

Если цель здесь состоит в том, чтобы найти все максимальные значения во всех возможных подмножествах массива, вероятно, существует алгоритм, который может это сделать.

 require 'benchmark'

def sliding_maximum(k, array)


 time=Benchmark.realtime do
=begin  
             my proposition >
  res=[]
  for i in 0..(array.length-k) do 
   res <<  array.slice(i,k).max
  end
  #return res  
=end     # time => 8.9185999968322e-05


=begin      
              @Cary's proposition >
(k..array.size-1).each_with_object([array.first(k).max]) do |i,a|
    mx = a.last
    a << (array[i-k] < mx ? [mx, array[i]] : array[i-k 1, i]).max
  end
=end    # time => 0.0001353049992758315


=begin     
           @tadman proposition 
 #array.each_cons(k).map(amp;:max)
=end     time 7.903100049588829e-05
 end 
 p time 

end

sliding_maximum(3, [1, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9, 3, 5, 7, 9])

  

Это код, в котором я пытался вычислить выполнение в реальном времени каждого предложения, включая мое. Не стесняйтесь изменять переданный массив или K, чтобы увидеть разницу в выполнении. Что касается меня, я вижу, что предложение @tadman (третье) работает быстрее для больших массивов.

Как работает метод

Я могу объяснить основную идею подхода, который я использовал здесь, на примере. Предположим, что массивом были [1 , 3, 2, 4] и k = 3 , и мы уже вычислили [1, 3, 2].max #=> 3 . Тогда, поскольку 1 < [1, 3, 2].max мы знаем это [3, 2].max == [1, 3, 2].max #=> true . Следовательно, мы можем вычислить [3, 2, 4].max , сравнив два известных значения: [[3, 2].max, 4].max => [3, 4] => 4 . Это небольшая экономия вычислительного времени для k = 3 , но она будет увеличиваться со значением k .

Вычислительная эффективность

Приведенный ниже метод имеет (в наихудшем случае) вычислительную сложность O( n*k ) ( n = arr.size ), но случайно сгенерированные массивы в среднем должны требовать чего-то вроде (n-k)*(1 2*(k-1)/k) операций.

Методы грубой силы, которые вычисляют a.max для каждого k фрагмента a массива, требуют (n-k)*k операций. Следовательно, для случайно сгенерированных массивов отношение количества операций, требуемых моим методом, к количеству операций, используемых методами грубой силы, составляет приблизительно

 (n-k)*(1 2*(k-1)/k)/(n-k)*k
  #=> (1 2*(k-1)/k)/k
  

Для k = 3 это соотношение равно 0.77 , но этот метод все еще может быть в невыгодном положении из-за вычислительных затрат. По мере k увеличения числитель приближается 3 , поэтому отношение приближается 3/k . Поэтому, по сравнению с методами грубой силы, мой метод будет приносить все более значительные дивиденды по мере k продвижения.

Код

 def sliding_max(arr, k)
  return nil if k > arr.size
  (k..arr.size-1).each_with_object([arr.first(k).max]) do |i,a|
    mx = a.last
    a << (arr[i-k] < mx ? [mx, arr[i]] : arr[i-k 1, k]).max
  end
end
  

Примеры

 sliding_max([1, 4, 2, 3, 2, 1, 0], 3)
  #=> [4, 4, 3, 3, 2]
sliding_max([1, 2, 3, 4, 5, 6, 7], 3)
  #=> [3, 4, 5, 6, 7] (fastest)
sliding_max([7, 6, 5, 4, 3, 2, 1], 3)
  #=> [7, 6, 5, 4, 3] (slowest)
  

Объяснение

Давайте пошагово рассмотрим метод для следующих аргументов.

 arr = [1, 4, 2, 3, 2, 1, 4]
k = 3

return nil if k > arr.size
  #=> return nil if 3 > 7 => false
a = [arr.first(k).max]
  #=> [[1, 4, 2].max] => [4]
enum = (k..arr.size-1).each_with_object(a)
  #=> #<Enumerator: 3..6:each_with_object([4])>
  

Генерируется первый элемент и передается в блок, а переменным блока присваиваются значения.

 i, a = enum.next
  #=> [3, [4]] 
i #=> 3 
a #=> [4] 
  

Теперь выполняется вычисление блока.

 mx = a.last
  #=> 4
arr[i-k] < mx
  #=> arr[3-3] < mx => 1 < 4 => true
  

итак, выполните

 b = [mx, arr[i]].max
  #=> [4, arr[3]].max => [4, 3].max => 4
a << b
  #=> [4, 4]
  

Следующее значение генерируется enum , передается в блок, переменным блока присваиваются значения и выполняется вычисление блока.

 i, a = enum.next
  #=> [4, [4, 4]] 
i #=> 4 
a #=> [4, 4] 
mx = a.last
  #=> 4 
arr[i-k] < mx
  #=> arr[4-3] < 4 => 4 < 4 => false 
  

Итак, на этот раз мы должны выполнить более дорогостоящее вычисление.

 b = arr[i-k 1, k].max
  #=> arr[4-3 1, 4].max => [2, 3, 2].max => 3
a << b
  #=> [4, 4, 3]
  

Остальные вычисления аналогичны.