Какой самый быстрый способ сделать XOR ОЧЕНЬ много двоичных массивов в Python? - PullRequest
Новая
       45

Какой самый быстрый способ сделать XOR ОЧЕНЬ много двоичных массивов в Python?

0 голосов
/ 31 мая 2018

Мне поручено вычислить расстояния Хэмминга между одномерными двоичными массивами в двух группах - группе из 3000 массивов и группе из 10000 массивов, и каждый массив имеет длину 100 элементов (битов).Так что это расчеты 3000x10000 HD для 100-битных объектов. И все, что нужно сделать не более чем за дюжину минут

Вот лучшее из того, что я придумал 

#X - 3000 by 100 bool np.array 
#Y - 10000 by 100 bool np.array
hd = []
i=1
for x in X:
    print("object nr " + str(i) + "/" + str(len(X)))
    arr = np.array([x] * len(Y)) 
    C = Y^arr # just xor this array by all the arrays in the other group simultainously
    hd.append([sum(c) for c in C]) #add up all the bits to get the hamming distance
    i+=1

return np.array(hd)

И это все ещена это уйдет 1-1,5 часа.Как мне сделать это быстрее?

Ответы [ 3 ]

0 голосов
/ 31 мая 2018

IIUC, вы можете использовать np.logical_xor и составление списка: 

result = np.array([[np.logical_xor(X[a], Y[b].T).sum() for b in range(len(Y))] 
                                                       for a in range(len(X))])

Вся операция выполняется на моем компьютере за 7 секунд. 

0:00:07.226645
0 голосов
/ 31 мая 2018

На случай, если вы не ограничены использованием Python, это решение на C ++, использующее bitset: 

#include <iostream>
#include <bitset>
#include <vector>
#include <random>
#include <chrono>

using real = double;

std::mt19937_64 rng;
std::uniform_real_distribution<real> bitset_dist(0, 1);
real prob(0.75);

std::bitset<100> rand_bitset()
{
    std::bitset<100> bitset;
    for (size_t idx = 0; idx < bitset.size(); ++idx)
    {
         bitset[idx] = (bitset_dist(rng) < prob) ? true : false;
    }
    return std::move(bitset);
}

int main()
{
    rng.seed(std::chrono::high_resolution_clock::now().time_since_epoch().count());

    size_t v1_size(3000);
    size_t v2_size(10000);

    std::vector<size_t> hd;
    std::vector<std::bitset<100>> vec1;
    std::vector<std::bitset<100>> vec2;
    vec1.reserve(v1_size);
    vec2.reserve(v2_size);
    hd.reserve(v1_size * v2_size); /// Edited from hd.reserve(v1_size);

    for (size_t i = 0; i < v1_size; ++i)
    {
        vec1.emplace_back(rand_bitset());
    }
    for (size_t i = 0; i < v2_size; ++i)
    {
        vec2.emplace_back(rand_bitset());
    }

    std::cout << "vec1 size: " << vec1.size() << '\n'
              << "vec2 size: " << vec2.size() << '\n';

    auto start(std::chrono::high_resolution_clock::now());
    for (const auto& b1 : vec1)
    {
        for (const auto& b2 : vec2)
        {
            /// Count only the bits that are set and store them
            hd.emplace_back((b1 ^ b2).count());
        }
    }
    auto time(std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start).count());

    std::cout << vec1.size() << " x " << vec2.size()
              << " xor operations on 100 bits took " << time << " ms\n";
    return 0;
}

На моей машине вся операция (3000 x 10000)занимает около 300 мс.

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

РЕДАКТИРОВАТЬ: У меня был неправильный размер для вектора HD.Резервирование необходимого объема памяти сокращает время операции до 190 мс, поскольку перемещения исключаются.

0 голосов
/ 31 мая 2018

Вы должны быть в состоянии значительно улучшить скорость суммирования, используя numpy для ее выполнения, вместо использования понимания списка и встроенной функции sum (которая не использует преимущества numpy векторизованных операций).

Просто замените: 

hd.append([sum(c) for c in C])

на: 

# Explicitly use uint16 to reduce memory cost; if array sizes might increase
# you can use uint32 to leave some wiggle room
hd.append(C.sum(1, dtype=np.uint16))

, который для двумерного массива возвратит новый одномерный массив, где каждое значение является суммойсоответствующая строка (благодаря указанию она должна работать на axis 1).Например: 

>>> arr = np.array([[True,False,True], [False,False,True], [True, True,True]], dtype=np.bool)
>>> arr.sum(1, np.uint16)
array([ 2, 1, 3], dtype=uint16)

Так как он выполняет всю работу на уровне C за одну операцию без преобразований типов (вместо вашего первоначального подхода, который требует цикл уровня Python, который работает с каждой строкой, то неявныйЦикл, который, в то время как на уровне C, все еще должен неявно преобразовывать каждое значение numpy одно за другим из np.bool в уровень Python int s просто для их суммирования), это должно выполняться существенно быстрее для масштабов массива, которые выdescription.

Примечание: хотя это и не источник ваших проблем с производительностью, нет никаких причин, чтобы вручную поддерживать значение индекса;enumerate может сделать это быстрее и проще.Просто замените: 

i=1
for x in X:
    ... rest of loop ...
    i+=1

на: 

for i, x in enumerate(X, 1):
    ... rest of loop ...

, и вы получите то же поведение, но немного быстрее, в целом более кратким и чище.

...