1

O objetivo do meu programa é implementar um heap de tamanho limitado, cuja as entradas são apenas números. Para definir a prioridade de cada elemento, é necessário buscar quando ele repetirá novamente pela primeira vez. Quanto maior a prioridade, nos mais altos níveis da árvore do heap ele deverá estar (o elemento com maior prioridade é a raíz).
Supondo que o heap tenha um tamanho 2:
- Os dois primeiros elementos são adicionados
- Para adicionar o terceiro elemento, é necessário remover o elemento do heap com maior prioridade e liberar espaço para o terceiro elemento
Exemplo:
0 1 2 2 1
A prioridade do primeiro 0 é um número grande o suficiente já que não se repete, do 1 é 5, do 2 é 4.
A prioridade do segundo 1 e 2 respectivamente: um número grande o suficiente pois não se repetem mais.
Obs: Se houvesse mais um número 2, a prioridade do último 2 seria 6.
Elementos do heap por ordem de interação supondo que tenha tamanho 2
1) 0 1
2) 1 2
3) 1 2
4) 1 2 (Neste caso pouco importa quem é a raíz)

O problema é: Implementei e esse programa está lento para 10000 entradas, como otimizar? Para buscar onde o próximo elemento de X se repete, supondo que a posicão de X é [Xo] eu caminho todo o vetor indo de [Xo+1] até achar o primeiro elemento (sei o tamanho do vetor então é feito somente 1 malloc).

Partes do programa que suponho que tenha as maiores complexidades, principalmente as funções ajustarRemocaoMaximo que garante a propriedade do heap e a função descrita anteriormente alterarPrioridade na qual o item elemento.quantidade é a prioridade.

/* Ajusta para que continue sendo heap apos a remocao da raiz */
void ajustarRemocaoMaximo(ElementoCache **pointerHeap){
    ElementoCache *heap = *pointerHeap;
    int pos = 1;
    if(pos*2 < tamanhoCache && ((2*pos)+1) < tamanhoCache){
        if(((2*pos)+1) >= tamanhoCache){
            if(heap[pos].quantidade < heap[pos*2].quantidade){
                ElementoCache *maiorFilho = &heap[2*pos];
                ElementoCache paiTemp = heap[pos];
                heap[pos] = *maiorFilho;
                *maiorFilho = paiTemp;
            }
            return ;
        }

        while(heap[pos].quantidade < heap[pos*2].quantidade || heap[pos].quantidade < heap[(2*pos)+1].quantidade){
            //if(heap[2*pos].elemento == -1)
            //    break;
            ElementoCache *maiorFilho;
            int posFilho = 0;
            if((heap[2*pos].quantidade > heap[(2*pos)+1].quantidade) || (heap[2*pos].quantidade == heap[(2*pos)+1].quantidade)){
                maiorFilho = &heap[2*pos];
                posFilho = 2*pos;
            }else if(heap[2*pos].quantidade < heap[(2*pos)+1].quantidade){
                maiorFilho = &heap[(2*pos)+1];
                posFilho = (2*pos)+1;
            }
            ElementoCache paiTemp = heap[pos];
            heap[pos] = *maiorFilho;
            *maiorFilho = paiTemp;
            pos = posFilho;
            if(pos >= (tamanhoCache-1) || (pos*2) >= (tamanhoCache-1)) break;
        }
    }
}

/* Verificar se determinado elemento esta no heap e o substitui */
int contemElemento(ElementoCache elemento, ElementoCache **pointerHeap){
    ElementoCache *heap = *pointerHeap;
    int i = 0;
    for(i = 1; i < tamanhoCache; i++){
        if(heap[i].elemento == elemento.elemento){
            heap[i] = elemento;
            return 1;
        }
    }
    return 0;
}

void alterarPrioridade(ElementoCache **pointElementos, int tamanho){
    ElementoCache *elementos = *pointElementos;
    int i = 0;
    int j = 0;
    for(i = 0; i < tamanho; i++){
        for(j = i+1; j < tamanho; j++){
            if(elementos[i].elemento == elementos[j].elemento){
                elementos[i].quantidade = j;
                break;
            }
            elementos[i].quantidade = 10001;
        }
    }
}

/* Ira inserir o elemento na ultima posicao do array e ajustar de acordo com a prioridade. O heap possuir -1 como elemento significa que eh uma posicao vazia */
void adicionarElemento(ElementoCache heap[], ElementoCache item){
    //Buscar primeira posicao vazia
    int i = 1;
    int contemPosicaoVazia = 0;
    if(heap[i].elemento == -1){
        heap[1] = item;
        contador++;
    }else{

        //Verificar se o elemento ja esta no heap
        if(contemElemento(item, &heap) == 1){
            ajustarRemocaoMaximo(&heap);
            return ;
        }
        int posicaoVazia = 0;
        for(i = 2; i < tamanhoCache; i++){
            if(heap[i].elemento == -1){
                contemPosicaoVazia = 1;
                posicaoVazia = i;
                break;
            }
        }
        //Tornar o maximo sempre a raiz da arvore
        if(contemPosicaoVazia == 1){
            heap[posicaoVazia] = item;
            contador++;
            if((posicaoVazia/2) != 0){ //FIXME: Posicao vazia nunca sera 0
                //Verifica se o filho eh maior que o pai
                while((heap[posicaoVazia].quantidade > heap[posicaoVazia/2].quantidade)){
                    ElementoCache temporario = heap[posicaoVazia/2];
                    heap[posicaoVazia/2] = heap[posicaoVazia];
                    heap[posicaoVazia] = temporario;
                    posicaoVazia = posicaoVazia/2;
                    if(posicaoVazia == 1) break;
                }
            }
        }else{
            //Remover a raiz da arvore. A nova raiz deve ser o ultimo elemento do heap
            heap[1] = heap[tamanhoCache-1];
            heap[tamanhoCache-1].elemento = -1;
            heap[tamanhoCache-1].quantidade = 0;
            ajustarRemocaoMaximo(&heap);
            adicionarElemento(heap, item);
        }
    }
}

void lerSolicitacoes(ElementoCache heap[], InfoCache *informacoes){
    int i = 0;
    for(i = 0; i < informacoes->qtdSolicitacoes; i++){
        adicionarElemento(heap, informacoes->elementos[i]);
    }
}
1
  • 1
    Lento é relativo, qual a performance do seu algoritmo hoje e quanto você esperava?
    – Genos
    14/11/2016 às 10:26

0

Você deve fazer log-in para responder a esta pergunta.

Pesquise outras perguntas com a tag .