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

Question

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

Например:

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

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

awk '!_[$0]++'

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

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

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

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

Answer 1

Вот «интуитивный» ответ, для более глубокого объяснения механизма awk см. @Cuonglm

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

a[$0]

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

!a[$0]

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

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

Answer 2

Вот обработка:

• 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++;

Answer 3

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

awk '!a[$0]++'

Этот милый малыш — плод любви, сочетающий в себе мощь и лаконичность awk. Вершина однострочников 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 был специально разработан для краткости при фильтрации текста.

Теперь немного псевдокода. В основном эта строка делает следующее:

for every line of input
  if i have not seen this line before then
    print line
  take note that i have now seen this line

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

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

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

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

for every line of input
  if line matches condition then
    execute code block

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

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

condition { code block }

В awk это называется «правилом».

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

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

{ code block }

тогда это будет неявно верно

true { code block }

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

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

condition

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

condition { print current line }

Давайте еще раз посмотрим на наш исходный код awk.

!a[$0]++

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

давайте запишем неявный цикл и если и напечатаем

for every line of input
  if !a[$0]++ then
    print line

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

for every line of input                      # implicit by awk
  if i have not seen this line before then   # at least we know the conditional part
    print line                               # implicit by awk
  take note that i have now seen this line   # ???

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

Давайте разберем этого зверя:

!a[$0]++

если вы немного знаете C или Java, вы уже должны знать некоторые символы. Семантика идентична или, по крайней мере, похожа.

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

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

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

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

   !        a[         $0       ]        ++
negator   array   current line      post increment

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

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

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

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

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

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

for every line of input
  if i have not seen this line before then   # decided based on value in a[$0]
    print line
  take note that i have now seen this line   # happens by increment from ++

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

мы начинаем с кода awk, встроенного в неявные функции

for each line as $0
  if !a[$0]++ then
    print $0

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

for each line as $0
  tmp = a[$0]++
  if !tmp then
    print $0

теперь разберем ++.

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

for each line as $0
  tmp = a[$0]       # get original value
  a[$0] = tmp + 1   # increment value in variable
  if !tmp then
    print $0

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

for each line as $0
  tmp = a[$0]       # query if have seen this line
  a[$0] = tmp + 1   # take note that has seen this line
  if !tmp then
    print $0

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

for every line of input:
  if i have not seen this line before:
    print line
  take note that i have now seen this line

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

сокращено до 8 символов

!a[$0]++

возможно из-за неявного цикла awks, неявного if, неявной печати, а также потому, что ++выполняет как запрос, так и делает заметки.

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

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

выполняет ++неявные преобразования в число. Пустая строка преобразуется в ноль. Другие строки будут преобразованы в число с помощью некоторого наилучшего алгоритма. Если строка не распознана как число, она снова преобразуется в ноль.

выполняет !неявное преобразование в логическое значение. Число ноль и пустая строка преобразуются в false. Все остальное преобразуется в true.

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

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

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

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

Именно так удаляются дубликаты.

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

---

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

замените $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

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

Answer 4

Хочу только добавить, что и то, expr++и другое ++expr— это просто сокращение от expr=expr+1. Но

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

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

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

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