Как эффективно перебрать строки файла в Bash?

Question

У меня есть файл example.txt, содержащий около 3000 строк со строкой в ​​каждой строке.Пример небольшого файла:

>cat example.txt
saudifh
sometestPOIFJEJ
sometextASLKJND
saudifh
sometextASLKJND
IHFEW
foo
bar

Я хочу проверить все повторяющиеся строки в этом файле и вывести их.Желаемый результат будет:

>checkRepetitions.sh
found two equal lines: index1=1 , index2=4 , value=saudifh
found two equal lines: index1=3 , index2=5 , value=sometextASLKJND

Я сделал скрипт checkRepetions.sh:

#!bin/bash
size=$(cat example.txt | wc -l)
for i in $(seq 1 $size); do
i_next=$((i+1))
line1=$(cat example.txt | head -n$i | tail -n1)
for j in $(seq $i_next $size); do
line2=$(cat example.txt | head -n$j | tail -n1)
if [ "$line1" = "$line2" ]; then
echo "found two equal lines: index1=$i , index2=$j , value=$line1"
fi
done
done

Однако этот скрипт очень медленный, его запуск занимает более 10 минут.В python это занимает менее 5 секунд ... Я пытался сохранить файл в памяти, выполнив lines=$(cat example.txt) и line1=$(cat $lines | cut -d',' -f$i), но это все еще очень медленно ...

Answer 1

Если вы не хотите использовать awk (хороший инструмент для работы, анализирующий ввод только один раз), Вы можете бегать по линиям несколько раз. Сортировка стоит дорого, но это решение позволяет избежать циклов, которые вы пробовали.

grep -Fnxf <(uniq -d <(sort example.txt)) example.txt

С помощью uniq -d <(sort example.txt) вы найдете все строки, которые встречаются более одного раза. Далее grep найдет эти (опция -f) полные (-x) строки без регулярных выражений (-F) и покажет строку, в которой они встречаются (-n).

Answer 2

Чтобы продемонстрировать относительно эффективный (в рамках языка и времени выполнения) подход native-bash, который вы можете увидеть в онлайн-интерпретаторе на https://ideone.com/iFpJr7:

#!/bin/bash
case $BASH_VERSION in ''|[123].*) echo "ERROR: bash 4.0 required" >&2; exit 1;; esac

# initialize an associative array, mapping each string to the last line it was seen on
declare -A lines=( )
lineNum=0

while IFS= read -r line; do
  lineNum=$(( lineNum + 1 ))
  if [[ ${lines[$line]} ]]; then
     printf 'found two equal lines: index1=%s, index2=%s, value=%s\n' \
       "${lines[$line]}" "$lineNum" "$line"
  fi
  lines[$line]=$lineNum
done <example.txt

Обратите внимание на использование while read для итерации построчно, как описано в BashFAQ # 1 : Как мне прочитать файл построчно (или поле за полем)? ;это позволяет нам открыть файл только один раз и прочитать его без необходимости подстановок команд (которые разделяют подоболочки) или внешних команд (которые должны запускаться операционной системой индивидуально каждый раз, когда они вызываются, и также дороги.).

Другая часть улучшения заключается в том, что мы читаем весь файл только один раз - реализуем алгоритм O (n) - в отличие от выполнения сравнений O (n ^ 2) в качествеоригинальный код сделал.

Answer 3

См. "Почему используется цикл оболочки для обработки текста, который считается плохой практикой" по некоторым причинам, по которым ваш скрипт такой медленный.

$ cat tst.awk
{ val2hits[$0] = val2hits[$0] FS NR }
END {
    for (val in val2hits) {
        numHits = split(val2hits[val],hits)
        if ( numHits > 1 ) {
            printf "found %d equal lines:", numHits
            for ( hitNr=1; hitNr<=numHits; hitNr++ ) {
                printf " index%d=%d ,", hitNr, hits[hitNr]
            }
            print " value=" val
        }
    }
}

$ awk -f tst.awk file
found 2 equal lines: index1=1 , index2=4 , value=saudifh
found 2 equal lines: index1=3 , index2=5 , value=sometextASLKJND

---

Чтобы дать вам представление о разнице в производительности, используйте сценарий bash, который написан для максимальной эффективности, и эквивалентный сценарий awk:

Баш:

$ cat tst.sh
#!/bin/bash
case $BASH_VERSION in ''|[123].*) echo "ERROR: bash 4.0 required" >&2; exit 1;; esac

# initialize an associative array, mapping each string to the last line it was seen on
declare -A lines=( )
lineNum=0

while IFS= read -r line; do
  (( ++lineNum ))
  if [[ ${lines[$line]} ]]; then
     printf 'Content previously seen on line %s also seen on line %s: %s\n' \
       "${lines[$line]}" "$lineNum" "$line"
  fi
  lines[$line]=$lineNum
done < "$1"

$ time ./tst.sh file100k > ou.sh
real    0m15.631s
user    0m13.806s
sys     0m1.029s

AWK:

$ cat tst.awk
lines[$0] {
    printf "Content previously seen on line %s also seen on line %s: %s\n", \
       lines[$0], NR, $0
}
{ lines[$0]=NR }

$ time awk -f tst.awk file100k > ou.awk
real    0m0.234s
user    0m0.218s
sys     0m0.016s

Нет различий в выводе обоих скриптов:

$ diff ou.sh ou.awk
$

Вышеприведенный пример использует 3-й запуск, чтобы избежать проблем с кэшированием, и тестируется на файл, сгенерированный следующим скриптом awk:

awk 'BEGIN{for (i=1; i<=10000; i++) for (j=1; j<=10; j++) print j}' > file100k

Если во входном файле было ноль повторяющихся строк (сгенерированных seq 100000 > nodups100k), сценарий bash выполнялся примерно за то же время, что и выше, тогда как сценарий awk выполнялся намного быстрее, чем выше:

$ time ./tst.sh nodups100k > ou.sh
real    0m15.179s
user    0m13.322s
sys     0m1.278s

$ time awk -f tst.awk nodups100k > ou.awk
real    0m0.078s
user    0m0.046s
sys     0m0.015s