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.