if-statement - Elixir 二分查找

Question

我在 Elixir 中构建了一个二分搜索，但我最终使用了 3 个 if 子句:

if actual == guessed_number, do:

if actual > guessed_number do:

if actual < guessed_number do:

是否可以根本不使用条件？也许与模式匹配？

Answer 1

免责声明:不要在生产中使用它，这比简单的线性搜索慢，因为链表不允许在恒定时间内进行随机访问。这篇文章仅是关于模式匹配方面的。

理论上你可以使用保护子句，但如果你过度使用它们会使事情变得更糟。假设您从这样的实现开始:

defmodule MyEnum do
  def binsearch(collection, key) do
    binsearch(collection, key, 1, length(collection))
  end

  defp binsearch(collection, key, lo, hi) do
    if hi < lo do
      -1
    else
      mid = div(lo + hi, 2)
      item = Enum.at(collection, mid)
      cond do
        key < item -> binsearch(collection, key, lo, mid-1)
        key > item -> binsearch(collection, key, mid+1, hi)
        true       -> mid
      end
    end
  end
end

也许你想提取 if进入保护条款:

defmodule MyEnum do
  def binsearch(collection, key) do
    binsearch(collection, key, 1, length(collection))
  end

  defp binsearch(_collection, _key, lo, hi) when hi < lo do
    -1
  end

  defp binsearch(collection, key, lo, hi) do
    mid = div(lo + hi, 2)
    item = Enum.at(collection, mid)
    cond do
      key < item -> binsearch(collection, key, lo, mid-1)
      key > item -> binsearch(collection, key, mid+1, hi)
      true       -> mid
    end
  end
end

现在你也可以拉 cond进guard clauses但这并不是真正的改进:

defmodule MyEnum do
  def binsearch(collection, key) do
    binsearch(collection, key, 1, length(collection))
  end

  defp binsearch(_collection, _key, low, hi) when hi < low do
    -1
  end

  defp binsearch(collection, key, low, hi) do
    mid = div(low + hi, 2)
    item = Enum.at(collection, mid)
    binsearch(collection, key, item, low, mid, hi)
  end

  defp binsearch(collection, key, item, low, mid, _hi) when key < item do
    binsearch(collection, key, low, mid-1)
  end

  defp binsearch(collection, key, item, _low, mid, hi) when key > item do
    binsearch(collection, key, mid+1, hi)
  end

  defp binsearch(_collection, _key, _item, _low, mid, _hi) do
    mid
  end
end