Qual è il modo ottimale per eseguire 5000 funzioni di sostituzione di stringhe uniche in termini di prestazioni?

2

Ristrutturazione di un codice e il modo in cui l'ho creato nel tempo ha parti che assomigliano a questo:

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 ");

Questo è di circa 250 chiamate alla funzione QString::replace , che non sembra ottimale. Ho circa 5000 tipi di chiamate simili e le mie stringhe sono molto grandi e mi piacerebbe imparare il modo ottimale per affrontare questo problema.

Ho programmato in Qt, e stavo solo pensando in cima alla mia testa, il modo migliore che potessi pensare di affrontare questo era

  1. Costruire un hash, con coppie Key["ABW"] Value[" Aruba "] codificate.
  2. Creazione di un'espressione regolare (ABW|AFG|AGO|...|ZMB)
  3. Corrispondenza dell'espressione regolare rispetto alla stringa
  4. Ottenere un elenco di corrispondenze
  5. Abbina in qualche modo l'elenco con l'hash e esegui il requisito per sostituire le chiamate.

Personalmente, mentre su una pista migliore rispetto alle 250 sostituzioni, non mi sento abbastanza sicuro per stabilire se è la pista migliore, o se è addirittura necessario, perché per quel che ne so GCC e altri compilatori ottimizzano cose come questa.

Qual è la strategia migliore e più ottimale quando si tratta di affrontare il problema di un numero enorme di chiamate di replace contro una stringa di grandi dimensioni in termini di raggiungimento delle migliori prestazioni?

C'è uno standard del settore quando si tratta di questo genere di cose?

    
posta Akiva 14.07.2018 - 22:29
fonte

4 risposte

7

Le librerie di espressioni regolari in alcune lingue consentono di specificare una funzione per determinare la sostituzione anziché una singola stringa. Questo, combinato con un hash delle tue corde e dei loro sostituti, lo farà rapidamente e con poco clamore.

Qui è in Python, solo perché è stato rapido e utile:

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 )

Ciò che ottieni dal fare questo è un singolo passaggio attraverso il tuo input che si ferma solo quando la macchina di stato del motore regex decide che qualcosa di interessante è stato abbinato. La funzione chiamata effettua una rapida ricerca, restituisce la sostituzione da aggiungere all'output e la scansione continua.

Ci sono anche modi più veloci per rimuoverlo che tagliano il motore regex completamente fuori dall'immagine, ma se stavi elaborando il tipo di volume necessario qualcosa del genere, probabilmente lo sapresti già. Non andare scimmia con l'ottimizzazione finché non puoi provare che c'è un collo di bottiglia inaccettabile.

    
risposta data 15.07.2018 - 01:13
fonte
4

Sembra che qualcosa possa essere efficacemente risolto creando un Trie tra tutte le stringhe che devono essere sostituite .

Quindi, in un passaggio, passa attraverso la stringa da sostituire, carattere per carattere. Se i caratteri consecutivi finiscono per abbinare una stringa nel trie, scrivi la stringa sostitutiva, altrimenti scrivi i caratteri nella stringa originale, nella stringa risultante.

    
risposta data 15.07.2018 - 07:28
fonte
3

La tua idea di usare espressioni regex e una tabella hash è probabilmente l'ideale. È molto meglio eseguire tutte le sostituzioni in un singolo passaggio anziché utilizzare più pass di sostituzione, perché:

  • correttezza: le sostituzioni ripetute potrebbero anche corrispondere al precedente testo di sostituzione, rendendo così l'ordine di sostituzione rilevante
  • input scanning: ogni passaggio sostitutivo deve eseguire la scansione dell'intero input. Una regex che corrisponde a tutti i tasti in una sola volta ha bisogno di un solo passaggio.
  • dimensionamento del buffer di output: per le sostituzioni sul posto, il buffer delle stringhe deve essere ridimensionato e la parte a destra della sostituzione deve essere spostata in una nuova posizione. Se scrivi il risultato (stringhe di input o di sostituzione non corrispondenti) in un buffer di output, non devi spostare alcun contenuto di stringa in giro, ma solo copiare in un'area di memoria non sovrapposta.

O formulati in termini di complessità algoritmica: k sostituzioni indipendenti su una stringa di lunghezza n gira in modo approssimativo O (k · n), mentre l'approccio regex + tabella hash può essere eseguito nel tempo O (k + n) - a una scala che è significativamente migliore. Dati i tuoi numeri (k = 250, n="molto grandi") è possibile che tu possa trarre maggiore vantaggio da algoritmi validi rispetto alle possibili micro-ottimizzazioni.

In pseudocodice, l'approccio ideale funziona in questo modo:

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

Si noti che questo tipo di attività è molto più semplice nei linguaggi di livello superiore. Per esempio. in Perl, il codice reale per la funzione sopra sarebbe:

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

In ogni caso, se continui ad usare le sostituzioni o passi ad un approccio più sofisticato, considera strongmente la separazione dei dati sostitutivi dal codice che esegue questa sostituzione. Quindi, anche il tuo codice sostitutivo esistente potrebbe essere semplificato in:

std::vector<std::pair<std::string, std::string>> all_replacements = ...;
for (auto replacement : all_replacements)
  s.replace(replacement.first, replacement.second);
    
risposta data 14.07.2018 - 23:36
fonte
1

Problema interessante!

Sono certo che qualcuno possa e troverà una soluzione migliore, ma ecco i miei pensieri iniziali: Il tuo collo di bottiglia più grande sarà la continua riallocazione della memoria. Ogni volta che fai una sostituzione, stai creando una nuova stringa, copiando il contenuto da src a destinazione e facendo una modifica sulla stringa dest (risultato) ... beh, più o meno, i dettagli sono oltre il punto. Il problema è che l'allocazione della memoria e la deallocazione saranno il colli di bottiglia > 90%. È molto costoso, quindi evitalo, se possibile, o riduci a icona.

La strategia che sto per proporre si basa sulla riduzione al minimo della allocazione della stringa di risultati in una sola volta.

1.) Costruisci una mappa di indici che indicano la posizione iniziale / finale e la stringa di sostituzione di un blocco che deve essere modificata. per esempio. "questo è solo test BEL e un altro test CHN" - > [[13,16, Belgio], [34,37, Cina]]

2.) La lunghezza risultante è la lunghezza della stringa originale + crescita delta, che è la somma della crescita per occorrenza:

 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!

La tua stringa di risultati sarà lunga 42 + 6 = 47 caratteri, allochi questa una volta .

3.) Reiterate e costruite la stringa dei risultati di conseguenza

Ecco un esempio di implementazione (controlla il metodo di sostituzione)

Penso che questa soluzione dovrebbe essere sufficiente per ora, fino a quando qualcuno non elabora il modo standard per affrontare questo problema!

    
risposta data 14.07.2018 - 23:39
fonte