Выбрать n случайных строк из большого файла

...
#include <time.h>
...
int main(int argc, char **argv){
        srand48( time(NULL) ) ;
...
}

А вот не за что получать-то. Забыл инициализировать генератор случайных чисел.

The lcong48(), seed48(), and srand48() functions are initialization functions. You should invoke one of these before calling either the drand48(), lrand48(), or mrand48() function.

http://publib.boulder.ibm.com/infocenter/zvm/v6r1/index.jsp?topic=/com.ibm.zv...

А вот не за что получать-то. Забыл инициализировать генератор случайных чисел.

Какая мне разница, если на выходе получаются разные строки?

НО ВЕДЬ НЕ ПО ПРАВИЛАМ!!!!111111уноуноуно

он не тебе писал

а потом ты плачешься что иксы текут. но зато их писали не закостенелые академики

По-моему, иксы как раз они и писали.

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

Какая мне разница, если на выходе получаются разные строки?

У меня не получаются разные строки:

$ ./main l 10 && date
2
318176
200249
468708
25623
439300
251842
374640
399528
483800
Вт. окт. 28 20:45:29 MSK 2014
$ ./main l 10 && date
2
318176
200249
468708
25623
439300
251842
374640
399528
483800
Вт. окт. 28 20:45:31 MSK 2014
$ ./main l 10 && date
2
318176
200249
468708
25623
439300
251842
374640
399528
483800
Вт. окт. 28 20:45:32 MSK 2014

иксы не на lisp или forth писаны, а на школосишке, смерд

Плевать на красоту кода

да. другое дело maintanability и security

Ага, спасибо. Я о другом подумал.

Я о другом подумал.

О чём же? Ведь вроде понятно написано.

О чём же?

Об уникальности строк в пределах одного выхлопа.

Исправляюсь

Но теперь время инициализации зависит от количества "энтропии". Может и несколько секунд "энтропию копить".

Еще маленькую засаду нашел. Исправляюсь.

остановите этот брутфорс мозга и наймите уже себе программиста

Дык академики, как правило, и используют сишку. На лиспах пишут мамкины борщевики же.

Компилируйте с -lm.

Там в шапке написано как компилять. -lm добавь. Ну или можно вообще, как выше предлагали, выкинуть dtime и сделать

	if(fail){
		r_ini = (long)(time(NULL));
	}

А в шапку еще добавить #include <time.h>, тогда не надо будет #include <math.h> и -lm.

А вообще, если это только в линуксе будет работать, вариант на случай невозможности открывания или чтения /dev/random можно выкинуть — маловероятно, чтобы в линуксах его не было.

Спасибо, просмотрел. Все окей.

Претензии — в студию!

И что-то программисты как-то не спешат свой вариант объявить.

Если еще какие баги будут — пиши.

Как быстрее всего выбрать из него 1000 случайных строк

я думаю быстрее всего будет:

1. создать массив из 1000 случайных чисел

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

3. из массива сделать sed скрипт вида

#!/bin/sed -nf
234p
345p
2322p
5453p
…
94834p

4. скормить скрипту большой файл.

что shuf линейный, то бишь О(n)

у тебя тут n порядка 100`000.А можно добится времени 0(ноль), т.к. sed будет обрабатывать файл быстрее, чем он читается и одновременно с этим. А у тебя 100000 строк загонится в память, потом произойдёт перестановка(за O(N)), а потом уже 1000 первых строк результата выведется. Это слишком сложный способ, если ты знаешь, сколько в файле строк и число выходных строк небольшое. Быстрее заранее сгенерировать номера нужных строк, а потом читать большой файл, и только выводить нужные строки.

open -> seek (X1)

как ты предлагаешь делать seek, если все строки разные? Ну скажи мне позицию начала строки №100?

sed молотит данные у меня на скорости 33 МБ/сек, head/tail - 25-27. Зато mawk - на 70.

sed молотит даже немножко быстрее mawk, потому что записи в sed всегда оканчиваются \n. Ты просто включи LC_ALL=C, и регулярки не юзай.

Делаем случайный lseek

так не честно. А если в начале файла все строки длинные, а в конце — короткие? Тогда оно будет выбирать начальные строки намного чаще, чем конечные.

Да и вообще вероятность выпадения строки у тебя зависит от длинны. Строка «ААААААААААААААААААААААААААААААААА» будет выпадать в десятки раз чаще, чем «А». Такого в условии не было.

там, кстати, можно обойтись простой dd, читать случайный блок размером в 4К (для ext4), и в нём искать строчки. Т.е. сишка тут не нужна.

А если в начале файла все строки длинные, а в конце — короткие?

Тогда у нас будет не равномерное распределение, а кривое. Но похрен. Все равно случайное.

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

Собственно, так у меня псевдо-БД и работают.

Ого, это на виртуалке с 1Гб памяти и ssd

кстати сразу предупреждать надо, на HDD это простое решение будет ЖУТКО тормозить.

если никто не побьет твой результат (кроме сишников).

а куда его побить-то? Тут уже в SSD упёрлось.

du testfile5 | cut -f1

Можно без пайпа, но нужен stat(1):

stat -c %s testfile5

Тогда у нас будет не равномерное распределение, а кривое. Но похрен. Все равно случайное.

да? Ты только в азартные игры не играй, а то тебе голову проломят. Кроме шуток.

Для того, чтобы честно выполнить эту задачу, придется сначала сделать индексный файл. А потом тупо из него брать случайные индексы и получать нужные строки. Скорость будет выше, чем в последней реализации.

я это и предлагал чуть выше.

Но нужна будет подготовительная работа.

безусловно.

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

и каким таким образом «целевой файл на 100500 строк» будет _быстро_ меняться? Только append, но для append нужно просканировать только новый хвост. А то я сомневаюсь, что можно быстро поменять _текстовый_ файл такой длинны.

и каким таким образом «целевой файл на 100500 строк» будет _быстро_ меняться?

Логи прокси, например. А чтобы жить было веселей, логи делаем поминутные и сливаем их воедино скриптиком. Логи старше суток удаляем.

Вот тебе и шустро меняющийся мегадохренищаместазанимающий файл.

P.S. Давно уже пора нормальную ФС замутить, в которой можно будет у файла откусывать кусок начала. А то до сих пор костыли городить приходится...

Кстати, почему никто не замечает эту ссылку? Вроде, алгоритм точно ложится на ОП пожелание.

Блин. Поражаюсь! Ведь все ФС по сути могли бы поддерживать эту элементарщину: выкинуть из файла ненужный кусок, не переписывая файл заново. И нихрена не поддерживают.

Почему???

Как вообще такое может быть? Ведь это — самое логичное, что приходит в голову, когда вспоминаешь про логи!

Зачем разбивать логи на толпу файлов, если можно вести один-единственный файл, у которого будет кроном начало обрезаться? Или просто файл будет всегда иметь фиксированный размер (добавили блок в конец — удалили блок из начала).

Чертовщина какая-то...

Логи

append

алгоритм тривиальный:

1. сканим весь файл, и запоминаем длину L0

2. получаем новую длину L1

3. сканим хвост длинной L1-L0

4. goto 2

Логи старше суток удаляем.

это тебе придётся ВЕСЬ файл переписать, если ты каждую минуту удаляешь строчки старше 24х часов. SSD такое издевательство пару недель выдержит и сдохнет. Не дольше.

Впрочем, HDD тоже побьёшь нафиг с таким режимом.

Блин. Поражаюсь! Ведь все ФС по сути могли бы поддерживать эту элементарщину: выкинуть из файла ненужный кусок, не переписывая файл заново. И нихрена не поддерживают.

поддерживают, если ты туда нули пишешь. Тогда блок на HDD не хранится. Да, я понимаю, не совсем то, что ты хочешь.

Но то, что ты хочешь, на практике не нужно.

За то частенько нужно вот что:

1. Создаёшь файл размером 100500

2. потихоньку его рандомно заполняешь. Например торрент выкачиваешь.

Такое ФС умеют, если конечно ты догадался сделать файл из /dev/zero.

Зачем разбивать логи на толпу файлов, если можно вести один-единственный файл, у которого будет кроном начало обрезаться? Или просто файл будет всегда иметь фиксированный размер (добавили блок в конец — удалили блок из начала).

потому что логи лучше вообще удалить, и хранить только сжатую копию старого лога. Логи очень хорошо жмутся. Потому твоё предложение не нужно. Зачем хранить лог в 100Мб, если можно хранить текущий хвост в 10Мб, и ещё старые 90Мб в виде 9и мегабайтного сжатого файла? Учти, что процессоры сейчас быстрые, да и сжатие логов можно сделать nice -19, что-бы не мешалось.

Я же сказал, задача для тех, кто дружит с си :) Допустим, что все строки гораздо меньше 4к. Следовательно, за один read можно получить 5-100 строк. Ну, дитя, сделай рандом ещё раз :)

p.s. Были бы индексы, то задача была иной.