45

This one-liner removes duplicate lines from text input without pre-sorting.

For example:

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

The original code I have found on the internets read:

awk '!_[$0]++'

This was even more perplexing to me as I took _ to have a special meaning in awk, like in Perl, but it turned out to be just a name of an array.

Now, I understand the logic behind the one-liner: each input line is used as a key in a hash array, thus, upon completion, the hash contains unique lines in the order of arrival.

What I would like to learn is how exactly this notation is interpreted by awk. E.g. what the bang sign (!) means and the other elements of this code snippet.

How does it work?

  • 4
    As it's a hash, it's unordered, so "in the order of arrival" isn't actually correct. – Kevin Oct 7 '14 at 6:10
38

Let's see,

 !a[$0]++

first

 a[$0]

we look at the value of a[$0] (array a with whole input line ($0) as key).

If it does not exist ( ! is negation in test will eval to true)

 !a[$0]

we print the input line $0 (default action).

Also, we add one ( ++ ) to a[$0], so next time !a[$0] will evaluate to false.

Nice, find!! You should have a look at code golf!

| improve this answer | |
  • 1
    So the essence is this: the expression in the single quotes is used by awk as a test for each input line; every time the test succeeds awk executes the action in curly braces, which, when omitted is {print}. Thanks! – Alexander Shcheblikin Oct 7 '14 at 1:21
  • @AlexanderShcheblikin in awk, the default action is {print $0}. This means that anything evaluated as true will execute this as default. So for example awk '1' file prints all the lines, awk '$1' file prints all those lines whose first field is not empty or 0, etc. – fedorqui Oct 7 '14 at 10:31
  • 1
    Your description has the action of ! explained before the action of ++ which seems to imply that ! is applied before ++, which can not possibly be. – Isaac yesterday
  • 1
    @Gilles'SO-stopbeingevil' The value of x++ is the old value of x. Yes, exactly, that is the value that the operation ++ returns for the rest of the expression to use. But when that value is return, the value at the memory position of the variable has been incremented. Your other examples are grossly wrong and plain silly. – Isaac 10 hours ago
  • 1
    @Gilles'SO-stopbeingevil' What is the result of awk 'BEGIN{x=0;print x+++(b=x),b}' ? Why ??? – Isaac 10 hours ago
31

Here is the processing:

  • a[$0]: look at the value of key $0, in associative array a. If it does not exist, create it.

  • a[$0]++: increment the value of a[$0], return the old value as value of expression. If a[$0] does not exist, return 0 and increment a[$0] to 1 (++ operator returns numeric value).

  • !a[$0]++: negate the value of expression. If a[$0]++ return 0, the whole expression is evaluated to true, make awk performed default action print $0. Otherwise, the whole expression is evaluated to false, causes awk do nothing.

References:

With gawk, we can use dgawk (or awk --debug with newer version) to debug a gawk script. First, create a gawk script, named test.awk:

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

Then run:

dgawk -f test.awk

or:

gawk --debug -f test.awk

In debugger console:

$ 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>

You can see, Op_postincrement was executed before Op_not.

You can also use si or stepi instead of s or step to see more clearly:

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++;
| improve this answer | |
  • 3
    @Archemar: Your answer indicate that ! is applied before ++. – cuonglm Oct 7 '14 at 5:37
  • 6
    This answer is wrong. The incrementation happens after the result of the ! operator is calculated. You are confusing operator precedence (!a[$0]++ is parsed like !(a[$0]++)) with order of evaluation (the assignment of the new value of a[$0] happens after the value of the expression has been calculated). – Gilles 'SO- stop being evil' Oct 7 '14 at 17:21
  • 5
    @Gnouc It says right in the passage you quoted, and if it worked the way you described, this code wouldn't have the desired effect. First the value !x is calculated, where x is the old value of a[$0]. Then a[$0] is set to 1+x. – Gilles 'SO- stop being evil' Oct 7 '14 at 17:26
  • 7
    I believe that your analysis of what awk does is correct. Sorry if I implied otherwise yesterday. However, your critique of Archemar's answer is wrong. Archemar does not misunderstand precedence, you do, you're confusing precedence with order of evaluation (see my previous comment). If you remove any mention of Archemar's answer in yours, your answer should be correct. As it is, it is focused on proving Archemar wrong, and this is not the case. – Gilles 'SO- stop being evil' Oct 8 '14 at 7:59
  • 6
    well, at least now I know about awk's debugger ... – Archemar Oct 8 '14 at 8:51
0

Result

First, the final result. :-)

Whichever expression is written, the only thing that awk needs to know is whether it is true or false. A 0 or an empty string value is understood as false. And any other result is understood as true. So:

awk 'expression' file

Is actually a short hand of:

awk 'expression {print $0}' file

If the expression result is true (for an specific line), that line gets printed. Otherwise, nothing gets printed.
Numerically: 1 prints, 0 don't.

What we need to understand then is what is the end result of the expression, and how do we get there.

Array

The sequence to process the expression !a[$0]++ must start at the most internal part of the expression, like processing parenthesis, we must start at the most internal pair of them, where all is known.

The only thing we do know is the value of $0, the value of the line being processed by awk. That gets used in an associative array a[$0]. Associative because the indexes could be text, not only numeric. The reference to the array at some key (for example a[one] if the line is one) instantiates (creates) the array space in memory to store it. It is also initialized to the empty string (equivalent to a[one]=""). If, in the future, there is another line that also has the value of one (the same key), no new memory is used, as the array position has already been created.

For each unique line in the input file, that line is stored as an index value in the memory. If there are many unique lines, a lot of memory might get used. But that is the trade-off of not having to sort/uniq the input file.

At this point we need to resolve how a !x++ should be processed.

++

This step has raised a lot of controversy in previous posts.
It has been discussed if the next operation is the ++ or the !. And, if the result of the ++ should be used to calculate the !.

I'll try to make it crystal clear.

It is clear from the operator precedence table that at the third level are the ++ and -- and pretty lower, at the 5 th level, the +, - and !.

In the same way as a 2+3*4 must be carried out in the order of precedence: first multiply 3 by 4 and to result of that expression add 2. Why first multiply? Because it is higher in the precedence table, and then add as it is at the lowest (last) level.

The ++ is higher than ! and must be applied first. There is no way around that IMO.

However, the ++ carry an internal twist. It actually generates two results. One is the value of the variable (technically an lvalue) that is incremented. That ends stored at a memory location. The second one is the value that is given as the result of the expresion as evaluated up to that point. That is given to the next element on the expression:

  1. The value of the variable (lvalue) is incremented and stored at its location in memory in the exact same way whether it is a pre-increment ++x or a post-increment x++. It doesn't matter.

  2. But the value given as the result of the expression x++ or ++x is different. In one: x++, the result of the expression, and the value used for the next operator in the written expression is before being incremented. Or, said the other way around (but not necessarily the sequence of what happens) is: the value is incremented after it is used in the expression. With the ++x the sequence and explanation is the other way around.

The reason on why the exact sequence might not be exactly defined is because, in most implementations, the order of the actions is:

  1. Retrieve the value of the variable (lvalue) and place it in a register (assume A).
  2. Apply the ++ operator, which, as I explained above must result in two values (on post-increment):
  • Copy the value in register A to register B.
  • Increment register B.

The two values are the results in register A and B.

  1. Some languages immediately store the value in register B into memory, And:

  2. Carry on with the expression using the value on register A.

  3. Some languages wait until all the parts of the expression have been evaluated (in the hopes that the value in the register B is used again somewhere in the expression and doesn't need to be retrieved again from memory) and then return the value in register B to memory.

But what should be clear by now is that the ++ is applied first.

!

Then, on the non-incremented value (for a post-increment) we apply the !.
If the value of a[$0] was null (started as empty) it is negated and generates a 1. With a result of 1, the line gets printed.

If the array element a[$0] has already been seen, the value stored at that array position is the result of a previous post-increment, so, it is numeric and greater than 0. The first time, the zero (equivalent to the empty string) is incremented to 1 and that is what the a[$0] contains. On successive lines it might be incremented to bigger numbers (unless it overflow) but it won't return to 0. The ! not of any number (except zero) is zero, and the line won't be printed.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.