什么 Erlang 数据结构用于有序集并可以进行查找？

Question

我正在解决一个问题，我需要记住我收到的事件的顺序，而且我还需要根据事件的 ID 查找事件。如果可能的话，如果没有第三方库，我如何在 Erlang 中有效地做到这一点？请注意，我有许多潜在的短暂演员，每个演员都有自己的事件（已经被认为是健忘症，但它需要表格的原子，如果我的演员死了，表格会保留下来）。

-record(event, {id, timestamp, type, data}).

Answer 1

你的问题清楚地表明你想按 ID 查找，但你是否想按时间或基于时间查找或遍历你的数据，以及你可能希望在这方面执行哪些操作并不完全清楚；你说 "remember the order of events" 但是用 ID 字段的索引存储你的记录就可以做到这一点。

如果您只需要按 ID 查找，那么任何常见的可疑对象都可以用作 suitable 存储引擎，因此 ets、gb_trees 和 dict 会很好。除非您需要交易和安全以及所有这些好的功能，否则不要使用 mnesia； mnesia 很好，但是要为所有这些东西付出高昂的性能代价，而且从你的问题来看，还不清楚你是否需要它。

如果您确实想按时间或基于时间查找或遍历数据，请考虑 ordered_set 的 ets table。如果那可以满足您的需要，那么它可能是一个不错的选择。在这种情况下，您将使用两个 table，一个 set 通过 ID 提供散列查找，另一个 ordered_set 通过时间戳查找或遍历。

如果您有两种不同的查找方法，那么就无法回避您需要两个索引的事实。您可以将整个记录存储在两者中，或者，假设您的 ID 是唯一的，您可以将 ID 作为数据存储在 ordered_set 中。您选择哪个实际上是存储利用率和读写性能的权衡问题。

Answer 2

根据 Michael 回答评论中讨论的详细信息，非常简单可行的方法是在存储订单的流程状态变量中创建一个元组事件与 K-V 事件存储分开。

考虑：

%%% Some type definitions so we know exactly what we're dealing with.
-type id()     :: term().
-type type()   :: atom().
-type data()   :: term().
-type ts()     :: calendar:datetime().
-type event()  :: {id(), ts(), type(), data()}.
-type events() :: dict:dict(id(), {type(), data(), ts()}).

% State record for the process.
% Should include whatever else the process deals with.
-record(s,
        {log    :: [id()],
         events :: event_store()}).

%%% Interface functions we will expose over this module.
-spec lookup(pid(), id()) -> {ok, event()} | error.
lookup(Pid, ID) ->
    gen_server:call(Pid, {lookup, ID}).

-spec latest(pid()) -> {ok, event()} | error.
latest(Pid) ->
    gen_server:call(Pid, get_latest).

-spec notify(pid(), event()) -> ok.
notify(Pid, Event) ->
    gen_server:cast(Pid, {new, Event}).

%%% gen_server handlers
handle_call({lookup, ID}, State#s{events = Events}) ->
    Result = find(ID, Events),
    {reply, Result, State};
handle_call(get_latest, State#s{log = [Last | _], events = Events}) ->
    Result = find(Last, Events),
    {reply, Result, State};
% ... and so on...

handle_cast({new, Event}, State) ->
    {ok, NewState} = catalog(Event, State),
    {noreply, NewState};
% ...

%%% Implementation functions
find(ID, Events) ->
    case dict:find(ID, Events) of
        {Type, Data, Timestamp} -> {ok, {ID, Timestamp, Type, Data}};
        Error                   -> Error
    end.

catalog({ID, Timestamp, Type, Data},
        State#s{log = Log, events = Events}) ->
    NewEvents = dict:store(ID, {Type, Data, Timestamp}, Events),
    NewLog = [ID | Log],
    {ok, State#s{log = NewLog, events = NewEvents}}.

这是一个完全直接的实现，隐藏了进程接口后面的数据结构细节。为什么我选择了一个字典？只是因为（很容易）。在不了解您的要求的情况下，我真的没有理由在 gb_tree 等地图上选择字典。如果您的数据相对较小（要存储成百上千的东西），性能通常不会有明显差异在这些结构中。

重要的是你要清楚地识别这个进程应该响应什么消息，然后通过创建在此模块上公开函数 的接口。在这之后，您可以将 dict 换成其他东西。如果您真的只需要最新的事件 ID 而永远不需要从序列日志中提取第 N 个事件，那么您可以放弃日志，只将最后一个事件的 ID 保留在记录中而不是列表中。

因此，首先让一些非常简单的东西像这样工作，然后确定它是否真的适合您的需要。如果没有，则对其进行调整。如果这现在有效，只需运行就可以了——不要过分关注性能或存储（除非你真的被迫这样做）。

如果您稍后发现您遇到性能问题，请关闭 dict 并列出其他内容——可能是 gb_tree 或 orddict 或 ETS 或其他。关键是让某些东西立即运行，以便您有一个基础来评估功能和运行基准（如有必要）。（尽管如此，大量大多数时候，我发现无论我作为指定原型开始使用什么，结果都非常接近任何东西最终的解决方案将是。）

什么 Erlang 数据结构用于有序集并可以进行查找？

What Erlang data structure to use for ordered set with the possibility to do lookups?

database

erlang

set

data-structures