LINUX.ORG.RU

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

 


2

1

Есть текстовый файл, который содержит 100 миллионов строк, например.

Как быстрее всего выбрать из него 1000 случайных строк (желательно башем или стандартными утилитами, но не perl/python)?

Заранее спасибо.

★★☆☆

 shuf -n 1000 input 

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

derlafff ★★★★★ ()
Последнее исправление: derlafff (всего исправлений: 2)
Ответ на: комментарий от derlafff

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

xtraeft ★★☆☆ ()

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

на С написать

anonymous ()
Ответ на: комментарий от xtraeft

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

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

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

shuf быстрый.

derlafff ★★★★★ ()
Ответ на: комментарий от derlafff

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

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

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

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

shuf быстрый.

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

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

xtraeft ★★☆☆ ()
Ответ на: комментарий от anonymous

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

xtraeft ★★☆☆ ()
#!/bin/sh
RCOUNT=`wc -l "$1" | cut -f1 -d" "`
let "number = $RANDOM % $RCOUNT"
sed -n ${number}p "$1"
$ ./rnd_sr.sh /usr/src/linux/.config 
#
$ ./rnd_sr.sh /usr/src/linux/.config 
CONFIG_CONTEXT_SWITCH_TRACER=y
$ ./rnd_sr.sh /usr/src/linux/.config 
# CONFIG_HSI is not set
$ ./rnd_sr.sh /usr/src/linux/.config 
CONFIG_AUTOFS4_FS=y
$ ./rnd_sr.sh /usr/src/linux/.config 
CONFIG_NET_SCHED=y
$ ./rnd_sr.sh /usr/src/linux/.config 
CONFIG_PCI_MMCONFIG=y
kostik87 ★★★★★ ()
Ответ на: комментарий от xtraeft

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

derlafff ★★★★★ ()
Ответ на: комментарий от kostik87

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

xtraeft ★★☆☆ ()
Ответ на: комментарий от derlafff

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

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

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

gh0stwizard ★★★★★ ()
Ответ на: комментарий от gh0stwizard

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

xtraeft ★★☆☆ ()
Ответ на: комментарий от derlafff

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

Цена?

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

xtraeft ★★☆☆ ()
Последнее исправление: xtraeft (всего исправлений: 1)
Ответ на: комментарий от kostik87

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

YAR ★★★★★ ()

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от xtraeft

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

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

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

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

xtraeft ★★☆☆ ()
Последнее исправление: xtraeft (всего исправлений: 1)
Ответ на: комментарий от xtraeft

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

YAR ★★★★★ ()
Последнее исправление: YAR (всего исправлений: 1)
Ответ на: комментарий от xtraeft

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

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

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

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

xtraeft ★★☆☆ ()
Ответ на: комментарий от xtraeft

минут за 20

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от xtraeft

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

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от YAR
dd if=testfile5 bs=1k skip=$(($RANDOM$RANDOM$RANDOM % $(du testfile5 | cut -f1))) | head | tail -n 1

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

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

YAR ★★★★★ ()
Ответ на: комментарий от Eddy_Em

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

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

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

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

xtraeft ★★☆☆ ()
Ответ на: комментарий от xtraeft

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

YAR ★★★★★ ()
Ответ на: комментарий от YAR

real 0m8.580s

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

xtraeft ★★☆☆ ()
Последнее исправление: xtraeft (всего исправлений: 1)
Ответ на: комментарий от xtraeft

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

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от YAR

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

xtraeft ★★☆☆ ()
Ответ на: комментарий от Eddy_Em

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

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

derlafff ★★★★★ ()
Ответ на: комментарий от Eddy_Em
wc -l test
1190656 test

time ./randline test 10000 
(многабукафф)
real	0m0.435s
user	0m0.006s
sys	0m0.036s
Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em
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

xtraeft ★★☆☆ ()
Последнее исправление: xtraeft (всего исправлений: 3)
Ответ на: комментарий от derlafff

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

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

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

xtraeft ★★☆☆ ()
Последнее исправление: xtraeft (всего исправлений: 2)
Ответ на: комментарий от xtraeft

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

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

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

Eddy_Em ☆☆☆☆☆ ()
Последнее исправление: Eddy_Em (всего исправлений: 1)
Ответ на: комментарий от Eddy_Em

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

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

xtraeft ★★☆☆ ()
Последнее исправление: xtraeft (всего исправлений: 1)
Ответ на: комментарий от xtraeft

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

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

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

xtraeft ★★☆☆ ()
Ответ на: комментарий от xtraeft

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

YAR ★★★★★ ()
Ответ на: комментарий от Eddy_Em

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

xtraeft ★★☆☆ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.