Как работает awk ‘!a[$0]++’?

Эта однострочная команда удаляет дублирующиеся строки из текстового ввода без предварительной сортировки.

Например:

$ cat >f
q
w
e
w
r
$ awk '!a[$0]++' <f
q
w
e
r
$ 

Оригинальный код, который я нашел в интернете, выглядел так:

awk '!_[$0]++'

Это было даже более запутанным для меня, поскольку я считал, что _ в awk имеет специальное значение, как в Perl, но оказалось, что это просто название массива.

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

Что я хотел бы узнать, так это то, как именно эта нотация интерпретируется awk. Например, что значит знак восклицания (!) и другие элементы этого фрагмента кода.

Как это работает?

Вот “интуитивный” ответ; для более детального объяснения механизма awk смотрите либо @Cuonglm’s

В данном случае, !a[$0]++, можно временно отложить пост-инкремент ++, так как он не меняет значения выражения. Поэтому смотрим только на !a[$0]. Здесь:

a[$0]

используется текущая строка $0 в качестве ключа массива a, принимается значение, хранящееся там. Если этот конкретный ключ никогда ранее не использовался, a[$0] оценивается как пустая строка.

!a[$0]

Знак ! отрицает предыдущее значение. Если оно было пустым или нулевым (ложным), теперь у нас есть истинный результат. Если оно было ненулевым (истинным), у нас ложный результат. Если все выражение оценено как истинное, то есть a[$0] изначально не было установлено, то вся строка печатается как действие по умолчанию.

Также, независимо от старого значения, оператор пост-инкремента увеличивает значение a[$0], так что в следующий раз, когда этот же элемент массива будет доступен, он будет положительным и всё условие провалится.

Вот процессинг:

• a[$0]: смотрим на значение ключа $0 в ассоциативном массиве a. Если он не существует, автоматически создаем его с пустой строкой.

• a[$0]++: увеличиваем значение a[$0], возвращаем старое значение как итоговое значение выражения. Оператор ++ возвращает числовое значение, так что если a[$0] изначально было пустым, возвращается 0, а a[$0] увеличивается до 1.

• !a[$0]++: отрицаем значение выражения. Если a[$0]++ вернуло 0 (ложное значение), все выражение оценивается как истинное, и awk выполняет действие по умолчанию print $0. В противном случае, если все выражение оценивается как ложное, никаких дополнительных действий не предпринимается.

Ссылки:

• Выражения в awk
• gawk – Операторы инкремента и декремента

С gawk мы можем использовать dgawk (или awk --debug с более новыми версиями) для отладки скрипта на gawk. Сначала создайте скрипт gawk, названный test.awk:

BEGIN {                                                                         
    a = 0;                                                                      
    !a++;                                                                       
}

Затем выполните:

dgawk -f test.awk

или:

gawk --debug -f test.awk

В консоли отладчика:

$ dgawk -f test.awk
dgawk> trace on
dgawk> watch a
Watchpoint 1: a
dgawk> run
Starting program: 
[     1:0x7fe59154cfe0] Op_rule             : [in_rule = BEGIN] [source_file = test.awk]
[     2:0x7fe59154bf80] Op_push_i           : 0 [PERM|NUMCUR|NUMBER]
[     2:0x7fe59154bf20] Op_store_var        : a [do_reference = FALSE]
[     3:0x7fe59154bf60] Op_push_lhs         : a [do_reference = TRUE]
Stopping in BEGIN ...
Watchpoint 1: a
  Old value: untyped variable
  New value: 0
main() at `test.awk':3
3           !a++;
dgawk> step
[     3:0x7fe59154bfc0] Op_postincrement    : 
[     3:0x7fe59154bf40] Op_not              : 
Watchpoint 1: a
  Old value: 0
  New value: 1
main() at `test.awk':3
3           !a++;
dgawk>

Вы можете увидеть, что Op_postincrement был выполнен перед Op_not.

Вы также можете использовать si или stepi вместо s или step чтобы увидеть более четко:

dgawk> si
[     3:0x7ff061ac1fc0] Op_postincrement    : 
3           !a++;
dgawk> si
[     3:0x7ff061ac1f40] Op_not              : 
Watchpoint 1: a
  Old value: 0
  New value: 1
main() at `test.awk':3
3           !a++;

ах, повсеместный, но также зловещий удалитель дубликатов awk

awk '!a[$0]++'

это сладкое дитя — плод любви мощности и краткости awk. вершина awk-однострочников. короткий, но мощный и таинственный одновременно. удаляет дубликаты, сохраняя порядок. достижение, которое не может достичь uniq или sort -u, которые удаляют только соседние дубликаты или должны нарушить порядок, чтобы удалить дубликаты. (хотя оно делает это за счет потребления памяти.)

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

сначала немного информации: awk — это язык программирования. эта команда awk '!a[$0]++' вызывает интерпретатор/компилятор awk на коде awk !a[$0]++. аналогично python -c 'print("foo")' или node -e 'console.log("foo")'. код awk часто является однострочником, потому что awk специально разработан для краткости для быстрого фильтрации текста в командной строке.

теперь немного псевдокода. то, что делает этот однострочник, в принципе следующее:

для каждой строки ввода
  если эта строка еще не встречалась, то
    распечатать строку
  пометить, что теперь эта строка встречалась

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

но как цикл, если, print и механизм хранения и извлечения строк помещаются в 8 символов кода awk? ответ — в неявности.

цикл, если и print неявны.

для объяснения давайте снова рассмотрим некоторый псевдокод:

для каждой строки ввода
  если строка соответствует некоторому условию, то
    выполнить некоторый код на строке

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

awk делает цикл за нас и пропускает шаблон кода для if. так что нам нужно просто написать условие и код в блоке if:

condition { code block }

в awk это называется “правило”.

мы можем опустить либо условие, либо блок кода (очевидно, мы не можем опустить оба) и awk заполнит недостающую часть неявными элементами.

если мы опустим условие

{ code block }

тогда оно будет неявным истинным

true { code block }

что означает, что блок кода будет выполняться для каждой строки

если мы опустим блок кода

condition

тогда это будет неявная печать текущей строки

condition { print current line }

давайте снова посмотрим на наш оригинальный код awk

!a[$0]++

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

давайте напишем неявные цикл, if и print

для каждой строки ввода
  если !a[$0]++ тогда
    печатать строку

сравните это с нашим оригинальным псевдокодом

для каждой строки ввода                      # неявное в awk
  если эта строка еще не встречалась, то       # по крайней мере, мы знаем условную часть
    печатать строку                            # неявное в awk
  пометить, что теперь эта строка уже встречалась # ???

мы понимаем цикл, if и print. но как это работает так, чтобы оно оценивалось как ложное только для дублированных строк? и как оно помечает строки, которые уже были встречены?

давайте разберём эту зверюгу:

!a[$0]++

если вы знаете немного c или java, вы уже должны знать часть символов. семантика идентична или хотя бы похожа.

восклицательный знак (!) — это отрицатель. он оценивает выражение до логического значения, и каким бы ни был результат, он отрицается. если выражение оценивается как истинное, конечный результат ложен и наоборот.

a[..] — это массив. ассоциативный массив. в других языках это называется map или словарь. в awk все массивы являются ассоциативными массивами. у a нет специального значения. это просто название для массива. это может быть x или eliminatetheduplicate.

$0 — это текущая строка из ввода. это специфическая переменная awk.

плюс плюс (++) — это оператор пост-инкремента. Этот оператор немного сложный, потому что он делает две вещи: значение переменной увеличивается, но также “возвращается” исходное, не увеличенное, значение для дальнейшей обработки.

   !        a[         $0       ]        ++
отрицатель  массив  текущая строка постинкремент

как они работают вместе?

примерно в таком порядке:

1. $0 — это текущая строка
2. a[$0] — это значение в массиве для текущей строки
3. оператор пост-инкремента (++) получает значение от a[$0]; увеличивает и сохраняет его обратно в a[$0]; затем “возвращает” исходное значение следующему оператору в очереди: отрицателю.
4. оператор отрицания (!) получает значение от ++, которое было исходным значением от a[$0]; оно оценивается как логическое и затем отрицается и передается неявному if.
5. if затем решает, печатать строку или нет.

это означает, что печатается строка или нет, или в контексте этой программы awk: является строка дубликатом или нет, в конечном счете, решается значением в a[$0].

следовательно: механизм, который отмечает, видели ли эту строку уже, должно быть, происходит, когда ++ сохраняет увеличенное значение обратно в a[$0].

давайте снова посмотрим на наш псевдокод

для каждой строки ввода
  если эта строка еще не встречалась, то     # решается на основе значения в a[$0]
    печатать строку
  пометить, что теперь эта строка встречалась # происходит за счет инкремента от ++

некоторые из вас уже, возможно, видят, как это работает, но так как мы так далеко зашли, давайте сделаем последние несколько шагов и разберем ++

мы начнем с кода awk, встроенного в неявные элементы

для каждой строки как $0
  если !a[$0]++ тогда
    печатать $0

давайте введем переменные, чтобы было больше места для работы

для каждой строки как $0
  tmp = a[$0]++
  если !tmp тогда
    печатать $0

теперь давайте разберем ++.

помните, что этот оператор делает две вещи: увеличивает значение переменной и возвращает исходное значение для дальнейшей обработки. так что ++ становится двумя строками:

для каждой строки как $0
  tmp = a[$0]       # получить исходное значение
  a[$0] = tmp + 1   # увеличить значение в переменной
  если !tmp тогда   # решать на основе исходного значения
    печатать $0

или, другими словами

для каждой строки как $0
  tmp = a[$0]       # запросить, видели ли эту строку
  a[$0] = tmp + 1   # пометить, что видели эту строку
  если !tmp тогда   # решать на основе того, видели ли эту строку
    печатать $0

сравните с нашим первым псевдокодом

для каждой строки ввода:
  если эта строка еще не встречалась:
    печатать строку
  пометить, что теперь эта строка встречалась

так что вот и все, что у нас есть. есть цикл, if, print, запрос и пометка. просто в другом порядке, чем псевдокод.

сжатый до 8 символов

!a[$0]++

возможно благодаря многим неявным элементам awk.

остается один вопрос. каково значение a[$0] для первой строки? или для любой строки, которая еще не встречалась? ответ снова в неявности.

в awk любая переменная, которая используется впервые, неявно объявляется и инициализируется пустой строкой. кроме массивов. массивы объявляются и инициализируются пустым массивом.

оператор ++ выполняет неявные преобразования в число. пустая строка преобразуется в ноль. другие строки будут преобразованы в число с помощью некоторого алгоритма best-effort. если строка не распознается как число, она снова преобразуется в ноль.

оператор ! выполняет неявное преобразование в boolean. число ноль и пустая строка преобразуются в ложь. все остальное преобразуется в истину.

это означает, что когда строка видится впервые, то a[$0] устанавливается в пустую строку. пустая строка преобразуется в ноль оператором ++, затем увеличивается до 1 и сохраняется обратно в a[$0]. исходный ноль преобразуется в ложь оператором !. результат от ! истинный, поэтому строка печатается.

значение в a[$0] теперь равно числу 1.

если строка видится во второй раз, то a[$0] равно числу 1, которое преобразуется в истину, и результат от ! ложный, так что это не печатается.

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

так дубликаты и удаляются.

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

---

бонус: некоторые варианты однострочника и суперкороткие объяснения того, что он делает.

замените $0 (вся строка) на $2 (второй столбец), и он будет удалять дубликаты, но только на основе второго столбца

$ cat input 
x y z
p q r
a y b

$ awk '!a[$2]++' input 
x y z
p q r

замените ! (отрицатель) на ==1 (равно одному), и он будет печатать первую строку, которая является дубликатом

$ cat input 
a
b
c
c
b
b

$ awk 'a[$0]++==1' input 
c
b

замените на >0 (больше нуля) и добавьте {print NR":"$0}, чтобы напечатать все дублированные строки с номером строки. NR — это специальная переменная awk, содержащая номер строки (номер записи на языке awk).

$ awk 'a[$0]++>0 {print NR":"$0}' input 
4:c
5:b
6:b

я надеюсь, что эти примеры помогут лучше понять концепции, объясненные выше.

Просто хочу добавить, что и expr++, и ++expr — это сокращенная форма для expr=expr+1. Но

$ awk '!a[$0]++' f # или 
$ awk '!(a[$0]++)' f

будет печатать все уникальные значения, так как expr++ будет оцениваться в expr перед добавлением, в то время как

$ awk '!(++a[$0])' f

будет просто ничего не печатать, так как ++expr будет оцениваться как expr+1, что всегда возвращает ненулевое значение в этом случае, и отрицание всегда будет давать нулевое значение.

q
w
e
w
r