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

它被实现为一个地图，它应该给我们 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 ms。

解决方案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")

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

Answer 2

String.replace/4 接受替换列表作为模式和函数。

to_replace = ~w|;;;ca ;;;ea ;;;d1 ;;;f1|
content = Enum.join(to_replace, " | ")
#? ";;;ca | ;;;ea | ;;;d1 | ;;;f1"
String.replace(content, to_replace, fn
  ";;;ca" -> "?"
  ";;;ea" -> "?"
  ";;;d1" -> "?"
  ";;;f1" -> "?"
end)
#? "? | ? | ? | ?"

如果要替换的项很多，也可以使用一些元编程来生成函数子句。

defmodule R do                           
  @r ~w|;;;ca ;;;ea ;;;d1 ;;;f1|
  @s ~w|? ? ? ?|
  Enum.each(Enum.zip(@r, @s), fn {r, s} ->
    defp one(unquote(r)), do: unquote(s)
  end)
  def all(content) do
    String.replace(content, @r, &one/1)
  end
end

R.all("|;;;ca|;;;ea|;;;d1|;;;f1")
#? "|?|?|?|?"