быстрый и параллельный алгоритм расчета частоты в elixir - PullRequest
Новая
       73

быстрый и параллельный алгоритм расчета частоты в elixir

0 голосов
/ 05 мая 2020

У меня есть два больших списка, длина элементов которых не постоянна. Каждый список включает миллионы пунктов. И я хочу подсчитать частоту элементов first list в second list!

Например: 

a = [[c, d], [a, b, e]]
b = [[a, d, c], [e, a, b], [a, d], [c, d, a]]

# expected result of calculate_frequency(a, b) is %{[c, d] => 2, [a, b, e] => 1} Or [{[c, d], 2}, {[a, b, e], 1}]

Из-за большого размера списков я бы хотел, чтобы этот процесс делаться одновременно. Итак, я написал эту функцию: 

  def calculate_frequency(items, data_list) do
    items
    |> Task.async_stream(
      fn item ->
        frequency =
          data_list
          |> Enum.reduce(0, fn data_row, acc ->
            if item -- data_row == [] do
              acc + 1
            else
              acc
            end
          end)

        {item, frequency}
      end,
      ordered: false
    )
    |> Enum.reduce([], fn {:ok, merged}, merged_list -> [merged | merged_list] end)
  end

Но этот алгоритм медленный. Что мне делать, чтобы сделать это быстро?

PS : Пожалуйста, не учитывайте тип входов и выходов, важна скорость выполнения.

Ответы [ 3 ]

0 голосов
/ 05 мая 2020

Я бы начал с нормализации данных, которые вы хотите сравнить, чтобы простая проверка на равенство могла определить, «равны ли два элемента», как вы бы это определили. Основываясь на вашем коде, я бы предположил, что Enum.sort/1 сработает, хотя MapSet.new/1 или функция, возвращающая карту, может сравнивать быстрее, если она соответствует вашему варианту использования. 

defp normalize(item) do
  Enum.sort(item)
end

def calculate_frequency(items, data_list) do
  data_list = Enum.map(data_list, &normalize/1)
  items = Enum.map(items, &normalize/1)
end

Если вы собираетесь чтобы получить большинство частот из списка данных, я бы затем вычислил все частоты для списка данных. В Elixir 1.10 были представлены Enum.frequencies/1 и Enum.frequencies_by/2, но при желании вы можете сделать это с уменьшением. 

def calculate_frequency(items, data_list) do
  data_frequencies = Enum.frequencies_by(data_list, &normalize/1) # does map for you

  Map.new(items, &Map.get(data_frequencies, normalize(&1), 0)) # if you want result as map
end

Я не проводил никаких тестов для своего или вашего кода. Если вы хотели сделать больше асинхронных вещей, вы могли бы заменить свое отображение на Task.async_stream/3, и вы могли бы заменить свой вызов частот комбинацией Stream.chunk_every/2, Task.async_stream/3 (где Enum.frequencies/1 - функция) и Map.merge/3.

0 голосов
/ 06 мая 2020

Не уверен, что это достаточно быстро, и уж точно не одновременно. Это O(m + n), где m - размер items, а n - размер data_list. Я не могу найти более быстрый параллельный способ, потому что объединение результатов всех подпроцессов также требует времени. 

data_list
|> Enum.reduce(%{}, fn(item, counts)-> 
  Map.update(counts, item, 1, &(&1 + 1)) 
end)
|> Map.take(items)

К вашему сведению, одновременное выполнение действий не обязательно означает выполнение действий параллельно. Если у вас только одно ядро ​​ЦП, параллелизм фактически замедляет работу, потому что одно ядро ​​ЦП может выполнять только одну задачу за раз.

0 голосов
/ 05 мая 2020

Поместите один список в MapSet.

Go через второй список и посмотрите, есть ли каждый элемент в MapSet.

Это линейно в длины списков, и обе операции должны иметь возможность распараллеливаться.

...