Si se implementa una clase de matriz de la forma en que se implementa comúnmente, su rendimiento es más lento en comparación con su equivalente STL como un vector. Entonces, ¿qué hace que los contenedores/algoritmos STL sean rápidos?¿Qué hace que STL sea rápido?
Algoritmos STL como for_each toman objetos de función que se pueden insertar fácilmente. C, por otro lado, usa indicadores de función que son mucho más difíciles de optimizar para el compilador.
Esto hace una gran diferencia en algunos algoritmos como la clasificación en la que la función del comparador debe llamarse muchas veces.
Wikipedia tiene some more information en caso de que esté interesado.
EDIT:
En cuanto a la clase vector de la STL, no creo que sea necesariamente más rápido que lo que se puede encontrar en, por ejemplo, glibc.
eso es probablemente uno de los puntos cruciales: D –
interesante ... – toto
La biblioteca estándar utiliza buenos algoritmos, como en el caso de una matriz (std :: vector), generalmente dobla el almacenamiento cada vez que se queda sin espacio, mientras que una implementación ingenua puede incrementar el almacenamiento en un elemento cada vez. Debido a que aumentar la cantidad de almacenamiento es muy lento (todos los datos existentes deben copiarse de la asignación anterior a la nueva asignación), esto puede marcar una gran diferencia.
De forma similar, todos los demás algoritmos se implementan de forma bastante óptima. La biblioteca estándar por lo general no utiliza ningún tipo de desenrollado de bucle u otras optimizaciones similares en el nivel del código fuente. Simplemente es un código regular bueno y simple (con nombres de variables horribles y muchas plantillas) que luego el compilador optimiza.
Lo que dije no está especificado por el estándar de C++, pero es lo que parece ser la práctica común en las implementaciones existentes.
El doble de almacenamiento puede ser bastante malo después de alcanzar un megabyte o más ... –
Hassan Syed: Nunca desperdicia más del 50% de la memoria asignada. Yo no llamaría eso "bastante malo". –
Aparentemente std :: vector crece por un factor de 1.5: http://amitp.blogspot.com/2003_11_01_amitp_archive.html#106843046050898865 – Manuel
Los algoritmos en el STL han sido estudiados durante años por todos los niveles de matemáticos y científicos informáticos, y normalmente utilizan los algoritmos más eficientes que su implementación puede no estar usando. La implementación común es una que probablemente no sea la más rápida, pero es más fácil de entender; el STL probablemente esté utilizando una implementación más optimizada.
Cuando todo tipo de personas altamente educadas han bendecido algo (SI lo han hecho), no suponga que no necesita pensar en ello. Ellos son bastante capaces y calificados para estar equivocados. –
-1: Diría que simplemente no es una afirmación verdadera. Los "algoritmos" son específicos de la implementación. Solo se especifica el comportamiento expuesto de los algoritmos/contenedores STL, etc. Hay muchas muchas implementaciones de STL y no todas han sido escrutadas (de hecho, diría que la mayoría no) a ningún nivel cercano al que usted reclama. Muchas implementaciones son mejores de lo que el codificador promedio puede escribir, pero un buen codificador puede competir fácilmente con ellas ... –
La mayoría de las clases de conjuntos aumentan el tamaño en un incremento constante en lugar de un factor constante (como requiere la biblioteca estándar). Esto significa que insertar un elemento toma más o menos tiempo lineal en lugar del tiempo constante amortizado para la biblioteca estándar.
Cualquier desarrollador que lo haga debe devolver su título de ciencias de la computación –
@DrJokepu: Asumirá que el desarrollador TIENE un título en ciencias de la computación:) +1 –
el código está escrito de una manera amigable para el compilador, p. En línea, etc.
por supuesto, los algoritmos que utilizan son de última generación.
Además de buenos algoritmos generales (como otros han notado), el STL también es bastante eficiente debido al uso intensivo de plantillas.
Template metaprograms tienen la buena característica de que el compilador los optimiza agresivamente. Algunos compiladores son muy buenos al respecto y reducen las plantillas al código más pequeño, más eficiente y requerido para una tarea determinada. Y en general, eso significa que las funciones están en línea siempre que sea posible, y el código para interactuar con un tipo particular se reduce a su forma más simple. La mayoría de las implementaciones de STL (y la mayoría de Boost), por supuesto, aprovechan esto al máximo.
"La forma en que se implementa comúnmente" es algo muy vago. Todos lo implementan a su manera.Técnicamente, comúnmente * no está implementado * pero reutilizado. –
Especifique a qué operaciones se refiere y cómo determinó que la biblioteca estándar es más rápida. –
@Mehrdad, Malte: Sí, estoy de acuerdo. Pero digamos que para una clase de matriz, insertando un elemento en el medio al desplazar los elementos una vez hacia atrás para crear un espacio vacío para el nuevo elemento. Esta implementación es mucho más lenta que push_back() de un vector. Lo determino obteniendo el tiempo o los ciclos del reloj. – jasonline