Ordenaçao externa multicaminhos utilizando metodo mergesort

uNclear
(usa Slackware)

Enviado em 09/03/2017 - 15:57h

Eu fiz um codigo de ordenaçao externa que separa a quantidade dos dados contidos no arquivo em 2, e começa a ordenar apatir dai como se fosse um mergesort, agora preciso fazer um codigo q utiliza multicaminhos, ou seja, que separa o arquivo em 3, 4 ou mais. Alguem ai sabe me falar se o codigo complica mt a cada vez que eu dividir mais o arquivo?

Espero ter sido claro.
Obrigado!

paulo1205
(usa Ubuntu)

Enviado em 09/03/2017 - 16:17h

Nunca tive de fazer isso, mas não creio que fique muito mais difícil.

No caso específico do merge, a dificuldade será que você terá de comparar n valores, e escolher o menor (ou o maior) entre eles, em vez de comparar só dois. Será o clássico algoritmo de presumir que o valor a ser usado será o primeiro, e depois varrer os outros n-1 valores, sendo que a cada vez que um valor mais adequado for encontrado, você muda a sua presunção, até ter examinado todos os n, com a pequena dificuldade adicional de que qualquer um desses n pode, a qualquer momento, estar ausente (i.e. aquele ramo já esgotou todos os valores).

uNclear
(usa Slackware)

Enviado em 09/03/2017 - 16:21h

O meu merge esta terminando antes de ordenar todo o arquivo. Visto que, dividi o arquivo principal em 3, o laço que checa se os 3 chegaram ao fim esta terminando antes de efetuar todas as ordenaçoes. E parece que as comparaçoes estao corretas.
Uma das soluçoes que pensei que primeiro ordenar 2 partes e depois ordernar com a 3 parte, mas n sei se ficaria bom

paulo1205
(usa Ubuntu)

Enviado em 09/03/2017 - 17:00h

Você pode sim, fazer um merge de 2, e depois fazer um merge desse resultado com um terceiro, mas eu acho que não é a melhor saída.

Você pode mostrar essa parte do código, para tentarmos ajudar a ver por que motivo está parando antes do fim?

uNclear
(usa Slackware)

Enviado em 09/03/2017 - 17:11h

bool intercalaBloco(ifstream auxE[3], ofstream auxS[3], int passo, int saida){

	//consideramos inicialmente que nao ia fazer nenhuma intercalaçao

	bool intercalou = false;

	Dado dados[3];

	

	//posicao relativa de leitura em cada um dos arquivos

	int pos[3] = {0, 0, 0};

	

	//variavel para informar se os dados do arquivos sao validos (se foram lidos do arquivo de entrada e ainda nao gravados no arquivo de saida)

	bool valido[3] = {false, false, false};

	

	//em cada passo de tamanho n lemos n dados de cada arquivo e fazemos intercalaçao parcial em um novo bloco de tamanho 3*n no arquivo de saida utilizado

	while( (pos[0] + pos[1] + pos[2]) < (3*passo)  ){

		//inicialmente verificamos se ha dados para ler 

		if( (pos[0] < passo) && (!valido[0]) ){

			//tentamos ler do arquivo, verificando se a leitura foi valida, leitura invalida -> final do arquivo

			if(auxE[0].read((char*) &dados[0], sizeof(Dado)) ){

				valido[0] = true;

			} else{

				//para encerrer o while e nao entrar no if novamente

				pos[0] = passo;

			}

		}

		

		// repetimos o processo para o segundo arquivo

		if( (pos[1] < passo) && (!valido[1]) ){

			if(auxE[1].read((char*) &dados[1], sizeof(Dado)) ){

				valido[1] = true;

			} else{

				//para encerrer o while e nao entrar no if novamente

				pos[1] = passo;

			}

		}

		

		if( (pos[2] < passo) && (!valido[2]) ){

			if(auxE[2].read((char*) &dados[2], sizeof(Dado)) ){			

				valido[2] = true;

			} else{

				//para encerrer o while e nao entrar no if novamente

				pos[2] = passo;

			}

			

		}

		

		//nesse momento temos dados lidos dos 3 arquivos a nao ser que um (ou ambos) tenha chegado ao fim

		

		//1º caso, os dois dados sao validos

		if( (valido[0] && valido[1] )&& valido[2] ){

			//marca que intercalou

			intercalou = true;

			//gravamos o menor valor no arquivo de saida

			if(dados[0].chave1 <= dados[1].chave1 && (dados[0].chave1 <= dados[2].chave1)){

				auxS[saida].write( (char*) &dados[0], sizeof(Dado) );

				//dado utilizado nao e mais valido, avança posiçao

				valido[0] = false;

				pos[0]++;

			}else if(dados[1].chave1 <= dados[0].chave1 && (dados[1].chave1 <= dados[2].chave1)){	

				auxS[saida].write( (char*) &dados[1], sizeof(Dado) );

				//dado utilizado nao e mais valido, avança posiçao

				valido[1] = false;

				pos[1]++;

			}else if(dados[2].chave1 <= dados[0].chave1 && (dados[2].chave1 <= dados[1].chave1)){

				auxS[saida].write( (char*) &dados[2], sizeof(Dado) );

				//dado utilizado nao e mais valido, avança posiçao

				valido[2] = false;

				pos[2]++;

			}

			/*else{

				auxS[saida].write( (const char*) &dados[1], sizeof(Dado) );

				//dado utilizado nao e mais valido, avança posiçao

				valido[1] = false;

				pos[1]++;

			}*/

		}

		

		//2º caso, apenas o primeiro dado e valido

		else if(valido[0]){

			//marca que intercalou

			intercalou = true;

			auxS[saida].write( (char*) &dados[0], sizeof(Dado) );

			//dado utilizado nao e mais valido, avança posiçao

			valido[0] = false;

			pos[0]++;

		}

		

		//3º caso, apenas o segundo dado e valido

		else if(valido[1]){

			//marca que intercalou

			intercalou = true;

			auxS[saida].write( (char*) &dados[1], sizeof(Dado) );

			//dado utilizado nao e mais valido, avança posiçao

			valido[1] = false;

			pos[1]++;

		}	

		else if(valido[2]){

			//marca que intercalou

			intercalou = true;

			auxS[saida].write( (char*) &dados[2], sizeof(Dado) );

			//dado utilizado nao e mais valido, avança posiçao

			valido[2] = false;

			pos[2]++;

		}

		//se chegou aqui termina o while na proxima iteraçao

		else {

			

		}

	}

	return intercalou;

}



void mergeexterno(ifstream &arqEntrada, ofstream &arqSaida){

	ofstream arqB1 ("arqB1.dat", ios::binary);

	ofstream arqB2 ("arqB2.dat", ios::binary);

	ofstream arqB3("arqB3.dat", ios::binary);

	

	if((!arqB1) && (!arqB2) && (!arqB3)){

		cerr << "Arquivos auxiliares nao puderam ser abertos (arqB1.dat ou arqB2.dat )" << endl;

		exit(EXIT_FAILURE);

	}

	

	Dado umDado;

	

	//posicionando ponteiro de leitura no final do arquivo

	arqEntrada.seekg(0, ios::end);

	

	//obtendo a posicao final do arquivo

	int tamanho = arqEntrada.tellg();

	

	//dado o tamanho do arquivo, sabe-se quantos registos ha no arquivo

	int numRegistros = tamanho / sizeof(Dado);

	cout << numRegistros << endl;

	//metade do numero de registros (arredondado pra cima)

	int metade = (numRegistros / 3) + 0.5;

	cout << metade << endl;

	//posicionando ponteiro de leitura no inicio do arquivo

	arqEntrada.seekg(0, ios::beg);

	

	//copiando dados para 3 arquivos auxiliares

	for(int i = 0; i < metade; i++){

		arqEntrada.read((char*) &umDado, sizeof(Dado) );

		arqB1.write((char*) &umDado, sizeof(Dado) );

	}

	for(int i = metade; i < metade * 2; i++){

		arqEntrada.read((char*) &umDado, sizeof(Dado) );

		arqB2.write((char*) &umDado, sizeof(Dado) );

	}

	for(int i = metade * 2; i < numRegistros; i++){

		arqEntrada.read((char*) &umDado, sizeof(Dado));

		arqB3.write((char*) &umDado, sizeof(Dado));

	}

	

	//finalizaçao primeira etapa

	arqB1.close();

	arqB2.close();

	arqB3.close();

	arqEntrada.close();

	

	//arquivos auxiliares

	ifstream auxEntrada[3];

	ofstream auxSaida[3];

	

	//variaveis de controle

	int passo = 1;

	bool ida = true;

	bool ultimo[3];

	

	//laço principal

	while(passo <= numRegistros){

		if(ida){

			auxEntrada[0].open("arqB1.dat", ios::binary);

			auxEntrada[1].open("arqB2.dat", ios::binary);

			auxEntrada[2].open("arqB3.dat", ios::binary);

			auxSaida[0].open("arqC1.dat", ios::binary);

			auxSaida[1].open("arqC2.dat", ios::binary);

			auxSaida[2].open("arqC3.dat", ios::binary);

		}else{

			auxEntrada[0].open("arqC1.dat", ios::binary);

			auxEntrada[1].open("arqC2.dat", ios::binary);

			auxEntrada[2].open("arqC3.dat", ios::binary);

			auxSaida[0].open("arqB1.dat", ios::binary);

			auxSaida[1].open("arqB2.dat", ios::binary);

			auxSaida[2].open("arqB3.dat", ios::binary);

		}

		

		if( (!auxEntrada[0]) || (!auxEntrada[1]) || (!auxSaida[0]) || (!auxSaida[1]) || (!auxEntrada[2]) || (!auxSaida[2]) ){

			cerr << "Arquivos auxiliares nao podem ser abertos (arqB1.dat ou arqB2.dat ou arqC1.dat ou arqC2.dat)" << endl;

			exit(EXIT_FAILURE);

		}



		//enquanto nao chegar ao final dos arquivos de entrada, vai intercalando os blocos

		while( (!auxEntrada[0].eof()) && (!auxEntrada[1].eof()) && (!auxEntrada[2].eof()) ){

			ultimo[0] = intercalaBloco(auxEntrada, auxSaida, passo, 0);

			ultimo[1] = intercalaBloco(auxEntrada, auxSaida, passo, 1);

			ultimo[2] = intercalaBloco(auxEntrada, auxSaida, passo, 2);

		}

		

		//fecha arquivos para permitir troca escrita <-> leitura, na proximo interaçao

		auxEntrada[0].close();

		auxEntrada[1].close();

		auxEntrada[2].close();

		auxSaida[0].close();

		auxSaida[1].close();

		auxSaida[2].close();

		

		ida = !ida;

		passo *= 3;

	}

	

	//merge terminado, agora lemos do arquivo auxiliar para arquivo de saida

	ifstream auxEnt;

	

	//identifique o arquivo auxiliar com dados ordenados

	if(ida){

		if(ultimo[0]){

			auxEnt.open("arqB1.dat", ios::binary);

		}else if(ultimo[1]){

			auxEnt.open("arqB2.dat", ios::binary);

		}else if(ultimo[2]){

			auxEnt.open("arqB3.dat", ios::binary);

		}

	}else{

		if(ultimo[0]){

			auxEnt.open("arqC1.dat", ios::binary);

		}else if(ultimo[1]){

			auxEnt.open("arqC2.dat", ios::binary);

		}else if(ultimo[2]){

			auxEnt.open("arqC3.dat", ios::binary);

		}

	}

	

	if(!auxEnt){

		cerr << "Arquivo auxiliar nao pode ser aberto" << endl;

		exit(EXIT_FAILURE);

	}

	

	while(auxEnt.read((char*) &umDado, sizeof(Dado)) ){

		arqSaida.write((const char*) &umDado, sizeof(Dado) );

	}

	

	auxEnt.close();

	

	//apagar arquivos auxiliares

	remove("arqB1.dat");

	remove("arqB2.dat");

	remove("arqC1.dat");

	remove("arqC2.dat");

	remove("arqC3.dat");

	remove("arqB3.dat");



}

 

Obrigado mais uma vez pela ajuda o/

paulo1205
(usa Ubuntu)

Enviado em 10/03/2017 - 11:11h

Olha, eu não olhei muito profundamente, mas acho que a a função intercalaBloco() pode ficar mais simples e, ao mesmo tempo, mais genérica.

Sem querer implementar uma substituição pronta, deixe-me mostrar um esquema de como poderia ficar.

/*

  Lê um elemento do tipo Dado a partir da posição corrente de um stream de entrada.

*/

std::istream &operator>>(std::istream &source, Dado &d){

  // Não tenta ler se o stream já estiver marcado com falha.

  if(source){

    /*

      Implemente de acordo com o tipo de dados “Dado”.  Se ele for

      um POD, pode ser que um simples



        source.read(reinterpret_cast<char *>(&d), sizeof d);



      baste.  Mas se for um tipo mais complexo, você pode ter de ler

      membro a membro a partir de source.

    */

  }

  return source;

}



/*

  Lê n elementos do tipo Dado para uma fila de elementos desse tipo, a qual

  serve como buffer.  Assume o tamanho default da fila com 8 elementos.

*/

unsigned leBufDados(std::istream &source, std::deque<Dado> &queue, unsigned n=8){

  Dado d;

  unsigned i;

  for(i=0; i<n && (source >> d); i++)

    queue.push_back(std::move(d));  // Se Dado for um POD, remova a chamada a std::move(), deixando só d.

  return i;

}



/*

  Função que faz o merge externo a partir de um vetor de arquivos (via ponteiros para

  streams) de entrada para um arquivo de saída.  Retorna um flag indicando se a saída

  foi gravada com sucesso e se chegou ao fim de todos os arquivos de entrada.

*/

bool intercalaBloco(std::vector<std::istream *> &v_in, std::ostream &out){

  unsigned N=v_in.size();

  std::vector<std::deque<Dado>> buffer(N);  // Cria vetor de buffers, um para cada arquivo.



  // Se o stream de saída não for válido, interrompe o merge.

  while(out){

    unsigned  n;

    for(n=0; n<N; n++)

      if(buffer[n].size()>0 || leBufDados(*v_in[n], buffer[n])) 

        break;  // Acho dado no primeiro arquivo que ainda não tiver acabado.

    if(n==N)

      break;  // Fim de todos os arquivos de entrada: sai do loop de merge.



    // Se chegou a este ponto, n indica o primeiro arquivo/buffer que tem dados.



    // Assume que o dado desse arquivo é o próximo que tem de ir para a saída.

    auto menor=&buffer[n];



    /*

      Examina os demais arquivos, para ver se algum deles ainda tem dados e se

      esse dado é menor do que o escolhido até o momento.



      EM TEMPO: note que eu comparo com “<” em lugar de “<=”.  Fazendo com “<”,

        eu garanto ordenação estável, ou seja, que registros com duas chaves

        idênticas dispostas relativamente numa determinada ordem no arquivo

        original aparecerão na mesma ordem relativa no arquivo de saída.  Essa é

        uma propriedade do Merge Sort que frequentemente é desejada, especial-

        mente quando o arquivo é ordenado sucessivamente com diferentes chaves,

        mas que você acabou desprezando ao fazer com “<=”.

    */

    for(; n<N; n++)

      if(

        (buffer[n].size()>0 || leBufDados(*v_in[n], buffer[n])) &&

        buffer[n].front().chave1 < menor->front().chave1

      )

        menor=&buffer[[n];



    // Grava o menor no arquivo de saída e retira-o do seu buffer de entrada.

    out << menor->front();

    menor->pop_front();

  }



  for(n=0; n<N; n++)

    if(!v_in[n].eof())

      return false;

  return out;

} 

uNclear
(usa Slackware)

Enviado em 10/03/2017 - 11:25h

Vou dar uma matutada nesse código e ver o que consigo assimilar, mas pela a passada rápida que dei nele, parece que o problema do meu código esta na comparação das chaves para descobrir quem e a menor, visto que no código que você apresentou ele joga os valores para um fila para comparar. Estou correto?

paulo1205
(usa Ubuntu)

Enviado em 10/03/2017 - 13:54h

Estou tentando pensar melhor sobre o problema. Está me parecendo mais complicado agora do que na primeira olhada.

uNclear
(usa Slackware)

Enviado em 11/03/2017 - 00:59h

Eu to apanhando demais pra esse código, ja debuguei ele varias vezes e foi meu professor que fez a base do merge externo com 2 arquivos e mandou modificar pra mais 3, eu cheguei em várias conclusões diferentes. Mas a que me convence mais e que a lógica pra 2 arquivos não serve pra 3. Eu acho que o problema está no passo, o passo nao deveria aumentar so porque a quantidade de arquivos aumentou eu acho.