LINUX.ORG.RU

Хочу говорить про Bash

 


3

4

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

Решил попробовать написать программку, которая удаляет дубликаты строк из .bash_history (там более 7000 строк у меня). Мне это показалось достойной задачкой для начинающего башиста, хотя и (может быть) довольно бесполезной. Кстати, есть такая программа shell-history-cleaner (кажется на расте написана, давно себе собрал, работает, но видимо заброшена автором), я пользуюсь, но попробовать свои силы надо было.

В результате мне удалось сделать задуманное, но хочется поговорить и о «неудачных» вариантах, которые может быть были бы более удачными, если бы я больше знал о bash и linux вообще, так что категорически приветствуется критика и подсказки более правильных решений или каких-нибудь хитростей командной строки.

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

Программа рабочая, делает дело, но долго. Мой файл перемалывает за минуту с небольшим, при этом нагружая одно виртуальное ядро процессора на 100%. Зная лоровские нарративы об ущербности bash как языка программирования, я подумал, что вот и столкнулся с подобной ущербностью, поэтому просто искал возможность хоть как-то оптимизировать процесс.

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

file=$1
mapfile -t list < <(grep -v '^$' $file)
while ((${#list[*]})); do
    line=${list[-1]}
    unset list[-1\]
    for i in ${!list[*]}; do
        [[ $line == "${list[i]}" ]] &&
            unset list[i\]
    done
    final+=("$line")
done
printf '%s\n' "${final[@]}" | tac > $file

Для таких же любителей как я поясню идею кода. На его краткость отлично повлиял тот факт, что в истории командной строки надо сохранять последние уникальные строки, то есть работать надо с конца файла, а у индексированных массивов как раз есть стабильная ссылка на последний индекс: array[-1]. То есть не надо ничего переворачивать.

Как я понимаю, самое тугое место в скрипте — сравнение строк, и что-то более быстрых вариантов походу нет. Далее надо думать о многопоточности, но я пока до этого не дозрел.

Поскольку на данном этапе я застрял и вроде бы ясно, что тема с массивами как-то всё усложняет, то решил написать скриптик в стиле unix-way, и искренне полагал, что это будет правильным решением задачки, ведь утилиты все написаны суровыми дядьками на Си, и там всё без дураков — быстро и надёжно. Пришла идея отбросить всю эту возню с поиском и удалением, а просто взять всё — и отфильтровать.

file=$1
list=$(tac $file | grep -v '^$')
while [[ $list ]]; do
    read -r line <<< $list
    list=$(grep -Fxv "$line" <<< $list)
    echo "$line"
done | tac > $file

Чтобы уважаемый лорчанин не хельпал ключи -F -x, напомню: F — читает regex буквально, а x — помещает выражение между ^$, иначе пришлось бы использовать ключ -P (perlre) и выражение выглядело бы как говно: "^\Q$line\E$", а работало бы ещё медленней, возможно, но это не точно. (кстати, я был весьма разочарован узнать, что с sed такое вообще не провернуть — никак не заставить подстановку читать буквально).

Итак, на короткой дистанции (разумеется, у меня был короткий вариант файла для тестов) этот скрипт почти в два раза обогнал предыдущий, но — что было для меня полнейшим разочарованием! — он совершенно заткнулся даже на средней дистанции (нагружая процессор на четверть, но размазано по потокам), то есть я его тупо прервал на какой-то там 10-ой минуте, так что о проверке на полном файле речи уже не шло. Как это понимать — не знаю, поясните. 1000 строк он смолол где-то за секунду с небольшим, а 3000 — уже застрял.

Ладно, пока не было новых идей, прочитал главу про ассоциативные массивы и сразу почуял, что это походу то, что мне надо, но я не ожидал, что настолько! Свойство хеша не дублировать индексы как будто специально создано для решения этой задачки. Быстро стало понятно, что надо просто переложить строки из обыкновенного массива в индексы хеша, а в значения хеша — номера индексов строк из обыкновенного массива.

file=$1
mapfile -t list < <(grep -v '^$' $file)
declare -A hash
for i in ${!list[*]}; do
    hash[${list[i]}]=$i
done
for i in "${!hash[@]}"; do
    final[${hash[$i]}]="$i"
done
printf '%s\n' "${final[@]}" > $file

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

Получается на bash таки можно что-то программировать и оно может работать быстро.


UPD

Наконец подсказали, что во втором скрипте у меня ошибка: read -r очищает строку от пробельных символов по краям, поэтому grep её не находит и получается бесконечный цикл. Спасибо @mky: Хочу говорить про Bash (комментарий)
Теперь этот скрипт переваривает тот же файл за 15-16 секунд!

file=$1
list=$(tac $file | grep -v '^$')
while [[ $list ]]; do
    IFS=$'\n' read -r line <<< $list
    list=$(grep -Fxve "$line" <<< $list)
    echo "$line"
done | tac > $file

UPD2

Спасибо анону, подкинул идею отфильтровать хешем в один проход: Хочу говорить про Bash (комментарий)

file=$1
mapfile -t list < <(tac $file | grep -v '^$')
declare -A hash
for i in "${list[@]}"; do
    [[ ${hash[$i]} ]] && continue
    hash[$i]=added
    final+=("$i")
done
printf '%s\n' "${final[@]}" | tac > $file

UPD3

Продолжаю благодарить анона, что замотивировал таки раскурить sort. Итак, почти самый шустрый вариант:

file=$1
list=$(< $file \
    grep -vn '^$' |
    tac |
    sort -t: -k2 -u |
    sort -t: -k1,1n |
    cut -d: -f2-)
echo "$list" > $file

На моём компе меньше трёх сотых секунды!


UPD4

Дошли руки до AWK и это походу победитель на скорость в стиле unix-way (анон давал такой рецепт в треде).

file=$1
list=$(tac $file |
    grep -v '^$' |
    awk '!added[$0]++')
tac <<< $list > $file

На моём компе — девять тысячных секунды!

★★★★★

Последнее исправление: papin-aziat (всего исправлений: 13)
Ответ на: комментарий от CrX

Неужели не лень каждый раз длинную команду писать

На zsh с этим удобно, в отличие от bash. Например, я не записываю длиннющие команды qemu в скрипт, а прямо в терминале набираю первые строки qe... и стрелочками клавиатуры перебираю историю.
В принципе и в bash так можно, но это специально настраивать, а этим мало кто хочет заниматься из башистов. Но зато bash всегда на первых местах разных голосований. )

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

а этим мало кто хочет заниматься из башистов

оно из коробки сразу работает ctrl+r - по крайней мере я ничего не настраивал, дистры разные - debian, arch, void

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

На zsh с этим удобно, в отличие от bash. Например, я не записываю длиннющие команды

Да, сам так делаю. НО тут sudo, а с sudo начинается относительно большое количество команд.

CrX ★★★★★
()