¿El hardware / implementación afectará la complejidad tiempo / espacio de los algoritmos?

32

Ni siquiera soy un estudiante de CS, así que esta podría ser una pregunta estúpida, pero por favor tengan paciencia conmigo ...

En la era anterior a la computadora, solo podemos implementar una estructura de datos de matriz con algo así como una matriz de cajones. Dado que uno tiene que ubicar el cajón con el índice correspondiente antes de extraerle el valor, la complejidad temporal de la búsqueda de matriz es , suponiendo una búsqueda binaria.O(log(n))

Sin embargo, la invención de las computadoras hizo una gran diferencia. Las computadoras modernas pueden leer desde su RAM tan rápido que ahora consideramos que la complejidad temporal de la búsqueda de matriz es (aunque técnicamente no es el caso, porque lleva más tiempo mover el registro a una distancia mayor, etc.)O(1)

Otro ejemplo son los diccionarios Python. Si bien uno puede obtener una complejidad de acceso al diccionario de con un método mágico sobrecargado mal escrito (o ridículamente mala suerte, es decir, claves que tienen muchas colisiones hash), generalmente se presume que es O ( 1 ) . En este caso, la complejidad del tiempo depende tanto de la implementación de la tabla hash de los diccionarios Python como de la implementación de las funciones hash de las teclas.O(n)__hash__O(1)

¿Esto implica que el hardware / implementación puede afectar la complejidad temporal de los algoritmos? (Si bien ambos ejemplos tratan sobre estructuras de datos en lugar de algoritmos, los últimos se basan en el primero, y nunca he oído hablar de la complejidad temporal de las estructuras de datos, por lo que estoy usando el término "algoritmos" aquí)

Para mí, los algoritmos son abstractos y conceptuales, cuyas propiedades como la complejidad del tiempo / espacio no deberían verse afectadas por si se implementan de una manera específica, pero ¿lo son?

nalzok
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Gilles 'SO- deja de ser malvado'

Respuestas:

42

Seguro. Ciertamente. Aquí le mostramos cómo conciliar su incomodidad.

O(logn)O(1)

Una vez que haya elegido un modelo de computación, el análisis del algoritmo es un ejercicio matemático puramente abstracto, conceptual, que ya no depende del hardware.

Sin embargo, en la práctica, generalmente queremos elegir un modelo de cálculo que refleje la realidad de nuestro hardware, al menos en un grado razonable. Entonces, si el hardware cambia, podríamos decidir analizar nuestros algoritmos bajo un modelo diferente de cómputo que sea más apropiado para el nuevo hardware. Así es como el hardware puede afectar el tiempo de ejecución.

La razón por la que esto no es obvio es porque, en las clases introductorias, a menudo no hablamos sobre el modelo de computación. Simplemente hacemos algunas suposiciones implícitamente, sin hacerlas explícitas. Eso es razonable, para fines pedagógicos, pero tiene un costo: oculta este aspecto del análisis. Ahora ya lo sabes.

DW
fuente
Como dijiste, usamos el modelo de acceso aleatorio como modelo de cálculo, pero cuando usamos GPU para ciertos cálculos, la complejidad del tiempo para algunos algoritmos cambia a medida que usa las instrucciones SIMD.
Deep Joshi
66
También tenga en cuenta que la notación O () es un límite superior. Incluso si utiliza la analogía del cajón, encontrar un cajón de tamaño limitado (la memoria real tiene un tamaño limitado) la construcción lleva O (1) tiempo. Incluso si le toma 20 minutos llegar al cajón más alejado (se pierde toda la memoria caché e incluso tiene que cargar los datos del intercambio), todavía es tiempo O (1) porque 20 minutos serán su constante oculta para acceder a la memoria.
Goswin von Brederlow
2
O(1)O(n)
1
@CortAmmon: incluso en una matriz grande, el uso de la búsqueda lineal puede ser más rápido que el uso de un mapa hash si todos menos algunos de los elementos que está buscando están muy cerca del comienzo. Por ejemplo, si el 50% de los elementos coincide con el primer elemento, el 25% coincide con el segundo, el 12.5% ​​coincide con el tercero, etc., excepto que un elemento impar coincidirá con algo que podría estar en cualquier lugar de la matriz, el número esperado de comparaciones con realizar búsquedas M en una lista de tamaño N sería 2M + N.
supercat
55
Las instrucciones de @DeepJoshi SIMD no cambian la complejidad de los algoritmos. Solo cambian la constante multiplicativa.
Gilles 'SO- deja de ser malvado'
5

Creo que hay un malentendido fundamental en la pregunta. Se compara a una persona que encuentra un objeto en una lista ordenada (por ejemplo, una página específica de un libro, dado su número) con una computadora que busca un elemento de una matriz.

O(logn)O(1)

Entonces, sí, el hardware (es decir, el modelo de cálculo) afecta el tiempo de ejecución de los algoritmos, como explica DW , pero eso no es en lo que parece estar basado su ejemplo de acceso a matriz.

David Richerby
fuente
2
Para ser justos, omitió todas las partes entre "el controlador de memoria establece los voltajes en los cables de dirección a la representación binaria de diecisiete" y "los datos vuelven". Una de esas piezas es casi seguro que es un árbol de búsqueda binario del tipo descrito por el OP; pero, no obstante, se ejecuta en tiempo constante porque log n es aproximadamente 64, para todo n .
Quuxplusone
@Quuxplusone ¿Qué parte de la memoria usa la búsqueda binaria? Las líneas de dirección seleccionan directamente las celdas de memoria.
David Richerby
Estamos operando muy lejos de mi área de especialización, pero lo que estaba tratando de implicar es que se implementará un decodificador de direcciones en términos de un árbol de demuxers . (Suponiendo que estamos golpeando directamente la memoria física, ignorando cualquier complicación adicional que viene con el almacenamiento en caché .) Nuevamente, toda esta complicación adicional solo agrega O(lg size-of-memory), es decir, insignificante, ¡pero eso es exactamente lo que OP estaba preguntando!
Quuxplusone
2

No, el hardware no afecta la complejidad de los algoritmos.

Pero sí afecta la elección del algoritmo, y puede afectar la utilidad del análisis de complejidad hasta un punto en el que el análisis deja de tener sentido (o simplemente es de interés académico).

Encontrar el cajón correcto (como acceder a un elemento de matriz) usa el algoritmo "abrir el enésimo elemento directamente por índice", no el algoritmo "buscar linealmente" o "hacer búsqueda binaria". Los algoritmos no cambian, sino la elección.

Por otro lado, el análisis de complejidad en sí mismo, o más bien su significado, se ve muy afectado por el hardware.

Muchos algoritmos que son estelares por su análisis de complejidad son de bajo rendimiento o incluso inútiles en la práctica porque el factor constante insignificante no es nada insignificante, sino dominante .

O, porque las suposiciones que alguna vez fueron verdaderas (o mayormente verdaderas) ya no son válidas. Como, por ejemplo, cada operación es casi la misma (solo pequeñas diferencias constantes que no importan), o no hace ninguna diferencia a qué ubicaciones de memoria tiene acceso en qué orden. Mediante el análisis de complejidad, puede concluir que algunos algoritmos son muy superiores porque solo necesitan muchas operaciones. En la práctica, es posible que cada operación provoque una pérdida de caché garantizada (o peor aún, un error de página), que introduce una k que es tan grande que ya no es insignificante, sino que domina todo.
Si el algoritmo A toma 500 operaciones para procesar un conjunto de datos de un tamaño dado y el algoritmo B toma solo 5, pero B causa 5 fallas que queman veinte millones de ciclos cada una, entonces, a pesar de lo que el análisis o el sentido común puedan decirle, A es mejor.

Esto ha llevado a sorpresas divertidas como, por ejemplo, en Cuckoo Hashing hace unos años. Lo cual fue muy superior porque [larga lista de beneficios]. Después de que el bombo se enfrió, resultó que era muy inferior porque garantizaba dos errores de caché (fallas, para conjuntos de datos más grandes) en cada acceso.

Similar ha sucedido con la identificación y el procesamiento de subconjuntos de datos. A menudo, la solución correcta hoy en día es: "hazlo todo" , es decir, en lugar de averiguar lo que necesitas probar y hacer eso, procesa el conjunto de datos completo de forma lineal, incluso si tal vez solo necesitas la mitad. Porque, lo creas o no, eso es más rápido debido a que no hay predicciones erróneas de sucursales, errores de caché ni fallas de página.
¿Necesita leer los primeros 8kB y los últimos 3kB de un archivo de 3MB? Bueno, lea el archivo completo y deseche lo que no quiere, porque buscar en el medio será diez veces más lento que simplemente leerlo completo.

¿Usar un mapa porque tiene complejidad logarítmica? ¿O una tabla hash, que tiene un tiempo de acceso constante? Constante suena increíble. Bueno, para cualquier cosa con menos de mil cosas (dependiendo del hardware, el tamaño de los datos y el patrón de acceso), una búsqueda lineal puede ser igual o mejor. Sorpresa.

Por lo tanto, no son los algoritmos per se los que se ven afectados, sino su utilidad y elección.

Damon
fuente