Elixir 中最有效的区间类型搜索

Question

我正在开始使用 Elixir 的旅程，正在寻找一些关于如何最好地解决特定问题的建议。

我有一个数据集需要尽快搜索。数据由形成封闭带的两个数字和与每个带关联的一些元数据组成。

例如：

From,To,Data    
10000,10999,MetaData1
11000,11999,MetaData2
12000,12499,MetaData3
12500,12999,MetaData4

这个数据集可能有超过 100,000 个条目。

我有一个 struct 定义的数据模型，以及一个创建 Elixir 列表内存表示的解析器。

defmodule Band do
    defstruct from: 0, to: 0, metadata: 0
end

解析器 returns 列表 Band struct。我定义了一个使用列表理解

的 find 方法

defp find_metadata(bands, number) do
        match? = fn(x) -> x.from <= number and x.to >= number end

        [match | _ ] = for band <- bands, match?.(band), do: band

        { :find, band }
end

根据我的新手知识，使用列表理解需要对列表进行完整遍历。为了避免扫描完整列表，我使用了其他语言的搜索树。

Elixir 中是否有 algorithm/mechanism/approach 可以更有效地解决此类搜索问题的方法？

谢谢。

Answer 1

如果 band 相互排斥，您可以将它们构建成按 from 排序的树。搜索那棵树应该需要 log(n) 时间。像下面这样的东西应该可以工作：

defmodule Tree do
  defstruct left: nil, right: nil, key: nil, value: nil

  def empty do
    nil
  end

  def insert(tree, value = {key, _}) do
    cond do
      tree == nil    -> %Tree{left: empty, right: empty, key: key, value: value}
      key < tree.key -> %{tree | left: insert(tree.left, value)}
      true           -> %{tree | right: insert(tree.right, value)}
    end
  end

  def find_interval(tree, value) do
    cond do
      tree == nil                -> nil
      value < tree.key           -> find_interval(tree.left, value)
      between(tree.value, value) -> tree.value
      true                       -> find_interval(tree.right, value)
    end
  end

  def between({left, right}, value) do
    value >= left and value <= right
  end
end

请注意，您也可以使用 Ranges 来存储 "bands"，就像您调用它们一样。另请注意，树不平衡。一个（可能）实现平衡树的简单方案是在插入间隔之前打乱间隔。否则你需要有一个更复杂的实现来平衡树。您可以查看 erlang 的 gb_trees 以获取灵感。

Elixir 中最有效的区间类型搜索

Most efficient interval type search in Elixir

search

list-comprehension

elixir