Login or Register to Ask a Question and Join Our Community


Shell Programming and Scripting

The builtin split function in AWK is too slow

Login to Discuss or Reply to this Discussion in Our Community

 
Thread Tools Search this Thread
Top Forums Shell Programming and Scripting The builtin split function in AWK is too slow
# 8  
Old 05-20-2010
OK, I will explain what I want to achieve.
I have two data files, I want to generate the result through grouping and sorting the data in these two files.
Code:
$ cat data1.txt
A:list1,list2,list3,list4
B:list1,list2,list3,list4
C:list1,list2,list6
D:list3
F:list2,list4,list5
G:list7
H:list2,list5
A:list1,list2,list3,list4
B:list1,list2,list3,list4
C:list1,list2,list6
D:list3
F:list2,list4,list5
G:list7
H:list2,list5

$ cat data2.txt
list1:A,B,C
list2:A,B,C,F,H
list3:A,B,D
list4:A,B,F
list5:H,F
list6:C
list7:G

desired output:
A:B,C,D,F,H
B:A,C,D,F,H
C:A,B,F,H
D:A,B
F:A,B,C,H
H:A,B,C,F

I will explain a little bit for the output. For the row that starts with "A", "B,C,D,F,H" are extracted from all those lists that contain "A", and they are sorted by their appearing frequency in descending order.

I have already written the code that can generate the desired output, but I have noticed that the split function I used in the program is TOO slow when it comes to splitting a string that contains over 30,000 fields(comma separated). So I am here seeking a solution to making it fast.

This is the code I used to generate the output:
Code:
#!/bin/awk -f

BEGIN { FS=":"; ts1 = "date \"+%s\""; }
NR == FNR { bookLists[$1]=$2; next }    #the first file
{ books[$1]=$2 }                                        #the second file
END {
{ print "There are in total", length(bookLists), "book lists and ", length(books), "books." > "make_data_log.txt" }
count = 0
#bookLists: A:list1,list2
#books: list1:A,B
cmd = "sort -k 3 -nr | awk ' { arr[$2]; if(!b) b=$1 } END { for (i in arr) str=str ? str\",\"i : i; print b, str} '"
for (i in bookLists) {
        #print "========== book " i "=========="
        split(bookLists[i], tmpBls, /,/)
        for (j in tmpBls) {
                split(books[tmpBls[j]], tmpBs, /,/)
                for (k in tmpBs)
                        ++result[tmpBs[k]]      #print i":", tmpBs[k]
                delete tmpBs
        }
        for (l in result) {
                if (i != l) print i, l, result[l] | cmd
                #if (i != l) print i, l, result[l]
                if (++num == 20) break
        }
        close(cmd)              #close the pipe, or this "sort" will be delayed until the awk program ends
        delete result
        delete tmpBls
        num = 0
        if (++count % 100000 == 0)
                print count >> "make_data_log.txt"
}

{ ts2 = "date \"+%s\""; print ts2-ts1, "seconds consumed." >> "make_data_log.txt" }

}



---------- Post updated at 08:39 PM ---------- Previous update was at 07:23 AM ----------

bump...
please, experts...how to make this script fast?
# 9  
Old 05-21-2010
Quote:
Originally Posted by kevintse
now I have this code:

Code:
awk -F: -vcmd="awk ' BEGIN { RS=\",\"} { print $1 }'" '{ print $2 | cmd; close(cmd)} ' data.txt

That code is incorrect. Since it occurs within double-quotes, $1 is replaced by the shell with the value of its first positional parameter, before AWK ever sees it. If, instead, you want it to refer the first field in AWK, you need to quote it, \$1.

The only reason I can think of for why you're getting the expected result is that the shell's first positional parameter, $1, is empty, and so AWK is only seeing "{ print }". Since lines split on the comma are yielding one-field records, within AWK, in this specific case, "print" (equivalent to "print $0") is equivalent to "print $1", and hence everything seems okay.

If I'm correct, setting $1 in the shell to a non-null value not equal to a literal '$0' or a literal '$1' will break the code.

Regards,
Alister

---------- Post updated 05-21-10 at 12:19 AM ---------- Previous update was 05-20-10 at 10:01 PM ----------
Quote:
Originally Posted by kevintse
Code:
$ cat data2.txt
list1:A,B,C
list2:A,B,C,F,H
list3:A,B,D
list4:A,B,F
list5:H,F
list6:C
list7:G

desired output:
A:B,C,D,F,H
B:A,C,D,F,H
C:A,B,F,H
D:A,B
F:A,B,C,H
H:A,B,C,F

I will explain a little bit for the output. For the row that starts with "A", "B,C,D,F,H" are extracted from all those lists that contain "A", and they are sorted by their appearing frequency in descending order.

I have already written the code that can generate the desired output.
That output is incorrect. If you take a close look at the desired output that you provided, they are incorrectly sorted. The easiest to spot is "H:A,B,C,F". H occurs with F twice, and the others once. That line should be, "H:F,A,B,C". As a matter of fact, with the exception of the C and D lines, they are all wrong. A quick look at your code suggests that the problem lies in:

Quote:
Originally Posted by kevintse
Code:
cmd = "sort -k 3 -nr | awk ' { arr[$2]; if(!b) b=$1 } END { for (i in arr)

Specifically, 'for (i in arr)' is not guaranteed to return the array elements in any specific order. That pipeline sorts with the sort command but then that order is disgarded when the "in" operator is used.

Regards,
Alister
# 10  
Old 05-21-2010
Try this awk program which doesn't use the split function :
Code:
awk -v Q="'" -F'[:,]' '
BEGIN {
   cmd = "sort -k3,3nr -k2,2 | awk " Q "{ out=out (NR==1 ? $1 \":\" : \",\") $2 } END { print out }" Q;
}
NR==FNR {
   list = $1;
   all  = "";
   for (i=2; i<=NF; i++) {
      all = all SUBSEP $i ;
      books[list, i-1] = $i;
   }
   books[list, "all"  ] = all SUBSEP;
   books[list, "count"] = NF-1;
   next;
}
{
   book  = $1;
   delete bookCount;
   for (i=2; i<=NF; i++) {
      list = $i;
      if (books[list, "all"] ~ SUBSEP book SUBSEP) {
         for (ib=1; ib<=books[list, "count"]; ib++) {
            bookCount[books[list, ib]]++;
         }
      }
   }
   for (b in bookCount) {
      if (b != book) {
         print book, b, bookCount[b] | cmd;
      }
   }
   close(cmd);
}

' kevin2.dat kevin1.dat

Input file 1 (kevin1.dat) :
Code:
A:list1,list2,list3,list4
B:list1,list2,list3,list4
C:list1,list2,list6
D:list3
F:list2,list4,list5
G:list7
H:list2,list5

Input file 2 (kevin2.dat) :
Code:
list1:A,B,C
list2:A,B,C,F,H
list3:A,B,D
list4:A,B,F
list5:H,F
list6:C
list7:G

Output:
Code:
$ time ./kevin.sh
A:B,C,F,D,H
B:A,C,F,D,H
C:A,B,F,H
D:A,B
F:A,B,H,C
H:F,A,B,C

real    0m1.142s
user    0m0.590s
sys     0m0.580s
$

The problem with that script is that we run a sort command for every book.
The following solution use only one sort command :
Code:
awk -v Q="'" -F'[:,]' '
NR==FNR {
   list = $1;
   all  = "";
   for (i=2; i<=NF; i++) {
      all = all SUBSEP $i ;
      books[list, i-1] = $i;
   }
   books[list, "all"  ] = all SUBSEP;
   books[list, "count"] = NF-1;
   next;
}
{
   book  = $1;
   delete bookCount;
   for (i=2; i<=NF; i++) {
      list = $i;
      if (books[list, "all"] ~ SUBSEP book SUBSEP) {
         for (ib=1; ib<=books[list, "count"]; ib++) {
            bookCount[books[list, ib]]++;
         }
      }
   }
   for (b in bookCount) {
      if (b != book) {
         print book, b, bookCount[b]
      }
   }
   close(cmd);
}

' kevin2.dat kevin1.dat  |
sort -k1,1 -k3,3nr -k2,2 |
awk '
{
   book = $1;
   if (book == prev) {
      out = out "," $2;
   } else {
      if (out) print prev ":" out;
      out = $2;
      prev = book;
   }
}
END { if (out) print prev ":" out; }
'

With the same input files, the out is the same but times are better :
Code:
$ time ./kevin2.sh
A:B,C,F,D,H
B:A,C,F,D,H
C:A,B,F,H
D:A,B
F:A,B,H,C
H:F,A,B,C

real    0m0.419s
user    0m0.152s
sys     0m0.169s
$

Jean-Pierre.
Last edited by aigles; 05-21-2010 at 05:59 PM..
These 2 Users Gave Thanks to aigles For This Post:
kevintse Neo
# 11  
Old 05-21-2010
I have been going through your posts, and I don't quite understand a few things in your data files.

Quote:
Originally Posted by kevintse
...I have two data files, I want to generate the result through grouping and sorting the data in these two files.
Code:
$ cat data1.txt
A:list1,list2,list3,list4
B:list1,list2,list3,list4
C:list1,list2,list6
D:list3
F:list2,list4,list5
G:list7
H:list2,list5
A:list1,list2,list3,list4
B:list1,list2,list3,list4
C:list1,list2,list6
D:list3
F:list2,list4,list5
G:list7
H:list2,list5
 
$ cat data2.txt
list1:A,B,C
list2:A,B,C,F,H
list3:A,B,D
list4:A,B,F
list5:H,F
list6:C
list7:G
 
desired output:
A:B,C,D,F,H
B:A,C,D,F,H
C:A,B,F,H
D:A,B
F:A,B,C,H
H:A,B,C,F

I will explain a little bit for the output. For the row that starts with "A", "B,C,D,F,H" are extracted from all those lists that contain "A", and they are sorted by their appearing frequency in descending order.
...
The portion in red color is a repetition of the portion immediately above it in your file data1.txt.

(1) Can your actual file have data like that ?
(2) If yes, then can the "second" set be different ? For example, is it possible to have two lines like so -

Code:
A:list1,list2,list3,list4
...
A:list1,list3,list5

(3) If yes, then can there be more than two sets in data1.txt ? like so -

Code:
A:list1,list2,list3,list4
...
A:list1,list3,list5
...
A:list1,list5,list7

(4) Do you collect a unique set of "lists", for each character on the left, in such a case ?
For example, for A => list1, list2, list3, list4, list5, list7 ?

(5) The character "C" is associated with 3 lists in data1.txt:

Code:
C:list1,list2,list6

And these lists have the following set of characters:

Code:
list1:A,B,C
list2:A,B,C,F,H
...
list6:C
...

So, the distinct set of characters associated with list1, list2 and list6 should be => (A, B, C, F, H)

Your desired output for "C" is like so -

Code:
desired output:
...
C:A,B,F,H

Have you removed "C" from the right-hand-side list, because it is common on either side of the ":" character ?

(6) Is that also the reason you've omitted "G:G" from your desired output ?

Quote:
...
This is the code I used to generate the output:
Code:
#!/bin/awk -f
 
BEGIN { FS=":"; ts1 = "date \"+%s\""; }
NR == FNR { bookLists[$1]=$2; next }    #the first file
{ books[$1]=$2 }                                        #the second file
END {
{ print "There are in total", length(bookLists), "book lists and ", length(books), "books." > "make_data_log.txt" }
count = 0
#bookLists: A:list1,list2
#books: list1:A,B
cmd = "sort -k 3 -nr | awk ' { arr[$2]; if(!b) b=$1 } END { for (i in arr) str=str ? str\",\"i : i; print b, str} '"
for (i in bookLists) {
        #print "========== book " i "=========="
        split(bookLists[i], tmpBls, /,/)
        for (j in tmpBls) {
                split(books[tmpBls[j]], tmpBs, /,/)
                for (k in tmpBs)
                        ++result[tmpBs[k]]      #print i":", tmpBs[k]
                delete tmpBs
        }
        for (l in result) {
                if (i != l) print i, l, result[l] | cmd
                #if (i != l) print i, l, result[l]
                if (++num == 20) break
        }
        close(cmd)              #close the pipe, or this "sort" will be delayed until the awk program ends
        delete result
        delete tmpBls
        num = 0
        if (++count % 100000 == 0)
                print count >> "make_data_log.txt"
}
 
{ ts2 = "date \"+%s\""; print ts2-ts1, "seconds consumed." >> "make_data_log.txt" }
 
}

...
What's the current response time for your actual data "data1.txt" (the one that has more than 30,000 strings delimited by commas) ?

And what is the acceptable response time for the same?

tyler_durden
# 12  
Old 05-22-2010
Quote:
Originally Posted by aigles
Try this awk program which doesn't use the split function :
Code:
awk -v Q="'" -F'[:,]' '
BEGIN {
   cmd = "sort -k3,3nr -k2,2 | awk " Q "{ out=out (NR==1 ? $1 \":\" : \",\") $2 } END { print out }" Q;
}
NR==FNR {
   list = $1;
   all  = "";
   for (i=2; i<=NF; i++) {
      all = all SUBSEP $i ;
      books[list, i-1] = $i;
   }
   books[list, "all"  ] = all SUBSEP;
   books[list, "count"] = NF-1;
   next;
}
{
   book  = $1;
   delete bookCount;
   for (i=2; i<=NF; i++) {
      list = $i;
      if (books[list, "all"] ~ SUBSEP book SUBSEP) {
         for (ib=1; ib<=books[list, "count"]; ib++) {
            bookCount[books[list, ib]]++;
         }
      }
   }
   for (b in bookCount) {
      if (b != book) {
         print book, b, bookCount[b] | cmd;
      }
   }
   close(cmd);
}

' kevin2.dat kevin1.dat

Input file 1 (kevin1.dat) :
Code:
A:list1,list2,list3,list4
B:list1,list2,list3,list4
C:list1,list2,list6
D:list3
F:list2,list4,list5
G:list7
H:list2,list5

Input file 2 (kevin2.dat) :
Code:
list1:A,B,C
list2:A,B,C,F,H
list3:A,B,D
list4:A,B,F
list5:H,F
list6:C
list7:G

Output:
Code:
$ time ./kevin.sh
A:B,C,F,D,H
B:A,C,F,D,H
C:A,B,F,H
D:A,B
F:A,B,H,C
H:F,A,B,C

real    0m1.142s
user    0m0.590s
sys     0m0.580s
$

The problem with that script is that we run a sort command for every book.
The following solution use only one sort command :
Code:
awk -v Q="'" -F'[:,]' '
NR==FNR {
   list = $1;
   all  = "";
   for (i=2; i<=NF; i++) {
      all = all SUBSEP $i ;
      books[list, i-1] = $i;
   }
   books[list, "all"  ] = all SUBSEP;
   books[list, "count"] = NF-1;
   next;
}
{
   book  = $1;
   delete bookCount;
   for (i=2; i<=NF; i++) {
      list = $i;
      if (books[list, "all"] ~ SUBSEP book SUBSEP) {
         for (ib=1; ib<=books[list, "count"]; ib++) {
            bookCount[books[list, ib]]++;
         }
      }
   }
   for (b in bookCount) {
      if (b != book) {
         print book, b, bookCount[b]
      }
   }
   close(cmd);
}

' kevin2.dat kevin1.dat  |
sort -k1,1 -k3,3nr -k2,2 |
awk '
{
   book = $1;
   if (book == prev) {
      out = out "," $2;
   } else {
      if (out) print prev ":" out;
      out = $2;
      prev = book;
   }
}
END { if (out) print prev ":" out; }
'

With the same input files, the out is the same but times are better :
Code:
$ time ./kevin2.sh
A:B,C,F,D,H
B:A,C,F,D,H
C:A,B,F,H
D:A,B
F:A,B,H,C
H:F,A,B,C

real    0m0.419s
user    0m0.152s
sys     0m0.169s
$

Jean-Pierre.

Hi, aigles
Thank you so so much. your script is much faster than mine.
And it helps me a lot, I have learned many things about AWK(oh, it surprises me that AWK can be written this way) from your script.
Thank you!
Last edited by kevintse; 05-22-2010 at 12:02 PM..
# 13  
Old 05-22-2010
It seems to me that both files contain the same information, though in different formats. A simpler solution would be to use a different algorithm, which builds an internal list of book-pairs in one pass using one data file:
Code:
#!/bin/sh

awk -F'[:,]' '
    { for(i=2;i<=NF;i++) for(j=2;j<=NF;j++) if (i!=j) a[$i" "$j]++}
    END { for (k in a) print k" "a[k] }' "$1" \
| sort -k1,1 -k3,3nr -k2,2 \
| awk '{b=$1; if (b!=ob) {if (NR>1) print s; s=$1":"$2; ob=b; next}; s=s","$2} END {print s}'

Test run:
Code:
$ cat data
list1:A,B,C
list2:A,B,C,F,H
list3:A,B,D
list4:A,B,F
list5:H,F
list6:C
list7:G
$ ./books.sh data
A:B,C,F,D,H
B:A,C,F,D,H
C:A,B,F,H
D:A,B
F:A,B,H,C
H:F,A,B,C



A perl solution which is probably faster:
Code:
for ($i=1; $i<=$#F; $i++) {
    for ($j=1; $j<=$#F; $j++) {
        if ($i!=$j) {
            $books{$F[$i]}{$F[$j]}++
        }
    }
}

END {
    for $k ( sort keys %books ) {
        @v = sort { $books{$k}{$b} != $books{$k}{$a}
                    ? $books{$k}{$b} <=> $books{$k}{$a}
                    : $a cmp $b
                  } keys %{ $books{$k} };
        print "$k:" . join (",", @v);
    }
}

Test run, using the same data file as with the sh/awk/sort solution:
Code:
$ perl -lan -F'[:,]' books.pl data
A:B,C,F,D,H
B:A,C,F,D,H
C:A,B,F,H
D:A,B
F:A,B,H,C
H:F,A,B,C

Note: Its been about 10 years since I've written anything more than a one-liner in perl, so perhaps a perl guru can slash that to a couple of lines. Smilie

Regards,
Alister
This User Gave Thanks to alister For This Post:
kevintse
# 14  
Old 05-23-2010
Hi, Alister
I am really grateful for your succinct solutions.
The perl script is faster. But I still need some help from you, I have never learnt perl, and I don't have spare time to learn it for the moment, I want to modify your script to just print the top 20 books associating each book. how?

Thank you!!!
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

awk to split one field and print the last two fields within the split part.

Hello; I have a file consists of 4 columns separated by tab. The problem is the third fields. Some of the them are very long but can be split by the vertical bar "|". Also some of them do not contain the string "UniProt", but I could ignore it at this moment, and sort the file afterwards. Here is... (5 Replies)
Discussion started by: yifangt
5 Replies

2. Shell Programming and Scripting

Perl split function

my @d =split('\|', $_); west|ACH|3|Y|LuV|N||N|| Qt|UWST|57|Y|LSV|Y|Bng|N|KT| It Returns d as 8 for First Line, and 9 as for Second Line . I want to Process Both the Files, How to Handle It. (3 Replies)
Discussion started by: vishwakar
3 Replies

3. Shell Programming and Scripting

PERL split function

Hi... I have a question regarding the split function in PERL. I have a very huge csv file (more than 80 million records). I need to extract a particular position(eg : 50th position) of each line from the csv file. I tried using split function. But I realized split takes a very long time. Also... (1 Reply)
Discussion started by: castle
1 Replies

4. Homework & Coursework Questions

PERL split function

Hi... I have a question regarding the split function in PERL. I have a very huge csv file (more than 80 million records). I need to extract a particular position(eg : 50th position) of each line from the csv file. I tried using split function. But I realized split takes a very long time. Also... (0 Replies)
Discussion started by: castle
0 Replies

5. Homework & Coursework Questions

PERL split function

Hi... I have a question regarding the split function in PERL. I have a very huge csv file (more than 80 million records). I need to extract a particular position(eg : 50th position) of each line from the csv file. I tried using split function. But I realized split takes a very long time. Also... (1 Reply)
Discussion started by: castle
1 Replies

6. Shell Programming and Scripting

Use split function in perl

Hello, if i have file like this: 010000890306932455804 05306977653873 0520080417010520ISMS SMT ZZZZZZZZZZZZZOC30693599000 30971360000 ZZZZZZZZZZZZZZZZZZZZ202011302942311 010000890306946317387 05306977313623 0520080417010520ISMS SMT ZZZZZZZZZZZZZOC306942190000 30971360000... (5 Replies)
Discussion started by: chriss_58
5 Replies

7. Shell Programming and Scripting

awk - split function

Hi, I have some output in the form of: #output: abc123 def567 hij890 ghi324 the above is in one column, stored in the variable x ( and if you wana know about x... x=sprintf(tolower(substr(someArray,1,1)substr(userArray,3,1)substr(userArray,2,1))) when i simply print x (print x) I get... (7 Replies)
Discussion started by: fusionX
7 Replies

8. UNIX for Dummies Questions & Answers

Split a file with no pattern -- Split, Csplit, Awk

I have gone through all the threads in the forum and tested out different things. I am trying to split a 3GB file into multiple files. Some files are even larger than this. For example: split -l 3000000 filename.txt This is very slow and it splits the file with 3 million records in each... (10 Replies)
Discussion started by: madhunk
10 Replies

9. Shell Programming and Scripting

perl split function

$mystring = "name:blk:house::"; print "$mystring\n"; @s_format = split(/:/, $mystring); for ($i=0; $i <= $#s_format; $i++) { print "index is $i,field is $s_format"; print "\n"; } $size = $#s_format + 1; print "total size of array is $size\n"; i am expecting my size to be 5, why is it... (5 Replies)
Discussion started by: new2ss
5 Replies

10. UNIX for Dummies Questions & Answers

split function

Hi all! I am relatively new to UNIX staff, and I have come across a problem: I have a big directory, which contains 100 smaller ones. Each of the 100 contains a file ending in .txt , so there are 100 files ending in .txt I want to split each of the 100 files in smaller ones, which will contain... (4 Replies)
Discussion started by: ktsirig
4 Replies
Login or Register to Ask a Question