Elixir/Erlang: быстрый поиск со статической таблицей

Question

В моем приложении мне нужно преобразовать целое число в некоторый член; например:

1 → :red 
2 → :green 
3 → :blue 

таблица является статическим, известно во время компиляции и его индексы колеблются от < 1, п>. Их около 60.

В каком виде должна отображаться таблица, поэтому поиск наиболее быстрый? Dict, HashDict, кортеж (с kernel.elem()), ets, функция с сопоставлением с образцом ...?

Answer 1

Как предложил Юлий Бекманн, в этом случае функции с сопоставлением с образцом должны быть достаточными, поскольку они соответствуют моим измерениям в 5 раз быстрее, чем доступ к карте.

Ниже вы можете найти реализацию того, что вы ищете (ориентир код включен в нижней части):

defmodule TermLookUpByInteger do 
    @term_by_integer %{ 
    1 => :aa, 11 => :ba, 21 => :ca, 31 => :da, 41 => :ea, 51 => :fa, 61 => :ga, 
    2 => :ab, 12 => :bb, 22 => :cb, 32 => :db, 42 => :eb, 52 => :fb, 62 => :gb, 
    3 => :ac, 13 => :bc, 23 => :cc, 33 => :dc, 43 => :ec, 53 => :fc, 63 => :gc, 
    4 => :ad, 14 => :bd, 24 => :cd, 34 => :dd, 44 => :ed, 54 => :fd, 64 => :gd, 
    5 => :ae, 15 => :be, 25 => :ce, 35 => :de, 45 => :ee, 55 => :fe, 65 => :ge, 
    6 => :af, 16 => :bf, 26 => :cf, 36 => :df, 46 => :ef, 56 => :ff, 66 => :gf, 
    7 => :ag, 17 => :bg, 27 => :cg, 37 => :dg, 47 => :eg, 57 => :fg, 67 => :gg, 
    8 => :ah, 18 => :bh, 28 => :ch, 38 => :dh, 48 => :eh, 58 => :fh, 68 => :gh, 
    9 => :ai, 19 => :bi, 29 => :ci, 39 => :di, 49 => :ei, 59 => :fi, 69 => :gi, 
    0 => :aj, 10 => :bj, 20 => :cj, 30 => :dj, 40 => :ej, 50 => :fj, 60 => :gj, 
    } 

    @doc """ 
    iex> TermLookUpByInteger.lookup_pmf(2) 
    :ab 
    """ 
    def lookup_pmf(int), do: do_lookup(int) 

    for {int, term} <- @term_by_integer do 
    defp do_lookup(unquote(int)), do: unquote(term) 
    end 

    @doc """ 
    iex> TermLookUpByInteger.lookup_m(3) 
    :ac 
    """ 
    def lookup_m(int), do: @term_by_integer[int] 
end 

# Benchmark: 

n = 1_000_000 
range = 1..(n) 
measure = fn fun -> :timer.tc(fn -> for _ <- range, do: fun.() end) end 
{time_pmf, _result} = measure.(fn -> TermLookUpByInteger.lookup_pmf(:random.uniform(60)) end) 
{time_m, _result} = measure.(fn -> TermLookUpByInteger.lookup_m(:random.uniform(60)) end) 

IO.puts "      Sample size: #{n}" 
IO.puts "Pattern matching functions lookup: #{time_pmf/1000} ms" 
IO.puts "      Map lookup: #{time_m/1000} ms" 
IO.puts "    Absolute Difference: #{(time_pmf-time_m)/1000} ms" 
IO.puts "    Relative Difference: #{round((time_pmf-time_m)/time_m*100)}%" 
IO.puts "       Faster: x #{Float.round(time_m/time_pmf, 2)} times" 

Результаты:

     Sample size: 1000000 
Pattern matching functions lookup: 447.6 ms 
         Map lookup: 2423.517 ms 
       Absolute Difference: -1975.917 ms 
       Relative Difference: -82% 
          Faster: x 5.41 times 

Я надеюсь, что будет полезно.

Answer 2

Если карта полностью статична и не изменится, вы можете использовать сгенерированное соответствие шаблонов. Это будет самый быстрый способ интегрировать этот поиск в ваше приложение.

Некоторые примеры кода, считывающие эти сопоставления из внешнего файла: https://github.com/h4cc/slugger/blob/master/lib/slugger.ex#L69-72 Вместо внешнего файла данные исходной карты могут храниться в @attribute.

Даже если в ходе выполнения потребуются новые сопоставления, их можно обработать с помощью сопоставления с шаблоном-шаблоном, выполняющего поиск в HashDict.

Answer 3

Если вы полагаетесь на быстрый доступ ко многим процессам, то mochiglobal может быть ответом. Это сложный постоянный пул, который сохраняет ключи и значения как функции в модуле. Каждый раз, когда вы делаете put/2, модуль перекомпилируется (он медленный, но в вашем случае это не имеет значения). При таком подходе value не копируется в кучу процесса, так как это вызов функции. Здесь лучше explanation.