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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У меня есть альтернативное решение. Так как платформа является DS, Вы, вероятно, не хотели бы пытаться держать файл в памяти. Это читает файл дважды. Однажды для подсчета строк и в 2-й раз для нахождения строки это хочет. Это работало бы медленнее, чем другие решения, предложенные до сих пор, но это использует едва любую память. Я даже записал это в 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);
}

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

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

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

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

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

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

if(rand() <= RAND_MAX / count)

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

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

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).

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

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

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

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

Вероятность того, что третья линия останется в keepline, равна:

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

И т.д. Все они равны 1/m.