?

Log in

No account? Create an account

Интервьюшную загадку заганули - Общество дровосеков Бердичева по изучению Мишны

Apr. 14th, 2016

09:28 am - Интервьюшную загадку заганули

Previous Entry Share Next Entry



Дан массив целых неотрицательных чисел. Требуется как можно эффективнее найти сумму попарных хэмминговых расстояний между ними.

Upd: Раскрыл все комменты. Ожидаемый ответ был эквивалентен этому

Tags:

Comments:

[User Picture]
From:sab123
Date:April 14th, 2016 04:46 pm (UTC)
(Link)
Попарных - это как? Соседние числа? Или каждое с каждым?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 14th, 2016 04:50 pm (UTC)
(Link)
Каждое с каждым, конечно.
(Reply) (Parent) (Thread)
[User Picture]
From:lev
Date:April 14th, 2016 04:51 pm (UTC)
(Link)
define "хэмминговых расстояний" plz
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 14th, 2016 05:00 pm (UTC)
(Link)
См. ниже.
(Reply) (Parent) (Thread)
[User Picture]
From:mopexod
Date:April 14th, 2016 04:56 pm (UTC)
(Link)
А хэммингово расстояние между двумя числами - количество бит в XOR-е между ними?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 14th, 2016 05:00 pm (UTC)
(Link)
Разумеется.
(Reply) (Parent) (Thread)
[User Picture]
From:excubitus
Date:April 14th, 2016 04:59 pm (UTC)
(Link)
Для каждого разряда по отдельности посчитать. Подсчитать, сколько в младших разрядах нулей и единиц, перемножить, сдвинуть числа вправо. Повторять для всех разрядов, или пока остались ненулевые числа (не уверен, что из этого эффективнее), накапливая результат.
(Reply) (Thread)
[User Picture]
From:kgeorgiy
Date:April 14th, 2016 05:26 pm (UTC)
(Link)
Посчитаем a[i] -- число единиц в i-м бите во всех числах, тогда ответ: b n^2 - sum_i=0..b (a[i]^2 - (n-a[i]^2)), где b -- номер максимального установленного бита.

Видимо, при использовании пирамидальной схемы с битовыми трюками, это можно сделать за O(n+b).
(Reply) (Thread)
[User Picture]
From:alikr
Date:April 14th, 2016 06:56 pm (UTC)
(Link)
Что то типа суммы произведений (суммы в каждом бите x (общее число элементов - сумма в каждом бите))
(Reply) (Thread)
From:ex_juan_gan
Date:April 14th, 2016 06:59 pm (UTC)
(Link)
А можно сначала построить дерево?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 14th, 2016 07:46 pm (UTC)
(Link)
Зачем?
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:sab123
Date:April 14th, 2016 07:18 pm (UTC)
(Link)
Похоже, что оно связано с предыдущей задачей про минимальное нужное количество бит для сложения :-)

В классическом виде алгоритм подсчета бит, который рассматривает слово как массив N однобитных чисел, делит на два массива по N/2 2-битных чисел, складывает и т.д. использует числовое пространство неэффективно. То есть, например, для 32-битного слова после

a = (a & 0x55555555) + ((a>>1) & 0x55555555)

каждое 2-битное число может хранить значения вплоть до 3, а на самом деле они окажутся не больше 2. Поэтому туда можно добавить еще одну половинку расслоенного числа, которая потом пойдет обрабатываться дальше "забесплатно". Если в процессоре есть достаточно регистров, можно выстроить целую пирамиду таких частичных результатов, которые будут добавляться по мере возможности. Xраниться будут что-нибудь типа 32-битного числа/массива (64 бит не надо, у нас нет столько чисел в массиве, и вообще верхнюю категорию достаточно log2(arraysize)), 16-битного, 8-битного, 4-битного, 2-битного, остающейся второй половинки 2-битного.

Но оптимальный порядок сложения будет запутанным, про него надо подумать отдельно.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 14th, 2016 07:47 pm (UTC)
(Link)
Нет, не связано. :) И считать сумму установленных бит в слове для решения задачи не нужно.
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:April 14th, 2016 07:38 pm (UTC)
(Link)
O(числа битов данных) устроит? А то ведь и быстрее можно.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 14th, 2016 07:45 pm (UTC)
(Link)
Интереснее побыстрее, конечно.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:vgramagin
Date:April 14th, 2016 08:33 pm (UTC)
(Link)
Я не очень понимаю, что такое хэммингово расстояние для целых чисел. Оно же для строк.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 14th, 2016 08:46 pm (UTC)
(Link)
Рассмотри числа как битовые строки.
(Reply) (Parent) (Thread)
From:ex_juan_gan
Date:April 14th, 2016 08:46 pm (UTC)
(Link)
А, знаю. use bags
(Reply) (Thread)
[User Picture]
From:cema
Date:April 14th, 2016 11:40 pm (UTC)
(Link)
Is Hamming distance the edit distance on the bitwise representation of the numbers, or something else?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 14th, 2016 11:47 pm (UTC)
(Link)
Not the edit distance. :)
(Reply) (Parent) (Thread)
[User Picture]
From:_guard_
Date:April 15th, 2016 07:56 am (UTC)
(Link)
O(N)*M, если все числа не больше 2^M (что на практике константа, так?):

s = 0
for j in [0...M]:
  k = 0
  for i in [0...N]:
    k += numbers[i] % 2
    numbers[i] = numbers[i] // 2
  s += k * (N - k) # <-- число пар 1 и 0 в j-м разряде


Edited at 2016-04-15 07:57 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 15th, 2016 02:42 pm (UTC)
(Link)
Формально так (и легко можно не модифицировать массив), но интереснее за один проход по массиву.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:b00ter
Date:April 15th, 2016 11:48 am (UTC)
(Link)
Я так понимаю, что неотрицательность - это неспроста, да?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 15th, 2016 02:44 pm (UTC)
(Link)
Раз в целях данной задачи элементы массива не используются в числовом значении, а только как битовые строки, то логично назвать их неотрицательными.
(Reply) (Parent) (Thread)
[User Picture]
From:outputlogic
Date:April 23rd, 2016 07:45 am (UTC)
(Link)
Похоже что надо использовать свойство XOR: (a^b)^(b^c)=a^c.
В процессе прохождения массива, надо накапливать частичные суммы, а также делать ХOR всех накопленных пар по диагонали.
Вот пример для массива {a,b,c,d}
1. a^b
2. a^b^c, b^c
3. a^b^c^d, b^c^d, c^d

В процессе делаем XOR пар по диагонали
(a^b)^(b^c)=a^c
(a^b^c)^(b^c^d)=a^d
(b^c)^(c^d)=b^d
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 23rd, 2016 11:43 pm (UTC)
(Link)
Это получается та же квадратичная сложность. Я раскрыл комменты.
(Reply) (Parent) (Thread)