считывание произвольного слова

Алгоритм прост: 1. Узнать кол-во строк в файле. 2. Найти случайное число N в диапазоне 1..<кол-во строк> (смотри man 3 random) 3. Вернуть N-ую строку из файла.

Удачи!

забыл добвать: Так-то!

Выбирай всегда слово номер 4. Может потом пойдешь мэйнтэйнить openssl в дебиане.

> Выбирай всегда слово номер 4. Может потом пойдешь мэйнтэйнить openssl в дебиане.

смеялся. хотя конечно шутка злая.

Если не обращать на шутников :)))

Алгоритм прост:

0) Читаем все что связано с потоковым чтением из файла через функции fopen(),fgets и прочими.

1) Рассчитываешь кол-во n-строк. Man fgets().

2) По кол-ву строк выделяешь динамически память на n-указателей по количеству найденных слов. Читаем в учебнике по С все, что касается двухмерных массивов и выделения памяти malloc(), calloc(). Объявляем двухмерный массив

char** words;

3) Далее вычитываешь тем же самым fgets() с одновременным выделением памяти под слово. words[n-1] = fgets();

4) Получаешь с помощью random() случайное слово: words[ random() % n ], где n-кол-во слов в файле.

5) Не забываешь освободить всю выделенную память.

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

Почему это будет работать? По индукции!

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

неожиданно. и правда, работает.

> Помогите пожалуйста с выбором алгоритма,подтолкните в нужное направление, совсем запуталась. Программа на С.

мапишь файл в память. выбираешь rand() % mapped_file_size. далее по указателю ищешь следующий перевод строки и выводишь строку от этого указателя до следующего перевода строки. Всё просто.

> На самом деле, достаточно иметь буфер на одну строку и счётчик прочитанных строк. На n-м шаге содержимое буфера заменяется на только что прочитанную строку с вероятностью 1/n.

Ага. Чудесный алгоритм! Вот кратчайший путь к этому знанию:

perldoc -q "random line"

+1 самое разумное, но можно еще упростить: имея размер файла выбрать значение от 0 до размера файла, потом прыгнуть туда в файле через fseek и прочитать со следующего перевода строки.

Но для честности советую почитать книжки про рандомизацию в C, т.к. прыжок на 123 и 124 байты с последующим чтением после перевода строки может дать одно слово - "жопа".

:-)

это если текст восьмибитный
а если же утф-8 то тогда жопа

> книжки про рандомизацию в C, т.к. прыжок на 123 и 124 байты с последующим чтением после перевода строки может дать одно слово - "жопа".

ну и при чем тут С?

элементарный теорвер же

> мапишь файл в память. выбираешь rand() % mapped_file_size. далее по указателю ищешь следующий перевод строки и выводишь строку от этого указателя до следующего перевода строки. Всё просто.

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

А если вот так считываю весь файл, подсчитываю количество переносов строки, потом случайно выбираю и после него считываю строку до следующего переноса?!

> подсчитываю количество переносов строки, потом случайно выбираю

случайно выбираю что? это надо все позиции переносов запомнить гдето же, а это уже не "подсчитываю"

и если собираешься считывать весь файл то выше уже предложили решение с 1/n.

> случайно выбираю что? это надо все позиции переносов запомнить гдето же, а это уже не "подсчитываю" и если собираешься считывать весь файл то выше уже предложили решение с 1/n.

Подсчитываю количество '\n' чтобы знать сколько строк, например оказалось 500. Сохраняю значение в какой-то переменной. Потом случайно выбираю значение от 1 до 500, например 100, перехожу на 100 значение '\n' выбираю следующую строку за ним. Вот и всё.

А решение 1/n что-то непонятно, можно подробней?!

>впрочем, этот алгоритм несложно скорректировать, так чтобы получилось равномерное распределение.

Мне что-то кажется, что скорректировать его можно только предварительным индексированием файла (какая-нибудь fortune, скорее всего, так и делает).

не обязательно

суть такова:
1) выбираем случайную позицию в файле, например X.
2) X оказывается внутри какого-то слова (или строки), длины N.
3) кидаем монетку и с вероятностью 1/N возвращаем найденное слово
если же не повезло, начинаем заново с пункта 1

Нетрудно доказать, что вероятность выбора любого слова будет одинакова

Причем если длина файла стремится к бесконечности, а слова в среднем короткие,
получаем очевидный профит (в сравнении с решением при котором требуется
прочитать весь файл).

элементано же

алсо: на шаге 2 потребуется прочитать какой-то кусок файла, но возможно не очень большой; на шаге 3 возможно надо брать 1/(N+1) или 1/(N+2), в зависимости от того как сколько байт в индикаторе конца строки

Ух ты... Зачёт. Сам(а) придумал(а)? :)

http://en.wikipedia.org/wiki/Rejection_sampling

> А решение 1/n что-то непонятно, можно подробней?!

Перед началом чтения файла создаёшь переменную "текущий результат".

Затем открываешь файл и начинаешь читать его строка за строкой. Первую считанную строку безусловно копируешь в эту переменную.

Если на этом файл закончится, то в "текущем результате" будет "случайно выбранная" единственная строка файла.

Если в файле есть вторая строка, то заменяешь "текущий результат" второй строкой с вероятностью 1/2.

Если на этом файл закончится, то в "текущем результате" окажется с вероятностью 1/2 первая строка и с вероятностью 1/2 - вторая строка.

Если файл не заканчивается, и далее считана третья строка, то кладёшь её в "текущий результат" с вероятностью 1/3. После этого в "текущем результате" оказывается третья строка с вероятностью 1/3, а первая и вторая - каждая с вероятностью (1-1/3)*1/2 = 1/3. То есть снова равновероятно.

И т.д.

Если хочешь код, надо назвать желаемый язык.

Некоторый недостаток этого метода - приходится генерировать довольно много случайных чисел. Главное преимущество - файл читается только ровно раз.

> http://en.wikipedia.org/wiki/Rejection_sampling

И ведь действительно, классика... Спасибо.

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

Программа получилась. Вот вывод time

real 0m0.012s
user 0m0.008s
sys 0m0.004s

Это при 9461 слове, это нормально?!

> Почему это будет работать? По индукции!

а не уменьшается ли вероятность выпадания строк к концу файла?

вот возьми и посчитай

> Это при 9461 слове, это нормально?!

Почему бы и нет? Вроде, задачи сделать это сверхбыстро не ставилось. Примерно 1 млн слов в секунду. Если считать, что слово занимает 7 байт, получается 7 Мб/сек. По-моему, неплохо. Если надо быстрее, надо посмотреть, на что уходит время.

> Почему бы и нет? Вроде, задачи сделать это сверхбыстро не ставилос

+1

если конечно это не программа для работы с банковскими картами
где требуется минимум операций.

>далее по указателю ищешь следующий перевод строки и выводишь строку от этого указателя до следующего перевода строки.

ага. а если прыгнет на последнюю строку?

эх, программисты...

> ага. а если прыгнет на последнюю строку?

файл сделай циклический же