c++ - remove - Rendimiento de vector sort/unique/erase vs. copy to unordered_set
funcion unique c++ (2)
El conjunto sin clasificar tiene una complejidad de tiempo constante o (1) para la inserción (en promedio), por lo que la operación será o (n) donde n es el número de elementos antes de la eliminación.
ordenar una lista de elementos de tamaño n es o (n log n), revisar la lista para eliminar duplicados es o (n). o (n log n) + o (n) = o (n log n)
El conjunto sin clasificar (que es similar a una tabla hash en el rendimiento) es mejor.
datos sobre tiempos de conjuntos no ordenados: http://en.cppreference.com/w/cpp/container/unordered_set
Tengo una función que hace que todos los vecinos de una lista de puntos en una cuadrícula salgan a cierta distancia, lo que implica una gran cantidad de duplicados (el vecino de mi vecino == yo otra vez).
He estado experimentando con un par de soluciones diferentes, pero no tengo idea de cuál es la más eficiente. A continuación se muestra un código que muestra dos soluciones que se ejecutan una al lado de la otra, una usando std :: vector sort-unique-erase, la otra usando std :: copy en std :: unordered_set.
También probé otra solución, que es pasar el vector que contiene los vecinos hasta ahora a la función vecino, que utilizará std :: find para asegurar que un vecino no exista antes de agregarlo.
Así que tres soluciones, pero no puedo entender bien cuál será más rápido. ¿Alguna idea a alguien?
El fragmento de código sigue:
// Vector of all neighbours of all modified phi points, which may initially include duplicates.
std::vector<VecDi> aneighs;
// Hash function, mapping points to their norm distance.
auto hasher = [&] (const VecDi& a) {
return std::hash<UINT>()(a.squaredNorm() >> 2);
};
// Unordered set for storing neighbours without duplication.
std::unordered_set<VecDi, UINT (*) (const VecDi& a)> sneighs(phi.dims().squaredNorm() >> 2, hasher);
... compute big long list of points including many duplicates ...
// Insert neighbours into unordered_set to remove duplicates.
std::copy(aneighs.begin(), aneighs.end(), std::inserter(sneighs, sneighs.end()));
// De-dupe neighbours list.
// TODO: is this method faster or slower than unordered_set?
std::sort(aneighs.begin(), aneighs.end(), [&] (const VecDi& a, const VecDi&b) {
const UINT aidx = Grid<VecDi, D>::index(a, phi.dims(), phi.offset());
const UINT bidx = Grid<VecDi, D>::index(b, phi.dims(), phi.offset());
return aidx < bidx;
});
aneighs.erase(std::unique(aneighs.begin(), aneighs.end()), aneighs.end());
Es probable que una gran cantidad de esto dependa del tamaño del conjunto de salida (que, a su vez, dependerá de cuán distante sea el vecino que muestre).
Si es pequeño, (no más de unas pocas docenas de elementos más o menos), la implementación del conjunto rodado a mano utilizando std::vector y std::find probablemente seguirá siendo bastante competitivo. Su problema es que se trata de un algoritmo O (N 2 ): cada vez que inserta un elemento, debe buscar todos los elementos existentes, por lo que cada inserción es lineal en la cantidad de elementos que ya están en el conjunto. Por lo tanto, a medida que el conjunto se hace más grande, es momento de insertar elementos aproximadamente cuadráticamente.
Al usar std::set , cada inserción solo tiene que hacer aproximadamente log 2 (N) comparaciones en lugar de N comparación. Eso reduce la complejidad general de O (N 2 ) a O (N log N). La principal deficiencia es que (al menos normalmente) se implementa como un árbol formado por nodos asignados individualmente. Eso típicamente reduce su localidad de referencia, es decir, cada elemento que inserte consistirá en los datos en sí más algunos punteros, y atravesar el árbol significa seguir los punteros. Dado que se asignan individualmente, las posibilidades son bastante buenas de que los nodos que están (actualmente) adyacentes en el árbol no sean adyacentes en la memoria, por lo que verá una cantidad considerable de errores de caché. En pocas palabras: si bien su velocidad crece bastante lentamente a medida que aumenta el número de elementos, las constantes involucradas son bastante grandes: para un número pequeño de elementos, comenzará bastante lento (generalmente bastante más lento que su versión enrollada a mano) )
Usar un vector / sort / unique combina algunas de las ventajas de cada uno de los anteriores. Almacenar los elementos en un vector (sin punteros adicionales para cada uno) generalmente conduce a un mejor uso de la memoria caché: los elementos en índices adyacentes también se encuentran en ubicaciones de memoria adyacentes, por lo que cuando inserta un nuevo elemento, es probable que la ubicación del nuevo elemento ya estar en el caché. La principal desventaja es que si se trata de un conjunto realmente grande, esto podría requerir bastante más memoria. Cuando un conjunto elimina duplicados a medida que inserta cada elemento (es decir, un elemento solo se insertará si es diferente de cualquier elemento del conjunto), insertará todos los elementos y al final eliminará todos los duplicados. Dada la disponibilidad actual de la memoria y la cantidad de vecinos que supongo que probablemente visitará, dudo que esto sea una gran desventaja en la práctica, pero en circunstancias incorrectas, podría conducir a un problema grave: casi cualquier uso de memoria virtual. casi seguro lo convertiría en una pérdida neta.
Mirando el último desde un punto de vista de complejidad, va a O (N log N), algo así como el conjunto. La diferencia es que con el conjunto es realmente más como O (N log M), donde N es el número total de vecinos, y M es el número de vecinos únicos. Con el vector, es realmente O (N log N), donde N es (nuevamente) el número total de vecinos. Como tal, si el número de duplicados es extremadamente grande, un conjunto podría tener una ventaja algorítmica significativa.
También es posible implementar una estructura tipo conjunto en secuencias puramente lineales. Esto conserva la ventaja del conjunto de solo almacenar elementos únicos, pero también la ventaja de referencia del lugar del vector. La idea es mantener la mayor parte del conjunto actual ordenado, para que pueda buscarlo en la complejidad del registro (N). Sin embargo, cuando inserta un nuevo elemento, simplemente lo coloca en el vector separado (o en una porción no ordenada del vector existente). Cuando realiza una nueva inserción, también realiza una búsqueda lineal en esos elementos sin clasificar.
Cuando esa parte no ordenada se vuelve demasiado grande (para una definición de "demasiado grande") ordena esos elementos y los combina en el grupo principal, luego comienza la misma secuencia nuevamente. Si define "demasiado grande" en términos de "log N" (donde N es el número de elementos en el grupo ordenado) puede retener la complejidad O (N log N) para la estructura de datos como un todo. Cuando jugué con él, descubrí que la porción no ordenada puede ser más grande de lo que esperaba antes de que empiece a causar un problema.