Интервьюшную загадку заганули

[spamsink]

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

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

Comments

[sab123.livejournal.com]

Попарных - это как? Соседние числа? Или каждое с каждым?

[spamsink]

Каждое с каждым, конечно.

[lev.livejournal.com]

define "хэмминговых расстояний" plz

[spamsink]

См. ниже.

[mopexod.livejournal.com]

А хэммингово расстояние между двумя числами - количество бит в XOR-е между ними?

[spamsink]

Разумеется.

[excubitus.livejournal.com]

Для каждого разряда по отдельности посчитать. Подсчитать, сколько в младших разрядах нулей и единиц, перемножить, сдвинуть числа вправо. Повторять для всех разрядов, или пока остались ненулевые числа (не уверен, что из этого эффективнее), накапливая результат.

[kgeorgiy.livejournal.com]

Посчитаем a[i] -- число единиц в i-м бите во всех числах, тогда ответ: b n^2 - sum_i=0..b (a[i]^2 - (n-a[i]^2)), где b -- номер максимального установленного бита.

Видимо, при использовании пирамидальной схемы с битовыми трюками, это можно сделать за O(n+b).

[alikr.livejournal.com]

Что то типа суммы произведений (суммы в каждом бите x (общее число элементов - сумма в каждом бите))

[juan-gandhi.livejournal.com]

А можно сначала построить дерево?

[spamsink]

Зачем?

[juan-gandhi.livejournal.com]

Разницу между ветками считать.
Впрочем, нет смысла.
Поразбираюсь еще.

[sab123.livejournal.com]

Похоже, что оно связано с предыдущей задачей про минимальное нужное количество бит для сложения :-)

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

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

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

Но оптимальный порядок сложения будет запутанным, про него надо подумать отдельно.

[spamsink]

Нет, не связано. :) И считать сумму установленных бит в слове для решения задачи не нужно.

[kcmamu.livejournal.com]

O(числа битов данных) устроит? А то ведь и быстрее можно.

[spamsink]

Интереснее побыстрее, конечно.

[aa-kir.livejournal.com]

Интересно, а как можно быстрее если каждый бит данных надо прочитать?

[spamsink]

Подразумевается, что операции над числами фиксированной разрядности выполняются за O(1) независимо от количества бит в числах. Поэтому, скажем, обычно считают, что суммирование или перемножение элементов массива требует O(N), будь это 32-битные целые, 64-битные целые или числа с плавающей точкой.

[aa-kir.livejournal.com]

Ну да. При фиксированной разрядности, если есть N чисел, то O(N) - это то же самое, что O(число битов). Так что быстрее чем O(число битов) никак невозможно...

[sab123.livejournal.com]

Кстати, да, вариант посчитать количество единиц и нулей в конкретном бите всех чисел мне в голову приходил, но я его отбросил и не прочухал, что O у него получается линейная от количества чисел при фиксированном размере слова (а при нефиксированном - от числа бит вообще), а не квадратичная как у суммирования (при любых оптимизациях суммирования).

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

for (l = 0; l < arraysize; l += 8) {
    for (k = 0..1) {
        for (j = 0..1) {
            for (i = 0..1) {
                index = i + j*2 + k*4;
                if (index >= arraysize)
                    break;
                v = array[index];
                inter1[0] += v & 0x55;
                inter1[1] += (v>>1) & 0x55;
            }
            inter2[0] += inter1[0] & 0x33;
            inter2[1] += (inter1[0]>>2) & 0x33;
            inter1[0] = 0;

            inter2[2] += inter1[1] & 0x33;
            inter2[3] += (inter1[1]>>2) & 0x33;
            inter1[1] = 0;
        }

        count[0] += inter2[0] & 0x7;
        count[1] += (inter2[0] >> 4) & 0x7;
        inter2[0] = 0;

        count[2] += inter2[1] & 0x7;
        count[3] += (inter2[1] >> 4) & 0x7;
        inter2[1] = 0;

        count[4] += inter2[2] & 0x7;
        count[5] += (inter2[2] >> 4) & 0x7;
        inter2[2] = 0;

        count[6] += inter2[3] & 0x7;
        count[7] += (inter2[3] >> 4) & 0x7;
        inter2[3] = 0;
    }
}

Ну, понятно, что развернутые присваивания можно свернуть в циклы.

А потом сумма будет Sum[for i =0..7](2*count[i]*(arraysize-count[i]))

Впрочем нет, при таких раскладах - не будет логарифмичности. Для логарифмичности нужно делать больше итераций по k и j, чем 2. Гм, надо подумать, сколько их можно делать.

[kcmamu.livejournal.com]

a[0...N-1] -- вход
b[0...log_2 N], c[0...log_2 N] -- рабочие массивы (сперва в них нули)
прочее -- одиночные переменные

for(i = 1; i <= N; i++)
for(d = a[i-1], j = 0; 1; j++) // в среднем крутится раза два 
if(i & (1 << j)) { c[j] = d; break; }
else { e = b[j] ^ c[j] ^ d; d = b[j] & (c[j] | d) | c[j] & d; b[j] = e; c[j] = 0; }

ответ = 0;
for(i = 0; i < разрядность; i++)
{
for(d = j = 0; j <= log_2 N; j++)
d += (!!(b[j] & (1 << i)) + !!(c[j] & (1 << i)) << j;

ответ += d * (N - d);
}

[spamsink]

Я раскрыл комменты. Да, это то, что я имел в виду, хотя и без двухрядного кода тоже было бы правильно. :)

[vgramagin.livejournal.com]

Я не очень понимаю, что такое хэммингово расстояние для целых чисел. Оно же для строк.

[spamsink]

Рассмотри числа как битовые строки.

[juan-gandhi.livejournal.com]

А, знаю. use bags

[cema.livejournal.com]

Is Hamming distance the edit distance on the bitwise representation of the numbers, or something else?

[spamsink]

Not the edit distance. :)

[soloviewoff.livejournal.com]

That is Levenshtein's, another guy's.  Though they match here I think as there are replacements only, no insertions or deletions.

[http://users.livejournal.com/_guard_/]

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-м разряде

[spamsink]

Формально так (и легко можно не модифицировать массив), но интереснее за один проход по массиву.

[http://users.livejournal.com/_guard_/]

А ну да, можно в м-массиве накапливать поразрядно счетчики единиц, потом подсчитать

[spamsink]

Уточню: так, чтобы выполнялось быстрее, чем за O(N*M).

[b00ter.livejournal.com]

Я так понимаю, что неотрицательность - это неспроста, да?

[spamsink]

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

[outputlogic.livejournal.com]

Похоже что надо использовать свойство 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

[spamsink]

Это получается та же квадратичная сложность. Я раскрыл комменты.