What is the optimal way to perform 5000 unique string replace functions in terms of performance?

Question

Restructuring some code, and the way I built it up over time has portions that look something like this:

s.replace("ABW"," Aruba ");
s.replace("AFG"," Afghanistan ");
s.replace("AGO"," Angola ");
s.replace("AIA"," Anguilla ");
s.replace("ALA"," Åland Islands ");
s.replace("ALB"," Albania ");
s.replace("AND"," Andorra ");
s.replace("ARE"," United Arab Emirates ");
s.replace("ARG"," Argentina ");
s.replace("ARM"," Armenia ");
s.replace("ASM"," American Samoa ");
s.replace("ATA"," Antarctica ");
s.replace("ATF"," French Southern Territories ");
s.replace("ATG"," Antigua and Barbuda ");
s.replace("AUS"," Australia ");
s.replace("AUT"," Austria ");
s.replace("AZE"," Azerbaijan ");
s.replace("BDI"," Burundi ");
s.replace("BEL"," Belgium ");
s.replace("BEN"," Benin ");
s.replace("BES"," Bonaire, Sint Eustatius and Saba ");
s.replace("BFA"," Burkina Faso ");
s.replace("BGD"," Bangladesh ");
s.replace("BGR"," Bulgaria ");
s.replace("BHR"," Bahrain ");
s.replace("BHS"," Bahamas ");
s.replace("BIH"," Bosnia and Herzegovina ");
s.replace("BLM"," Saint Barthélemy ");
s.replace("BLR"," Belarus ");
s.replace("BLZ"," Belize ");
s.replace("BMU"," Bermuda ");
s.replace("BOL"," Plurinational State of Bolivia, ");
s.replace("BRA"," Brazil ");
s.replace("BRB"," Barbados ");
s.replace("BRN"," Brunei Darussalam ");
s.replace("BTN"," Bhutan ");
s.replace("BVT"," Bouvet Island ");
s.replace("BWA"," Botswana ");
s.replace("CAF"," Central African Republic ");
s.replace("CAN"," Canada ");
s.replace("CCK"," Cocos (Keeling) Islands ");
s.replace("CHE"," Switzerland ");
s.replace("CHL"," Chile ");
s.replace("CHN"," China ");
s.replace("CIV"," Côte d'Ivoire ");
s.replace("CMR"," Cameroon ");
s.replace("COD","  the Democratic Republic of the Congo ");
s.replace("COG"," Congo ");
s.replace("COK"," Cook Islands ");
s.replace("COL"," Colombia ");
s.replace("COM"," Comoros ");
s.replace("CPV"," Cabo Verde ");
s.replace("CRI"," Costa Rica ");
s.replace("CUB"," Cuba ");
s.replace("CUW"," Curaçao ");
s.replace("CXR"," Christmas Island ");
s.replace("CYM"," Cayman Islands ");
s.replace("CYP"," Cyprus ");
s.replace("CZE"," Czechia ");
s.replace("DEU"," Germany ");
s.replace("DJI"," Djibouti ");
s.replace("DMA"," Dominica ");
s.replace("DNK"," Denmark ");
s.replace("DOM"," Dominican Republic ");
s.replace("DZA"," Algeria ");
s.replace("ECU"," Ecuador ");
s.replace("EGY"," Egypt ");
s.replace("ERI"," Eritrea ");
s.replace("ESH"," Western Sahara ");
s.replace("ESP"," Spain ");
s.replace("EST"," Estonia ");
s.replace("ETH"," Ethiopia ");
s.replace("FIN"," Finland ");
s.replace("FJI"," Fiji ");
s.replace("FLK"," Falkland Islands (Malvinas) ");
s.replace("FRA"," France ");
s.replace("FRO"," Faroe Islands ");
s.replace("FSM"," Federated States of Micronesia, ");
s.replace("GAB"," Gabon ");
s.replace("GBR"," United Kingdom ");
s.replace("GEO"," Georgia ");
s.replace("GGY"," Guernsey ");
s.replace("GHA"," Ghana ");
s.replace("GIB"," Gibraltar ");
s.replace("GIN"," Guinea ");
s.replace("GLP"," Guadeloupe ");
s.replace("GMB"," Gambia ");
s.replace("GNB"," Guinea-Bissau ");
s.replace("GNQ"," Equatorial Guinea ");
s.replace("GRC"," Greece ");
s.replace("GRD"," Grenada ");
s.replace("GRL"," Greenland ");
s.replace("GTM"," Guatemala ");
s.replace("GUF"," French Guiana ");
s.replace("GUM"," Guam ");
s.replace("GUY"," Guyana ");
s.replace("HKG"," Hong Kong ");
s.replace("HMD"," Heard Island and McDonald Islands ");
s.replace("HND"," Honduras ");
s.replace("HRV"," Croatia ");
s.replace("HTI"," Haiti ");
s.replace("HUN"," Hungary ");
s.replace("IDN"," Indonesia ");
s.replace("IMN"," Isle of Man ");
s.replace("IND"," India ");
s.replace("IOT"," British Indian Ocean Territory ");
s.replace("IRL"," Ireland ");
s.replace("IRN"," Islamic Republic of Iran, ");
s.replace("IRQ"," Iraq ");
s.replace("ISL"," Iceland ");
s.replace("ISR"," Israel ");
s.replace("ITA"," Italy ");
s.replace("JAM"," Jamaica ");
s.replace("JEY"," Jersey ");
s.replace("JOR"," Jordan ");
s.replace("JPN"," Japan ");
s.replace("KAZ"," Kazakhstan ");
s.replace("KEN"," Kenya ");
s.replace("KGZ"," Kyrgyzstan ");
s.replace("KHM"," Cambodia ");
s.replace("KIR"," Kiribati ");
s.replace("KNA"," Saint Kitts and Nevis ");
s.replace("KOR"," Republic of Korea, ");
s.replace("KWT"," Kuwait ");
s.replace("LAO"," People's Democratic Republic Lao ");
s.replace("LBN"," Lebanon ");
s.replace("LBR"," Liberia ");
s.replace("LBY"," Libya ");
s.replace("LCA"," Saint Lucia ");
s.replace("LIE"," Liechtenstein ");
s.replace("LKA"," Sri Lanka ");
s.replace("LSO"," Lesotho ");
s.replace("LTU"," Lithuania ");
s.replace("LUX"," Luxembourg ");
s.replace("LVA"," Latvia ");
s.replace("MAC"," Macao ");
s.replace("MAF"," Saint Martin (French part) ");
s.replace("MAR"," Morocco ");
s.replace("MCO"," Monaco ");
s.replace("MDA"," Moldova, Republic of ");
s.replace("MDG"," Madagascar ");
s.replace("MDV"," Maldives ");
s.replace("MEX"," Mexico ");
s.replace("MHL"," Marshall Islands ");
s.replace("MKD"," the former Yugoslav Republic of Macedonia, ");
s.replace("MLI"," Mali ");
s.replace("MLT"," Malta ");
s.replace("MMR"," Myanmar ");
s.replace("MNE"," Montenegro ");
s.replace("MNG"," Mongolia ");
s.replace("MNP"," Northern Mariana Islands ");
s.replace("MOZ"," Mozambique ");
s.replace("MRT"," Mauritania ");
s.replace("MSR"," Montserrat ");
s.replace("MTQ"," Martinique ");
s.replace("MUS"," Mauritius ");
s.replace("MWI"," Malawi ");
s.replace("MYS"," Malaysia ");
s.replace("MYT"," Mayotte ");
s.replace("NAM"," Namibia ");
s.replace("NCL"," New Caledonia ");
s.replace("NER"," Niger ");
s.replace("NFK"," Norfolk Island ");
s.replace("NGA"," Nigeria ");
s.replace("NIC"," Nicaragua ");
s.replace("NIU"," Niue ");
s.replace("NLD"," Netherlands ");
s.replace("NOR"," Norway ");
s.replace("NPL"," Nepal ");
s.replace("NRU"," Nauru ");
s.replace("NZL"," New Zealand ");
s.replace("OMN"," Oman ");
s.replace("PAK"," Pakistan ");
s.replace("PAN"," Panama ");
s.replace("PCN"," Pitcairn ");
s.replace("PER"," Peru ");
s.replace("PHL"," Philippines ");
s.replace("PLW"," Palau ");
s.replace("PNG"," Papua New Guinea ");
s.replace("POL"," Poland ");
s.replace("PRI"," Puerto Rico ");
s.replace("PRK"," Democratic People's Republic of Korea, ");
s.replace("PRT"," Portugal ");
s.replace("PRY"," Paraguay ");
s.replace("PSE"," State of Palestine, ");
s.replace("PYF"," French Polynesia ");
s.replace("QAT"," Qatar ");
s.replace("REU"," Réunion ");
s.replace("ROU"," Romania ");
s.replace("RUS"," Russian Federation ");
s.replace("RWA"," Rwanda ");
s.replace("SAU"," Saudi Arabia ");
s.replace("SDN"," Sudan ");
s.replace("SEN"," Senegal ");
s.replace("SGP"," Singapore ");
s.replace("SGS"," South Georgia and the South Sandwich Islands ");
s.replace("SHN"," Saint Helena, Ascension and Tristan da Cunha ");
s.replace("SJM"," Svalbard and Jan Mayen ");
s.replace("SLB"," Solomon Islands ");
s.replace("SLE"," Sierra Leone ");
s.replace("SLV"," El Salvador ");
s.replace("SMR"," San Marino ");
s.replace("SOM"," Somalia ");
s.replace("SPM"," Saint Pierre and Miquelon ");
s.replace("SRB"," Serbia ");
s.replace("SSD"," South Sudan ");
s.replace("STP"," Sao Tome and Principe ");
s.replace("SUR"," Suriname ");
s.replace("SVK"," Slovakia ");
s.replace("SVN"," Slovenia ");
s.replace("SWE"," Sweden ");
s.replace("SWZ"," Swaziland ");
s.replace("SXM"," Sint Maarten (Dutch part) ");
s.replace("SYC"," Seychelles ");
s.replace("SYR"," Syrian Arab Republic ");
s.replace("TCA"," Turks and Caicos Islands ");
s.replace("TCD"," Chad ");
s.replace("TGO"," Togo ");
s.replace("THA"," Thailand ");
s.replace("TJK"," Tajikistan ");
s.replace("TKL"," Tokelau ");
s.replace("TKM"," Turkmenistan ");
s.replace("TLS"," Timor-Leste ");
s.replace("TON"," Tonga ");
s.replace("TTO"," Trinidad and Tobago ");
s.replace("TUN"," Tunisia ");
s.replace("TUR"," Turkey ");
s.replace("TUV"," Tuvalu ");
s.replace("TWN"," Taiwan Province of China ");
s.replace("TZA"," United Republic of Tanzania, ");
s.replace("UGA"," Uganda ");
s.replace("UKR"," Ukraine ");
s.replace("UMI"," United States Minor Outlying Islands ");
s.replace("URY"," Uruguay ");
s.replace("USA"," United States of America ");
s.replace("UZB"," Uzbekistan ");
s.replace("VAT"," Holy See ");
s.replace("VCT"," Saint Vincent and the Grenadines ");
s.replace("VEN"," Bolivarian Republic of Venezuela, ");
s.replace("VGB"," British Virgin Islands, ");
s.replace("VIR"," U.S. Virgin Islands, ");
s.replace("VNM"," Viet Nam ");
s.replace("VUT"," Vanuatu ");
s.replace("WLF"," Wallis and Futuna ");
s.replace("WSM"," Samoa ");
s.replace("YEM"," Yemen ");
s.replace("ZAF"," South Africa ");
s.replace("ZMB"," Zambia ");
s.replace("ZWE"," Zimbabwe ");

That alone is about 250 calls to the QString::replace function, which does not seem optimal. I have about 5000 similar types of calls, and my strings are very large, and I would like to learn the optimal way to tackle this issue.

I program in Qt, and just thinking off the top of my head, the most optimal way I could think of tackling this was

1. Building a hash, with hardcoded Key["ABW"] Value[" Aruba "] pairs.
2. Building a regular expression (ABW|AFG|AGO|...|ZMB)
3. Matching the regular expression against the string
4. Getting a list of matches
5. Match that list against the hash somehow, and running the requisite replace calls.

I figure while on a better track than the 250 replace functions, I do not feel confident enough to ascertain whether it is the best track, or whether it really is even necessary, because for all I know, GCC and other compilers optimizes things like this on its own.

What is the best and most optimal strategy when it comes to tackling the issue of a massive number of replace calls against a large string in terms of achieving the best performance?

Is there an industry standard when it comes to this sort of thing?

Answer 1

The regular expression libraries in some languages let you specify a function to determine the replacement instead of a single string. That, combined with a hash of your strings and their replacements, will get it done quickly and with little fuss.

Here it is in Python, just because that happened to be quick and handy:

import re

# Word boundary, three capital letters, word boundary.
# Compile only once to avoid repetitive compilation.

matcher = re.compile(r'\b[A-Z]{3}\b')

# String/replacement hash
replacements = {
    "FOO": "Fooville",
    "BAR": "Barneo",
    "BAZ": "Baz Republic",
    "QUX": "Quuxistan"
    }

def replace_target(match):
    target = match.group()
    # Get replacement, returning the original text
    # if there's no replacement for it in the table.
    return replacements.get(target, target)


for string in [
        "He flew from FOO to BAR.",
        "BAZ has great beaches.",
        "QUX was conquered by XYZ in 1806."
        ]:
    print re.sub( matcher, replace_target, string )

What you get from doing this is a single pass through your input that only stops when the regex engine's state machine decides something interesting has been matched. The function that's called does a quick lookup, returns the replacement to be added to the output and scanning continues.

There are even speedier ways to pull this off that cut the regex engine completely out of the picture, but if you were processing the kinds of volume the needed something like that, you'd probably already know it. Don't go ape with optimization until you can prove there's an unacceptable bottleneck.

Answer 2

This seems like something which can be efficiently addressed by building a Trie out of all the strings that need to be replaced.

Then in one pass, go through the string to be replaced on, character by character. If consecutive characters end up matching a string in the trie, write out the replacement string, else write out the characters in the original string, in the result string.

Answer 3

Your idea of using regexes and a hash table is probably ideal. It is likely much better to perform all replacements in a single pass instead of using multiple replacement passes, because:

• correctness: repeated replacements could also match the previous replacement text, thus making order of replacement relevant
• input scanning: each replacement pass needs to scan the whole input. A regex that matches all keys at once needs only one pass.
• output buffer sizing: for in-place replacements, the string buffer needs to be resized and the part to the right of the replacement needs to be shifted to a new location. If you write the result (non-matched input or replacement strings) into an output buffer you don't have to shift any string contents around, just copies to a non-overlapping memory area.

Or phrased in terms of algorithmic complexity: k independent replacements on a string of length n runs in roughly O(k·n) time, whereas the regex+hash table approach can run in O(k + n) time – at a scale that's significantly better. Given your numbers (k = 250, n = “very large”) it's feasible that you will benefit more from good algorithms than possible micro-optimizations.

In pseudocode, the ideal approach works something like this:

string multi_replace(string input, hash_table replacements):
  regex matcher = compile(matches any replacements.keys())
  string result = reserve input.size()
  iter input_offset = input.start()
  for (iter match_start, iter match_end) = matcher.all_matches(input):
    if match_start > input_offset:
      copy(input[input_offset .. match_start] into result.end())
    key = input[match_start .. match_end]
    copy(replacements[key]) into result.end())
    input_offset = match_end
  return result

Note that this kind of task is much easier in higher-level languages. E.g. in Perl, the real code for the above function would be:

sub multi_replace {
  my ($input, $replacements) = @_;
  my $matcher = join '|', map quotemeta, keys %$replacements;
  return $input =~ s/($matcher)/$replacements->{$1}/gr;
}

In any case, whether you keep using replacements or switch to a more sophisticated approach, strongly consider separating the replacement data from the code that performs this replacement. Then, even your existing replacement code could be simplified to:

std::vector<std::pair<std::string, std::string>> all_replacements = ...;
for (auto replacement : all_replacements)
  s.replace(replacement.first, replacement.second);

Answer 4

Interesting problem!

I am sure that someone can and will come up with a better solution, but here are my initial thoughts: Your biggest bottleneck will be the continual reallocation of memory. Whenever you do a replace, you are creating a new string, copying the content from src to destination and doing a modification on the dest (result) string... well more or less, the details are besides the point. The problem is that memory allocation and deallocation will be >90% bottleneck. Its is very expensive so avoid it, if you can, or minimize it.

The strategy I am going to propose is based on minimizing the result string allocation to just once.

1.) Build a map of indices indicating start/end pos as well as the replacing string of a block that needs to be changed. e.g. "this is just BEL test and another CHN test" -> [[13,16,Belgium], [34,37,China]]

2.) The resulting length is the length of the original string + delta growth, which is the sum of growth per occurrence:

 4 chars - from index 13 to 16 ("BEL" -> "Belgium", -3+7 = +4 growth)
 2 chars - from index 37 to 40 ("CHN" -> "China", -3+5 = +2 growth)
 ------
 6 sum!

Your result string will be 42 + 6 = 47 chars long, you allocate this once.

3.) Reiterate and construct your result string accordingly

Here is an example implementation (check out the replace method)

I think this solution should suffice for now, until someone pulls out the standard way to approach this problem!