ruby - ¿Por qué[20,…, 13, 14].min(2)=>[13, 20]?

Question

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

¿Por qué no es [13, 14] ? ¿Y cómo obtengo lo que quiero, los dos elementos más pequeños (en tiempo lineal)?

La oración del documento "Si se da el argumento n, los n elementos mínimos se devuelven como una matriz" no me queda muy claro, pero creo que dice que el min(2) debería darme los dos elementos más pequeños. No pude encontrar mucho al respecto, pero este hilo , que podría ser el origen, parece estar de acuerdo conmigo y dice que debería devolver lo mismo que sort.first(n) , que no:

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

Lo siento si la pregunta es tonta y lo siento por el ejemplo "grande", pero ya está reducido: eliminar un número más (que no sea 13 o 14) me da [13, 14] .

Answer 1

Acabo de publicar una explicación para el error en el sistema de seguimiento de problemas de Ruby :

Supongo que encontré el problema. Tomando el primer ejemplo:

[20, 32, 32, 21, 30, 25, 29, 13, 14].min(2)

Esto llamará a la función "nmin_run" en el archivo "enum.c", que establece "bufmax" a 4 veces el número de mínimos (n) que queremos (para el ejemplo, bufmax es 8), y luego en la línea 1327 Llamará a la función "nmin_i" para cada elemento de la matriz original.

En la función "nmin_i", cuando el búfer está lleno ("data-> curlen == data-> bufmax"), se llama a la función "nmin_filter". En el ejemplo, eso sucede cuando curlen es 8, y entonces el búfer es [20, 32, 32, 21, 30, 25, 29, 13]. El "nmin_filter" hará una ordenación rápida hasta que los n elementos más pequeños estén en la parte más a la izquierda del búfer, y descartará el resto de los elementos, lo que nos deja con [20, 13] en el búfer.

Y ahora empieza el problema. Al final de "nmin_filter", el límite (aparentemente con la intención de almacenar el mayor valor en el búfer) se establece en el último valor en el búfer (en el ejemplo, 13), que no es verdadero. Y luego, basado en ese valor, "nmin_i" descartará todos los elementos restantes mayores que eso (en el ejemplo, descartando los 14). El búfer se ordena y devuelve:

[13, 20]

Así que la solución es eliminar toda la parte relacionada con el límite o tomar el último pivote como límite.

Answer 2

Por cierto, respondiendo a tu pregunta ...

¿Y cómo obtengo lo que quiero, los dos elementos más pequeños (en tiempo lineal)?

Si este método no existía o, mientras tanto, se rompe, puede seleccionar los dos elementos más pequeños en tiempo lineal usando Quickselect , que es básicamente lo que Ruby hace en min debajo del capó.

Aquí está mi traducción directa de Wikipedia:

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

Y luego probamos tu ejemplo:

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

¡Hurra! Acabamos de arreglar el min . Sin embargo, tenga en cuenta que esta implementación tiene una complejidad de espacio lineal al tamaño del arreglo original, mientras que la implementación de Ruby es lineal al valor n . Además, si la matriz original tiene demasiados duplicados, esto tendrá un mal rendimiento y debería buscar
Partición de 3 vías.

Si solo desea el min para n = 2 y está realmente preocupado por el rendimiento, es posible hacer una versión optimizada para ese caso con O(L) garantizada (suponiendo que L es la longitud de la matriz).

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

Y utilízalo de forma análoga:

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