Почему [20,..., 13, 14].min(2) => [13, 20]? - программирование

Почему это не [13, 14]? И как сделать я получаю то, что хочу, два самых маленьких элемента (в линейном времени)?

Предложение doc "Если аргумент n задан, минимальные n элементов возвращаются как массив" мне не совсем понятно, но я думаю, что он говорит, что min(2) должен дать мне самые маленькие два элемента. Я не мог много узнать об этом, но этот поток, который может быть источником, кажется, согласен со мной и говорит, что он должен вернуть то же, что и sort.first(n), чего нет:

Извините, если тупой вопрос и извините за "большой" пример, но это уже уменьшено - удаление еще одного номера (кроме 13 или 14) дает мне [13, 14].

Ответы

Ответ 1

Я только что опубликовал объяснение ошибки в системе отслеживания ошибок Ruby:

Полагаю, я нашел проблему. Взяв первый пример:
[20, 32, 32, 21, 30, 25, 29, 13, 14].min(2)
Это вызовет функцию "nmin_run" в файле "enum.c", которая устанавливает "bufmax" в 4 раза больше минимальных (n) минимумов (для Например, bufmax равно 8), а затем в строке 1327 вызовет функция "nmin_i" для каждого элемента исходного массива.

В функции "nmin_i" , когда буфер заполнен ( "data- > curlen == data- > bufmax" ), вызывается функция "nmin_filter". В примере, это происходит, когда curlen равно 8, и поэтому буфер [20, 32, 32, 21, 30, 25, 29, 13]. "Nmin_filter" будет выполнять quicksort до тех пор, пока n наименьшие элементы находятся в самой левой части буфера, и отбросит остальные элементы, что оставляет нас с [20, 13] в буфере.

И теперь начинается проблема. В конце "nmin_filter" предел (по-видимому, с целью сохранения наибольшего значения в buffer) устанавливается на последнее значение в буфере (в примере 13), что неверно. И затем, основываясь на этом значении, "nmin_i" отбросит все остальные элементы больше этого (в примере, отбрасывая пункт 14). Затем буфер сортируется и возвращается:
[13, 20]
Таким образом, решение либо удаляет всю связанную с ограничением часть, либо принимает последний стержень как предел.

Ответ 2

Кстати, отвечая на ваш вопрос...

И как делать Я получаю то, что хочу, два самых маленьких элемента (в линейном времени)?

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

Вот мой прямой перевод из Википедии:

class Array
  def mymin(n)
    return self.sort if self.size <= n

    a = self.dup
    left = 0
    right = a.size - 1
    loop do
      pivot_index = left + (right - left) / 2;
      pivot_value = a[pivot_index]
      a[pivot_index], a[right] = a[right], a[pivot_index]
      store_index = left
      left.upto(right - 1).each do |i|
         if a[i] < pivot_value
           a[store_index], a[i] = a[i], a[store_index]
           store_index += 1
         end
      end
      a[right], a[store_index] = a[store_index], a[right]
      if n - 1 == store_index
        break
      elsif n - 1 < store_index
        right = store_index - 1
      else
        left = store_index + 1
      end
    end
    a.take(n).sort
  end
end

И затем мы попробуем ваш пример:

[20, 32, 32, 21, 30, 25, 29, 13, 14].mymin(2)
# => [13, 14]

Ура! Мы только что установили min. Помните, однако, что эта реализация имеет пространственную сложность, линейную по размеру исходного массива, тогда как реализация Ruby линейна по отношению к значению n. Кроме того, если в вашем исходном массиве слишком много дубликатов, это будет иметь плохую производительность, и вы должны искать 3-полосное разбиение.

Если вы хотите только min для n = 2 и действительно обеспокоены производительностью, можно сделать оптимизированную версию для этого случая с O(L) гарантированной (если L - длина массива).

class Array
  def min2
    m1 = nil
    m2 = nil
    self.each do |x|
      if m1.nil? || x < m1
        m2 = m1
        m1 = x
      elsif m2.nil? || x < m2
        m2 = x
      end
    end
    [m1, m2].compact
  end
end

И используйте его аналогичным образом:

[20, 32, 32, 21, 30, 25, 29, 13, 14].min2
# => [13, 14]