Dificuldade para gravar dados em um arquivo (Iniciante C) [RESOLVIDO]

paulo1205
(usa Ubuntu)

Enviado em 26/02/2019 - 00:52h

Note porém que seu algoritmo, conquanto funcione, será terrivelmente lento para você filtrar 201.000 linhas de tamanho muito longo (a não ser que você tenha um caso trivial, em que quase todas as linhas sejam iguais), pois cada nova linha terá de ser comparada com todas as anteriores, de modo que o algoritmo tem tempo de execução quadrático (ou seja: proporcional ao quadrado do número de linhas). Assim, se você não quiser acabar com um laço de repetição com dezenas de bilhões de repetições, tem de mudar de estratégia.

Uma forma de reduzir a complexidade do algoritmo é evitando ter de varrer todo o conteúdo do segundo arquivo para cada linha nova lida do primeiro. Usando busca binária, você pode conseguir reduzir a ordem de complexidade de cada busca de n para log n, o que já é um grande ganho. Como serão mais de 200.000 buscas, você terá algo em torno de alguns milhões de comparações, umas mil vezes menos do que com busca linear.

Se você puder usar hashes, a complexidade da busca tende a cair mais ainda, da ordem de n para um valor praticamente constante a cada busca, de modo que a quantidade de operações tende a ser próxima da quantidade de itens.

O problema é que criar arquivos representando árvores e tabelas hash não é trivial de fazer na unha. Felizmente, porém, existem bibliotecas prontas para isso, como Berkeley DB (hoje pertencente à Oracle, mas mesmo a antiga versão 1.85, que costumava vir com os BSD e algumas distribuições de Linux, basta para tanto) e a GDBM.

O exemplo abaixo usa uma tabela hash por meio de Berkeley DB num arquivo temporário, que é apagado ao final do programa. Normalmente o Berkeley DB é usado para associar cada chave de consulta a um valor, mas no caso em questão, interessa apenas a chave de consulta, de modo que o valor associado é deliberadamente deixado vazio.

#include <stdio.h>

#include <string.h>

#include <sys/types.h>

#include <limits.h>

#include <db_185.h>  // Ou apenas <db.h>, se for num BSD ou com um Linux antigo.

#include <fcntl.h>

#include <unistd.h>





int main (){

  FILE *File1 = fopen("1", "w+"), *File2 = fopen("2", "w+");

  fputs("Linha A\nLinha B\nLinha B\nLinha C\nLinha D\nLinha A\n", File1);

  

  rewind(File1);



  char Line_File1[10] = {0};



  DB *known_lines=dbopen("known_lines.db", O_CREAT|O_TRUNC|O_RDWR, 0644, DB_HASH, NULL);



  while(fgets(Line_File1, sizeof(Line_File1), File1) != NULL) {

    DBT key, value;

    key.data=Line_File1;

    key.size=strlen(Line_File1);

    if(known_lines->get(known_lines, &key, &value, 0)==1){

      value.data=NULL;

      value.size=0;

      known_lines->put(known_lines, &key, &value, 0);

      fputs(Line_File1, File2);

    }

  }

  known_lines->close(known_lines);

  unlink("known_lines.db");

  fclose(File2);

  fclose(File1);

} 

Para compilar, use algo como “gcc -Wall -Werror -O2 -pedantic-errors filtra_repetidos.c -o filtra_repetidos -ldb”.


... “Principium sapientiae timor Domini, et scientia sanctorum prudentia.” (Proverbia 9:10)