3

I have a big text file(with 5m lines) in this format(4 columns, separated by ;):

string1; string2; string3; userId

The first 3 strings (SHA1s) form a single ID, called appId (so it can be simlified like this: appId; userId). The second column (string2, or second part of appId) itself may be composed of some parts separated by comma ,. The file is sorted.

I would like to have the list of users of each app in front of it, like this:

input file:

app1, user1
app1, user2
app1, user3
app2, user1

output file:

app1: user1, user2, user3
app2: user1

part of "real" input file:

44a934ca4052b34e70f9cb03f3399c6f065becd0;bf038823f9633d25034220b9f10b68dd8c16d867;309;8ead5b3e0af5b948a6b09916bd271f18fe2678aa
44a934ca4052b34e70f9cb03f3399c6f065becd0;bf038823f9633d25034220b9f10b68dd8c16d867;309;a21245497cd0520818f8b14d6e405040f2fa8bc0
5c3eb56d91a77d6ee5217009732ff421e378f298;200000000000000001000000200000,6fd299187a5c347fe7eaab516aca72295faac2ad,e25ba62bbd53a72beb39619f309a06386dd381d035de372c85d70176c339d6f4;16;337556fc485cd094684a72ed01536030bdfae5bb
5c3eb56d91a77d6ee5217009732ff421e378f298;200000000000000001000000200000,6fd299187a5c347fe7eaab516aca72295faac2ad,e25ba62bbd53a72beb39619f309a06386dd381d035de372c85d70176c339d6f4;16;382f3aaa9a0347d3af9b35642d09421f9221ef7d
5c3eb56d91a77d6ee5217009732ff421e378f298;200000000000000001000000200000,6fd299187a5c347fe7eaab516aca72295faac2ad,e25ba62bbd53a72beb39619f309a06386dd381d035de372c85d70176c339d6f4;16;396529e08c6f8a98a327ee28c38baaf5e7846d14

The "real" output file should look like this:

44a934ca4052b34e70f9cb03f3399c6f065becd0;bf038823f9633d25034220b9f10b68dd8c16d867;309:8ead5b3e0af5b948a6b09916bd271f18fe2678aa, a21245497cd0520818f8b14d6e405040f2fa8bc0
5c3eb56d91a77d6ee5217009732ff421e378f298;200000000000000001000000200000,6fd299187a5c347fe7eaab516aca72295faac2ad,e25ba62bbd53a72beb39619f309a06386dd381d035de372c85d70176c339d6f4;16:337556fc485cd094684a72ed01536030bdfae5bb, 382f3aaa9a0347d3af9b35642d09421f9221ef7d, 396529e08c6f8a98a327ee28c38baaf5e7846d14

How can I do this?


Edit: Also, there can be thousands of users per app, so how long can a line be? Is there any limitation for line length?

1
  • I haven't tried anything, because I'm new to awk. I saw this: theunixschool.com/2012/06/… (item number 10) but the answer has limited the number of items.
    – Javad
    Jul 22, 2014 at 11:50

4 Answers 4

3

In Perl

perl -F';' -lane 'push @{$h{join ";",@F[0..2]}},$F[3];
                  END{
                    for(sort keys %h){
                        print "$_: ". join ",",@{$h{$_}};
                    }
                  }' your_file

You should be able to do something similar in awk using associative arrays, but I'm not really that well-versed in awk so I can't contribute actual code.

Explanation

Here's an expanded version of the above code that uses as little "magic" as possible:

open($FH,"<","your_file");
while($line=<$FH>){ # For each line in the file (accomplished by -n)
    chomp $line; # Remove the newline at the end (done by -l)
    # The ; is set by -F and storing the split in @F done by -a
    @F = split /;/,$line # Split the line into fields on ;
    $app_id = join ";",@F[0..2]; # AppID is the first 3 fields
    push @{$h{$app_id}},$F[3]; # The 4th field is added onto the hash
} # The whole file has been read at this point.
foreach $key (sort keys %h){ # Sort the hash by AppID
     print "$key: " . join ",",@{h{$key}}."\n"; # Print the array values
     # The newline ("\n") added at the end is also done by -l
}

Now there is only the push statement left to explain in more detail:

  • push is usually used to add elements to an array variable. For example:

    push @a,$x
    

    appends the contents of the variable $x to the array @a.

  • The loop that reads the file line-by-line is filling in a hash table (%h). The keys to the hash are the AppIDs and the value that corresponds to each key is an array containing all the user IDs associated with that AppID. This is an anonymous array (it has no name); in Perl this is implemented as an array reference (somewhat similar to C pointers). And since the value of %h that corresponds to the AppID $app_id is denoted by $h{$app_id}, tacking on the Perl array sigial (@) treats the hash value as an array (de-references the array reference) and pushes the current user ID onto it.

  • An alternative that may feel less "Perlish" to you would be to concatenate the 4th field to the current value:

    while(...) { ... $h{$app_id} = $h{$app_id} . ",$F[3]" }
    foreach $key (sort keys %h) { print "$_: $h{$_}" }
    

    where the . in Perl is the string concatenation operator.

Note that in the explanation code, I have omitted the perl -e '...' wrapper so the syntax highlighting can get to the code and make it more readable.

20
  • Thanks Joseph! How can I run this script in bash? I pasted it there, modified the file name, and pressed enter, but it seems to be in edit mode, not runnng mode
    – Javad
    Jul 22, 2014 at 11:58
  • This can make a crash since when the input is a big file
    – cuonglm
    Jul 22, 2014 at 11:59
  • 1
    @Metallica I think comments can be edited only during the 5 minutes following their creation. In such cases, you can delete it and write it again, though.
    – Qeole
    Jul 22, 2014 at 13:05
  • 1
    @Metallica Code updated and tested. Sorry for that. Perl scripts are not generally faster than GNU tools. It all depends on the algorithm. I suspect that regex matching and pattern space manipulation is what's slowing down the sed answer. On the other hand, the Perl script above uses hash tables which are known for their fast access time.
    – Joseph R.
    Jul 22, 2014 at 13:49
  • 1
    @Qeole Not necessarily. I believe it would take considerable C programming experience to create a text processing tool that outperforms venerable tools like awk and perl. Even if that's not the case, I still think the design effort would outweigh the performance boost.
    – Joseph R.
    Jul 22, 2014 at 14:47
2

Since you state that the file is sorted, shouldn't it be possible to use a simple loop with memory for only the preceding appId string? Kind of like @Qeole's sed approach but avoiding the overhead of regular expresssions by using the shell's delimited read function plus string comparison:

#!/bin/bash

appId=""

while IFS=\; read -r s1 s2 s3 userId; do
  if [ "$s1;$s2;$s3" == "$appId" ]; then
    printf ', %s' "$userId"
  else
    appId="$s1;$s2;$s3"
    printf '\n%s:%s' "$appId" "$userId"
  fi
done < yourfile
printf '\n'

NOTE: this prints an additional newline at the start of output, but that could be prevented with minimal additional complexity. Bash should be fairly quick for this kind of thing but if not, you could re-implement in pretty much any similar scripting language.

2

With sed:

sed 's/;/:\t/3;H;1h;x                                                                                        
s/^\(\([^:]*\):.*\)\n\2/\1/                                                                                      
/\n/P;//g;h;$!d' <input |
tr : \\n

That prints:

44a934ca4052b34e70f9cb03f3399c6f065becd0;bf038823f9633d25034220b9f10b68dd8c16d867;309
        8ead5b3e0af5b948a6b09916bd271f18fe2678aa
        a21245497cd0520818f8b14d6e405040f2fa8bc0
5c3eb56d91a77d6ee5217009732ff421e378f298;200000000000000001000000200000,6fd299187a5c347fe7eaab516aca72295faac2ad,e25ba62bbd53a72beb39619f309a06386dd381d035de372c85d70176c339d6f4;16
        337556fc485cd094684a72ed01536030bdfae5bb
        382f3aaa9a0347d3af9b35642d09421f9221ef7d
        396529e08c6f8a98a327ee28c38baaf5e7846d14

You can drop tr to keep the groups on the same line. The ids will be :colon delimited in that case. You might also need to replace the \t escape in the first line with a literal <tab> character - or you can feel free to remove the \tabs completely - they only serve to make the output more readable (in my opinion) and are not vital to the function of the regex in any way.

2
  • Thank you for your answer. I think the suggested hash table approach (in Perl) is the fastest one, since the time complexity of a hash table lookup is O(1).
    – Javad
    Jan 11, 2015 at 6:54
  • @Metallica - I would be interested in seeing that tested. The hash table itself beats the comparison method here almost definitely - but even that is not very complex, and the script here is very simple. sed usually beats perl in performance by a significant margin - but I am rather dubious here.
    – mikeserv
    Jan 11, 2015 at 7:03
1

A sed answer:

sed ': l;N;s/^\([^;]\+;[^;]\+;[^;:]\+\)[;:] *\(.*\)\n\1;\(.*\)/\1: \2, \3/;tl;P;D' input_file.txt

File is read only once, so performance shouldn't be too bad, but I can't tell you more than that.

With details:

sed ': l;        # Label l

     N;          # Add next line of input to pattern space

     s/^\([^;]\+;[^;]\+;[^;:]\+\)[;:] *\(.*\)\n\1;\(.*\)/\1: \2, \3/;
                 # If two lines in pattern space start with same AppID, then
                 # take user ID and append it to first line, then delete second line

         tl;     # If previous substitution succeeded, i.e. we scanned two lines with 
                 # same AppID, then loop to label l. Else go on…

     P;          # Print first line from pattern space (here there should be two lines
                 # in pattern space, starting with a different AppID)

     D;          # Delete first line of pattern space; start script again with
                 # remaining text in pattern space, or next input line if pattern
                 # space is empty
    ' input_file.txt

(But I've no idea about potential limitations for line length, sorry.)

6
  • This seems to assume that repeated AppIDs will be on consecutive lines. The OP didn't specify this.
    – Joseph R.
    Jul 22, 2014 at 12:38
  • 1
    @JosephR. Indeed I assumed that. But OP does mention that “The file is sorted.” Isn't that enough?
    – Qeole
    Jul 22, 2014 at 12:39
  • Thanks @Qeole ! This worked, but it's slow, is there any other faster solutions? (I piped the output to a new file). I need it to finish the operation in couples of minutes, at most.
    – Javad
    Jul 22, 2014 at 12:58
  • 1
    Instead of redirecting output, you can also use sed -i option (to edit your file in place. Maybe backup your file first). I don't know if you'll gain anything in performance, though. I can't think of anything faster with sed, maybe try something with awk, perl or python
    – Qeole
    Jul 22, 2014 at 13:03
  • It took ~8 minutes to work on a 60,000-line subset of my file! I need a much faster solution!
    – Javad
    Jul 22, 2014 at 13:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .