Bit-Count или вес Хэмминга BitString в Elixir?

Пожалуйста, как мы можем efficiently вычислить вес битовой строки в эликсире?

Пример: 0b0101101001 имеет вес Хэмминга 5 (т. Е. Установлено 5 бит)

Моя попытка:

iex> Enum.count(Integer.to_char_list(n,2),&(&1===49))

elixir hammingweight bitstring
person Charles Okwuagwu    schedule 02.12.2015    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Вот более эффективное решение, которое (для меня) также более четко показывает намерение:

for(<<bit::1 <- :binary.encode_unsigned(n)>>, do: bit) |> Enum.sum

Тест с использованием программы benchfella со 100 000 двоичных цифр:

Benchfella.start

defmodule HammingBench do
  use Benchfella

  @n Stream.repeatedly(fn -> Enum.random [0, 1] end)
    |> Enum.take(100_000)
    |> Enum.join
    |> String.to_integer(2)

  bench "CharlesO" do
    Enum.count(Integer.to_char_list(@n,2),&(&1===49)) 
  end

  bench "Patrick Oscity" do
    for(<<bit::1 <- :binary.encode_unsigned(@n)>>, do: bit) |> Enum.sum
  end
end

Результаты тестов:

$ mix bench
Compiled lib/hamming_bench.ex
Generated hamming_bench app
Settings:
  duration:      1.0 s

## HammingBench
[20:12:03] 1/2: Patrick Oscity
[20:12:06] 2/2: CharlesO

Finished in 8.4 seconds

## HammingBench
Patrick Oscity         500   4325.79 µs/op
CharlesO                 1   5754094.00 µs/op
person Patrick Oscity    schedule 02.12.2015
comment
Спасибо, что поделились, 500: 1 :( - person Charles Okwuagwu; 02.12.2015
comment
Не могли бы вы пролить свет на то, почему ваша реализация намного быстрее, это действительно поможет. - person Charles Okwuagwu; 02.12.2015
comment
Медленная часть вашей реализации - это преобразование целого числа в список символов. С другой стороны, двоичное сопоставление с образцом сильно оптимизировано. Однако для небольшого количества цифр разница в производительности незначительна. - person Patrick Oscity; 02.12.2015
comment
Совет: если вы поместите код в файл bench/hamming_bench.exs, вам не нужно будет вызывать Benchfella.start вручную. - person Alexei Sholik; 02.12.2015
comment
Для всех, кто читает это, кто хочет понять причины ускорения, см. groups.google.com/forum/ - person Alexei Sholik; 03.12.2015