Trabalhando com threads

Smalltalk Membro desde: 30/05/2008 17:49:00 Mensagens: 2 Offline

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!!!

Voce pode começar lendo esse artigo:

http://www.guj.com.br/java.tutorial.artigo.43.1.guj

vlws

GUJ Ranger Membro desde: 27/04/2005 18:52:49 Mensagens: 822 Offline

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.");
	}
}

[]´s

GUJ Expert Membro desde: 18/02/2008 16:17:53 Mensagens: 3002 Offline

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.

Smalltalk Membro desde: 30/05/2008 17:49:00 Mensagens: 2 Offline

Flw Rafael fui de grã ajuda.... t mais

GUJ Expert Membro desde: 22/03/2005 20:57:48 Mensagens: 3433 Offline

Bruno Laturner wrote: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.

Dê uma olhada em Executer , ExecuterService, Future e Callable no pacote java.util.concurrent

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.

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

This message was edited 1 time. Last update was at 02/06/2008 12:01:31

sergiotaborda wrote:Dê uma olhada em Executer , ExecuterService, Future e Callable no pacote java.util.concurrent

Postei um exemplo sobre isso aqui: http://www.guj.com.br/posts/list/50321.java#264645

Smalltalk Membro desde: 20/07/2009 12:01:02 Mensagens: 1 Offline

latino wrote: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!!!

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

Notícias, artigos e o maior fórum brasileiro sobre Java