298

Suppose you have a file that contains IP addresses, one address in each line:

10.0.10.1
10.0.10.1
10.0.10.3
10.0.10.2
10.0.10.1

You need a shell script that counts for each IP address how many times it appears in the file. For the previous input you need the following output:

10.0.10.1 3
10.0.10.2 1
10.0.10.3 1

One way to do this is:

cat ip_addresses |uniq |while read ip
do
    echo -n $ip" "
    grep -c $ip ip_addresses
done

However it is really far from being efficient.

How would you solve this problem more efficiently using bash?

(One thing to add: I know it can be solved from perl or awk, I'm interested in a better solution in bash, not in those languages.)

ADDITIONAL INFO:

Suppose that the source file is 5GB and the machine running the algorithm has 4GB. So sort is not an efficient solution, neither is reading the file more than once.

I liked the hashtable-like solution - anybody can provide improvements to that solution?

ADDITIONAL INFO #2:

Some people asked why would I bother doing it in bash when it is way easier in e.g. perl. The reason is that on the machine I had to do this perl wasn't available for me. It was a custom built linux machine without most of the tools I'm used to. And I think it was an interesting problem.

So please, don't blame the question, just ignore it if you don't like it. :-)

3

17 Answers 17

515
sort ip_addresses | uniq -c

This will print the count first, but other than that it should be exactly what you want.

3
  • 82
    which you can then pipe to "sort -nr" to have sorted in descending order, from highest to lowest count. ie sort ip_addresses | uniq -c | sort -nr
    – Brad Parks
    Mar 11, 2014 at 11:45
  • 21
    And sort ip_addresses | uniq -c | sort -nr | awk '{ print $2, $1 }' to get the ip address in the first column and count in the second. Sep 19, 2016 at 22:25
  • one more tweak for sort part: sort -nr -k1,1 Dec 10, 2019 at 10:19
69

The quick and dirty method is as follows:

cat ip_addresses | sort -n | uniq -c

If you need to use the values in bash you can assign the whole command to a bash variable and then loop through the results.

PS

If the sort command is omitted, you will not get the correct results as uniq only looks at successive identical lines.

10
  • It's very similar efficiency-wise, you still have quadratic behavior
    – Vinko Vrsalovic
    Dec 19, 2008 at 12:22
  • Quadratic meaning O(n^2)?? That would depend on the sort algorithm surely, it's unlikely to use such a bogo-sort as that.
    – paxdiablo
    Dec 19, 2008 at 13:08
  • Well, in the best case it'd be O(n log(n)), which is worse than two passes (which is what you get with a trivial hash based implementation). I should have said 'superlinear' instead of quadratic.
    – Vinko Vrsalovic
    Dec 19, 2008 at 13:23
  • And it's still in the same bound that what the OP asked to improve efficiency wise...
    – Vinko Vrsalovic
    Dec 19, 2008 at 13:24
  • In addition, cat foo | sort | uniq is redundant at best, saua's solution is the simplest (still suffering from the super linear behavior though).
    – Vinko Vrsalovic
    Dec 19, 2008 at 13:25
35

for summing up multiple fields, based on a group of existing fields, use the example below : ( replace the $1, $2, $3, $4 according to your requirements )

cat file

US|A|1000|2000
US|B|1000|2000
US|C|1000|2000
UK|1|1000|2000
UK|1|1000|2000
UK|1|1000|2000

awk 'BEGIN { FS=OFS=SUBSEP="|"}{arr[$1,$2]+=$3+$4 }END {for (i in arr) print i,arr[i]}' file

US|A|3000
US|B|3000
US|C|3000
UK|1|9000
4
  • 2
    +1 because it shows what to do when not only the count is needed
    – user829755
    Sep 26, 2014 at 14:21
  • 1
    +1 because sort and uniq are easiest for doing counts, but don't help when you need to compute/sum fields values. awk's array syntax is very powerful and key to grouping here. Thanks!
    – odony
    Feb 25, 2016 at 12:51
  • 2
    one more thing, watch out that awk's print function seems to downscale 64 bits integers to 32 bits, so for int values exceeding 2^31 you may want to use printf with the %.0f format instead of print there
    – odony
    Feb 25, 2016 at 13:05
  • 2
    People looking for "group by" with string concatenation instead of number addition would replace arr[$1,$2]+=$3+$4 with e.g. arr[$1,$2]=(arr[$1,$2] $3 "," $4). I needed this to provide a grouped-by-package list of files (two columns only) and used: arr[$1]=(arr[$1] $2)` with success. Feb 12, 2018 at 11:00
25

The canonical solution is the one mentioned by another respondent:

sort | uniq -c

It is shorter and more concise than what can be written in Perl or awk.

You write that you don't want to use sort, because the data's size is larger than the machine's main memory size. Don't underestimate the implementation quality of the Unix sort command. Sort was used to handle very large volumes of data (think the original AT&T's billing data) on machines with 128k (that's 131,072 bytes) of memory (PDP-11). When sort encounters more data than a preset limit (often tuned close to the size of the machine's main memory) it sorts the data it has read in main memory and writes it into a temporary file. It then repeats the action with the next chunks of data. Finally, it performs a merge sort on those intermediate files. This allows sort to work on data many times larger than the machine's main memory.

2
  • Well, it's still worse than a hash count, no? Do you know what sorting algorithm does sort use if the data fits in memory? Does it vary in the numeric data case (-n option)?
    – Vinko Vrsalovic
    Dec 21, 2008 at 17:32
  • It depends on how sort(1) is implemented. Both GNU sort (used on Linux distributions) and the BSD sort go to large lengths to use the most appropriate algorithm. Dec 23, 2008 at 14:59
17
cat ip_addresses | sort | uniq -c | sort -nr | awk '{print $2 " " $1}'

this command would give you desired output

7

Solution ( group by like mysql)

grep -ioh "facebook\|xing\|linkedin\|googleplus" access-log.txt | sort | uniq -c | sort -n

Result

3249  googleplus
4211 linkedin
5212 xing
7928 facebook
4

It seems that you have to either use a big amount of code to simulate hashes in bash to get linear behavior or stick to the quadratic superlinear versions.

Among those versions, saua's solution is the best (and simplest):

sort -n ip_addresses.txt | uniq -c

I found http://unix.derkeiler.com/Newsgroups/comp.unix.shell/2005-11/0118.html. But it's ugly as hell...

2
  • I agree. This is the best solution so far and similar solutions are possible in perl and awk. Can anybody provide a cleaner implementation in bash?
    – Zizzencs
    Dec 19, 2008 at 13:38
  • Not that I know of. You can get better implementations in languages supporting hashes, where you do for my $ip (@ips) { $hash{$ip} = $hash{$ip} + 1; } and then just print the keys and values.
    – Vinko Vrsalovic
    Dec 19, 2008 at 14:07
4

I feel awk associative array is also handy in this case

$ awk '{count[$1]++}END{for(j in count) print j,count[j]}' ips.txt

A group by post here

1
  • Yepp, great awk solution, but awk was just not avaialable on the machine I was doing this on.
    – Zizzencs
    Dec 23, 2008 at 12:09
3

You probably can use the file system itself as a hash table. Pseudo-code as follows:

for every entry in the ip address file; do
  let addr denote the ip address;

  if file "addr" does not exist; then
    create file "addr";
    write a number "0" in the file;
  else 
    read the number from "addr";
    increase the number by 1 and write it back;
  fi
done

In the end, all you need to do is to traverse all the files and print the file names and numbers in them. Alternatively, instead of keeping a count, you could append a space or a newline each time to the file, and in the end just look at the file size in bytes.

3

Most of the other solutions count duplicates. If you really need to group key value pairs, try this:

Here is my example data:

find . | xargs md5sum
fe4ab8e15432161f452e345ff30c68b0 a.txt
30c68b02161e15435ff52e34f4fe4ab8 b.txt
30c68b02161e15435ff52e34f4fe4ab8 c.txt
fe4ab8e15432161f452e345ff30c68b0 d.txt
fe4ab8e15432161f452e345ff30c68b0 e.txt

This will print the key value pairs grouped by the md5 checksum.

cat table.txt | awk '{print $1}' | sort | uniq  | xargs -i grep {} table.txt
30c68b02161e15435ff52e34f4fe4ab8 b.txt
30c68b02161e15435ff52e34f4fe4ab8 c.txt
fe4ab8e15432161f452e345ff30c68b0 a.txt
fe4ab8e15432161f452e345ff30c68b0 d.txt
fe4ab8e15432161f452e345ff30c68b0 e.txt
1
  • You'd better with uniq sed command: sort <table.txt | sed ':a;N;s/^\(.\{32\}\) \(.*\)\n\1 \(.*\)$/\1 \2 \3/;ta;P;D;ba' This will print 1 line by md5sum, with each file in same line. Mar 12, 2022 at 7:38
2

Importing data to sqlite db and using sql syntax (just an other idea). I know it's too much for this example but would be useful for complex queries with multiple files (tables)

#!/bin/bash
trap clear_db EXIT
clear_db(){ rm -f "mydb$$"; }

# add header to input_file (IP)
INPUT_FILE=ips.txt

# import file into db
sqlite3 -csv mydb$$ ".import ${INPUT_FILE} mytable"

# using sql statements on table 'mytable' 
sqlite3 mydb$$ -separator " "  "SELECT IP, COUNT(*) FROM mytable GROUP BY IP;"

10.0.10.1 3
10.0.10.2 1
10.0.10.3 1
2

GROUP BY under

Regarding this SO thread, there are some different answer regarding different needs.

1. Counting IP as SO request (GROUP BY IP address).

As IP are easy to convert to single integer, for small bunch of address, if you need to repeat this kind of operation many time, using a pure function could be a lot more efficient!

Pure (no fork!)

There is a way, using a function. This way is very quick as there is no fork!...

countIp () { 
    local -a _ips=(); local _a
    while IFS=. read -a _a ;do
        ((_ips[_a<<24|${_a[1]}<<16|${_a[2]}<<8|${_a[3]}]++))
    done
    for _a in ${!_ips[@]} ;do
        printf "%.16s %4d\n" \
          $(($_a>>24)).$(($_a>>16&255)).$(($_a>>8&255)).$(($_a&255)) ${_ips[_a]}
    done
}

Note: IP addresses are converted to 32bits unsigned integer value, used as index for array. This use simple bash arrays!

time countIp < ip_addresses 
10.0.10.1    3
10.0.10.2    1
10.0.10.3    1
real    0m0.001s
user    0m0.004s
sys     0m0.000s

time sort ip_addresses | uniq -c
      3 10.0.10.1
      1 10.0.10.2
      1 10.0.10.3
real    0m0.010s
user    0m0.000s
sys     0m0.000s

On my host, doing so is a lot quicker than using forks, upto approx 1'000 addresses, but take approx 1 entire second when I'll try to sort'n count 10'000 addresses.

2. GROUP BY duplicates (files content)

By using checksum you could indentfy duplicate files somewhere:

find . -type f -exec sha1sum {} + |
    sort |
        sed '
          :a;
          $s/^[^ ]\+ \+//;
          N;
          s/^\([^ ]\+\) \+\([^ ].*\)\n\1 \+\([^ ].*\)$/\1 \2\o11\3/;
          ta;
          s/^[^ ]\+ \+//;
          P;
          D;
          ba
    '

This will print all duplicates, by line, separated by Tabulation ($'\t' or octal 011 ou could change /\1 \2\o11\3/; by /\1 \2|\3/; for using | as separator).

./b.txt   ./e.txt
./a.txt   ./c.txt    ./d.txt

Could be written as (with | as separator):

find . -type f -exec sha1sum {} + | sort | sed ':a;$s/^[^ ]\+ \+//;N;
  s/^\([^ ]\+\) \+\([^ ].*\)\n\1 \+\([^ ].*\)$/\1 \2|\3/;ta;s/^[^ ]\+ \+//;P;D;ba'

Pure way

By using nameref, you could build bash arrays holding all duplicates:

declare -iA sums='()'
while IFS=' ' read -r sum file ;do
    declare -n list=_LST_$sum
    list+=("$file")
    sums[$sum]+=1
done < <(
    find . -type f -exec sha1sum {} +
)

From there, you have a bunch of arrays holding all duplicates file name as separated element:

for i in ${!sums[@]};do
     declare -n list=_LST_$i
     printf "%d %d %s\n" ${sums[$i]} ${#list[@]} "${list[*]}"
done

This may output something like:

2 2 ./e.txt ./b.txt
3 3 ./c.txt ./a.txt ./d.txt

Where count of files by md5sum (${sums[$shasum]}) match count of element in arrays ${_LST_ShAsUm[@]}.

for i in ${!sums[@]};do
    declare -n list=_LST_$i
    echo ${list[@]@A}
done
declare -a _LST_22596363b3de40b06f981fb85d82312e8c0ed511=([0]="./e.txt" [1]="./b.txt")
declare -a _LST_f572d396fae9206628714fb2ce00f72e94f2258f=([0]="./c.txt" [1]="./a.txt" [2]="./d.txt")

Note that this method could handle spaces and special characters in filenames!

3. GROUP BY columns in a table

As efficient sample using awk was provided by Anonymous, here is a pure solution.

So you want to sumarize columns 3 to last column and group by columns 1 and 2, having table.txt looking like

US|A|1000|2000
US|B|1000|2000
US|C|1000|2000
UK|1|1000|2000
UK|1|1000|2000|3000
UK|1|1000|2000|3000|4000

For not too big tables, you could:

myfunc() {
    local -iA restabl='()';
    local IFS=+
    while IFS=\| read -ra ar; do
        restabl["${ar[0]}|${ar[1]}"]+="${ar[*]:2}"
    done
    for i in ${!restabl[@]} ;do
        printf '%s|%s\n' "$i" "${restabl[$i]}"
    done
}

Could ouput something like:

myfunc <table.txt 
UK|1|19000
US|A|3000
US|C|3000
US|B|3000

And to have table sorted:

myfunc() {
    local -iA restabl='()';
    local IFS=+ sorted=()
    while IFS=\| read -ra ar; do
        sorted[64#${ar[0]}${ar[1]}]="${ar[0]}|${ar[1]}"
        restabl["${ar[0]}|${ar[1]}"]+="${ar[*]:2}"
    done
    for i in ${sorted[@]} ;do
        printf '%s|%s\n' "$i" "${restabl[$i]}"
    done
}

Must return:

myfunc <table 
UK|1|19000
US|A|3000
US|B|3000
US|C|3000
1

I'd have done it like this:

perl -e 'while (<>) {chop; $h{$_}++;} for $k (keys %h) {print "$k $h{$k}\n";}' ip_addresses

but uniq might work for you.

1
  • As I told in the original post perl is not an option. I know it is easy in perl, no problem with that :-)
    – Zizzencs
    Dec 23, 2008 at 12:06
1

This does not answer the count element of the original question, but this question is the first search engine result when searching for what I wanted to achieve, so I thought this may help someone as it relates to 'group by' functionality.

I wanted to order files based on groupings of them, where the presence of some string in the filename determined the group.

It uses a temporary grouping/ordering prefix which is removed after ordering; sed substitute expressions (s#pattern#replacement#g) match the target string and prepend an integer to the line corresponding to the desired sort order of that target string. Then, grouping prefix is removed with cut.

Note that the sed expressions could be joined (e.g. sed -e '<expr>; <expr>; <expr>;') but here they're split for readability.

It's not pretty and probably not fast (I'm dealing with <50 items) but it at-least conceptually simple and doesn't require learning awk.

#!/usr/bin/env bash

for line in $(find /etc \
    | sed -E -e "s#^(.*${target_string_A}.*)#${target_string_A_sort_index}:\1#;" \
    | sed -E -e "s#^(.*${target_string_B}.*)#${target_string_B_sort_index}:\1#;" \
    | sed -E -e "s#^/(.*)#00:/\1#;" \
    | sort \
    | cut -c4-
)
do
    echo "${line}"
done

e.g. Input

/this/is/a/test/a
/this/is/a/test/b
/this/is/a/test/c
/this/is/a/special/test/d
/this/is/a/another/test/e
#!/usr/bin/env bash

for line in $(find /etc \
    | sed -E -e "s#^(.*special.*)#10:\1#;" \
    | sed -E -e "s#^(.*another.*)#05:\1#;" \
    | sed -E -e "s#^/(.*)#00:/\1#;" \
    | sort \
    | cut -c4-
)
do
    echo "${line}"
done
/this/is/a/test/a
/this/is/a/test/b
/this/is/a/test/c
/this/is/a/another/test/e
/this/is/a/special/test/d
3
  • The pipes of sed into sed should almost certainly be refactored, perhaps into Awk.
    – tripleee
    Jun 21, 2022 at 11:30
  • You seem to be describing the decorate - sort - undecorate pattern.
    – tripleee
    Jun 21, 2022 at 11:32
  • From the answer: "Note that the sed expressions could be joined [..] but here they're split for readability". From the answer: "doesn't require learning awk". Thanks anyway.
    – TKF
    Jun 21, 2022 at 11:42
1

A combination of awk + sort (with version sort flag) is probably fastest (if ur environment has awk at all):

echo "${input...}" |

{m,g}awk '{ __[$+_]++ } END { for(_ in __) { print "",+__[_],_ } }' FS='^$' OFS='\t' | 

gsort -t$'\t' -k 3,3 -V

Only the post GROUP-BY summary rows are being sent to the sorting utility - which is far less system intensive sort compared to pre-sorting the input rows for no reason.

For small inputs, e.g. fewer than 1000 rows or so, just directly sort|uniq -c it.

    3   10.0.10.1
    1   10.0.10.2
    1   10.0.10.3
0

I understand you are looking for something in Bash, but in case someone else might be looking for something in Python, you might want to consider this:

mySet = set()
for line in open("ip_address_file.txt"):
     line = line.rstrip()
     mySet.add(line)

As values in the set are unique by default and Python is pretty good at this stuff, you might win something here. I haven't tested the code, so it might be bugged, but this might get you there. And if you want to count occurrences, using a dict instead of a set is easy to implement.

Edit: I'm a lousy reader, so I answered wrong. Here's a snippet with a dict that would count occurences.

mydict = {}
for line in open("ip_address_file.txt"):
    line = line.rstrip()
    if line in mydict:
        mydict[line] += 1
    else:
        mydict[line] = 1

The dictionary mydict now holds a list of unique IP's as keys and the amount of times they occurred as their values.

4
  • this doesn't count anything. you need a dict that keeps score.
    – user3850
    Dec 20, 2008 at 16:48
  • Doh. Bad reading of the question, sorry. I originally had a little something about using a dict to store the amount of times each IP address occured, but removed it, because, well, I didn't read the question very well. * tries to wake up properly
    – wzzrd
    Dec 20, 2008 at 16:59
  • 2
    There is a itertools.groupby() which combined with sorted() does exactly what OP asks.
    – jfs
    Dec 21, 2008 at 15:28
  • It is a great solution in python, which was not available for this :-)
    – Zizzencs
    Dec 23, 2008 at 12:08
-9

Sort may be omitted if order is not significant

uniq -c <source_file>

or

echo "$list" | uniq -c

if the source list is a variable

1
  • 1
    To further clarify, from the uniq man page: Note: ’uniq’ does not detect repeated lines unless they are adjacent. You may want to sort the input first, or use ‘sort -u’ without ‘uniq’. Dec 19, 2008 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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