Qual é a melhor maneira de retornar uma linha aleatória em um arquivo de texto usando C?

Qual é a melhor maneira de retornar uma linha aleatória em um arquivo de texto usando C? Ele tem que usar a biblioteca padrão de E / S ( ) porque é para o homebrew do Nintendo DS.

Esclarecimentos:

  • Usar um header no arquivo para armazenar o número de linhas não funcionará para o que eu quero fazer.
  • Eu quero que seja o mais random possível (o melhor é se cada linha tiver uma probabilidade igual de ser escolhida como qualquer outra linha).
  • O arquivo nunca será alterado enquanto o programa estiver sendo executado. (É o DS, então não há multitarefa.)

Leia cada linha e use um número random para escolher se deseja manter essa linha ou ignorá-la. Para a primeira linha, você deseja que as odds de 1: 1 sejam mantidas; para o segundo, você quer chances de 1: 2, etc.

 count = 0; while (fgets(line, length, stream) != NULL) { count++; if ((rand() * count) / RAND_MAX == 0) strcpy(keptline, line); } 

Eu não verifiquei que isso tem as qualidades aleatórias adequadas, mas parece certo à primeira vista.


Tem sido apontado que o transbordamento de números inteiros rapidamente se tornaria um problema com a forma como a comparação é codificada, e eu mesmo tinha chegado independentemente à mesma conclusão. Existem provavelmente muitas maneiras de consertá-lo, mas esta é a primeira que vem à mente:

 if ((rand() / (float)RAND_MAX) <= (1.0 / count)) 

A resposta de Mark está quase correta, exceto por dois problemas:

  1. Se uma linha for maior que o length - 1 caractere (incluindo a nova linha), o loop while será incrementado pelo menos duas vezes para a mesma linha: uma vez para o primeiro length - 1 caracteres, outro para o próximo length - 1 caracteres, etc .
  2. O cálculo de rand() * count pode causar um estouro de inteiro.

Para resolver o primeiro problema, você pode chamar fgets em um buffer de lixo até que ele retorne NULL (indicando um erro de E / S ou EOF sem leitura de dados) ou o buffer de lixo contenha uma nova linha:

 count = 0; while (fgets(line, length, stream) != NULL) { char *p = strchr(line, '\n'); if (p != NULL) { assert(*p == '\n'); *p = '\0'; // trim the newline } else { // haven't reached EOL yet. Read & discard the rest of the line. #define TRASH_LENGTH 1024 char trash[TRASH_LENGTH]; while((p = fgets(trash, TRASH_LENGTH, stream)) != NULL) { if ((p = strchr(trash, '\n')) != NULL) // reached EOL break; } } assert(strchr(line, '\n') == NULL); // `line` does not contain a newline count++; // ... 

O segundo problema pode ser resolvido com a sugestão de @tvanfosson se a aritmética de ponto flutuante não estiver disponível:

 int one_chance_in(size_t n) { if (rand() % n == 0) // `rand` returns an integer in [0, `RAND_MAX`] return 1; else return 0; } 

Mas note que rand() % n não é uma variável aleatória discreta uniforme, mesmo se rand() for assumido como um porque a probabilidade de rand() % n == 0 poder ser tanto quanto 1 / RAND_MAX maior que o desejado probabilidade 1 / n . Na minha máquina, RAND_MAX é 2147483647, então a diferença é 4.66 × 10 -10 , mas o padrão C requer apenas que RAND_MAX seja pelo menos 32767 (3.05 × 10-5 diferença).

Além disso, se alguém se perguntar por que esse esquema funciona (como eu estava), pode ser útil trabalhar com o cálculo da probabilidade de a primeira linha permanecer em keptline se houver m linhas e generalizar: Na primeira iteração do loop , a probabilidade de que a primeira linha seja copiada para keptline é 1/1. Na segunda iteração do loop, a probabilidade de a segunda linha não sobrescrever a primeira linha é 1/2. Na terceira iteração, a probabilidade de a terceira linha não sobrescrever a primeira linha é de 2/3. Continuando, a probabilidade de a última linha não sobrescrever a primeira linha é ( m – 1) / m . Assim, a probabilidade de que a primeira linha permaneça na linha keptline após iterar em todas as linhas é:

1/1 × 1/2 × 2/3 × 3/4 × … × ( m – 2) / ( m – 1) × ( m – 1) / m = 1 / m

A probabilidade de a segunda linha permanecer no keptline é:

1/2 × 2/3 × 3/4 × … × ( m – 2) / ( m – 1) × ( m – 1) / m = 1 / m

A probabilidade de que a terceira linha permaneça no keptline é:

1/3 × 3/4 × … × ( m – 2) / ( m – 1) × ( m – 1) / m = 1 / m

Etc. Eles são todos 1 / m .

Esse método é bom porque:

i) Você pode continuar gerando linhas aleatórias sem grandes custos

ii) Você só tem que ler o arquivo um total de 1 vez + 1 linha de cada vez por linha aleatória que você deseja. O excesso de dados lidos é apenas igual ao tamanho do arquivo.

iii) Dá a cada linha uma chance justa, não importando qual seja sua posição no arquivo.

iv) Dá a cada linha uma chance justa, não importando sua extensão no arquivo.

A sugestão:

Eu sugeriria um algoritmo de 2 passadas. Bem, realmente é um passe de 1 + N linhas. Onde N é o número de linhas aleatórias que você deseja.

O primeiro passo que você usaria para calcular quantas linhas e as posições iniciais de cada linha.

Você então pega um número random de 0 até o número de linhas menos 1. Use esse número random, que é o seu índice de linha, obtenha a posição inicial para aquele índice de linha. Procure essa posição.

Você tem apenas mais 1 leitura necessária e sabe o tamanho exato. (até o índice inicial da próxima linha)

Como armazenar o número de linhas e o índice de cada linha:

Para armazenar o número de linhas, você pode obviamente usar apenas um int.

Se você puder usar um vetor, poderá adicionar cada índice de linha ao vetor. Se não, você pode simplesmente criar uma matriz de ints com o número máximo de linhas que você acha que haverá. Em seguida, indexe nessa matriz.

Outras respostas:

Outra resposta mencionada é que você pode escolher um número random de 1 para o tamanho do arquivo e, em seguida, usar a nova linha mais próxima. Mas isso não vai funcionar. Por exemplo, você pode ter 1 linha que é realmente longa e as outras que não são tão longas. Nesse caso, você teria uma distribuição desigual.

  1. Obtenha o comprimento do arquivo.
  2. Escolha uma posição aleatória no arquivo.
  3. Procure essa posição.
  4. Iterar para frente até encontrar um caractere de nova linha.
  5. Se você não encontrar um caractere de nova linha, volte ao início.
  6. Use gets () para ler a linha.

Eu tenho uma solução alternativa. Como a plataforma é o DS, você provavelmente não desejará tentar manter o arquivo na memory. Isso lê o arquivo duas vezes. Uma vez para contar as linhas e a segunda vez para encontrar a linha que deseja. Isso seria mais lento do que as outras soluções sugeridas até agora, mas quase não usa memory. Eu até escrevi em C para você (omiti tratamento de erros):

 main(int argc, char **argv) { FILE *f; int nLines = 0; char line[1024]; int randLine; int i; srand(time(0)); f = fopen(argv[1], "r"); /* 1st pass - count the lines. */ while(!feof(f)) { fgets(line, 1024, f); nLines++; } randLine = rand() % nLines; printf("Chose %d of %d lines\n", randLine, nLines); /* 2nd pass - find the line we want. */ fseek(f, 0, SEEK_SET); for(i = 0; !feof(f) && i <= randLine; i++) fgets(line, 1024, f); printf("%s", line); } 

UPDATE: Oops, eu deveria ter lido a resposta de Brian R. Bondy antes de postar isso, mas eu estava meio obcecada em escrever o código e não percebi. Isso é quase o mesmo, exceto que não armazena as posições de linha em uma matriz. Você pode fazer isso de qualquer maneira, dependendo do tamanho do arquivo e se a velocidade é mais importante do que salvar memory.

Tudo o que você precisa é gerar um número random não escalonado por linha, mantendo o valor máximo para todos os números randoms gerados. Sempre que você atualiza o valor máximo, você sobrescreve a linha selecionada com a linha atual.

No final, você obtém a linha associada ao maior número rand () cuspido, que deve ser igualmente provável entre todas as suas linhas.

Apenas uma nota rápida sobre a maneira de Mark Ransom evitar o estouro de inteiro: o DS não tem FPU, então a divisão de ponto flutuante será emulada no software e muito lenta. Você vai querer evitar typecasting / promoção para flutuar ou dobrar a todo custo, se a velocidade é uma preocupação.

Aqui está uma maneira diferente de evitar o estouro de inteiro que evita qualquer matemática de ponto flutuante:

 if(rand() <= RAND_MAX / count) 

As probabilidades podem ser ligeiramente distorcidas devido à divisão de inteiros, mas isso certamente deve ser executado muito mais rápido em um DS.

Use uma combinação do deslocamento random de Adam na abordagem de arquivo e na abordagem de probabilidade de Mark. O método de Adam pode levá-lo aleatoriamente para uma seção do arquivo. Então você usa a abordagem de Mark para evitar preferir as strings maiores. O algoritmo de Mark irá preferir as primeiras strings de onde quer que ele comece,