Então pessoal tenho q criar uma classe em java que permita paralelizar uma pesquisa em um array de inteiros. Isso deve ser feito com o seguinte método: public static int parallelSearck(int x, int[] A, int numThreads). Este método cria tantas threads quanto especificadas em numThreads, divide o array A em muitas partes e cada thread parte do array para procurar sequencialmente pelo valor x. Se uma thread encontrar o valor x, então é retornado o índice i (A[i] = x), ao contrário - 1.
O meu problema é que não sei nem por onde começar.
Alguém tem alguma diga de como faço essa implementação… vlw galera!!!
Tava precisando mesmo tirar um pouco da ferrugem em threads, segue um código que fiz aqui pra exemplificar o funcionamento.
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* Classe que efetua uma busca paralela em um array de inteiros.
*
* @author Rafaelprp
* @date 31/05/2008
*/
public class TesteMain {
/**
* Aqui que começa a mágica.
*/
public static void main(String[] args) {
//Quanto mais itens, mais claro fica o comportamento paralelo das threads.
final int QUANTIDADE_ITENS = 20000;
//Geração do array de itens únicos pode demorar bastante.
//Uma boa ideía é gerar um array bem grande, que demora uns 5 minutos
//e depois serializar ele prum txt, e depois só ficar
//utilizando ele.
final boolean ITENS_UNICOS = true;
final int QTD_THREADS = 10;
final int VALOR_PROCURADO = 12436;
long time = System.currentTimeMillis();
Object[] array = getArray(QUANTIDADE_ITENS, ITENS_UNICOS);
time = (System.currentTimeMillis() - time);
System.out.println("######################");
System.out.println("Tempo para criação do array: " + time + " ms");
System.out.println("######################\n");
// só agora começa a busca.
buscar(QTD_THREADS, array, VALOR_PROCURADO);
}
/**
* Monta um array de inteiros de 0 a *total*, com ou sem elementos
* repetidos. Este método é opcional, só é usado par simular um array
* heterogêneo.
*
* Dependnedo da quantidade de itens, esse método quando for executado para
* gerar um array de itens únicos, pode demorar bastante...
*/
private static Object[] getArray(int totalElementos, boolean itensUnicos) {
List<Integer> lista = new ArrayList<Integer>();
Random rand = new Random();
while (lista.size() < totalElementos) {
Integer num = rand.nextInt(totalElementos);
if (!itensUnicos || !lista.contains(num)) {
lista.add(num);
}
}
return lista.toArray();
}
/**
* Efetua a busca.
*
* @param qtdThreads -
* Quantidade de threads que vc quer usar.
* @param array -
* Array com os itens da busca.
* @param target -
* Target procurado.
*/
private static void buscar(int qtdThreads, Object[] array, Object target) {
// Aproximadamente quantos itens do array serão vasculhados por thread.
int itensPorThread = (int) Math
.ceil((double) array.length / qtdThreads);
// Todas as threads pertencerão a esse grupo, isso é com para controle.
ThreadGroup group = new ThreadGroup("ThreadGroup Busca");
int inicio = 0;
int fim = itensPorThread;
List<Thread> threadList = new ArrayList<Thread>();
// Configuro as threads.
for (int i = 0; i < qtdThreads; i++) {
if (fim >= array.length) {
fim = (array.length - 1);
}
Runnable runnable = new BuscaParalela(array, target, inicio, fim);
threadList.add(new Thread(group, runnable, "T" + i));
inicio = ++fim;
fim += itensPorThread;
}
long time = System.currentTimeMillis();
// Inicio as threads
fire(threadList);
time = (System.currentTimeMillis() - time);
System.out.println("\n######################\n"
+ "Tempo decorrido na busca com : " + qtdThreads + " threads: "
+ time + " ms" + "\n######################\n");
}
/**
* Inicia as threads já configuradas.
*/
private static void fire(List<Thread> threads) {
for (Thread thread : threads) {
thread.start();
}
}
}
/**
* Essa é a classe que roda em cada thread, ela quem faza busca. Outro método de
* busca mais eficaz poderia fácilmente ser usado, utilizei a busca sequencial
* pois não é o foco do programa.
*/
class BuscaParalela implements Runnable {
private Object[] array;
private Object target;
private int inicio, fim;
/**
* Construtor.
*
* @param array -
* Array contendo todos os itens.
* @param target -
* O target que deve ser encontrado.
* @param inicio -
* O início da área de busca dessa instância.
* @param fim -
* O fim da área de busca dessa instância.
*/
BuscaParalela(Object[] array, Object target, int inicio, int fim) {
this.array = array;
this.target = target;
this.inicio = inicio;
this.fim = fim;
}
/**
* Efetua a busca.
*/
public void run() {
System.out.println("Iniciando busca de " + inicio + " - " + fim);
for (int i = inicio; i <= fim; i++) {
if (target.equals(array[i])) {
System.out.println("\n######################\n" + "'" + target
+ "' achado na posição " + i + " pela thread '"
+ Thread.currentThread().getName() + "'"
+ "\n######################\n");
// Matar as outras threads do grupo, opcional.
// Thread.currentThread().getThreadGroup().interrupt();
return;
}
}
System.out.println("Thread '" + Thread.currentThread().getName()
+ "' terminou a busca sem sucesso.");
}
}
Fiquei pensando em assuntos extras para esse problema.
Como que eu faria um controlador p/ essas threads que recebesse, caso alguma tenha sucesso encontrar, a posição onde está o item procurado, que também parasse as outras threads quando recebesse esse valor, ou que percebesse que todas as threads pararam sem encontrar uma resposta, porém sem ficar checando toda hora se elas estão vivas ou não, algo como ela ficar de prontidão p/ receber valores, mas sem comer recursos de cpu. Um sistema baseado em listeners e callbacks.
Outra pergunta, como faço p/ reusar uma thread que já terminou seu processamento, p/, por exemplo, dar outro intervalo de pesquisa p/ ela procurar. O objetivo seria criar um número fixo de threads, umas 4, para checarem 10 intervalos, mas sem dar new para criar novas threads.
[quote=Bruno Laturner]Fiquei pensando em assuntos extras para esse problema.
Como que eu faria um controlador p/ essas threads que recebesse, caso alguma tenha sucesso encontrar, a posição onde está o item procurado, que também parasse as outras threads quando recebesse esse valor, ou que percebesse que todas as threads pararam sem encontrar uma resposta, porém sem ficar checando toda hora se elas estão vivas ou não, algo como ela ficar de prontidão p/ receber valores, mas sem comer recursos de cpu. Um sistema baseado em listeners e callbacks.
[/quote]
Dê uma olhada em Executer , ExecuterService, Future e Callable no pacote java.util.concurrent
[quote]
Outra pergunta, como faço p/ reusar uma thread que já terminou seu processamento, p/, por exemplo, dar outro intervalo de pesquisa p/ ela procurar. O objetivo seria criar um número fixo de threads, umas 4, para checarem 10 intervalos, mas sem dar new para criar novas threads.[/quote]
Vc não pode reutilizar threads que já terminaram. Simplesmente não pode.
O truque é manter um Thread , ou mais, ativas num loop infinito e passar a elas Runnables ou Collables para serem executados.
Quanto não há nada para correr a Thread simplesmente entra em espera ( sleep). Este tipo de mecanismo é simples de utilizar com os Executer disponiveis principallemnte ThreadPoolExecuterService
[quote=latino]Então pessoal tenho q criar uma classe em java que permita paralelizar uma pesquisa em um array de inteiros. Isso deve ser feito com o seguinte método: public static int parallelSearck(int x, int[] A, int numThreads). Este método cria tantas threads quanto especificadas em numThreads, divide o array A em muitas partes e cada thread parte do array para procurar sequencialmente pelo valor x. Se uma thread encontrar o valor x, então é retornado o índice i (A[i] = x), ao contrário - 1.
O meu problema é que não sei nem por onde começar.
Alguém tem alguma diga de como faço essa implementação… vlw galera!!!
[/quote]
olha num tenho nenhuma ideia por enquanto … qndo eu conseguir algma ideia te passso. ok ?
uma perguntinha se vc tiver orkut me passa teu i-mail por favor… te adoro xauu
