4

O numero de elemento chegam a 100000 e tenho que comparar com outro vetor de 100000, como eu posso fazer isso com um ganho de desemprenho muito alto

Forma como estou comparando os vetores

for(i = 0; i < teste; i++)
{
    for(j = 0; j < teste; j++)
    {
        if(indice[i] == aux[j])
        {
            cont++;
        }
    }
}
3
  • Para teu cenário esse modo recursivo é o recomendado, já que você precisa verificar cada valor; caso pretenda apenas comparar se os vetores são iguais, pode usar strcmp. Commented 30/05/2018 às 2:28
  • olá Mauro, o vetor são de números, então não vai da pra utilizar o strcmp, você poderia me dar um exemplo de como seria esse modo recursivo ?, obrigado desde já Commented 30/05/2018 às 2:32
  • Tem os valores iguais de que forma ? tem os mesmos numeros nas mesmas posições ? Ou os mesmos numeros mesmo que em posições diferentes ?
    – Isac
    Commented 30/05/2018 às 10:48

3 Respostas 3

3

Você pode tentar criar um vetor hash, por exemplo

char hash[0x7FFFFFFF];

se forem possíveis quaisquer números inteiros positivos.

Inicialize o vetor,

for (int i = 0; i < 0x7FFFFFFF; ++i)
{
    hash[i] = 0;
}

Itere um dos seus vetores originais e use o hash para saber que aquele número existe neste vetor:

for (int i = 0; i < teste; ++i)
{
    hash[indice[i]] = 1;
}

Daí itere o segundo vetor, incrementando cont caso o hash já esteja preenchido,

for (int i = 0; i < teste; ++i)
{
    if (hash[aux[i]])
    {
        ++cont;
    }
}

Dessa forma a complexidade passa a ser O(n), em vez de O(n^2), que era teu caso.

O problema, agora, é que é usada muita memória RAM. 1 GB de RAM, no mínimo, só para o vetor hash...

Então existe uma contrapartida entre complexidade algorítmica e complexidade espacial, que deve ser sempre levada em consideração.

3
  • 1
    Acho legal citar os métodos de busca/ordenação também! Podem ser úteis para aprendizagem (por exemplo, este algoritmo usado na pergunta seria um "Bubble Sort".. introduzir um "Shell Sort" ou "Selection Sort" para o Rafael estudar ia bem!) Commented 30/05/2018 às 11:48
  • 2
    Obrigado marcelo funcionou Commented 30/05/2018 às 16:12
  • Vou pesquisar Cleber, obrigado pela dica Commented 30/05/2018 às 16:12
-1
#include <stdio.h>

int vet[3] = {2, 5, 7};
int var[3] = {2, 5, 5};

void verifica(int valor, int posicao){
    if(valor == vet[posicao]){
        printf("%d = %d\n",valor, vet[posicao]);
    }else{
        printf("[%d] != [%d] Não é igual !",valor, vet[posicao]);
    }
}

int main(){
    
    for(int i = 0; i < 3; i++){
        verifica(var[i], i);
    }

    return 0;
}
1
  • 1
    Sua resposta pode ser melhorada adicionando informações fundamentais. Basta editar para adicionar mais detalhes, como citações ou documentação para que outras pessoas possam confirmar que sua resposta está correta. Você pode encontrar mais informações sobre como escrever boas respostas na Central de Ajuda.
    – Comunidade Bot
    Commented 11/11/2021 às 2:45
-2

EDIT: Não tinha visto os comentários do post inicial. Pensei que a intenção era verificar a igualdade de dois vetores (em um sentido mais matemático). Aparentemente, deseja-se tratar uma array como um conjunto de elementos (repetidos ou não), e verificar se eles possuem os mesmos elementos. Sendo assim, esta solução não funcionará.


Se a intenção é apenas verificar se dois vetores são iguais, E considerando que estes sejam de mesmo tamanho, você pode talvez utilizar o memcmp:

#include <stdio.h>

/* memcmp é declarado nesta lib */
#include <string.h>

int vet1[] = {0, 1, 3};
int vet2[] = {0, 1, 2};

int main() {
  /* Note que esta comparação só é válida pois:
   * 1. Ambos os vetores possuem o mesmo tamanho (3 elementos); E
   * 2. Ambos os vetores possuem o mesmo tipo de elemento (int).
   */
  if (memcmp(&vet1, &vet2, sizeof vet1) == 0) {
    printf("iguais\n");
  } else {
    printf("diferentes\n");
  }
}

Pastebin (executável): https://glot.io/snippets/g44yb5qaoh

Isto só funciona se os dois vetores possuírem o mesmo layout em memória, o que é o caso. Sendo assim, eles podem ser comparados byte a byte, ao invés de elemento a elemento.

Em alguns casos, memcmp é uma melhor opção do que um simples loop, já que a maioria dos toolchains otimizam-o via SIMD ou funcionalidade semelhante a nível de hardware. Vide:

Caso não haja uma otimização disponível, dada a simples assinatura do memcmp, não deve ser difícil implementar esta função usando compiler intrinsics [1]. No seu caso, especificamente (decidir se um vetor é igual ao outro), pode-se simplificar a definição da função para contemplar apenas igualdade (i.e. remover do retorno da função a necessidade de efetuar o cálculo da diferença entre os primeiros bytes que diferem nos dois vetores).


[1] Vide também: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

9
  • 1
    Ele não que ver se dois vetores são idênticos. Quer saber se dois vetores de mesmo comprimento possuem os mesmos elementos independente da ordem que se encontrem. No caso seria necessário ordenar os dois vetores antes de usar a função memcmp(). Commented 11/11/2021 às 11:51
  • Como está escrito atualmente, sua resposta não é clara. Por favor, pode editar para adicionar mais detalhes, que ajudarão outras pessoas a entender como isso resolve a pergunta feita. Você pode encontrar mais informações sobre como escrever boas respostas na Central de Ajuda.
    – Comunidade Bot
    Commented 11/11/2021 às 11:59
  • @AugustoVasques isso não ficou claro no enunciado. O que você descreve é mais similar a conjuntos. Ele falou sobre comparação de vetores, e não sobre comparação de conjuntos. Commented 11/11/2021 às 12:01
  • @FlávioLisbôa, você está equivocado. Na pergunta, aquela estrutura de comparação envolvendo laços aninhados é a contração dos algoritmos de comparação como o algoritmo de ordenação bubble sort. Commented 11/11/2021 às 12:02
  • @AugustoVasques agora li os comentários do post inicial, e percebi o que o autor realmente quis perguntar. Editei a resposta para indicar que ela não funcionará para o que foi pedido. Obrigado pela revisão. Commented 11/11/2021 às 12:08

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

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .