¿Qué algoritmo está detrás del descubrimiento de STL?

Question

Acabo de crear una función de búsqueda personalizada para cadenas en un mapa. Desarrollé algún tipo de algoritmo de búsqueda lineal (que descubrí más tarde) y no estaba satisfecho con la velocidad de la función. Así que busqué una función más rápida y encontré la función propia del mapa: map :: find.

Esto fue increíblemente más rápido que el algoritmo lineal que estaba usando.

En otro ejemplo, la función de STL find también fue mucho más rápido que otra función lineal que estoy usando.

Pero, ¿cómo es esto posible? Si usa el algoritmo de búsqueda binaria, primero debe ordenar el mapa, lo que tomaría (hipotéticamente) más tiempo cuanto más grande sea su mapa.

¿También cómo saber los algoritmos detrás de esas funciones básicas? ¿Hay una lista o algún tipo de base de datos para encontrar esto?

¡Gracias por todas sus respuestas! Subí las mejores respuestas y acepté la respuesta de Max Lybbert porque era la más detallada.

Paul :)

Answer 1

Desarrollé algún tipo de algoritmo de búsqueda lineal (que descubrí más adelante) y no estaba satisfecho con la velocidad de la función. Así que busqué una función más rápida y encontré la función propia del mapa: map::find.

Esto fue increíblemente más rápido que el algoritmo lineal que estaba usando.

std::map está diseñado para mantener los datos ordenados a medida que se insertan en el contenedor. Ese es uno de sus trabajos principales. También es la razón por la que debe definir algún tipo de orden parcial para los datos que ingresa en un std::map.

Esto significa que cada inserción tarda un poco más de insertar en otros recipientes (insertar en un std::list - una vez que tenga el punto de inserción - por ejemplo, es O (1), como se añadiendo a un std::vector o añadiendo/prepending a std::deque). Pero la búsqueda está garantizada para usar la búsqueda binaria (o, más bien, para navigate the red-black tree behind the std::map (en "Optimización prematura o prudente")).

En otro ejemplo, la función de STL find fue también mucho más rápida que otra función lineal que estoy usando.

Pero, ¿cómo es esto posible? Si usa el algoritmo de búsqueda binaria, primero debe ordenar el mapa, lo que tomaría (hipotéticamente) más tiempo cuanto más grande sea su mapa.

No hay nada de hipotético al respecto. La ordenación de sus datos lleva tiempo, y siempre lleva más tiempo el mayor número de elementos de datos.

std::find es capaz de manejar datos no ordenados, por lo que se debe implementar como una búsqueda lineal (comparar std::binary_search/std::lower_bound). Pero se permite que std::find sea disimulado y desenrolle bucles, compare más de un elemento a la vez (si los elementos son pequeños, y especialmente si son tipos primitivos que se prestan a un toque de bits de bajo nivel), etc.

¿También cómo saber los algoritmos detrás de esas funciones básicas? ¿Hay una lista o algún tipo de base de datos para encontrar esto?

Personalmente, aprendí muchos algoritmos al leer lo que estaba disponible en el STL y en algunos otros idiomas. Me pareció más fácil estudiar los contenedores primero.

Answer 2

std::map almacena sus elementos en forma ordenada (casi siempre en un árbol binario de búsqueda auto-equilibrio).

std::map::find toma ventaja de esto y utiliza un dichotomic search.

Answer 3

La implementación está bien, depende de la implementación.

Pero por lo que las clases de complejidad genéricos van, se puede comprobar, por ejemplo, esta persona con una visión general de los métodos comunes STL:

http://www.cplusplus.com/reference/stl/

Answer 4

Técnicamente, no hay este tipo de algoritmos. El estándar define qué tan bien debería funcionar cada algoritmo, no cómo debería hacerlo. Cada compilador envía una implementación de la biblioteca estándar.

Dicho esto, hay implementaciones gratuitas de la STL. Podrías mirar su código. Por ejemplo, STL Port.

¿También cómo saber los algoritmos detrás de esas funciones básicas? ¿Hay una lista o algún tipo de base de datos para encontrar esto?

Bueno, está el Dictionary of Algorithms and Data Structures pero es un poco complicado.

Answer 5

Los algoritmos STL son casi siempre más rápidos que cualquier cosa que pueda escribir usted mismo, ya que hace un montón de optimizaciones bajo las sábanas. También es más rápido utilizar iteradores que operador [] cuando se itera a través de un vector u otro contenedor de acceso aleatorio porque hay menos sobrecarga.

Debe consultar los libros de Scott Meyers Effective C++ Third Edition y Effective STL. (El material en C++ más efectivo está incluido en la 3ª edición de C++ efectivo.)