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出来作为保护条款,但这并不是一个改进:

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

Answer 2

你不能用模式匹配来做到这一点.但是,您可以使用cond类似Erlang的if:

cond do
    actual == guessed_number ->
        ...
    actual > guessed_number ->
        ...
    actual < guessed_number ->
        ...
end