查找地图中的最小值

Question

我有一个组织的地图 follows.Key 是一个简单的术语，可以说是一个整数，但值是复杂的元组 {BB,CC,DD}。在地图中找到最小 CC 的最佳方法是什么？到目前为止我有以下

-module(test).
-author("andre").

%% API
-export([init/0]).

init() ->
  TheMap = build(maps:new(), 20),
  io:format("Map: ~p~n", [TheMap]),
  AKey = hd(maps:keys(TheMap)),
  AValue = maps:get(AKey, TheMap),
  maps:fold(fun my_min/3, {AKey, AValue}, TheMap).

build(MyMap, Count) when Count == 0 ->
  MyMap;
build(MyMap, Count) ->
  NewMap = maps:put(Count, {random:uniform(100), random:uniform(100), random:uniform(100)}, MyMap),
  build(NewMap, Count - 1).

my_min(Key, {A,B,C}, {MinKey, {AA,BB,CC}}) ->
  if B < BB -> {Key, {A,B,C}};
     B >= BB -> {MinKey, {AA,BB,CC}}
  end.

我的地图很小，所以我不太担心使用AKey和AValue来找到折叠的初始值，但我想知道是否有更好的方法或其他数据结构。

-- 谢谢

Answer 1

您所拥有的接近于一个好的解决方案，但还可以改进。无需挖掘第一个键和值来使用折叠的初始值，因为您可以传递一个人工值来代替并让您的折叠函数处理它。此外，您还可以改进功能头中模式匹配的使用。最后，使用 start 而不是 init，因为这样在从命令行调用 erl 时更容易调用。

这是一个改进版本：

-module(test).
-author("andre").

%% API
-export([start/0]).

start() ->
    TheMap = build(maps:new(), 20),
    io:format("Map: ~p~n", [TheMap]),
    maps:fold(fun my_min/3, {undefined, undefined}, TheMap).

build(MyMap, 0) ->
    MyMap;
build(MyMap, Count) ->
    NewMap = maps:put(Count, {random:uniform(100), random:uniform(100), random:uniform(100)}, MyMap),
    build(NewMap, Count - 1).

my_min(Key, Value, {undefined, undefined}) ->
    {Key, Value};
my_min(Key, {_,B,_}=Value, {_, {_,BB,_}}) when B < BB ->
    {Key, Value};
my_min(_Key, _Value, Acc) ->
    Acc.

my_min/3 fold 函数有三个子句。第一个匹配特殊起始值 {undefined, undefined} 和 returns 作为新的累加器值，无论它传递给什么 {Key, Value}。这样做的好处不仅是你可以避免在开始折叠之前进行特殊处理，而且如果地图为空，你将得到特殊值 {undefined, undefined} 作为结果，你可以相应地处理它。第二个子句使用守卫检查折叠累加器中值的 B 是否小于 BB 值，如果是，则 return {Key, Value} 作为新的累加器值。最后一个子句只是 return 现有累加器值，因为仅当值大于或等于现有累加器中的值时才调用此子句。

您也可以考虑使用一个简单的 key/value 元组列表，因为对于少量元素，它的性能可能优于地图。如果您的测量表明您应该使用列表，那么类似的折叠也适用。

Answer 2

-module(test).
-author("andre").

%% API
-export([init/0]).

init() ->
    TheMap = build(maps:new(), 24),
    io:format("Map: ~p~n", [TheMap]),
    List = maps:to_list(TheMap),
    io:format("List: ~p~n", [List]),

    Fun = fun({_, {_, V1, _}} = Element, {_, {_, V2, _}}) when V1 < V2 ->
      Element;
       (_, Res) ->
      Res
    end,

    Res = lists:foldl(Fun, hd(List),  tl(List)),
    io:format("Res: ~p~n", [Res]).


build(MyMap, Count) when Count == 0 ->
    MyMap;
build(MyMap, Count) ->
    NewMap = maps:put(Count, {random:uniform(100), random:uniform(100), random:uniform(100)}, MyMap),
    build(NewMap, Count - 1).

您可以使用maps:to_list/1 to convert the map to a list, then you can use lists:foldl/3计算最小值。

查找地图中的最小值

Find the minimum value in a map

erlang