Есть ли способ улучшить скорость создания списка с неповторяющимися случайными числами в Elixir? - PullRequest
Новая
       11

Есть ли способ улучшить скорость создания списка с неповторяющимися случайными числами в Elixir?

1 голос
/ 31 января 2020

Я ищу возможность улучшить скорость алгоритма: 

{k, _} = Integer.parse IO.gets("Amount of generated numbers? ")
{n, _} = Integer.parse IO.gets("What is the highest number which can be generated? ")

{:ok, time1} = DateTime.now("Etc/UTC")

numbers = Enum.to_list(1..n)
answer = Enum.reduce(1..k, [], fn _t, a -> [Enum.random(numbers -- a)] ++ a end)

{:ok, time2} = DateTime.now("Etc/UTC")

IO.puts("microsecond diff:")
IO.puts(DateTime.diff(time2, time1, :microsecond))

IO.inspect(answer, charlists: :as_lists)

Мне удалось немного улучшить его, добавив случайное число в массив «а» вместо добавления, также имея отдельный переменная 'numbers' также увеличивает скорость (это совершенно очевидно, но изначально я поместил 'Enum.to_list' в функцию ?). При этом алгоритм Elixir в ~ 100 раз медленнее, чем Python, что делает то же самое (я тестировал для k = 999 и n = 10000): 

import random
from datetime import datetime

k = int(input("Amount of generated numbers? "))
n = int(input("What is the highest number which can be generated? "))

time1 = datetime.now()
numbers = []
for i in range(1, n + 1):
    numbers.append(i)

result = []
for i in range(1, k + 1):
    d_my = random.random()
    r = int(d_my * n)

    result.append(numbers[r])

    numbers[r] = numbers[n - 1]
    n = n - 1
time2 = datetime.now()
print(time2 - time1)
# for r in result:
#    print(r, end=" ")

Я не ожидается, что алгоритм Elixir должен быть таким же быстрым, как Python, но любые мысли о том, как я могу улучшить первый, приветствуются.

Ответы [ 2 ]

2 голосов
/ 31 января 2020

Я думаю, что самое большое замедление вашего примера с эликсиром - это сколько вы перечисляете. На каждой итерации вы делаете дорогостоящую разницу, тогда как Enum.random/1, который повторяет список снова.

Редактировать: я собираюсь предоставить более простые примеры и тесты для них

Есть я могу подумать о двух основных подходах:

  1. Повторно генерировать случайное число, пропуская любые повторы.
  2. Выбрать случайные числа из набора оставшихся опций.

Вариант 1 будет быстрее, когда ваш max (то, что я называю вашим вводом "наибольшего числа") значительно больше, чем ваш count (то, что я называю вашим вводом "суммы"). Когда count приближается к max, вариант 2 будет догонять и затем передавать скорость по варианту 1.

Вариант 1

Этот подход сохраняет набор уже выбранных чисел и проверяет его. как это порождает новые. Самый большой фактор, определяющий производительность - столкновения. Когда count мало по сравнению с max, столкновения менее вероятны, и выбрасывается меньшее число. По мере приближения count к max коллизии становятся все более вероятными, и тратится много времени на генерирование чисел, которые будут выбрасываться.

Мой первоначальный ответ был более сложным примером такого подхода. Наш сторонник этого подхода в приведенном ниже тесте может быть довольно простым. 

defmodule RandUniq.Stream do
  @behaviour RandUniq

  @impl RandUniq
  def take(count, max) do
    fn -> :random.uniform(max) end
    |> Stream.repeatedly()
    |> Stream.uniq()
    |> Enum.take(count)
  end
end

Вариант 2

Общие реализации этого подхода создают новую, рандомизированную структуру данных на основе max, которая тогда можно просто взять count из него. Это требует больших начальных затрат, поскольку каждый элемент размещается в случайном порядке, что может быть расточительным для небольшого count по сравнению с max. Тем не менее, работа для большого count в основном такая же, как и для маленького, так что именно в этом и заключается этот подход.

Мы включим пару чемпионов для этого подхода на основе Enum.take_random/2 и Enum.shuffle/1. 

defmodule RandUniq.TakeRandom do
  @behaviour RandUniq

  @impl RandUniq
  def take(count, max) do
    Enum.take_random(1..max, count)
  end
end

defmodule RandUniq.Shuffle do
  @behaviour RandUniq

  @impl RandUniq
  def take(count, max) do
    1..max
    |> Enum.shuffle()
    |> Enum.take(count)
  end
end

Контроль

Для теста давайте также включим оригинал. 

defmodule RandUniq.Control do
  @behaviour RandUniq

  @impl RandUniq
  def take(count, max) do
    numbers = Enum.to_list(1..max)

    Enum.reduce(1..count, [], fn _t, a ->
      [Enum.random(numbers -- a)] ++ a
    end)
  end
end

Тест

Вот как на моем автомате (входные данные вида count / max): 

##### With input 1000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Stream           1404.78        0.71 ms    ±17.04%        0.67 ms        1.07 ms
Elixir.RandUniq.TakeRandom        247.34        4.04 ms     ±4.77%        3.99 ms        4.65 ms
Elixir.RandUniq.Shuffle           167.64        5.96 ms    ±13.41%        5.83 ms        8.49 ms
Elixir.RandUniq.Control             0.33     3013.59 ms     ±0.63%     3013.59 ms     3026.97 ms

Comparison:
Elixir.RandUniq.Stream           1404.78
Elixir.RandUniq.TakeRandom        247.34 - 5.68x slower +3.33 ms
Elixir.RandUniq.Shuffle           167.64 - 8.38x slower +5.25 ms
Elixir.RandUniq.Control             0.33 - 4233.43x slower +3012.87 ms

##### With input 2000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Stream            718.81        1.39 ms     ±9.76%        1.35 ms        1.90 ms
Elixir.RandUniq.TakeRandom        184.45        5.42 ms     ±8.14%        5.33 ms        6.73 ms
Elixir.RandUniq.Shuffle           162.37        6.16 ms    ±11.64%        6.03 ms        8.67 ms
Elixir.RandUniq.Control            0.170     5897.41 ms     ±0.00%     5897.41 ms     5897.41 ms

Comparison:
Elixir.RandUniq.Stream            718.81
Elixir.RandUniq.TakeRandom        184.45 - 3.90x slower +4.03 ms
Elixir.RandUniq.Shuffle           162.37 - 4.43x slower +4.77 ms
Elixir.RandUniq.Control            0.170 - 4239.14x slower +5896.02 ms

##### With input 3000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Stream            448.74        2.23 ms     ±8.41%        2.20 ms        2.80 ms
Elixir.RandUniq.Shuffle           166.81        5.99 ms    ±11.74%        5.86 ms        8.44 ms
Elixir.RandUniq.TakeRandom        162.07        6.17 ms     ±5.27%        6.12 ms        7.18 ms
Elixir.RandUniq.Control            0.112     8951.54 ms     ±0.00%     8951.54 ms     8951.54 ms

Comparison:
Elixir.RandUniq.Stream            448.74
Elixir.RandUniq.Shuffle           166.81 - 2.69x slower +3.77 ms
Elixir.RandUniq.TakeRandom        162.07 - 2.77x slower +3.94 ms
Elixir.RandUniq.Control            0.112 - 4016.91x slower +8949.31 ms

##### With input 4000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Stream            293.83        3.40 ms     ±9.04%        3.35 ms        4.39 ms
Elixir.RandUniq.Shuffle           173.81        5.75 ms    ±10.26%        5.64 ms        7.54 ms
Elixir.RandUniq.TakeRandom        138.75        7.21 ms     ±8.61%        7.11 ms        9.26 ms
Elixir.RandUniq.Control           0.0865    11566.12 ms     ±0.00%    11566.12 ms    11566.12 ms

Comparison:
Elixir.RandUniq.Stream            293.83
Elixir.RandUniq.Shuffle           173.81 - 1.69x slower +2.35 ms
Elixir.RandUniq.TakeRandom        138.75 - 2.12x slower +3.80 ms
Elixir.RandUniq.Control           0.0865 - 3398.48x slower +11562.71 ms

##### With input 5000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Stream            216.28        4.62 ms     ±7.90%        4.60 ms        5.66 ms
Elixir.RandUniq.Shuffle           168.73        5.93 ms    ±10.47%        5.83 ms        7.93 ms
Elixir.RandUniq.TakeRandom        126.83        7.88 ms     ±6.92%        7.81 ms        9.17 ms
Elixir.RandUniq.Control           0.0687    14556.00 ms     ±0.00%    14556.00 ms    14556.00 ms

Comparison:
Elixir.RandUniq.Stream            216.28
Elixir.RandUniq.Shuffle           168.73 - 1.28x slower +1.30 ms
Elixir.RandUniq.TakeRandom        126.83 - 1.71x slower +3.26 ms
Elixir.RandUniq.Control           0.0687 - 3148.10x slower +14551.37 ms

##### With input 6000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Stream            176.27        5.67 ms     ±6.76%        5.61 ms        6.80 ms
Elixir.RandUniq.Shuffle           172.27        5.80 ms     ±9.31%        5.73 ms        7.34 ms
Elixir.RandUniq.TakeRandom        115.76        8.64 ms    ±11.56%        8.66 ms       10.86 ms
Elixir.RandUniq.Control           0.0635    15740.88 ms     ±0.00%    15740.88 ms    15740.88 ms

Comparison:
Elixir.RandUniq.Stream            176.27
Elixir.RandUniq.Shuffle           172.27 - 1.02x slower +0.132 ms
Elixir.RandUniq.TakeRandom        115.76 - 1.52x slower +2.97 ms
Elixir.RandUniq.Control           0.0635 - 2774.60x slower +15735.20 ms

##### With input 7000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Shuffle           171.13        5.84 ms    ±10.26%        5.70 ms        7.77 ms
Elixir.RandUniq.Stream            140.55        7.11 ms     ±9.16%        7.10 ms        8.84 ms
Elixir.RandUniq.TakeRandom        103.55        9.66 ms     ±9.93%        9.92 ms       11.36 ms
Elixir.RandUniq.Control           0.0561    17837.14 ms     ±0.00%    17837.14 ms    17837.14 ms

Comparison:
Elixir.RandUniq.Shuffle           171.13
Elixir.RandUniq.Stream            140.55 - 1.22x slower +1.27 ms
Elixir.RandUniq.TakeRandom        103.55 - 1.65x slower +3.81 ms
Elixir.RandUniq.Control           0.0561 - 3052.52x slower +17831.30 ms

##### With input 8000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Shuffle           172.44        5.80 ms     ±9.72%        5.68 ms        7.46 ms
Elixir.RandUniq.Stream            109.34        9.15 ms    ±10.45%        8.99 ms       11.37 ms
Elixir.RandUniq.TakeRandom         90.51       11.05 ms     ±9.95%       11.11 ms       13.33 ms
Elixir.RandUniq.Control           0.0507    19712.01 ms     ±0.00%    19712.01 ms    19712.01 ms

Comparison:
Elixir.RandUniq.Shuffle           172.44
Elixir.RandUniq.Stream            109.34 - 1.58x slower +3.35 ms
Elixir.RandUniq.TakeRandom         90.51 - 1.91x slower +5.25 ms
Elixir.RandUniq.Control           0.0507 - 3399.20x slower +19706.22 ms

##### With input 9000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Shuffle           163.33        6.12 ms    ±10.87%        6.01 ms        8.20 ms
Elixir.RandUniq.TakeRandom         87.59       11.42 ms    ±12.70%       11.59 ms       14.92 ms
Elixir.RandUniq.Stream             77.42       12.92 ms     ±7.04%       12.91 ms       15.04 ms
Elixir.RandUniq.Control           0.0458    21839.19 ms     ±0.00%    21839.19 ms    21839.19 ms

Comparison:
Elixir.RandUniq.Shuffle           163.33
Elixir.RandUniq.TakeRandom         87.59 - 1.86x slower +5.29 ms
Elixir.RandUniq.Stream             77.42 - 2.11x slower +6.79 ms
Elixir.RandUniq.Control           0.0458 - 3567.03x slower +21833.07 ms

##### With input 10000 / 10000 #####
Name                                 ips        average  deviation         median         99th %
Elixir.RandUniq.Shuffle           152.63        6.55 ms    ±15.19%        6.35 ms       11.46 ms
Elixir.RandUniq.TakeRandom         99.66       10.03 ms    ±13.20%        9.72 ms       13.49 ms
Elixir.RandUniq.Stream             26.56       37.65 ms    ±11.88%       36.73 ms       55.84 ms
Elixir.RandUniq.Control           0.0420    23822.66 ms     ±0.00%    23822.66 ms    23822.66 ms

Comparison:
Elixir.RandUniq.Shuffle           152.63
Elixir.RandUniq.TakeRandom         99.66 - 1.53x slower +3.48 ms
Elixir.RandUniq.Stream             26.56 - 5.75x slower +31.10 ms
Elixir.RandUniq.Control           0.0420 - 3635.98x slower +23816.10 ms

Кажется, RandUniq.Stream, наш чемпион по варианту 1, остается самым быстрым, пока count не достигнет 60-70 % от max (по крайней мере, в этом масштабе). Затем RandUniq.Shuffle, основываясь на ответе @ zwipp ie, выходит на первое место.

0 голосов
/ 31 января 2020

Как насчет: 

(1..n) |> Enum.shuffle |> Enum.take(k)

Кажется, что работает довольно быстро.

Обновление:

Я протестировал это решение и сравнил его с Enum.take_random производительностью. Последний в два раза быстрее: 

Name                   ips        average  deviation         median         99th %
take_random         507.13        1.97 ms     ±4.22%        1.96 ms        2.37 ms
shuffle_take        251.84        3.97 ms     ±7.76%        3.92 ms        4.83 ms

Comparison:
take_random         507.13
shuffle_take        251.84 - 2.01x slower +2.00 ms
...