Dada una array arr[] de tamaño N y un entero T que representa el recuento de subprocesos , la tarea es encontrar todos los elementos de la array que no se repiten utilizando subprocesos múltiples .
Ejemplos:
Entrada: arr[] = { 1, 0, 5, 5, 2}, T = 3
Salida: 0 1 2
Explicación:
La frecuencia de 0 en el arreglo arr[] es 1.
La frecuencia de 1 en el arreglo arr[ ] es 1.
La frecuencia de 2 en el arreglo arr[] es 1.
Por lo tanto, la salida requerida es 0 1 2Entrada: arr[] = { 1, 1, 5, 5, 2, 4 }, T = 3
Salida: 2 4
Explicación:
La frecuencia de 2 en el arreglo arr[] es 1.
La frecuencia de 4 en el arreglo arr [] es 1.
Por lo tanto, la salida requerida es 2 4
Enfoque: la idea es utilizar la biblioteca pthread disponible en C++ para crear múltiples subprocesos para el flujo de procesos simultáneos y realizar múltiples operaciones (pthread create, pthread join, lock, etc.) en un programa multiproceso. Siga los pasos a continuación para resolver el problema:
- Divida la array en T subarreglos, de modo que cada subarreglo de tamaño N / T se ejecute en un solo subproceso.
- Inicialice un mapa , digamos mp , para almacenar las frecuencias de cada elemento del arreglo .
- Cree un pthread_mutex_lock , digamos lock1 , para garantizar que todos los subprocesos no tropiecen entre sí y dañen el contenedor del mapa.
- Defina una función func() para ejecutar el cuerpo de un hilo. Esta función a menudo se denomina núcleo del subproceso y se proporciona durante la creación del subproceso.
- Bloquee el hilo actual usando pthread_mutex_lock() para que no se superponga con otros hilos
- Recorra el rango dado como un argumento para la función func() en la array arr[] e incremente la frecuencia del elemento de la array que se encuentra.
- Libera el hilo actual usando la función pthread_mutex_unlock() .
- Inicialice una array, digamos thread[] , de tipo pthread_t para almacenar los hilos.
- Itere sobre el rango [0, T] y cree un hilo llamando a la función pthread_create() y guárdelo en el hilo [i]
- Mientras cada subproceso realiza sus tareas individuales, la función main() deberá esperar hasta que cada uno de los subprocesos finalice su trabajo.
- Use la función pthread_join() para esperar hasta que cada subproceso termine de ejecutar la función func()
- Iterar sobre el rango [0, T] y llamar a la función pthread_create() para cada hilo [i]
- Finalmente, recorra el mapa mp e imprima el elemento que aparece solo una vez.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
#include <pthread.h>
using namespace std;
// Structure of subarray
// of the array
struct range_info {
// Stores start index
// of the subarray
int start;
// Stores end index
// of the subarray
int end;
// Stores pointer to the
// first array element
int* a;
};
// Declaring map, and mutex for
// thread exclusion(lock)
map<int, int> mp;
pthread_mutex_t lock1;
// Function performed by every thread to
// count the frequency of array elements
// in current subarray
void* func(void* arg)
{
// Taking a lock so that threads
// do not overlap each other
pthread_mutex_lock(&lock1);
// Initialize range_info
// for each thread
struct range_info* rptr
= (struct range_info*)arg;
// Thread is going through the array
// to check and update the map
for (int i = rptr->start;
i <= rptr->end; i++) {
// Stores iterator to the map
map<int, int>::iterator it;
// Update it
it = mp.find(rptr->a[i]);
// If rptr->a[i] not found
// in map mp
if (it == mp.end()) {
// Insert rptr->a[i] with
// frequency 1
mp.insert({ rptr->a[i], 1 });
}
else {
// Update frequency of
// current element
it->second++;
}
}
// Thread releases the lock
pthread_mutex_unlock(&lock1);
return NULL;
}
// Function to find the unique
// numbers in the array
void numbers_occuring_once(int arr[],
int N, int T)
{
// Stores all threads
pthread_t threads[T];
// Stores start index of
// first thread
int spos = 0;
// Stores last index
// of the first thread
int epos = spos + (N / T) - 1;
// Traverse each thread
for (int i = 0; i < T; i++) {
// Initialize range_info for
// current thread
struct range_info* rptr
= (struct range_info*)malloc(
sizeof(struct range_info));
// Update start index of
// current subarray
rptr->start = spos;
// Stores end index of
// current subarray
rptr->end = epos;
// Update pointer to the first
// element of the array
rptr->a = arr;
// creating each thread with
// appropriate parameters
int a
= pthread_create(&threads[i], NULL,
func, (void*)(rptr));
// updating the parameters
// for the next thread
spos = epos + 1;
epos = spos + (N / T) - 1;
if (i == T - 2) {
epos = N - 1;
}
}
// Waiting for threads to finish
for (int i = 0; i < T; i++) {
int rc
= pthread_join(threads[i], NULL);
}
// Traverse the map
for (auto it: mp) {
// If frequency of current
// element is 1
if (it.second == 1) {
// Print the element
cout << it.first << " ";
}
}
}
// Drivers Code
int main()
{
// initializing the mutex lock
pthread_mutex_init(&lock1, NULL);
int T = 3;
int arr[] = { 1, 0, 5, 5, 2, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
numbers_occuring_once(arr, N, T);
}
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Nota: Se recomienda ejecutar el programa en un sistema basado en Linux usando el siguiente comando:
g++ -pthread nombre_programa.cpp