?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
cut fields faster in text file
nyaload
_winnie
Написал аналог утилиты cut, вырезающей столбцы из tab-delimited файла.
Работает в 2-3 раза быстрее стандартного cut и в 5-10 раз быстрей awk -F '\t' (зависит от системы), в 50 раз быстрей питона.
Как и оригинальный cut, не умеет переставлять столбцы местами, только выделяет часть из них.

http://dobrokot.ru/dump/cut_field_fast.cpp

Довольно противно на C/C++ писать то что на питоне получается в одну строку, типа sorted(set(int(x) for x in command_line.split(','))), и самое обидное что такого тупого кода парсинга командной строки - больше, и он сложней чем основной алгоритм...

Tags: , ,

  • 1
Когда я последний раз писал файложевалку на C для скорости, соответствующий однострочник на привычном перле был таким, что показалось проще всего разобраться эмбеддингом перла. Хотя вот сейчас смотрю на тот код — можно было и popen("perl -e ...") обойтись.

(Deleted comment)
Ну, основная жевалка байтов - понятно почему. cut или awk уже не устраивали.

Разбор параметров на C++ - для честного сравнения с cut -f. И для того что бы можно было выложить, если кому понадобится, без зависимостей от bash/python/perl/... и с возможностью не редактировать исходник для того что бы использовать другие чиселки.

На Haskell напиши.
Ну или чётче задачу, я напишу.

> Ну или чётче задачу,
cut --help, про режим -f
Работать должно не медленней ;)

Можно быстрее.

У тебя цикл по байтам - это гарантированно медленно. Можно использовать функцию strpbrk (для поиска \t, \n), затем выводить целые куски. Например, в eglibc она реализована довольно хорошо (есть код для процессоров с SSE 4.2, но и без этого тоже неплохо).

PS. Для тех, кто спрашивает, зачем нужно - например, для чтения tab separated дампа БД (там правда задача сложнее, так как надо поддерживать escape-последовательности, парсить числа и т. п.).

Re: Можно быстрее.

Если поля короткие 5-15 байт, то не факт что мощный сетап SSE (выравнивание на 8 байт) поможет

BTW, спелл-чекер в редакторе спасет отца русской демократии.

А вообще, да, самый тяжелый код -- это всякая бизнес-логика, обработка прав доступа, обработка ошибок и УИ.

Вот поэтому и говорят, что Python это быстрый скриптовый язык. Потому как он всего лишь в 20-50 раз медленнее, чем С++.

Работает в 2-3 раза быстрее стандартного cut
У меня на лаптопе всё совсем не так:
[cut]% time cut -f 1,5,10 < /tmp/out.txt > /tmp/cut.txt
cut -f 1,5,10 < /tmp/out.txt > /tmp/cut.txt  2.08s user 0.23s system 99% cpu 2.321 total
[cut]% time ./cut-fast-g++ 1,5,10 < /tmp/out.txt > /tmp/cut.txt
./cut-fast-g++ 1,5,10 < /tmp/out.txt > /tmp/cut.txt  3.20s user 0.18s system 99% cpu 3.389 total
[cut]% time ./cut-fast-icc 1,5,10 < /tmp/out.txt > /tmp/cut.txt
./cut-fast-icc 1,5,10 < /tmp/out.txt > /tmp/cut.txt  1.78s user 0.26s system 99% cpu 2.051 total
Результаты довольно косистентные, не меняются сколь-либо ощутимо от порядка запуска. Компилировал при помощи g++ -O3 и icc -O3 на x64. Справедливости ради, стоит отметить, что стандартный cut у меня в системе компилировался явно не при помощи интеловского компилятора, а при помощи всё того же g++ -O3.

Щас ещё хаскелльную попробую накатаю, по идее может порвать и cut, wc я уже рвал (конкретных результатов поблизости нет, но при желании могу прогнать снова).

Хммм, интересно, спасибо.
А какая OS?

$ time cut -f 1,5,100 <sim6-1000 >/dev/null

real 0m2.957s
user 0m2.640s
sys 0m0.296s

$ time ./cut_field_fast 1,5,100 <sim6-1000 >/dev/null

real 0m1.635s
user 0m1.388s
sys 0m0.244s

$ time awk -F '\t' '{print $1,$5,$100}' <sim6-1000 >/dev/null

real 0m1.255s
user 0m0.900s
sys 0m0.356s

1) sim6-1000 - он как генерится?
2) какая OS?

Edited at 2012-01-31 11:17 am (UTC)

По поводу того, что может в данном случае потенциально (в будущем) занять нишу Си++: http://make-linux.blogspot.com/2012/02/c-ooc.html

к сожалению программа на c++ некорректна, в частности она неверно обрабатывает случаи:

./a.out 10,2,5 ; ./a.out 10,10,10

т.е. такие в которых колонки или не по порядку, или повторяются.

//qnikst

Она в той же степени некорректна, что и стандартный cut

  • 1