Как оптимизировать программу с двумя циклами

Question

У меня есть следующая программа

def calc_res(a)
  n = a.length
  result = 0
  for i in 0 .. (n - 1)
    for j in i .. (n - 1)
      if (a[i] != a[j] && j - i > result) then
        result = j - i
      end
    end
  end
  return result
end

, которая возвращает следующий вывод

irb(main):013:0> calc_res([4, 6, 2, 2, 6, 6, 4])
=> 5

, но если размер массива слишком велик, например, [0,1,2,3,.....70000]

* 1009, требуется время* может ли кто-нибудь подсказать мне, как я могу его оптимизировать?

Спасибо

Answer 1

Более рубиновые версии включают в себя:

def calc_res(a)
  last = a.last
  idx = a.find_index {|e| e != last }&.+(1) || a.size
  a.size - idx
end

def calc_res(a)
  last = a.last
  a.size - a.each.with_index(1).detect(->{[a.size]}) {|e,_| e != last }.last 
end

def calc_res(a)
  last = a.last
  a.reduce(a.size) do |memo, e| 
    return memo unless e == last
    memo -= 1
  end
end

def calc_res(a)
  return 0 if b = a.uniq and b.size == 1
  a.size - a.index(b[-1]).+(1)
end

Answer 2

Насколько я понимаю, проблема состоит в том, чтобы найти два уникальных элемента в массиве, расстояние между которыми (разность индексов) является максимальным, и вернуть расстояние, на которое они разделены.Я возвращаю nil, если все элементы одинаковы.

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

def calc_res(a)
  sz = a.size-1
  sz.downto(2).find { |n| (0..sz-n).any? { |i| a[i] != a[i+n] } }
end

a = [4,6,2,2,6,6,4]
calc_res a
  #=> 5

Если sz = a.size-1, sz - максимально возможное расстояние, два элемента могут быть разделены.Если, например, a = [1,2,3,4], sz = 3, то есть количество позиций 1 и 4, находятся на расстоянии друг от друга.

Для a, sz = a.size-1 #=> 6.Сначала я определяю, являются ли какие-либо пары элементов, которые находятся на расстоянии n = sz, уникальными.[a[0], a[6]] #=> [4,4] является единственной парой элементов 6, расположенных отдельно.Поскольку они не уникальны, я уменьшаю n на единицу (до 5) и исследую все пары элементов на n позиции друг от друга, ища тот, чьи элементы являются уникальными.Различаются две пары 5 позиций: [a[0], a[5]] #=> [4,6] и [a[1], a[6]] #=> [6,4].Оба они соответствуют тесту, поэтому мы закончили и возвращаем n #=> 5.Фактически мы закончили тестирование первой из этих двух пар.Если бы ни эти пары не содержали уникальных значений, n было бы уменьшено на 1 до 4, а три пары [a[0], a[4]] #=> [4,6], [a[1], a[5]] #=> [6,6] и [a[2], a[6]] #=> [2,6] были бы найдены для поиска одной с уникальными значениями и т. Д..

См. Integer # downto , Enumerable # find и Enumerable # any? .

Answer 3

Если я понял проблему, которую вы пытаетесь решить (из кода)

def calc_res(a)
  last_index = a.length - 1
  index = 0
  while a[index] == a.last do
    index = index + 1
    break if index == last_index
  end
  last_index - index
end

Он проверяет элементы от начала, если они равны элементам от конца, конец он перемещает индекс в направлении последнего элемента,Как я понял, вы ищете максимальную длину между различными элементами.

Для вас проблема с [4, 6, 2, 2, 6, 6, 4] будет иметь одну итерацию и вернет 5, для проблемы с[1 ... 70000] он будет иметь ноль итераций и вернет разницу в позициях для этих двух (размер массива - 1)