Как я могу ускорить это?

Question

Следующий код составляет список имен и «чисел» и дает каждому человеку случайный возраст от 15 до 90 лет.

#!/bin/sh

file=$1
n=$2

# if number is zero exit
if [ "$n" -eq "0" ]
then
    exit 0
fi

echo "Generating list of $n people."

for i in `seq 1 $n`;
do
    let "NUM=($RANDOM%75)+15"
    echo "name$i $NUM (###)###-####" >> $file
done

echo "List generated."

С его помощью я пытаюсь составить список из 1М имен. Это медленно, я ожидал этого; Это было так медленно, что я потерял терпение и попробовал 10K имен. Это тоже было медленно, но это было сделано за несколько секунд.

Причина, по которой я генерирую имена, заключается в их сортировке. Что меня удивило, так это то, что когда я сортировал список из 10 тысяч имен, это было мгновенно.

Как это может быть?

Есть ли что-то, что делает это безбожно медленным? И сортировка, и генерация обращаются к файлам, так как сортировка может быть быстрее? Моя математика случайных чисел в генераторе списков замедляет его?

Вот мой скрипт сортировки.

#!/bin/sh
#first argument is list to be sorted, second is output file
tr -s '' < $1 | sort -n -k2 > $2

Answer 1

for i in `seq 1 $n`

Хлоп! Это генерирует 1 000 000 аргументов для цикла for. Этот seq вызов займет длительное, длинное, длинное время. Попробуйте

for ((i = 1; i <= n; i++))

Кстати, обратите внимание на отсутствие знаков доллара. В частности, синтаксис var++ требует от вас опускать знак доллара в имени переменной. Вы также можете использовать или опустить их в другом месте: это может быть i <= n или $i <= $n, либо один. Как я понимаю, вы должны полностью опускать знаки доллара в выражениях let, declare и for ((x; y; z)). Обратитесь к разделу АРИФМЕТИЧЕСКАЯ ОЦЕНКА справочной страницы sh за подробным объяснением.

Answer 2

Не новый ответ, просто новый код.

Это то, что IMHO является хорошим промежуточным звеном между красивым и эффективным кодом (настолько эффективный, насколько это возможно в Bash, он медленный, это оболочка ...)

for ((i=1;i<=n;i++));
do
  echo "name$i $((NUM=(RANDOM%75)+15)) (###)###-####"
done > "$file"

Альтернатива, без использования классической счетной петли

i=1
while ((i<=n)); do
  echo "name$((i++)) $((NUM=(RANDOM%75)+15)) (###)###-####"
done > "$file"

Обе скорости примерно одинаковы.

Исправления такие же, как и все остальные:

• не часто закрывать и открывать заново файл
• использовать арифметику оболочки
• ах да, и используйте ЦИТАТЫ, но это для здравомыслия, а не для скорости

Answer 3

Использование оболочки для генерации случайных чисел, подобных этой, не совсем то, для чего она предназначена. Скорее всего, вам лучше кодировать что-то, чтобы генерировать случайные числа из равномерного распределения на другом языке, например, Fortran, Perl или C.

В вашем коде одна вещь, которая будет очень медленной, это генерация последовательности чисел из 1..1e7 и присвоение их всех переменной. Это, вероятно, очень расточительно, но вы должны сообщить, если вы хотите быть уверены. Как указывает хаос , добавление в файл также может быть очень дорогостоящим!

В Python вы можете сделать что-то вроде этого:

#!/usr/bin/python
import random
count = 1

print ' '.join( ['name', 'age'] )
while count <= 1000000:
    age = random.randrange(15,90)
    count = count + 1
    name = 'name' + str(count)
    print ' '.join( [ name, str(age) ] )

Запуск этого на моем ноутбуке занимает ~ 10 секунд. Присвоение seq от 1 до 1000000 занимает ~ 10 секунд, когда вы добавляете генерацию случайных чисел, ваш скрипт занимает более трех минут на той же машине. Я разочаровался так же, как и вы, и поиграл со сценарием, чтобы попытаться сделать его быстрее. Вот моя сокращенная версия вашего кода, с которым я играю:

for x in `seq 1 10000`; do
   let "NUM=($RANDOM%75)+15"
   echo $NUM >> test.txt
done

Запуск занимает около 5,3 с:

$ time ./test.sh
real    0m5.318s
user    0m1.305s
sys     0m0.675s

Удаление файла, добавляющего и просто перенаправляющего STDOUT в один файл, дает следующий скрипт:

for x in `seq 1 10000`; do
   let "NUM=($RANDOM%75)+15"
   echo $NUM
done

Выполнение этого занимает около полсекунды:

$ time ./test.sh > test.txt
real    0m0.516s
user    0m0.449s
sys     0m0.067s

Медлительность вашей программы, по крайней мере частично, связана с добавлением в этот файл. Любопытно, что когда я пытался поменять местами вызов seq с циклом for, я не заметил никакого ускорения.

Answer 4

Полагаю, источником проблемы может быть файл '>> $ file'. В моей системе ваш сценарий генерирует 10000 за 10 секунд. Если я удаляю аргумент $ file и вместо этого просто использую stdout и записываю все это в файл, который занимает менее секунды.

$ time ./gen1.sh n1.txt 10000 Формирование списка 10000 человек. Список создан.

реальный 0m7.552s пользователь 0m1.355s sys 0m1.886s

$ time ./gen2.sh 10000> n2.txt

реальный 0m0.806s пользователь 0m0.576s sys 0m0,140s

Answer 5

Не знаю, вся ли это история, но повторное открытие файла для добавления его к каждому имени не может помочь. Выполнение всего этого в любом контексте, где вы можете сохранить дескриптор открытого файла для записи, должно очень помочь.

Answer 6

(У меня такое чувство, что вам может не понравиться этот ответ, но вы технически не указали, что ответ должен был остаться в bash!: P)

Обычно быстро разрабатывать что-либо на языке прототипирования, а затем, при необходимости, переключаться на другой язык (часто C). Вот очень похожая программа на Python для сравнения:

#!/usr/bin/python
import sys
import random

def main(args=None):
    args = args or []
    if len(args) == 1:
        # default first parameter
        args = ["-"] + args
    if len(args) != 2:
        sys.stderr.write("error: invalid parameters\n")
        return 1
    n = int(args[1])
    output = sys.stdout if args[0] == "-" else open(args[0], "a")

    for i in xrange(1, n + 1):
        num = random.randint(0, 74)
        output.write("name%s %s (###)###-####\n" % (i, num))

    sys.stderr.write("List generated.\n") # see note below

if __name__ == "__main__":
    sys.exit(main(sys.argv[1:]))

Примечание: Только использование stdout для «реального вывода» вместо уведомлений о состоянии позволяет этой программе запускаться параллельно с другими, передавая данные напрямую из stdout одного в stdin другого. (Это возможно со специальными файлами в * nix, но проще, если вы можете использовать стандартный вывод.) Пример:

$./rand_names.py 1000000 | sort -n -k2 > output_file

И это должно быть достаточно быстро:

$time ./rand_names.py 1000000 > /dev/null
List generated.

real    0m16.393s
user    0m15.108s
sys     0m0.171s

Answer 7

Попробуйте это для своего основного цикла:

seq 1 $n | while read i
do
    let "NUM=($RANDOM%75)+15"
    echo "name$i $NUM (###)###-####"
done > $file

Это заставит seq и цикл работать параллельно вместо ожидания завершения seq перед началом цикла. Это будет быстрее для нескольких ядер / процессоров, но немного медленнее для одного ядра.

И я согласен с остальными: должен ли это быть bash?

Редактировать: добавить предложение хаоса, чтобы сохранить файл открытым, а не открывать для добавления для каждого имени.