¿Por qué std::list::reverse tiene complejidad O(n)?

10 minutos de lectura

avatar de usuario
Curioso

¿Por qué la función inversa para el std::list ¿La clase en la biblioteca estándar de C ++ tiene un tiempo de ejecución lineal? Yo pensaría que para las listas doblemente enlazadas, la función inversa debería haber sido O (1).

Invertir una lista doblemente enlazada solo debería implicar cambiar los punteros de la cabeza y la cola.

  • No entiendo por qué la gente vota negativamente esta pregunta. Es una pregunta perfectamente razonable de hacer. Invertir una lista doblemente enlazada debería llevar O(1) tiempo.

    – Curioso

    24/02/2016 a las 20:23

  • desafortunadamente, algunas personas confunden los conceptos de “la pregunta es buena” con “la pregunta tiene una buena idea”. Me encantan las preguntas como esta, donde básicamente “mi comprensión parece diferente a una práctica comúnmente aceptada, por favor ayuda a resolver este conflicto”, porque expandir tu forma de pensar te ayuda a resolver muchos más problemas en el futuro. Parecería que otros adoptan el enfoque de “eso es un desperdicio de procesamiento en el 99.9999% de los casos, ni siquiera lo pienses”. Si te sirve de consuelo, ¡me han votado negativo por mucho, mucho menos!

    – CorsiKa

    24/02/2016 a las 22:31

  • Sí, esta pregunta obtuvo una cantidad desmesurada de votos negativos por su calidad. Probablemente sea el mismo que votó a favor de la respuesta de Blindy. Para ser justos, “invertir una lista doblemente enlazada debería implicar simplemente cambiar los punteros de cabeza y cola” generalmente no es cierto para la impl de lista enlazada estándar que todos aprenden en la escuela secundaria, o para muchas implementaciones que la gente usa. Muchas veces, en SO, la reacción visceral inmediata de las personas a la pregunta o respuesta impulsa la decisión de votar a favor o en contra. Si hubieras sido más claro en esa oración o la hubieras omitido, creo que habrías obtenido menos votos negativos.

    – Chris Beck

    25 de febrero de 2016 a las 8:53

  • O déjame poner la carga de la prueba contigo, @Curious: he preparado una implementación de lista doblemente enlazada aquí: ideone.com/c1HebO. ¿Puede indicar cómo esperaría que Reverse función que se implementará en O(1)?

    – CompuChip

    25 de febrero de 2016 a las 10:58

  • @CompuChip: en realidad, según la implementación, es posible que no. No necesita un booleano adicional para saber qué puntero usar: simplemente use el que no le apunta a usted… lo que bien podría ser automático con una lista enlazada con XOR por cierto. Entonces, sí, depende de cómo se implemente la lista, y la declaración OP podría aclararse.

    – Matthieu M.

    25 de febrero de 2016 a las 13:33

Hipotéticamente, reverse podría haber sido O(1). Allí (nuevamente hipotéticamente) podría haber un miembro de la lista booleana que indica si la dirección de la lista vinculada es actualmente la misma o la opuesta a la dirección original donde se creó la lista.

Desafortunadamente, eso reduciría el rendimiento de básicamente cualquier otra operación (aunque sin cambiar el tiempo de ejecución asintótico). En cada operación, sería necesario consultar un booleano para considerar si seguir un puntero “siguiente” o “anterior” de un enlace.

Dado que presumiblemente esto se consideraba una operación relativamente poco frecuente, el estándar (que no dicta las implementaciones, solo la complejidad), especificó que la complejidad podría ser lineal. Esto permite que los punteros “siguiente” siempre signifiquen la misma dirección sin ambigüedades, lo que acelera las operaciones de casos comunes.

  • @MooseBoys: no estoy de acuerdo con tu analogía. La diferencia es que, en el caso de una lista, la implementación podría proporcionar reverse con O(1) complejidad sin afectar el gran-o de cualquier otra operación, mediante el uso de este truco de bandera booleana. Pero, en la práctica, una rama adicional en cada operación es costosa, incluso si técnicamente es O(1). Por el contrario, no puede crear una estructura de lista en la que sort es O(1) y todas las demás operaciones tienen el mismo costo. El punto de la pregunta es que, aparentemente, puedes obtener O(1) revertir gratis si solo te importa Big O, entonces, ¿por qué no lo hicieron?

    – Chris Beck

    24 de febrero de 2016 a las 22:49

  • Si usó una lista vinculada a XOR, la inversión se convertiría en tiempo constante. Sin embargo, un iterador sería más grande, e incrementarlo/disminuirlo sería un poco más costoso computacionalmente. Eso podría verse eclipsado por los inevitables accesos a la memoria aunque para ningún tipo de lista enlazada.

    – Deduplicador

    25 de febrero de 2016 a las 1:26

  • @IlyaPopov: ¿Todos los nodos realmente necesitan esto? El usuario nunca hace preguntas al nodo de la lista en sí, solo al cuerpo de la lista principal. Por lo tanto, acceder al valor booleano es fácil para cualquier método al que llame el usuario. Podría establecer la regla de que los iteradores se invaliden si la lista se invierte y/o almacenar una copia del valor booleano con el iterador, por ejemplo. Así que creo que no afectaría necesariamente a la gran O. Lo admito, no revisé la especificación línea por línea. 🙂

    – Chris Beck

    25 de febrero de 2016 a las 3:47


  • @Kevin: Hm, ¿qué? No puede xor dos punteros directamente de todos modos, primero debe convertirlos en números enteros (obviamente del tipo std::uintptr_t. Después puedes xor ellos.

    – Deduplicador

    25 de febrero de 2016 a las 5:40

  • @Kevin, definitivamente podría hacer una lista vinculada XOR en C ++, es prácticamente el lenguaje infantil del cartel para este tipo de cosas. Nada dice que tienes que usar std::uintptr_tpodrías enviar a un char matriz y luego XOR los componentes. Sería más lento pero 100% portátil. Probablemente podría hacer que seleccione entre estas dos implementaciones y solo usar la segunda como alternativa si uintptr_t Está perdido. Algunos si se describen en esta respuesta: stackoverflow.com/questions/14243971/…

    – Chris Beck

    25 de febrero de 2016 a las 6:41


avatar de usuario
5gon12eder

Eso pudo ser O(1) si la lista almacenaría una bandera que permite intercambiar el significado de “prev” y “next” punteros que tiene cada nodo. Si invertir la lista fuera una operación frecuente, dicha adición podría ser útil y no conozco ninguna razón por la cual implementarla sería prohibido por la norma actual. Sin embargo, tener tal bandera haría ordinario el recorrido de la lista más caro (aunque sólo sea por un factor constante) porque en lugar de

current = current->next;

en el operator++ del iterador de lista, obtendrías

if (reversed)
  current = current->prev;
else
  current = current->next;

que no es algo que decidirías agregar fácilmente. Dado que las listas generalmente se recorren con mucha más frecuencia de lo que se invierten, sería muy imprudente que el estándar mandato esta tecnica. Por lo tanto, se permite que la operación inversa tenga complejidad lineal. Tenga en cuenta, sin embargo, que tO(1) ⇒ tO(norte) por lo que, como se mencionó anteriormente, se permitiría implementar su “optimización” técnicamente.

Si proviene de un entorno Java o similar, es posible que se pregunte por qué el iterador tiene que verificar la bandera cada vez. ¿No podríamos tener dos tipos de iteradores distintos, ambos derivados de un tipo base común, y tener std::list::begin y std::list::rbegin devolver polimórficamente el iterador apropiado? Si bien es posible, esto empeoraría aún más las cosas porque avanzar el iterador sería una llamada de función indirecta (difícil de alinear) ahora. En Java, está pagando este precio de forma rutinaria de todos modos, pero, de nuevo, esta es una de las razones por las que muchas personas recurren a C++ cuando el rendimiento es crítico.

Como señaló Benjamin Lindley en los comentarios, desde reverse no está permitido invalidar los iteradores, el único enfoque permitido por el estándar parece ser almacenar un puntero a la lista dentro del iterador, lo que provoca un doble acceso indirecto a la memoria.

  • @galinette: std::list::reverse no invalida los iteradores.

    – Benjamín Lindley

    24 de febrero de 2016 a las 21:08

  • @galinette Lo siento, leí mal su comentario anterior como “bandera por iterador” en lugar de “bandera por nodo” como lo escribiste. Por supuesto, una bandera por nodo sería contraproducente ya que, nuevamente, tendría que hacer un recorrido lineal para voltearlos a todos.

    – 5gon12eder

    24/02/2016 a las 21:30


  • @ 5gon12eder: podría eliminar la ramificación a un costo muy bajo: almacene el next y prev punteros en una matriz y almacenar la dirección como un 0 o 1. Para iterar hacia adelante, seguirías pointers[direction] y para iterar a la inversa pointers[1-direction] (o viceversa). Esto aún agregaría un poco de sobrecarga, pero probablemente menos que una rama.

    – Jerry Ataúd

    25 de febrero de 2016 a las 6:22

  • Probablemente no pueda almacenar un puntero a la lista dentro de los iteradores. swap() se especifica para que sea un tiempo constante y no invalide ningún iterador.

    –Tavian Barnes

    25 de febrero de 2016 a las 19:13

  • @TavianBarnes ¡Maldita sea! Bueno, triple indirección entonces… (Quiero decir, no realmente triple. Tendrías que almacenar la bandera en un objeto asignado dinámicamente, pero el puntero en el iterador, por supuesto, puede apuntar directamente a ese objeto en lugar de indirectamente sobre la lista).

    – 5gon12eder

    25 de febrero de 2016 a las 23:09


Seguramente, dado que todos los contenedores que admiten iteradores bidireccionales tienen el concepto de rbegin() y rend(), ¿esta pregunta es discutible?

Es trivial construir un proxy que invierta los iteradores y acceda al contenedor a través de eso.

Esta no operación es de hecho O(1).

como:

#include <iostream>
#include <list>
#include <string>
#include <iterator>

template<class Container>
struct reverse_proxy
{
    reverse_proxy(Container& c)
    : _c(c)
    {}

    auto begin() { return std::make_reverse_iterator(std::end(_c)); }
    auto end() { return std::make_reverse_iterator(std::begin(_c)); }

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); }

    Container& _c;
};

template<class Container>
auto reversed(Container& c)
{
    return reverse_proxy<Container>(c);
}

int main()
{
    using namespace std;
    list<string> l { "the", "cat", "sat", "on", "the", "mat" };

    auto r = reversed(l);
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));

    return 0;
}

Rendimiento esperado:

mat
the
on
sat
cat
the

Dado esto, me parece que el comité de normas no se ha tomado el tiempo de exigir O(1) orden inverso del contenedor porque no es necesario, y la biblioteca estándar se basa en gran medida en el principio de exigir solo lo estrictamente necesario mientras evitando la duplicación.

Solo mi 2c.

Porque tiene que atravesar cada nodo (n total) y actualizar sus datos (el paso de actualización es de hecho O(1)). Esto hace que toda la operación O(n*1) = O(n).

También intercambia puntero anterior y siguiente para cada nodo. Es por eso que se necesita Lineal. Aunque se puede hacer en O (1) si la función que usa este LL también toma información sobre LL como entrada, como si está accediendo normalmente o al revés.

avatar de usuario
danilobraga

Sólo una explicación del algoritmo. Imagina que tienes una matriz con elementos, luego necesitas invertirla. La idea básica es iterar en cada elemento cambiando el elemento de la primera posición a la última posición, el elemento de la segunda posición a la penúltima posición, y así sucesivamente. Cuando llegue a la mitad de la matriz, habrá cambiado todos los elementos, por lo tanto, en (n/2) iteraciones, lo que se considera O (n).

Es O(n) simplemente porque necesita copiar la lista en orden inverso. Cada operación de elemento individual es O (1) pero hay n de ellos en la lista completa.

Por supuesto, hay algunas operaciones de tiempo constante involucradas en la configuración del espacio para la nueva lista y el cambio de punteros después, etc. La notación O no considera constantes individuales una vez que incluye un factor n de primer orden.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad