Поиск максимального отклонения

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

В принципе, вы должны найти максимальное отклонение от заданного количества последовательных целых чисел. Есть два входа; первый аргумент - это массив целых чисел, а второй аргумент - количество последовательных целых чисел. И вы печатаете максимальное отклонение. Например, если у вас есть [10, 1, 5, 2, 6, 3] и 3 в качестве аргументов, выход должен быть равен 9, поскольку [10, 1, 5] даст максимальное отклонение 9 (10-1).

Можно ли реорганизовать его быстрее?

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
11 голосов | спросил yangtheman 16 FebruaryEurope/MoscowbSun, 16 Feb 2014 12:17:42 +0400000000pmSun, 16 Feb 2014 12:17:42 +040014 2014, 12:17:42

1 ответ


10

Некоторые примечания:

  • find_deviation(v, d): попробуйте написать более значимые имена для переменных. Специально, я бы дал имя плюрара для v, так как это коллекция.

  • max = 0, each, inline if: Все это означает, что вы думаете в императивных терминах. Некоторые заметки о функциональном программировании с Ruby .

Я бы написал с функциональным подходом:

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

Теперь эта функция имеет точно такую ​​же временную сложность, что и ваша (хотя она может быть быстрее или медленнее в зависимости от того, как работает Ruby). Сложность: len (значения) = n -> О (п * м). Обратите внимание, что вы можете использовать Enumerable # minmax, чтобы избежать обхода, но все равно такая же сложность.

Чтобы сделать это быстрее, вот идея, хотя это не так просто: используйте структуру с O (log n) раз для вставки /удаления /max /min (для этого идеально подходит дерево двоичного поиска) для хранения значений Скользящего окна, таким образом, общая сложность O (n log m). Я думаю, что некоторые из тестов имеют большие значения m, поэтому тривиальный подход O (n m) слишком медленный.

[править] Просто для удовольствия я написал реализацию O (n log m) в Haskell (я не нашел BST-камень для 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
ответил tokland 16 FebruaryEurope/MoscowbSun, 16 Feb 2014 16:28:41 +0400000000pmSun, 16 Feb 2014 16:28:41 +040014 2014, 16:28:41

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132