Necesito insertar 10 millones de cadenas en un conjunto C++ STL. Las cuerdas están ordenadas. ¿Tendré un problema patológico si inserto las cadenas en orden ordenado? ¿Debo aleatorizar primero? ¿O la implementación de G ++ STL volverá a equilibrarse automáticamente para mí?¿Debo aleatoriamente mezclar antes de insertar en el conjunto STL?
La única pregunta que tengo:. Lo que realmente necesita un set?
Si los datos ya está ordenada y no es necesario insertar/eliminar elementos después de la creación, un deque sería mejor:
en binary_search: sospecho que necesita más de un ForwardIterator para una búsqueda binaria, supongo que este sitio está desactivado nuevamente :(
La implementación del conjunto generalmente utiliza un árbol rojo-negro, que se reequilibrará por usted. Sin embargo, la inserción puede ser más rápida (o no) si aleatoriza los datos antes de insertarlos; la única forma de estar seguro es haciendo una prueba con su implementación de conjunto y datos específicos. Los tiempos de recuperación serán los mismos, de cualquier manera.
Una de mis quejas con el conjunto stl, es que no se puede asignar memoria para ello con anticipación. Que sería mi problema si estás poniendo 10 millones de cuerdas en un stl set. – JSchlather
árbol rojo-negro garantiza la complejidad O (log N) para las operaciones de inserción. ¿Por qué aleatorizar? –
@Kyril Garantiza que, como orden máxima aleatorizada, se puede obtener un mejor rendimiento, ya que es probable que sea necesario realizar un menor reequilibrio. –
http://en.wikipedia.org/wiki/Standard_Template_Library
conjunto: "implementado usando un árbol binario de búsqueda auto-equilibrio."
Tal vez 'unordered_set' puede ser una alternativa.
La implementación volverá a equilibrarse automáticamente. Sin embargo, dado que sabe que la entrada está ordenada, puede prestarle un poco de ayuda: puede proporcionar una "sugerencia" cuando realiza una inserción, y en este caso, el suministro del iterador al elemento insertado previamente será exactamente el correcto. sugerencia para suministrar para la siguiente inserción. En este caso, cada inserción tendrá una complejidad constante amortizada en lugar de la complejidad logarítmica que de otro modo esperaría.
Buen consejo, pero el árbol se reequilibrará con bastante frecuencia. –
@Matthieu: Es cierto. Estoy bastante seguro, al menos en términos de complejidad, es mejor que barajar los datos primero. Con los datos mezclados, la complejidad general es O (N lg N) ya que debe buscar el punto de inserción para cada nuevo elemento. Con los datos ordenados, cada inserción ha amortizado la complejidad constante, por lo que la complejidad general se amortiza O (N). Sin embargo, aún puede cuestionarse si es mejor en la práctica. Si puede guardar todos los datos en la memoria, podría intentar construir el árbol perfectamente desde el principio (bisectar recursivamente los datos). –
Me gusta esta idea de bisección, aunque supongo que en la práctica, dada la cantidad de registros, sería más lento que el reequilibrio debido a problemas de caché a medida que seguimos llegando a nuevas páginas de memoria. –
g ++ 's libstdC++ utiliza árboles rojos negros para conjuntos y mapas.
http://en.wikipedia.org/wiki/Red-black_tree
Esto es un árbol de auto equilibrio, y las inserciones son siempre O (log n). El estándar de C++ también requiere que todas las implementaciones tengan esta característica, por lo que en la práctica, casi siempre son árboles de color rojo oscuro, o algo muy similar.
Así que no se preocupe por el orden de poner los elementos en
Una solución muy económica y simple es insertar desde ambos extremos de sus colecciones de cadenas. Es decir, primero agregue "A", luego "ZZZZZ", luego "AA", luego "ZZZZY", etcétera hasta que se encuentre en el medio. No requiere un alto costo de barajado, pero es probable que evite los casos patológicos.
No, la documentación es correcta. binary_search usa "advance", que es un tiempo constante para el iterador de acceso aleatorio, y lineal para ForwardIterator. Entonces ForwardIterator es el requisito mínimo para el algoritmo. Ver nota al pie en http://www.sgi.com/tech/stl/binary_search.html. – BenG
Prefiero usar un juego porque, francamente, esa es la funcionalidad que necesito. – vy32
@BennyG: gracias por esto. Como se indica en ambos sitios para los Agentes no aleatorios de acceso, la cantidad de pasos es lineal, no logarítmica. De alguna manera había asumido que solo podíamos tener una complejidad logarítmica. –