Какой лучший способ вернуть случайную строку в текстовом файле с помощью C?

Question

Какой лучший способ вернуть случайную строку в текстовом файле с помощью C? Он должен использовать стандартную библиотеку ввода / вывода (<stdio.h>), потому что она предназначена для домашнего приготовления Nintendo DS.

Разъяснения:

• Использование заголовка в файле для хранения количества строк не сработает для того, что я хочу сделать.
• Я хочу, чтобы он был как можно более случайным (лучше всего, если каждая строка имеет одинаковую вероятность выбора, как и любая другая строка.)
• Файл никогда не изменится во время работы программы. (Это DS, так что нет многозадачности.)

Answer 1

Прочитайте каждую строку и используйте случайное число, чтобы выбрать, сохранять ли эту строку или игнорировать ее. Для первой строки вы хотите сохранить шансы 1: 1; для второго вам нужны шансы 1: 2 и т. д.

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

Я не проверял, что это имеет правильные случайные качества, но это кажется правильным на первый взгляд.

---

Было отмечено, что целочисленное переполнение может быстро стать проблемой при кодировании сравнения, и я сам пришел к тому же выводу. Вероятно, есть много способов исправить это, но это первое, что приходит на ум:

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

Answer 2

Марк отвечает почти правильно, за исключением двух вопросов:

1. Если строка длиннее length - 1 символов (включая новую строку), то цикл while будет увеличивать count не менее чем в два раза для одной и той же строки: один раз для первых length - 1 символов, другой для следующие length - 1 символов и т. д.
2. Вычисление rand() * count может вызвать переполнение целых чисел.

Чтобы решить первую проблему, вы можете вызвать fgets в буфер для мусора до тех пор, пока он не вернет NULL (что указывает на ошибку ввода-вывода или EOF без чтения данных) или в буфере для мусора есть новая строка:

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++;
    // ...

Вторую проблему можно решить с помощью предложения @ tvanfosson, если арифметика с плавающей точкой недоступна:

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

Но обратите внимание, что rand() % n не является равномерной, дискретной случайной величиной , даже если rand() предполагается равной единице, потому что вероятность того, что rand() % n == 0 может составлять 1 / RAND_MAX выше, чем желаемая вероятность 1 / n. На моей машине RAND_MAX равно 2147483647, поэтому разница составляет 4,66 × 10 ^-10 , но стандарт C требует только, чтобы RAND_MAX было не менее 32767 (3,05 × 10 ^{-5 *). 1035 * разница).}

Кроме того, для всех, кто интересуется, почему эта схема работает (как я), было бы полезно проработать расчет вероятности того, что первая строка останется в keptline, если есть m линии и обобщение: в первой итерации цикла вероятность того, что первая строка будет скопирована в keptline, равна 1/1. Во второй итерации цикла вероятность того, что вторая строка будет не перезаписать первую строку, равна 1/2. На третьей итерации вероятность того, что третья строка будет не перезаписать первую строку, равна 2/3. Продолжая, вероятность того, что последняя строка не перезапишет первую строку, равна ( m - 1) / m . Таким образом, вероятность того, что первая строка останется в keptline после итерации по всем строкам:

1/1 × 1/2 × 2/3 × 3/4 × ... × ( м - 2) / ( м - 1) × ( м - 1) / м = 1 / м

Вероятность того, что вторая строка останется в keptline, равна:

1/2 × 2/3 × 3/4 × ... × ( м - 2) / ( м - 1) × ( м - 1) / м = 1 / м

Вероятность того, что третья строка останется в keptline, равна:

1/3 × 3/4 × ... × ( м - 2) / ( м - 1) × ( м - 1) / м = 1 / м

Etc. Все они 1 / м .

Answer 3

Этот метод хорош, потому что:

i) Вы можете генерировать случайные строки без больших затрат

ii) Вам нужно только прочитать файл в общей сложности 1 раз + 1 строка за раз по случайной строке, которую вы хотите. Избыток прочитанных данных равен только размеру файла.

iii) Дает каждой строке равные шансы, независимо от ее положения в файле.

iv) Это дает каждой строке реальный шанс, независимо от ее длины в файле.

Предложение:

Я бы предложил 2-х проходный алгоритм. Ну, на самом деле это 1 проход + N строк. Где N - количество случайных строк, которые вы хотите.

Первый проход, который вы будете использовать для вычисления количества строк и начальных позиций каждой строки.

Затем вы берете случайное число от 0 до количества строк минус 1. Используйте это случайное число, которое является вашим индексом строки, чтобы получить начальную позицию для этого индекса строки. Искать в этой позиции.

Затем вам нужно только 1 чтение, и вы знаете точный размер. (до начального индекса следующей строки)

Как хранить количество строк и индекс каждой строки:

Для хранения количества строк вы, очевидно, можете просто использовать int.

Если вы можете использовать вектор, вы можете добавить каждый индекс строки в вектор. Если нет, вы можете просто создать массив целых чисел с максимальным количеством строк, которые, как вы думаете, будут. Затем индекс в этот массив.

Другие ответы:

В другом ответе упоминается, что вы можете выбрать случайное число от 1 до размера файла, а затем использовать ближайшую новую строку. Но это не сработает. Например, у вас может быть 1 очень длинная строка, а другие не очень длинные. В этом случае распределение будет неравномерным.

Answer 4

1. Получить длину файла.
2. Выберите случайную позицию в файле.
3. Искать в этой позиции.
4. Перейдите вперед, пока не найдете символ новой строки.
5. Если вы не нашли символа новой строки, вернитесь к началу.
6. Используйте get () для чтения строки.

Answer 5

Просто краткая заметка о Mark Ransom * способ избежать целочисленного переполнения : DS не имеет FPU, поэтому деление с плавающей запятой будет эмулироваться в программном обеспечении и будет очень медленным. Если вы хотите избежать скорости, вам следует избегать приведения / раскрутки типов в любой ценой.

Вот другой способ избежать целочисленного переполнения, позволяющего избежать математических операций с плавающей запятой:

if(rand() <= RAND_MAX / count)

Вероятности могут быть слегка искажены из-за целочисленного деления, но это, безусловно, должно работать намного быстрее в DS.

Answer 6

Все, что вам нужно сделать, - это генерировать одно немасштабированное случайное число на строку, сохраняя максимальное значение для всех генерируемых вами случайных чисел. Всякий раз, когда вы обновляете максимальное значение, вы перезаписываете выбранную строку текущей строкой.

В конце вы получите строку, связанную с выпавшим наибольшим числом rand (), что должно быть одинаково вероятно среди всех ваших строк.

Answer 7

Используйте комбинацию случайного смещения Адама в файловом подходе и вероятностном подходе Марка. Метод Адама может случайным образом доставить вас в раздел файла. Затем вы используете подход Марка, чтобы избежать предпочтения больших строк. Алгоритм Марка предпочтет первые несколько строк с того места, где он начинается,

Answer 8

У меня есть альтернативное решение. Поскольку платформа - это DS, вы, вероятно, не захотите пытаться удерживать файл в памяти. Это читает файл дважды. Один раз пересчитать строки и второй раз найти нужную. Это будет работать медленнее, чем другие решения, предложенные до сих пор, но практически не использует память. Я даже написал это на C для вас (я пропустил обработку ошибок):

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);
}

ОБНОВЛЕНИЕ: Ой, я должен был прочитать ответ Брайана Р. Бонди, прежде чем я написал это, но я был немного одержим написанием кода и не заметил. Это почти то же самое, за исключением того, что не сохраняет позиции строк в массиве. Вы можете сделать это в любом случае, в зависимости от размера файла и от того, важнее ли скорость, чем экономия памяти.