8

I have a file containing a list of replacement pairs (about 100 of them) which are used by sed to replace strings in files.

The pairs go like:

old|new
tobereplaced|replacement
(stuffiwant).*(too)|\1\2

and my current code is:

cat replacement_list | while read i
do
    old=$(echo "$i" | awk -F'|' '{print $1}')    #due to the need for extended regex
    new=$(echo "$i" | awk -F'|' '{print $2}')
    sed -r "s/`echo "$old"`/`echo "$new"`/g" -i file
done

I cannot help but think that there is a more optimal way of performing the replacements. I tried turning the loop around to run through lines of the file first but that turned out to be much more expensive.

Are there any other ways of speeding up this script?

EDIT

Thanks for all the quick responses. Let me try out the various suggestions before choosing an answer.

One thing to clear up: I also need subexpressions/groups functionality. For example, one replacement I might need is:

([0-9])U|\10  #the extra brackets and escapes were required for my original code

Some details on the improvements (to be updated):

  • Method: processing time
  • Original script: 0.85s
  • cut instead of awk: 0.71s
  • anubhava's method: 0.18s
  • chthonicdaemon's method: 0.01s
4
  • This question has had answers here. Yes, you are looking for speed, but please, why two questions.
    – martin
    Aug 29, 2014 at 8:22
  • 1
    To be honest, that question doesn't really bring up the element of speed nor that of subexpressions. The answers that have given here have been much more helpful.
    – Reuben L.
    Aug 29, 2014 at 14:24
  • 1
    Ok, then clarify your question with respect to the subexpressions by placing them in the data and provide input and desired output, that will greatly improve your question and clearly distinguish it from the other ones.
    – martin
    Aug 29, 2014 at 14:36
  • +1 for running all the benchmarks. I learnt few tricks myself.
    – anubhava
    Aug 29, 2014 at 15:18

9 Answers 9

12

You can use sed to produce correctly -formatted sed input:

sed -e 's/^/s|/; s/$/|g/' replacement_list | sed -r -f - file
6
  • 1
    hmmmm sed: -e expression #1, char 17: unknown option to 's'. character 17 happens to be the | delimiter in my replacements file
    – Reuben L.
    Aug 29, 2014 at 14:45
  • having said that, I get the concept now and am trying to test it out.
    – Reuben L.
    Aug 29, 2014 at 14:58
  • 2
    the issue is with the comma (typo?). but anyway, absolutely blistering speed and quite parsimonious as well! thanks!
    – Reuben L.
    Aug 29, 2014 at 15:06
  • Sorry about that - I was editing the expression and didn't test the last iteration. Glad you figured it out. Aug 31, 2014 at 5:43
  • 1
    @shrx You can use a FIFO. Change file at the end to <( whatever your command to generate input ) Nov 27, 2014 at 15:50
4

I recently benchmarked various string replacement methods, among them a custom program, sed -e, perl -lnpe and an probably not that widely known MySQL command line utility, replace. replace being optimized for string replacements was almost an order of magnitude faster than sed. The results looked something like this (slowest first):

custom program > sed > LANG=C sed > perl > LANG=C perl > replace

If you want performance, use replace. To have it available on your system, you'll need to install some MySQL distribution, though.

From replace.c:

Replace strings in textfile

This program replaces strings in files or from stdin to stdout. It accepts a list of from-string/to-string pairs and replaces each occurrence of a from-string with the corresponding to-string. The first occurrence of a found string is matched. If there is more than one possibility for the string to replace, longer matches are preferred before shorter matches.

...

The programs make a DFA-state-machine of the strings and the speed isn't dependent on the count of replace-strings (only of the number of replaces). A line is assumed ending with \n or \0. There are no limit exept memory on length of strings.


More on sed. You can utilize multiple cores with sed, by splitting your replacements into #cpus groups and then pipe them through sed commands, something like this:

$ sed -e 's/A/B/g; ...' file.txt | \
  sed -e 's/B/C/g; ...' | \
  sed -e 's/C/D/g; ...' | \
  sed -e 's/D/E/g; ...' > out

Also, if you use sed or perl and your system has an UTF-8 setup, then it also boosts performance to place a LANG=C in front of the commands:

$ LANG=C sed ...
3
  • On that topic, does sed run faster with N number of -e or N number of singular sed commands? When N > 100.
    – Reuben L.
    Aug 29, 2014 at 7:03
  • IIRC, it was a bit faster to use a N of replacements in a single sed command than N number sed commands. I remember being a bit surprised, that running a few hundred processes in parallel did not degrade performance by too much.
    – miku
    Aug 29, 2014 at 7:12
  • 1
    mysql replace can only replace fixed strings. sd is a similar tool in rust
    – milahu
    Jan 27, 2022 at 7:52
1

You can cut down unnecessary awk invocations and use BASH to break name-value pairs:

while IFS='|' read -r old new; do
   # echo "$old :: $new"
   sed -i "s~$old~$new~g" file
done < replacement_list

IFS='|' will give enable read to populate name-value in 2 different shell variables old and new.

This is assuming ~ is not present in your name-value pairs. If that is not the case then feel free to use an alternate sed delimiter.

7
  • 1
    This seems to be really speedy, but I am having issues with subexpressions. Instead of returning the values stored in groups, I am getting them literally (e.g. \1 \2, etc...).
    – Reuben L.
    Aug 29, 2014 at 14:10
  • Can yo tell me some example lines with those subexpressions so that I can reproduce it and suggest you a fix.
    – anubhava
    Aug 29, 2014 at 14:15
  • Thanks for the reply, one example is ([0-9])U|\\10.
    – Reuben L.
    Aug 29, 2014 at 14:16
  • 1
    Thanks for the answer and the extra help! Sadly, I will have to give the vote to chthonicdaemon's answer for being faster and slightly more parsimonious.
    – Reuben L.
    Aug 29, 2014 at 15:14
  • 1
    No doubts about the merit of chthonicdaemon's answer. I have myself upvoted him for that innovative trick.
    – anubhava
    Aug 29, 2014 at 15:16
1

Here is what I would try:

  1. store your sed search-replace pair in a Bash array like ;
  2. build your sed command based on this array using parameter expansion
  3. run command.
patterns=(
  old new
  tobereplaced replacement
)
pattern_count=${#patterns[*]} # number of pattern
sedArgs=() # will hold the list of sed arguments

for (( i=0 ; i<$pattern_count ; i=i+2 )); do # don't need to loop on the replacement…
  search=${patterns[i]};
  replace=${patterns[i+1]}; # … here we got the replacement part
  sedArgs+=" -e s/$search/$replace/g"
done
sed ${sedArgs[@]} file

This result in this command:

sed -e s/old/new/g -e s/tobereplaced/replacement/g file

0

You can try this.

pattern=''
cat replacement_list | while read i
do
    old=$(echo "$i" | awk -F'|' '{print $1}')    #due to the need for extended regex
    new=$(echo "$i" | awk -F'|' '{print $2}')
    pattern=${pattern}"s/${old}/${new}/g;"
done
sed -r ${pattern} -i file

This will run the sed command only once on the file with all the replacements. You may also want to replace awk with cut. cut may be more optimized then awk, though I am not sure about that.

old=`echo $i | cut -d"|" -f1`
new=`echo $i | cut -d"|" -f2`
3
  • 0.3s improvement. Not bad.
    – Reuben L.
    Aug 29, 2014 at 7:11
  • I was mistaken, the cut did speed up the process but the pattern bit didn't actually work. For some reason, the first character of the filename fed to sed was deleted. Trying to figure out why.
    – Reuben L.
    Aug 29, 2014 at 13:48
  • The useless use of cat and the multiple quoting errors do not bode well for this answer. Proceed with caution.
    – tripleee
    Mar 25, 2019 at 11:42
0

You might want to do the whole thing in awk:

awk -F\| 'NR==FNR{old[++n]=$1;new[n]=$2;next}{for(i=1;i<=n;++i)gsub(old[i],new[i])}1' replacement_list file

Build up a list of old and new words from the first file. The next ensures that the rest of the script isn't run on the first file. For the second file, loop through the list of replacements and perform them each one by one. The 1 at the end means that the line is printed.

2
  • One issue for me is that I use groups (i.e. \1) in the sed replacements.
    – Reuben L.
    Aug 29, 2014 at 14:02
  • Are you using gawk? If so, this could be adapted to use gensub
    – Tom Fenech
    Aug 29, 2014 at 14:10
0
{ cat replacement_list;echo "-End-"; cat YourFile; } | sed -n '1,/-End-/ s/$/³/;1h;1!H;$ {g
t again
:again
   /^-End-³\n/ {s///;b done
      }
   s/^\([^|]*\)|\([^³]*\)³\(\n\)\(.*\)\1/\1|\2³\3\4\2/
   t again
   s/^[^³]*³\n//
   t again
:done
  p
  }'

More for fun to code via sed. Try maybe for a time perfomance because this start only 1 sed that is recursif.

for posix sed (so --posix with GNU sed)

explaination

  • copy replacement list in front of file content with a delimiter (for line with ³ and for list with -End-) for an easier sed handling (hard to use \n in class character in posix sed.
  • place all line in buffer (add the delimiter of line for replacement list and -End- before)
  • if this is -End-³, remove the line and go to final print
  • replace each first pattern (group 1) found in text by second patttern (group 2)
  • if found, restart (t again)
  • remove first line
  • restart process (t again). T is needed because b does not reset the test and next t is always true.
0

Thanks to @miku above;

I have a 100MB file with a list of 80k replacement-strings.

I tried various combinations of sed's sequentially or parallel, but didn't see throughputs getting shorter than about a 20-hour runtime.

Instead I put my list into a sequence of scripts like "cat in | replace aold anew bold bnew cold cnew ... > out ; rm in ; mv out in".

I randomly picked 1000 replacements per file, so it all went like this:

# first, split my replace-list into manageable chunks (89 files in this case)
split -a 4 -l 1000 80kReplacePairs rep_

# next, make a 'replace' script out of each chunk
for F in rep_* ; do \
    echo "create and make executable a scriptfile" ; \
    echo '#!/bin/sh' > run_$F.sh ; chmod +x run_$F.sh ; \
    echo "for each chunk-file line, strip line-ends," ; \
    echo "then with sed, turn '{long list}' into 'cat in | {long list}' > out" ; \
    cat $F | tr '\n' ' ' | sed 's/^/cat in | replace /;s/$/ > out/' >> run_$F.sh ;
    echo "and append commands to switch in and out files, for next script" ; \
    echo -e " && \\\\ \nrm in && mv out in\n" >> run_$F.sh ; \
done

# put all the replace-scripts in sequence into a main script
ls ./run_rep_aa* > allrun.sh

# make it executable
chmod +x allrun.sh 

# run it
nohup ./allrun.sh &

.. which ran in under 5 mins, a lot less than 20 hours !

Looking back, I could have used more pairs per script, by finding how many lines would make up the limit.

xargs --show-limits </dev/null 2>&1 | grep --color=always "actually use:"
    Maximum length of command we could actually use: 2090490

So just under 2MB; how many pairs would that be for my script ?

head -c 2090490 80kReplacePairs | wc -l

    76923

So it seems I could have used 2 * 40000-line chunks

0

to expand on chthonicdaemon's solution

live demo

#! /bin/sh

# build regex from text file

REGEX_FILE=some-patch.regex.diff

# test
# set these with "export key=val"
SOME_VAR_NAME=hello
ANOTHER_VAR_NAME=world


escape_b() {
  echo "$1" | sed 's,/,\\/,g'
}


regex="$(
  (echo; cat "$REGEX_FILE"; echo) \
  | perl -p -0 -e '
    s/\n#[^\n]*/\n/g;
    s/\(\(SOME_VAR_NAME\)\)/'"$(escape_b "$SOME_VAR_NAME")"'/g;
    s/\(\(ANOTHER_VAR_NAME\)\)/'"$(escape_b "$ANOTHER_VAR_NAME")"'/g;
    s/([^\n])\//\1\\\//g;
    s/\n-([^\n]+)\n\+([^\n]*)(?:\n\/([^\n]+))?\n/s\/\1\/\2\/\3;\n/g;
  '
)"

echo "regex:"; echo "$regex" # debug

exec perl -00 -p -i -e "$regex" "$@"

prefixing lines with -+/ allows empty "plus" values, and protects leading whitespace from buggy text editors

sample input: some-patch.regex.diff

# file format is similar to diff/patch
# this is a comment

# replace all "a/a" with "b/b"
-a/a
+b/b
/g

-a1|a2
+b1|b2
/sg
# this is another comment

-(a1).*(a2)
+b\1b\2b

-a\na\na
+b

-a1-((SOME_VAR_NAME))-a2
+b1-((ANOTHER_VAR_NAME))-b2

sample output

s/a\/a/b\/b/g;

s/a1|a2/b1|b2/;;

s/(a1).*(a2)/b\1b\2b/;

s/a\na\na/b/;

s/a1-hello-a2/b1-world-b2/;

this regex format is compatible with sed and perl

since miku mentioned mysql replace: replacing fixed strings with regex is non-trivial, since you must escape all regex chars, but you also must handle backslash escapes ...

naive escaper:

echo '\(\n' | perl -p -e 's/([.+*?()\[\]])/\\\1/g' 
\\(\n

Your Answer

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

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