Elixir 和字符串中的多个替换字符

Question

我是一个初学者，使用旧数据库，其中的字符像 Ę,ę,Ń,ń保存为 ;;;ca ...它是带有 Phoenix 框架的 Elixir 语言。
我想在代码中多次替换该字符，我有一个功能:

  def convert_content(content) do
    content = String.replace(content, ";;;ca", "Ę")
    content = String.replace(content, ";;;ea", "ę")
    content = String.replace(content, ";;;d1", "Ń")
    content = String.replace(content, ";;;f1", "ń")
  end

但是很慢..我找到了https://github.com/elixir-lang/elixir/pull/4474但它不起作用。感谢帮助。

Answer 1

问题

我认为您的问题源于您遍历字符串的事实 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

它被实现为一个 map ，它应该给我们 O(log n) 查找。

方案一

首先，我从一个天真的版本开始；你展示的那个。

  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

我采取的第二种方法是使用这里其他答案的建议，即使用 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")

另请注意，通过使用一些宏可以使这些解决方案更漂亮。请参阅另一个答案。