Lua: Doing fast multiple replacements in long strings

I have

A list of pattern/replacement pairs.

A long string to do the replacements on (several kByte or even MBytes).

All occurrences of all patterns have to be replaced by their corresponding replacement texts. Each pattern may exist more than once in the string.

Currently, I do this by iterating over the list of pattern/replacement pairs and using string.gsub every time:

for _, pattern, replace in iter(replace_patterns) do
 body = body:gsub(pattern, replace)
end

(iter is a helper function to better iterate through the patterns.)

Question: Is this the best way to do it? I fear this to be inefficient as every call to gsub will scan the whole long string.

P.S. I read https://stackoverflow.com/a/12865406/5005936 (helped me to reduce string usage and others) and https://stackoverflow.com/a/38422229/5005936 (but I don't want to write native code in this context...)

edited Nov 16 '18 at 4:46

asked Nov 16 '18 at 4:37

dsteinkopf

119113

1

Have you looked at LPeg? It is fast and would allow you to scan a string only once.

– cyclaminist
Nov 16 '18 at 23:54

add a comment |

I have

A list of pattern/replacement pairs.

A long string to do the replacements on (several kByte or even MBytes).

All occurrences of all patterns have to be replaced by their corresponding replacement texts. Each pattern may exist more than once in the string.

Currently, I do this by iterating over the list of pattern/replacement pairs and using string.gsub every time:

for _, pattern, replace in iter(replace_patterns) do
 body = body:gsub(pattern, replace)
end

(iter is a helper function to better iterate through the patterns.)

Question: Is this the best way to do it? I fear this to be inefficient as every call to gsub will scan the whole long string.

edited Nov 16 '18 at 4:46

asked Nov 16 '18 at 4:37

dsteinkopf

119113

1

Have you looked at LPeg? It is fast and would allow you to scan a string only once.

– cyclaminist
Nov 16 '18 at 23:54

add a comment |

I have

A list of pattern/replacement pairs.

A long string to do the replacements on (several kByte or even MBytes).

All occurrences of all patterns have to be replaced by their corresponding replacement texts. Each pattern may exist more than once in the string.

Currently, I do this by iterating over the list of pattern/replacement pairs and using string.gsub every time:

for _, pattern, replace in iter(replace_patterns) do
 body = body:gsub(pattern, replace)
end

(iter is a helper function to better iterate through the patterns.)

Question: Is this the best way to do it? I fear this to be inefficient as every call to gsub will scan the whole long string.

edited Nov 16 '18 at 4:46

asked Nov 16 '18 at 4:37

dsteinkopf

119113

I have

A list of pattern/replacement pairs.

A long string to do the replacements on (several kByte or even MBytes).

All occurrences of all patterns have to be replaced by their corresponding replacement texts. Each pattern may exist more than once in the string.

Currently, I do this by iterating over the list of pattern/replacement pairs and using string.gsub every time:

for _, pattern, replace in iter(replace_patterns) do
 body = body:gsub(pattern, replace)
end

(iter is a helper function to better iterate through the patterns.)

Question: Is this the best way to do it? I fear this to be inefficient as every call to gsub will scan the whole long string.

string replace lua

edited Nov 16 '18 at 4:46

asked Nov 16 '18 at 4:37

dsteinkopf

119113

edited Nov 16 '18 at 4:46

asked Nov 16 '18 at 4:37

dsteinkopf

119113

edited Nov 16 '18 at 4:46

asked Nov 16 '18 at 4:37

dsteinkopf

119113

asked Nov 16 '18 at 4:37

dsteinkopf

119113

asked Nov 16 '18 at 4:37

dsteinkopf

119113

1

Have you looked at LPeg? It is fast and would allow you to scan a string only once.

– cyclaminist
Nov 16 '18 at 23:54

add a comment |

1

Have you looked at LPeg? It is fast and would allow you to scan a string only once.

– cyclaminist
Nov 16 '18 at 23:54

Have you looked at LPeg? It is fast and would allow you to scan a string only once.

– cyclaminist
Nov 16 '18 at 23:54

add a comment |

1 Answer
1

active

oldest

votes

Couple of things you may want to try (you'll have to run some benchmarks on your strings to see what works best):

Use find instead of gsub as it takes starting position, which allows to avoid re-scanning the same (long) string for each pattern

Use table.concat to concatenate final strings together; essentially, use find to get positions where the replacements start and cut the (sub-) strings to populate the table with replacements and the strings between them. Then concatenate the results together to get back the string you need.

You'll have to run the tests, as it's difficult to give some reasonable advice without knowing the number of patterns and approximate number of replacements for each pattern.

answered Nov 16 '18 at 5:35

Paul Kulchenko

19.4k22541

How do I avoid scanning the whole string again for each pattern? find is only able to search for one pattern, isn't it? What am I missing?

– dsteinkopf
Nov 16 '18 at 7:42

Doing some performance tests was a good idea: I got the result, that for a string with a length of 1 MByte and 8 Patterns (which is typical maximum), my replacement takes about 100ms. It also turned out that time increases linearly with string length and number of replacement patterns (as expected).

– dsteinkopf
Nov 16 '18 at 9:49

add a comment |

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53331511%2flua-doing-fast-multiple-replacements-in-long-strings%23new-answer', 'question_page');

);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

Couple of things you may want to try (you'll have to run some benchmarks on your strings to see what works best):

Use find instead of gsub as it takes starting position, which allows to avoid re-scanning the same (long) string for each pattern

Use table.concat to concatenate final strings together; essentially, use find to get positions where the replacements start and cut the (sub-) strings to populate the table with replacements and the strings between them. Then concatenate the results together to get back the string you need.

You'll have to run the tests, as it's difficult to give some reasonable advice without knowing the number of patterns and approximate number of replacements for each pattern.

answered Nov 16 '18 at 5:35

Paul Kulchenko

19.4k22541

How do I avoid scanning the whole string again for each pattern? find is only able to search for one pattern, isn't it? What am I missing?

– dsteinkopf
Nov 16 '18 at 7:42

Doing some performance tests was a good idea: I got the result, that for a string with a length of 1 MByte and 8 Patterns (which is typical maximum), my replacement takes about 100ms. It also turned out that time increases linearly with string length and number of replacement patterns (as expected).

– dsteinkopf
Nov 16 '18 at 9:49

add a comment |

Couple of things you may want to try (you'll have to run some benchmarks on your strings to see what works best):

Use find instead of gsub as it takes starting position, which allows to avoid re-scanning the same (long) string for each pattern

Use table.concat to concatenate final strings together; essentially, use find to get positions where the replacements start and cut the (sub-) strings to populate the table with replacements and the strings between them. Then concatenate the results together to get back the string you need.

You'll have to run the tests, as it's difficult to give some reasonable advice without knowing the number of patterns and approximate number of replacements for each pattern.

answered Nov 16 '18 at 5:35

Paul Kulchenko

19.4k22541

How do I avoid scanning the whole string again for each pattern? find is only able to search for one pattern, isn't it? What am I missing?

– dsteinkopf
Nov 16 '18 at 7:42

Doing some performance tests was a good idea: I got the result, that for a string with a length of 1 MByte and 8 Patterns (which is typical maximum), my replacement takes about 100ms. It also turned out that time increases linearly with string length and number of replacement patterns (as expected).

– dsteinkopf
Nov 16 '18 at 9:49

add a comment |

Couple of things you may want to try (you'll have to run some benchmarks on your strings to see what works best):

Use find instead of gsub as it takes starting position, which allows to avoid re-scanning the same (long) string for each pattern

Use table.concat to concatenate final strings together; essentially, use find to get positions where the replacements start and cut the (sub-) strings to populate the table with replacements and the strings between them. Then concatenate the results together to get back the string you need.

You'll have to run the tests, as it's difficult to give some reasonable advice without knowing the number of patterns and approximate number of replacements for each pattern.

answered Nov 16 '18 at 5:35

Paul Kulchenko

19.4k22541

Couple of things you may want to try (you'll have to run some benchmarks on your strings to see what works best):

Use find instead of gsub as it takes starting position, which allows to avoid re-scanning the same (long) string for each pattern

Use table.concat to concatenate final strings together; essentially, use find to get positions where the replacements start and cut the (sub-) strings to populate the table with replacements and the strings between them. Then concatenate the results together to get back the string you need.

You'll have to run the tests, as it's difficult to give some reasonable advice without knowing the number of patterns and approximate number of replacements for each pattern.

answered Nov 16 '18 at 5:35

Paul Kulchenko

19.4k22541

answered Nov 16 '18 at 5:35

Paul Kulchenko

19.4k22541

answered Nov 16 '18 at 5:35

Paul Kulchenko

19.4k22541

answered Nov 16 '18 at 5:35

Paul Kulchenko

19.4k22541

How do I avoid scanning the whole string again for each pattern? find is only able to search for one pattern, isn't it? What am I missing?

– dsteinkopf
Nov 16 '18 at 7:42

Doing some performance tests was a good idea: I got the result, that for a string with a length of 1 MByte and 8 Patterns (which is typical maximum), my replacement takes about 100ms. It also turned out that time increases linearly with string length and number of replacement patterns (as expected).

– dsteinkopf
Nov 16 '18 at 9:49

add a comment |

How do I avoid scanning the whole string again for each pattern? find is only able to search for one pattern, isn't it? What am I missing?

– dsteinkopf
Nov 16 '18 at 7:42

Doing some performance tests was a good idea: I got the result, that for a string with a length of 1 MByte and 8 Patterns (which is typical maximum), my replacement takes about 100ms. It also turned out that time increases linearly with string length and number of replacement patterns (as expected).

– dsteinkopf
Nov 16 '18 at 9:49

How do I avoid scanning the whole string again for each pattern? find is only able to search for one pattern, isn't it? What am I missing?

– dsteinkopf
Nov 16 '18 at 7:42

Doing some performance tests was a good idea: I got the result, that for a string with a length of 1 MByte and 8 Patterns (which is typical maximum), my replacement takes about 100ms. It also turned out that time increases linearly with string length and number of replacement patterns (as expected).

– dsteinkopf
Nov 16 '18 at 9:49

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Myujth