c++ - read - vector double

¿Cómo se implementa nth_element?

Question

Hay muchos reclamos en StackOverflow y en otros lugares que nth_element es O (n) y que normalmente se implementa con Introselect: http://en.cppreference.com/w/cpp/algorithm/nth_element

Quiero saber cómo se puede lograr esto. Miré la explicación de Introselect de Wikipedia y eso me dejó más confundido. ¿Cómo puede un algoritmo cambiar entre QSort y Median-of-Medians?

Encontré el documento de Introsort aquí: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep=rep1&type=pdf Pero eso dice:

En este documento, nos concentramos en el problema de clasificación y volvemos al problema de selección solo brevemente en una sección posterior.

He intentado leer el STL en sí mismo para comprender cómo se implementa nth_element , pero eso se vuelve peludo muy rápido.

¿Alguien podría mostrarme un pseudocódigo sobre cómo se implementa Introselect? O incluso mejor, el código real de C ++ que no sea el STL, por supuesto :)

Answer 1

Descargo de responsabilidad: No sé cómo se implementa std::nth_element en cualquier biblioteca estándar.

Si sabe cómo funciona Quicksort, puede modificarlo fácilmente para hacer lo que se necesita para este algoritmo. La idea básica de Quicksort es que en cada paso, se divide la matriz en dos partes, de manera que todos los elementos menos que el pivote están en la sub-matriz izquierda y todos los elementos iguales o mayores que el pivote están en la sub-matriz derecha . (Una modificación de Quicksort conocida como Quicksort ternaria crea una tercera sub-matriz con todos los elementos iguales al pivote. Luego, la sub-matriz derecha solo contiene entradas estrictamente mayores que el pivote). Quicksort luego procede clasificando recursivamente el sub izquierdo y derecho -artículos.

Si solo desea mover el elemento n -ésimo en su lugar, en lugar de recurrir a ambas subarreglas, puede indicar en cada paso si tendrá que descender hacia la subinterfaz izquierda o derecha. (Lo sabe porque el n -ésimo elemento en una matriz ordenada tiene un índice n, por lo que se convierte en una cuestión de comparar índices). Por lo tanto, a menos que su Quicksort sufra la peor degeneración, se reduce el tamaño de la matriz restante en cada paso. . (Nunca vuelvas a mirar la otra sub-matriz.) Por lo tanto, en promedio, estás tratando con matrices de las siguientes longitudes en cada paso:

1. Θ ( N )
2. Θ ( N / 2)
3. Θ ( N / 4)
4. ...

Cada paso es lineal en la longitud de la matriz que está tratando. (Lo recorres una vez y decides en qué sub-matriz debe ir cada elemento dependiendo de cómo se compara con el pivote).

Puede ver que después de los pasos Θ (log ( N )), eventualmente llegaremos a una matriz Singleton y habremos terminado. Si sumas N (1 + 1/2 + 1/4 +…), obtendrás 2 N. O, en el caso promedio, ya que no podemos esperar que el pivote siempre sea exactamente la mediana, algo del orden de Θ ( N ).

Answer 2

El código del STL (versión 3.3, creo) es este:

template <class _RandomAccessIter, class _Tp>
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
                   _RandomAccessIter __last, _Tp*) {
  while (__last - __first > 3) {
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1))));
    if (__cut <= __nth)
      __first = __cut;
    else 
      __last = __cut;
  }
  __insertion_sort(__first, __last);
}

Simplifiquemos eso un poco:

template <class Iter, class T>
void nth_element(Iter first, Iter nth, Iter last) {
  while (last - first > 3) {
    Iter cut =
      unguarded_partition(first, last,
                          T(median(*first,
                                   *(first + (last - first)/2),
                                   *(last - 1))));
    if (cut <= nth)
      first = cut;
    else 
      last = cut;
  }
  insertion_sort(first, last);
}

Lo que hice aquí fue eliminar los guiones bajos y las cosas en mayúsculas, que es solo para proteger el código de cosas que el usuario podría definir legalmente como macros. También eliminé el último parámetro, que solo se supone que ayuda en la deducción del tipo de plantilla, y renombré el tipo de iterador por brevedad.

Como debe ver ahora, divide el rango repetidamente hasta que menos de cuatro elementos permanecen en el rango restante, que luego se clasifica simplemente.

Ahora, ¿por qué es eso O (n)? En primer lugar, la clasificación final de hasta tres elementos es O (1), debido al máximo de tres elementos. Ahora, lo que queda es la partición repetida. La partición en sí misma es O (n). Aquí, sin embargo, cada paso reduce a la mitad el número de elementos que deben tocarse en el siguiente paso, por lo que tiene O (n) + O (n / 2) + O (n / 4) + O (n / 8), que es menos que O (2n) si lo sumas. Como O (2n) = O (n), tiene una complejidad de linar en promedio.

Answer 3

Hiciste dos preguntas, la titular

¿Cómo se implementa nth_element?

A lo que ya respondiste:

Hay muchos reclamos en y en otros lugares que nth_element es O (n) y que normalmente se implementa con Introselect.

Lo cual también puedo confirmar al ver mi implementación estándar. (Más sobre esto más adelante.)

Y aquel en el que no entiendes la respuesta:

¿Cómo puede un algoritmo cambiar entre QSort y Median-of-Medians?

Veamos el pseudo código que extraje de mi stdlib:

nth_element(first, nth, last)
{ 
  if (first == last || nth == last)
    return;

  introselect(first, nth, last, log2(last - first) * 2);
}

introselect(first, nth, last, depth_limit)
{
  while (last - first > 3)
  {
      if (depth_limit == 0)
      {
          // [NOTE by editor] This should be median-of-medians instead.
          // [NOTE by editor] See Azmisov''s comment below
          heap_select(first, nth + 1, last);
          // Place the nth largest element in its final position.
          iter_swap(first, nth);
          return;
      }
      --depth_limit;
      cut = unguarded_partition_pivot(first, last);
      if (cut <= nth)
        first = cut;
      else
        last = cut;
  }
  insertion_sort(first, last);
}

Sin entrar en detalles sobre las funciones referenciadas heap_select y heap_select , podemos ver claramente que nth_element proporciona pasos de subdivisión introselect 2 * log2(size) (el doble de lo necesario por quickselect en el mejor de los casos) hasta que heap_select inicia el problema bueno.