c++ - programacion - problemas de iteracion

C++ iterar vector al azar

Question

Estoy trabajando en un programa multiproceso en el que todos los subprocesos comparten algún vector (solo lectura). El objetivo de cada hilo es recorrer todo el vector. No obstante, todos los hilos deben visitar este vector de una manera diferente.

Dado que el vector es constante y compartido entre todos los subprocesos, no puedo usar random_shuffle y simplemente iterar sobre él. Por ahora, mi solución es crear un vector de referencia cruzada que contendrá índices sobre el vector compartido y luego barajar este vector, es decir

     std::vector<int> crossref(SIZE) ; // SIZE is the size of the shared vector
     std::iota (std::begin(crossref), std::end(crossref), 0); // Fill with indices ref 
     std::mt19937 g(SEED); // each thread has it own seed.
     std::shuffle (crossref_.begin(), crossref_.end(), g); // Shuffle it 

No obstante, hacer esto revela algunos problemas (1) no es muy eficiente ya que cada hilo necesita acceder a su vector de referencia antes de acceder al compartido, (2) tengo algún problema de rendimiento debido a la cantidad de memoria requerida: el vector compartido es Muy grande y tengo muchos hilos y procesadores.

¿Alguien tiene algunas ideas de mejora que eviten la necesidad de memoria adicional?

Answer 1

Esta no es una respuesta completa, pero debería llevarnos a una solución correcta.

Usted ha escrito algunas cosas que podríamos tomar como suposiciones:

(1) no es muy eficiente ya que cada subproceso necesita acceder a su vector de referencia cruzada antes de acceder al compartido,

Es poco probable que esto sea cierto. Estamos hablando de una búsqueda indirecta. A menos que sus datos de referencia sean realmente un vector de ints, esto representará una parte infinitesimal de su tiempo de ejecución. Si sus datos de referencia son un vector de caracteres, simplemente haga N copias de los mismos y mezclelos ...

(2) Tengo algunos problemas de rendimiento debido a la cantidad de memoria requerida: el vector compartido es muy grande y tengo muchos subprocesos y procesadores.

¿Cuan grande? ¿Lo mediste? ¿Cuántos objetos discretos hay en el vector? ¿Qué tan grande es cada uno?

¿Cuántos hilos?

¿Cuántos procesadores?

¿Cuanta memoria tienes?

¿Has perfilado el código? ¿Estás seguro de dónde está el cuello de botella de rendimiento? ¿Has considerado un algoritmo más elegante?

Answer 2

Parece que this tipo resolvió tu problema de una manera muy agradable.

Esto es lo que dice en la primera línea del post: En este post voy a mostrar una manera de hacer un iterador que visitará los elementos de una lista en un orden aleatorio, solo visitaré cada elemento una vez y le dirá cuándo. Ha visitado todos los artículos y está terminado. Lo hace sin almacenar una lista aleatoria, y tampoco tiene que realizar un seguimiento de los elementos que ya ha visitado.

Aprovecha la potencia de un algoritmo de cifrado de bloque de longitud de bits variable para generar cada índice en la matriz.

Answer 3

Puede utilizar la noción algebraica de raíz primitiva módulo n . Básicamente

Si n es un entero positivo, los enteros entre 1 y n - 1 que son coprime para formar el grupo de clases primitivas módulo n. Este grupo es cíclico si y solo si n es igual a 2, 4, p ^ k, o 2p ^ k donde p ^ k es la potencia de un número primo impar

Wikipedia muestra cómo puedes generar números por debajo de 7 usando 3 como generador.

De esta afirmación se deriva un algoritmo.

1. Toma tu numero n
2. Encuentra el siguiente número primo m que es más grande que n
3. Para cada uno de tus hilos, elige un número aleatorio único F(0) entre 2 y m
4. Calcule el siguiente índice usando F(i+1) = (F(i) * F(0)) mod m . Si ese índice está dentro del rango [0, n] , acceda al elemento. Si no se va hacia el siguiente índice.
5. Deténgase después de m - 1 iteraciones (o cuando obtiene 1, es lo mismo).

Como m es primo, cada número entre 2 y m-1 es coprime to m por lo que es un generador de la secuencia {1 ... m} . Se le garantiza que no se repetirá ningún número en los primeros pasos m - 1 , y que aparecerán todos los números m - 1 .

Complejidad:

• Paso 2: Hecho una vez, complejidad equivalente a encontrar números primos hasta n, es decir, tamiz de Eratóstenes
• Paso 3: Hecho una vez, puedes elegir 2, 3, 4, 5, etc ... Lo que es tan bajo como O(thread count)
• Paso 4: O(m) tiempo, O(1) en el espacio por hilo. No es necesario almacenar el F (i). Solo necesitas saber primer valor y último valor. Se trata de las mismas propiedades que el incremento.

Answer 4

Si entiendo bien, desea generar una permutación aleatoria de manera incremental, es decir , desea llamar n veces a una función f para que genere todos los números permutados de 1 a n , de modo que la función tenga memoria constante.

Dudo que exista si desea obtener una distribución uniforme entre las permutaciones, pero puede estar satisfecho con un subconjunto del conjunto de permutaciones.

Si este es el caso, puede generar una permutación tomando un número p primo con n y calcule para cada i en [1, n]: ip (mod n) . Por ejemplo, si tiene n = 5 yp = 7, entonces 7% 5 = 2, 14% 5 = 4, 21% 5 = 1, 28% 5 = 3, 35% 5 = 0. Puede combinar varias de estas funciones para obtener algo satisfactorio para usted ...

Answer 5

Si la memoria es su mayor problema, entonces tendrá que intercambiar ciclos de CPU por espacio de memoria.

Por ejemplo, c ++ ''s std::vector<bool> ( http://en.cppreference.com/w/cpp/container/vector_bool ) es una matriz de bits muy eficiente en memoria.

Cada subproceso puede tener su propio vector<bool> indica si ha visitado o no un índice particular. Entonces tendrías que usar los ciclos de CPU para elegir aleatoriamente un índice que aún no ha visitado y terminar cuando todos los bool sean true .