# Perform multiple replacements on a string in a single pass

**URL:** <https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247>\
**Category:** Performance\
**Tags:** strings, regex\
**Created:** [July 17, 2020, 4:22pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247 "2020-07-17T16:22:12Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![nstgc](https://avatars.discourse-cdn.com/v4/letter/n/e0b2c6/32.png) [@nstgc](https://discourse.julialang.org/u/nstgc)\
**Post date:** [July 17, 2020, 4:22pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/1 "2020-07-17T16:22:12Z")

</div>

I have a couple of scripts which perform multiple replacements on the same string. It seems as though this can be sped up by searching for all potential matches. For example, something like

```julia
julia>replace("123",[r"1" => s"a",r"2" => s"b"])
"ab3"

```

To be clear, that isn’t real output. Or maybe something with an `or` logic. Note that putting a `.` after `replace` outputs an array with each individual substitution. ie

```julia
julia> replace.("123",[r"1" => s"a",r"2" => s"b"])
2-element Array{String,1}:
 "a23"
 "1b3"

```

which is not what I want.

Currently what I’ve been doing is

```julia
str = read(file,String)
for sub in [list of pairs]
    str = replace(str,sub)
end

```

which loops over all the substitution pairs that I need performed. But looping seems inefficient when it seems like it should be possible to perform all subs as you go through the file.

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [July 17, 2020, 5:12pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/2 "2020-07-17T17:12:26Z")

</div>

Don’t think this exists because it won’t generalize. What happens when two substitutions collide?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 17, 2020, 5:22pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/3 "2020-07-17T17:22:51Z")

</div>

> [@nstgc](#):
>
> `replace("123",[r"1" => s"a",r"2" => s"b"])`

To do this kind of thing in a single pass, you could do something like:

```julia
julia> subs = Dict("1" => "a", "2" => "b");

julia> replace("123", r"1|2" => s -> subs[s])
"ab3"

```

```julia

```

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [July 17, 2020, 5:39pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/4 "2020-07-17T17:39:28Z")

</div>

What I would expect is that the first substitution that matches is used, or an error is throw. Seems intuitive to me.

---

<div class="post-metadata">

**Author:** ![nstgc](https://avatars.discourse-cdn.com/v4/letter/n/e0b2c6/32.png) [@nstgc](https://discourse.julialang.org/u/nstgc)\
**Post date:** [July 17, 2020, 5:48pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/5 "2020-07-17T17:48:52Z")

</div>

> [@tbeason](#):
>
> Don’t think this exists because it won’t generalize. What happens when two substitutions collide?

First or last takes precedence?

> [@stevengj](#):
>
> To do this kind of thing in a single pass, you could do something like:
> 
> ```julia
> julia> subs = Dict("1" => "a", "2" => "b");
> 
> julia> replace("123", r"1|2" => s -> subs[s])
> "ab3"
> 
> ```

That certainly looks a lot nicer, however in my test it’s much slower.

```julia
julia> str = read("file",String)
julia> function test(str)
       subbed = str
       for rs in [
       "e" => "1"
       "t" => "2"
       ]
       subbed = replace(subbed,rs)
       end
       end

julia> function test2(str)
       subs = Dict("e" =>"1", "t" => "2")
       subbed = replace(str, r"e|t" => s -> subs[s])
       end
julia> @time test2(str);
  0.004076 seconds (68.29 k allocations: 2.935 MiB)
julia> @time test(str);
  0.002202 seconds (13 allocations: 319.844 KiB)

```

The test file being used is about 136kB.

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [July 17, 2020, 5:55pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/6 "2020-07-17T17:55:47Z")

</div>

What about if you start substituting your own substitutions though?

eg

```julia
replace("123",[r"1" => s"a", r"a2" => s"12"])

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 17, 2020, 6:02pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/7 "2020-07-17T18:02:02Z")

</div>

Yes, regular expressions allocate a bunch of temporary objects on each match to represent matches and substrings (which is why it is showing so many more allocations for `test2`), but the advantage of a single regex pass should increase if you have more and longer strings.

(Conversely, if you are really only doing single-character replacements, it will probably be more efficient to use a single `map` call.)

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [July 17, 2020, 6:10pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/8 "2020-07-17T18:10:12Z")

</div>

One thing I always expect from replacement methods is that it acts on the original string, and not in a partially changed string. The moment a replacement happens the next character the algorithm look at must be the first character _after_ the replacement (i.e., a character from the original string). I think this behavior is common to all replacement methods I have used in my life.

---

<div class="post-metadata">

**Author:** ![nstgc](https://avatars.discourse-cdn.com/v4/letter/n/e0b2c6/32.png) [@nstgc](https://discourse.julialang.org/u/nstgc)\
**Post date:** [July 17, 2020, 6:10pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/9 "2020-07-17T18:10:33Z")

</div>

> [@tbeason](#):
>
> `replace("123",[r"1" => s"a", r"a2" => s"12"])`

That returns an error.

@stevengj

Some of the regex expressions are convoluted and exceed 80 characters and I’m matching things ranging from single characters to about ten and I’m subbing them with strings ranging from 5 to 20 characters. I’m not sure if that is the sort of range you’re talking about, but I’ll see how it works in my main problem and report back.

Thanks for the clarification.

Also, if I may, where might I go to unravel what your suggestion actually does? I tried `@less` but that just took me to the definition of `replace`. This is a bit beyond me and I’d like to use this as a learning experience as well as a practical answer if possible.

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [July 17, 2020, 6:15pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/10 "2020-07-17T18:15:03Z")

</div>

I don’t think that is necessarily correct (starting the second replacement from the character following the spot where the first took place). That would imply that

```julia
replace("123",[r"2" => s"b", r"1" => s"a"])

```

would only do the first sub and not the second.

Anyway, perhaps maybe there are ways to generalize this and I just don’t see it.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 17, 2020, 6:23pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/11 "2020-07-17T18:23:09Z")

</div>

> [@nstgc](#):
>
> Also, if I may, where might I go to unravel what your suggestion actually does?

Which parts don’t you understand?

---

<div class="post-metadata">

**Author:** ![nstgc](https://avatars.discourse-cdn.com/v4/letter/n/e0b2c6/32.png) [@nstgc](https://discourse.julialang.org/u/nstgc)\
**Post date:** [July 17, 2020, 6:29pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/12 "2020-07-17T18:29:34Z")

</div>

I’m not understanding what is going on behind the scene, so-to-speak.

Or at least I’m not certain. I think I could translate that to psudo-code, but the internal workings overall confuse me a bit.

It seems like `replace` starts by searching through the file until it comes upon a match in the regex. Then it performs a look up in the dictionary and uses that before moving on.

My question, I guess is, what’s going on with the anonymous function. How is the function getting it’s input? What is telling the function “we stopped at ‘e’ so look up the appropriate substitution”? Yes, that is my problem. I don’t see how the matched expression is being passed to the function. Or at least that’s one of them.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 17, 2020, 6:32pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/13 "2020-07-17T18:32:07Z")

</div>

> [@nstgc](#):
>
> I don’t see how the matched expression is being passed to the function. Or at least that’s one of them.

Julia calls a regular-expression library (PCRE) that returns each time it encounters a match. Given information about the match (its locations in the string), Julia passes a corresponding `SubString` (a type of string) argument containing the matched substring to your anonymous function, which computes the substitution string. Then Julia calls PCRE to find the next match, etcetera.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [July 17, 2020, 7:41pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/14 "2020-07-17T19:41:22Z")

</div>

No. You understood me wrong.

The original string is scanned from the first character to the last character. The first regex in the array that matches the current character (until the end of the match) is applied. After this the algorithm keep scanning the original string from the next character that was not replaced by this last match, but it continues to check for matchs starting from the first element of the regex array to the last element of the regex array. This is, for any give character the match-checking always happen in order, and if a match is found the match-checking is interrupted, the replacement is made, the next character to look is the first after the replacement, _and the first match to check is again the first match of the regex array not the index in which it stopped last time_.

Consequently, both replacements would happen in your example. For the first character the first match does not trigger but the second does. For the second character of the original string the first match triggers, _because all matches are always checked, and they are checked in the order given_.

---

<div class="post-metadata">

**Author:** ![bernhard](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bernhard/32/2619_2.png) [@bernhard](https://discourse.julialang.org/u/bernhard)\
**Post date:** [July 17, 2020, 7:45pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/15 "2020-07-17T19:45:12Z")

</div>

I actually was hoping/searching for such a function numerous times.

The reason is probably at least twofold  
A) I do not know much about regex  
B) When developing code, I often clean/parse/amend strings in a stepwise manner (ie I may want to see the intermediate results on-screen (for selected elements).

Usually I don’t even have a for loop but simply a few lines with replace calls.  
I guess that works just fine, but I also wondered why the function does not allow to submit multiple pairs

---

<div class="post-metadata">

**Author:** ![DouglasLivingstone](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/douglaslivingstone/32/29025_2.png) [@DouglasLivingstone](https://discourse.julialang.org/u/DouglasLivingstone)\
**Post date:** [January 17, 2022, 7:57am UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/16 "2022-01-17T07:57:53Z")

</div>

As of Julia 1.7, multiple replacements are now supported: [Base.replace](https://docs.julialang.org/en/v1/base/strings/#Base.replace-Tuple%7BAbstractString,%20Vararg%7BPair%7D%7D)

For example:

```julia

julia> replace("abcabc", "a" => "b", "b" => "c", r".+" => "a")
"bca"

```

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [January 17, 2022, 9:11am UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/17 "2022-01-17T09:11:26Z")

</div>

Perfect, this is exactly the behaviour that I argued in favor in this thread.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [January 17, 2022, 9:41am UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/18 "2022-01-17T09:41:29Z")

</div>

> [@DouglasLivingstone](#):
>
> `r".+"`

For regex noobs, could you explain what this does in the context of the example? Thank you.

---

<div class="post-metadata">

**Author:** ![DouglasLivingstone](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/douglaslivingstone/32/29025_2.png) [@DouglasLivingstone](https://discourse.julialang.org/u/DouglasLivingstone)\
**Post date:** [January 18, 2022, 1:56pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/19 "2022-01-18T13:56:02Z")

</div>

Absolutely, can do. First off, the `r` prefix means that the string literal will be parsed with the [@r\_str](https://docs.julialang.org/en/v1/base/strings/#Base.@r_str) macro which will convert the string into a [Regex](https://docs.julialang.org/en/v1/base/strings/#Base.Regex), so the regular expression itself is just `.+`. The dot matches [any character](https://www.regular-expressions.info/dot.html), and the plus is a [repetition operator](https://www.regular-expressions.info/repeat.html) meaning “repeat one or more times,” so overall this Regex means “match any character one or more times”.

It looks like they picked this example in the docs to show that all of the replacements are happening together. If this example was the same as repeated calls to the `replace` function, then this final replacement would just replace any string with one or more characters with a single `"a"`, but as you can see, the actual output starts with `"bc"` instead.

Overall, the replacements look like this:

The first character of the string is compared with the first character of the first pattern, in this case there’s a match, and that happens to be the whole of the first pattern, so `"b"` is appended to the output:

```julia
input: abcabc
        ^
output: b

```

Next, the second character is compared against the first character of the first pattern. This isn’t a match, so the second character is compared against the first character of the second pattern. This is a match, so that character is replaced:

```julia
input: abcabc
         ^
output: bc

```

Finally, the third character doesn’t match the first or second pattern, but the Regex will match any character, so it does so, matching the whole rest of the string:

```julia
input: abcabc
          ^^^^
output: bca

```

Since the Regex has already matched up until the end of the string, the first and second patterns never get a chance to match the second `"a"` or `"b"`, so that’s the end. An improvement to this example might be to include some characters in the source string which are _not_ replaced.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [January 18, 2022, 2:13pm UTC](https://discourse.julialang.org/t/perform-multiple-replacements-on-a-string-in-a-single-pass/43247/20 "2022-01-18T14:13:17Z")

</div>

@DouglasLivingstone, thanks for the brilliant and clear explanation. Really appreciated.