¿Qué algoritmos se usan con más frecuencia en la práctica?

19

¿Qué algoritmos se usan con más frecuencia?

Escriba un solo algoritmo por respuesta, intente mantener su respuesta corta (una o dos líneas).

ds.algorithms big-list Kaveh
fuente
Kaveh, ¿tal vez deberías esperar las respuestas antes de suministrar tantas? :)
Suresh Venkat
1
@Suresh: Lo siento. :)
Kaveh
3
¿Más a menudo en qué sentido? (¿Número de programas de computadora diferentes que implementan el algoritmo? ¿Número de piezas de software instaladas que usan el algoritmo? ¿Número de ejecuciones del algoritmo? ¿Cantidad de datos procesados ​​usando el algoritmo? ¿Segundos de CPU usados ​​por el algoritmo?) ¿Dónde? (Academia, industria, PC domésticas?) ¿Es posible estimar algo como esto? ¿Podemos tener alguna información para respaldar alguna de las respuestas?
Jukka Suomela
1
La pregunta es demasiado vaga, como señaló Jukka Suomela. Sin más aclaraciones, las respuestas no serán mejores que la tabla de contenido de un libro de texto sobre algoritmos.
Tsuyoshi Ito
1
Hay un libro reciente: "Nueve algoritmos que cambiaron el futuro: las ingeniosas ideas que impulsan las computadoras de hoy" por John MacCormick. Ver press.princeton.edu/titles/9528.html
Alessandro Jacopson el

Respuestas:

18

¿La Transformada rápida de Fourier es el problema algorítmico resuelto la mayoría de las veces al día por sistemas informáticos reales? Tiene que estar cerca. Entonces nominaría el algoritmo FFT de Cooley-Tukey .

Aaron Sterling
fuente
Me gusta esto, FFT se pasa por alto en la educación básica en ciencias de la computación, pero ciertamente es un algoritmo con un tremendo impacto en nuestra sociedad moderna, y muchas cosas modernas que nos rodean están arruinando FFT todo el tiempo.
Jukka Suomela
14

Multiplicación.

Quizás uno de los algoritmos más antiguos, no totalmente triviales, y un problema que se resuelve con más frecuencia que FFT.

Jukka Suomela
fuente
La multiplicación no es un algoritmo, es un problema con muchos subproblemas resueltos por diferentes algoritmos: entero de tamaño fijo y coma flotante, realizado por hardware o software; bignums de tamaño variable (módulo o no), matrices, ...
Gilles 'SO- deja de ser malvado'
Me refería a los circuitos de multiplicación de hardware en las CPU modernas (para enteros y números de punto flotante; estos dos no son tan diferentes al final). Según tengo entendido, tienden a ser versiones "solo" muy ingeniosamente diseñadas del mismo enfoque básico: el algoritmo de "multiplicación larga", que ya era conocido en la Edad Media.
Jukka Suomela
Creo que la resta (comparación) se usa con mucha más frecuencia que la multiplicación, y no veo ninguna razón por la cual la multiplicación cuente como un algoritmo y la suma / resta no. Sin embargo, no sé si esto califica como respuesta.
Tsuyoshi Ito
Sí, la suma y la resta se usan incluso con más frecuencia que la multiplicación; de hecho, el algoritmo de multiplicación larga esencialmente reduce una multiplicación a una suma. Sin embargo, no sé si hay un solo algoritmo de suma / resta que podamos nominar aquí.
Jukka Suomela
@JukkaSuomela: la suma y resta del complemento a dos sería un buen candidato.
John Gietzen
13

Algoritmos de ruta más corta de Dijkstra y Bellman-Ford . Hay al menos 35,000 sistemas autónomos (AS) activos en Internet a partir de 2010. Cada AS ejecuta un protocolo de enrutamiento de estado de enlace (Dijkstra) o un protocolo de enrutamiento de vector de distancia (Bellman-Ford). Los enrutadores dentro de un AS generalmente actualizan sus tablas periódicamente cada pocos minutos, digamos 10.

Por lo tanto, el número de ejecuciones de Dijkstra & Bellman-Ford por día asciende a al menos 5 millones. Y eso es solo de los enrutadores.

No hemos contado los cálculos de rutas más cortas de Google Maps y los me gusta, que deberían representar fácilmente 10 veces más. Medio billón de ejecuciones al día no es descabellado.

Hung Q. Ngo
fuente
Medio billón de ejecuciones al día puede parecer mucho, pero tengamos en cuenta que tenemos, por ejemplo, miles de millones de teléfonos móviles en este planeta. ¿Qué hacen esas cosas todo el tiempo? ¿O qué están haciendo durante cada llamada telefónica? No lo sé, pero supongo que al menos están haciendo mucho más FFT que los caminos más cortos.
Jukka Suomela
8

Ordenación rápida

Kaveh
fuente
14
Por cierto, ¿es realmente el caso de que quicksort es el algoritmo de clasificación que se usa más comúnmente en el mundo real? Eché un vistazo rápido a la implementación de una función de "clasificación" de uso general en algunos lenguajes de programación comúnmente utilizados. Perl: parece haber cambiado de quicksort a mergesort recientemente. Python: utiliza Timsort (híbrido de clasificación de fusión / inserción). Java: solía ser mergesort, hoy en día Timsort. Las bases de datos tienden a usar ordenamiento externo. ¿Quicksort ya es una especie en peligro de extinción?
Jukka Suomela
Creo que ese es un muy buen punto. Sería genial si alguien puede editar la respuesta.
Juan Bermejo Vega
@Juan, aunque el punto que mencionó Jukka es correcto, no veo ninguna razón para editar la respuesta.
Kaveh
7

Creo que el algoritmo más utilizado es Parity Check (o tal vez CRC o algún tipo de código de corrección de errores), porque aparecen en cada acceso RAM.

Diego de Estrada
fuente
También se usa al menos una vez para cada paquete que se envía a través de cualquier red basada en IP
Claus Broch
5

Algoritmo simple : ¿no sigue siendo competitivo con los mejores métodos de puntos interiores? Si es así, tiene que usarse mucho.

Mugizi Rwebangira
fuente
4

k

En términos más generales, debe mirar a los ganadores del premio Kanellakis para obtener ideas que tengan peso teórico y práctico.

Suresh Venkat
fuente
gracias por el enlace, se ve muy interesante. La motivación parcial para la pregunta fue encontrar un buen nombre algorítmico pegadizo para el sitio. :)
Kaveh
4

Coincidencia de expresiones regulares por conversión a autómatas finitos: creo que grep funciona en este sentido.

Neeldhara
fuente
3

Es difícil pensar en algoritmos más utilizados que en las implementaciones modernas de TCP : es decir , evitar la congestión , retransmitir rápidamente . Aunque eso depende de cómo se determina qué cumple con los criterios para un algoritmo ...

Lev Reyzin
fuente
Pero, ¿puede realmente usar algoritmos TCP con más frecuencia que FFT (que ya está en esta lista)? Si mi computadora envía un solo paquete IP (TCP o no), ¿no suele desencadenar un montón de cálculos FFT? Por lo general, los paquetes se transmiten en algún momento mediante el uso de tecnologías como WLAN, ADSL y GSM, y creo que la mayoría de ellos utilizan modulaciones que dependen en gran medida de FFT.
Jukka Suomela
Creo que tienes razón.
Lev Reyzin
3

Eliminación Gaussiana Esto todavía se usa en la práctica, ¿verdad? Si no, reemplácelo con lo que se use con más frecuencia para resolver sistemas lineales ...

Mugizi Rwebangira
fuente
2

SHA-1 (y funciones hash en general). Probablemente supere a la mayoría de los otros algoritmos en términos del número de ejecuciones.

Hung Q. Ngo
fuente
2

Los algoritmos relacionados con el árbol B + se utilizan para las cosas de la base de datos

Prabu
fuente
2

Algoritmos de programación. Son utilizados por cada dispositivo de usuario y servidor en todo el mundo. Se están utilizando una serie de variaciones, encontré muchas referencias para la "cola de comentarios multinivel"

chazisop
fuente
1

Esta respuesta interpreta "con mayor frecuencia" en términos de ciclos de CPU reales.

Cuando estaba aprendiendo informática en los años 70, recuerdo haber leído que la gran mayoría de los ciclos de la computadora (léase: mainframe) estaban dedicados a la clasificación. Las aplicaciones comerciales exigen una amplia clasificación para análisis e informes. No creo que eso haya cambiado mucho, pero, por supuesto, el aumento de otras aplicaciones (correo electrónico, procesamiento de textos, etc.) debe haber alterado la combinación. Esos tipos suelen ser estables (no Quicksort) debido a la necesidad de ordenar sucesiones de campos para crear subsorts.

Estrictamente hablando, sin embargo, el algoritmo que se usa con más frecuencia es, sin lugar a dudas, lo que sea ejecutado por el proceso de espera del sistema de Windows cuando no sucede nada más ;-).

whuber
fuente
1

Spray Matrix Vector Multiply

... es el caballo de batalla computacional detrás de la solución de casi todos los sistemas lineales. Como resultado, se ejecuta cada vez

  • Científicos / ingenieros resuelven ecuaciones diferenciales
  • Los estadísticos encuentran nuevas correlaciones (PCA)
  • Google ejecuta pagerank
  • Su teléfono predice su ubicación a partir de GPS, acelerómetros, ubicaciones de torres celulares
  • Tu auto ajusta tu suspensión en movimiento
  • etc ....

La mayoría de los FLOP en cualquier supercomputadora o clúster se gastan dentro de un vecino mate escaso.

MRocklin
fuente
1

El método de Newton Se usa para calcular raíces cuadradas, para la división de computación. Se puede usar para hacer programación lineal. En general, es el caballo de batalla de la optimización (convexa). Se puede usar para resolver ecuaciones diferenciales en Física minimizando la acción / energía.

Jules
fuente
1

Hashing y árboles rojo-negros.

Ya están implementados en STL (hash_map, map), y cada programador sabe que dicho contenedor es increíblemente conveniente siempre que desee almacenar información indexada por un tipo de datos arbitrario.

zotachidil
fuente
0

Programación Dinámica .

Creo que DP se usa "con más frecuencia" que otros algoritmos citados en la encuesta hasta ahora. Infiero "más a menudo" en el sentido de con qué frecuencia un programador implementó un concepto de algoritmo no trivial en la vida real, en lugar de cuántas veces se invoca una implementación particular de un algoritmo.

DP es versátil y tiene muchas caras. A veces lo usé de manera inconsciente y luego me di cuenta de que estaba haciendo DP.

Por supuesto, hay cosas que son aún más comunes que el Programa dinámico, pero en su mayoría son estructuras de datos (matriz, lista vinculada, hash).

Hardy Leung
fuente
77
Esto es un poco diferente de las otras sugerencias, ya que es un paradigma de diseño de algoritmo (similar a codicioso o primal-dual) y no solo un algoritmo único.
Jukka Suomela
0

String Matching, utilizado todo el tiempo en software de aplicación y en el nivel de base de datos.

En el caso exacto, hay varios algoritmos bastante involucrados (KMP, Boyer-Moore) con algunos que alcanzan el tiempo de ejecución esperado sublineal. También son interesantes para estudiar desde un punto de vista de CS.

La coincidencia aproximada de cadenas, es decir, las alineaciones, es probablemente aún más interesante. ¿Conoces las características de "autocorrección"? Además, las búsquedas en datos de cadenas ruidosas (por ejemplo, ADN) se realizan mediante alineaciones.

Rafael
fuente