Ответ 1
Обычно я использую paste -sd+|bc:
$ time seq 1 20000000 | paste -sd+|bc
200000010000000
real 0m10.092s
user 0m10.854s
sys 0m0.481s
(Для строгого соответствия Posix paste должен быть предоставлен явный аргумент: paste -sd+ -|bc. По-видимому, это необходимо с реализацией BSD paste, установленной по умолчанию в OS X.)
Однако это приведет к сбою для больших входов, потому что bc буферизует все выражение в памяти перед его оценкой. В моей системе bc закончилась память, пытаясь добавить 100 миллионов номеров, хотя она смогла сделать 70 миллионов. Но другие системы могут иметь меньшие емкости.
Так как bc имеет переменные, вы можете избежать длинных строк, повторяя добавление к переменной вместо создания одного длинного выражения. Это (насколько я знаю) 100% совместимый с Posix, но есть 3-кратное ограничение времени:
$ time seq 1 20000000|sed -e's/^/s+=/;$a\' -es|bc
200000010000000
real 0m29.224s
user 0m44.119s
sys 0m0.820s
Другой способ обработки случая, когда размер ввода превышает bc буферную емкость, заключается в использовании стандартного инструмента xargs для добавления чисел в группы:
$ time seq 1 100000000 |
> IFS=+ xargs sh -c 'echo "$*"' _ | bc | paste -sd+ | bc
5000000050000000
real 1m0.289s
user 1m31.297s
sys 0m19.233s
Количество строк ввода, используемых каждой оценкой xargs, будет варьироваться от системы к системе, но обычно оно будет в сотнях, и это может быть намного больше. Очевидно, что вызовы xargs | bc могут быть скованы произвольно для увеличения емкости.
Возможно, необходимо ограничить размер расширения xargs, используя переключатель -s, в системах, где ARG_MAX превышает емкость команды bc. Помимо эксперимента, чтобы установить ограничение на bc, нет никакого переносимого способа установить, какой может быть этот предел, но он должен быть не менее LINE_MAX, который, как гарантируется, должен быть не менее 2048. Даже с 100- которые позволят уменьшить коэффициент в 20 раз, поэтому цепочка из 10 xargs|bc будет обрабатывать более 10 13 добавок, если вы готовы подождать пару месяцев для этого, чтобы завершить.
В качестве альтернативы построению большого конвейера с фиксированной длиной вы можете использовать функцию для рекурсивного вывода вывода из xargs|bc до тех пор, пока не будет создано только одно значение:
radd () {
if read a && read b; then
{ printf '%s\n%s\n' "$a" "$b"; cat; } |
IFS=+ xargs -s $MAXLINE sh -c 'echo "$*"' _ |
bc | radd
else
echo "$a"
fi
}
Если вы используете очень консервативное значение для MAXLINE, это довольно медленно, но с правдоподобными большими значениями оно не намного медленнее, чем простое решение paste|bc:
$ time seq 1 20000000 | MAXLINE=2048 radd
200000010000000
real 1m38.850s
user 0m46.465s
sys 1m34.503s
$ time seq 1 20000000 | MAXLINE=60000 radd
200000010000000
real 0m12.097s
user 0m17.452s
sys 0m5.090s
$ time seq 1 100000000 | MAXLINE=60000 radd
5000000050000000
real 1m3.972s
user 1m31.394s
sys 0m27.946s
Как и решения bc, я приурочил некоторые другие возможности. Как показано выше, при вводе 20 миллионов номеров paste|bc заняло 10 секунд. Это почти идентично времени, используемому при добавлении 20 миллионов номеров с помощью
gawk -M '{s+=$0} END{print s}'
Языки программирования, такие как python и perl, оказались быстрее:
# 9.2 seconds to sum 20,000,000 integers
python -c $'import sys\nprint(sum(int(x) for x in sys.stdin))'
# 5.1 seconds
perl -Mbignum -lne '$s+=$_; END{print $s}'
Я не смог протестировать dc -f - -e '[+z1<r]srz1<rp' на больших входах, поскольку его производительность представляется квадратичной (или хуже); он суммировал 25 тысяч номеров за 3 секунды, но потребовалось 19 секунд, чтобы собрать 50 тысяч и 90 секунд, чтобы сделать 100 тысяч.
Несмотря на то, что bc не самый быстрый, а ограничения памяти требуют неудобных обходных решений, у него есть преимущество в разработке кода в системах, совместимых с Posix, без необходимости установки расширенных версий любой стандартной утилиты (awk) или языки программирования, не требуемые Posix (perl и python).