Для себя уже навалял кучку полезных скриптиков и походу изучения 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
На моём компе — девять тысячных секунды!
