Проблема
Я думаю, что ваша проблема связана с тем, что вы пересекаете свою строку n раз, если у вас есть n символов для замены.
Таким образом, чтобы сделать это быстрее для одной строки, вам нужно пересечь вашу строку только один раз. Это сделало бы это, я думаю, быстрее. Я не вижу немедленного ответа о том, как вы можете это сделать, кроме как по собственному алгоритму.
Итак, чтобы проверить, о чем я думаю, я написал небольшой скрипт для тестирования и выяснил, что предложенная вами реализация является самой быстрой из всех.
Измерение
Сначала заметка о том, как я тестировал производительность. Я сгенерировал случайную строку для проверки каждого алгоритма. Таким образом, каждый алгоритм был протестирован с одним и тем же вводом, и генерация ввода не учитывалась в результатах.
Затем я запускал каждый алгоритм 100 раз, рассчитывая время выполнения с помощью :timer.rc/1. Я суммировал все результаты и разделил их на 100, чтобы получить среднее время выполнения.
Я также, учитывая, что в вашем вопросе не было деталей, использовал свой собственный алфавит. Вы можете заменить его, как считаете нужным. Я только предполагал, что префикс каждой строки для замены - «;;;;».
Вот алфавит.
def alphabet do
%{
";;;;a" => "a",
";;;;b" => "b",
";;;;c" => "c",
";;;;d" => "d",
";;;;e" => "e",
";;;;f" => "f",
";;;;g" => "g",
";;;;h" => "h",
";;;;i" => "i",
";;;;j" => "j",
";;;;k" => "k",
";;;;l" => "l",
";;;;m" => "m",
";;;;n" => "n",
";;;;o" => "o",
";;;;p" => "p",
";;;;q" => "q",
";;;;r" => "r",
";;;;s" => "s",
";;;;t" => "t",
";;;;u" => "u",
";;;;v" => "v",
";;;;w" => "w",
";;;;x" => "x",
";;;;y" => "y",
";;;;z" => "z"
}
end
Он реализован в виде карты, которая должна дайте нам O (log n) поиска.
Решение 1
Сначала я начал с наивной версии; тот, который вы показали.
def naive(input) do
alphabet()
|> Map.keys()
|> Enum.reduce(input, fn key, str ->
String.replace(str, key, alphabet()[key])
end)
end
Здесь вы просто пересекаете все ключи алфавита и проверяете, присутствуют ли они в строке, и если да, то вы заменяете их все.
Среднее время выполнения этой функции с входным размером 10000 и 100 запусков составляет 1.40691 мс .
Решение 2
Второй подход I Потребовалось использовать предложение другого ответа здесь, а именно, используя String.replace/4 вместо ручной проверки каждого случая.
Обратите внимание, что для краткости я вырезал здесь большой кусок алфавита.
def better(input) do
String.replace(
input,
[
";;;;a",
";;;;b",
...
";;;;y",
";;;;z"
],
fn
";;;;a" -> "a"
";;;;b" -> "b"
...
";;;;y" -> "y"
";;;;z" -> "z"
end
)
end
Среднее время выполнения этой функции с входным размером 10000 и 100 запусков составляет 1,3419400000000001 мс
Решение 3
Окончательный вариант Решение с моей стороны, где я попытался развернуть свой собственный алгоритм.
Идея состоит в том, чтобы пройти строку, и как только мы увидим, что строка начинается с четырех ";" Символы мы можем заменить на основе пятого символа.
def alphabet2 do
%{
?a => ?a,
?b => ?b,
...
?y => ?y,
?z => ?z
}
end
def process(cl, acc) do
case cl do
[] ->
acc
[?;, ?;, ?;, ?;, c | r] ->
new_char = alphabet2()[c]
process(r, [new_char | acc])
[c | r] ->
process(r, [c | acc])
end
end
def even_better(input) do
cl = String.to_charlist(input)
process(cl, []) |> Enum.reverse() |> List.to_string()
end
Среднее время выполнения этой функции с входным размером 10000 и 100 прогонов составляет 1,21495 мс.
Заключение
Ваше решение достаточно быстро для того, что у вас есть. Единственное, что я могу порекомендовать сделать, - это распараллелить обработку пакета строк. Вы не можете сделать одну строку быстрее, но вы можете с большей легкостью обработать кучу строк быстрее.
Тесты
Код производительности, который я использовал, следующий:
avg_ms =
1..runs
|> Enum.map(fn _ -> :timer.tc(fn -> even_better(str) end) end)
|> Enum.reduce(0, fn {time, _}, acc -> acc + time end)
|> (fn s -> s / runs / 1000 end).()
IO.puts("Even Better took avg #{avg_ms} ms")
Также обратите внимание, что эти решения можно сделать красивее с помощью некоторых макросов. Смотрите другой ответ для этого.