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

Ответ 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)) 

Ответ 2

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

• Если строка длиннее length - 1 символов (включая новую строку), то цикл while будет увеличивать count не менее двух раз для одной и той же строки: один раз для первых символов length - 1, другой для следующие length - 1 символы и т.д.
• Вычисление 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

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

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

Etc. Они все 1/м.

Ответ 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 4

• Получить длину файла.
• Выберите произвольную позицию в файле.
• Ищите эту позицию.
• Итерации вперед, пока не найдете символ новой строки.
• Если вы не найдете символ новой строки, вернитесь к началу.
• Использование gets() для чтения строки.

Ответ 5

У меня есть альтернативное решение. Поскольку платформа является 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);
}

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

Ответ 6

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

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

Ответ 7

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

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

if(rand() <= RAND_MAX / count)

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

Ответ 8

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