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

 shuf -n 1000 input 

Гуглом пользоваться не учили?

Спасибо, но это очень медленные способы. Первому даже LC_ALL=C не поможет.

shuf: read error: Cannot allocate memory
:)

Как быстрее всего

на С написать

Небось в соседних тредах кричишь, что 64 бита — ненужно?

Что за система?

Спасибо, но это очень медленные способы.

shuf быстрый.

Небось в соседних тредах кричишь, что 64 бита — ненужно?

Нет, у меня везде 64битные системы и железо.

Что за система?

Вдс с убунтой и гигом памяти. Файл, из которого делаю выборку, имеет размер ~2 Гб.

shuf быстрый.

Ну и даже если память есть свободная, оно все равно тормозит. Или я хочу невозможного? Проверил на рабочем компьютере:

time shuf -n 1000 ADULT.OCTOBER
real	1m24.717s

Вот я и надеялся, вдруг уже кто-то написал подобное.

На SO пишут, что shuf линейный, то бишь О(n). Если еще (чуть) большей скорости, напиши себе затычку на сишечке.

Я ждал этого комментария. Знаешь, как оно тормозит?

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

Ты хотел на чистом баше.

1. Рандом на Х чисел
2. open -> seek (X1) -> read -> [seek(X2) -> read, ...] -> close
3. ???
4. PROFIT!!!

P.S. Как найти начало и конец строки после read, думаю, задача тривиальная для сишнека.

Ага, как-то так, но я не сишник.
Не хочешь такую утилиту за деньги написать?

Давай напишу, лол

Давай.
1. Имя файла и количество строк, которые нужно выбрать, передавать через argv ($1 $2).
2. Должно работать при размере файла большем, чем есть свободной памяти.
3. Кодировка файла utf-8.
4. Открытые сорцы, лицензия любая.

Цена?

Можешь сразу на ник@гмейл писать

Лучше уж тогда head / tail заюзать для выборки

Медленно.

head/tail со случайными номерами строк.

Учитывая то, что конец строки — '\n', даже мой вариант будет работать. Нуно?

Еще один.

Учитывая то, что конец строки — '\n', даже мой вариант будет работать. Нуно?

Через head/tail? Нет.
Можешь показать пример, а я сделаю бенчмарк и сам все поймешь.

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

Таки да, даже медленнее оказалось. sed молотит данные у меня на скорости 33 МБ/сек, head/tail - 25-27. Зато mawk - на 70. Т.е., в целом, если запихнуть в него массив рандомных чисел и печатать строки, соответствующие номеру, то за один проход можно получить нужный список.

Нет, на сишечке.

1. Делаем случайный lseek
2. Ищем первое '\n'
3. Считываем строчку и показываем на экране.

Повторяем нужное количество раз. Почти то же самое у меня в самопальной БД: в одном файле хранятся позиции записей с шагом в неделю, в другом — сами записи. Процедура поиска проста: сначала в первом файле ищем примерную позицию, потом делаем seek и ищем уже точную позицию запрашиваемой даты. Шустро-просто. Работает с файлами любых размеров. Ради прикола тестил на синтетическом пятигиговом.

derlafff уже делает.
Правда обещал минут за 20, но видимо не успел.
Если не сделает - попрошу тебя, а то мне вечером уже надо юзать.

минут за 20

Ну, смотря что за ТЗ. А то и дольше уйдет, если нужно дофига параметров командной строки брать. А если тупо 2 (и материться, если их не 2), то да — 20-30 минут, наверное.

Ну, смотря что за ТЗ

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

А если тупо 2

Да, только 2. Файл-источник и количество строк.

Свисти, если что. Я домой пошел. Если мелкая не сильно настырно будет заставлять с нею играть, то накалякаю что-нибудь.

Поддержка 32-битного хлама нужна?

dd if=testfile5 bs=1k skip=$(($RANDOM$RANDOM$RANDOM % $(du testfile5 | cut -f1))) | head | tail -n 1

Такой себе псевдорандом :)

// Серьезно не воспринимать )

Поддержка 32-битного хлама нужна?

С ней будет сильно медленнее? Вроде не нужна, но теоретически может попасться такая виртуалка. Если медленнее или дольше писать, то поддержка 32 бит не нужна.

derlafff сказал сегодня закончит.

Впринципе, можешь свой вариант написать. Заплачу обоим, заодно посмотрим чей вариант работает быстрее :)

real 0m30.874s

хаха, быстрее чем shuf

В целом, если более грамотно сделать обработку данных от dd (ибо сейчас часть строк может никогда не попасть в вывод) и убрать ту цепочку $RANDOM'ов, то вполне боевой вариант. Но /me обедает, потому лень.

real 0m8.580s

Ого, это на виртуалке с 1Гб памяти и ssd. И память не жрет.
Отличное решение, без шуток.
С меня пиво, если никто не побьет твой результат (кроме сишников).

http://en.wikipedia.org/wiki/Reservoir_sampling, тред дальше заголовка не читал.

С ней будет сильно медленнее?

Не сильно. И только на 32-битных.

Тогда пиши на ник @ гмейл, если не передумал.

Оказывается твой вариант быстро работает только на маленьком количесте выбираемых строк (до 10 тысяч).

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

Я так сделал на сишечке, медленно. Нормальная генерация случайных и последовательный проход всего файла быстрее

Вариант 1 (ленивый). Будет медленным, наверное.

time ./eddy keys.txt 10000 > res.txt

real    0m0.869s
user    0m0.076s
sys     0m0.279s

Ого, зачет. Очень быстро. Только там \n куда то пропадает, если в файл перенаправлять выхлоп:

wc -l res.txt ; sort -u res.txt |wc -l
10000 res.txt
4

Если ТСу надо, попробую еще с lseek, пусть сначала простой вариант с mmap проверит. По-моему, этого достаточно. Тем паче, что всю грязную работу ведро на себя берет.

По-моему, этого достаточно.

Достаточно, более чем (100 000 строк выбирает за 7 секунд, миллион за 2 минуты). Только бы ту проблему пофиксить, о которой я выше писал.

Это из-за буферизации. Пиши в строке 113:

write(1, "\n", 1);

Я думаю, с явным указанием lseek будет медленнее, т.к. придется вручную читать какое-то количество данных в буфер и вырывать строчку. Если буфер взять слишком маленьким, придется дочитывать, если же буфер взять слишком большим, то процесс замедлится.

Это из-за буферизации. Пиши в строке 113:

Спасибо, помогло. Работает сильно быстрее, чем у derlafff.
Оставь свои контакты-реквизиты и сумму, заплачу.

У меня только paypal (от остальных "электронных денег" толку 0). Годится?

Да. Сумму и адрес можешь скинуть мне на почту (ник @ гмейл).

Остальное, в целом, зависит от скорости работы цикла-обвязки вокруг той строчки. А несколько рандомных заданий обработать - да, не получится.

Получил. Спасибо!

Это тебе спасибо, сейчас весь процесс занимает 2 минуты вместо 20-60.