Как хранить двоичные данные, когда вы только заботитесь о скорости?

Question

У меня есть N точек в измерениях D, где N - 1 миллион и D 100. Все мои точки имеют двоичные координаты, т. Е. {0, 1}^D, и меня интересует только скорость.

В настоящее время в моей реализации используется std::vector<int>. Мне интересно, могу ли я выиграть с точки зрения более быстрого выполнения, изменив мой data-structure. Я делаю только вставки и поиск (я не меняю биты).

Все связанные вопросы Я нашел упоминание std::vector<char>, std::vector<bool> и std::bitset, но все упоминания о преимуществах пространства, которые следует использовать, можно получить с помощью таких структур.

Какова структура данных, когда скорость является главной проблемой для двоичных данных на C++?

---

Я намерен заселить свою структуру данных с двоичными данными, а затем сделать много смежных запросов (я имею в виду, что я на самом деле не заботиться о я-я координата точки, если я доступ точка I будет иметь доступ ко всем ее координатам непрерывно). Я вычислим Хэмминг расстояние между собой.

Answer 1

Местность ссылки, вероятно, будет движущей силой. Поэтому довольно очевидно, что вы представляете координаты D одной точки в качестве непрерывного битребектора. std::bitset<D> было бы логичным выбором.

Однако следующая важная вещь, которую нужно осознать, заключается в том, что вы видите, что местность выгодна легко до 4 КБ. Это означает, что вы не должны выбирать одну точку и сравнивать ее со всеми остальными точками N-1. Вместо этого группируйте точки в наборах по 4 КБ каждый и сравнивайте эти группы. Оба способа: O(N*N), но второй будет намного быстрее.

Возможно использование бинарного разряда O(N*N) с использованием неравенства треугольника - Hamming(a,b)+Hamming(b,c) >= Hamming (a,c). Мне просто интересно, как. Вероятно, это зависит от того, как вы хотите получить результат. Наивный выход был бы N * N множеством расстояний, и это неизбежно O(N*N).

Answer 2

Если значения независимо, равномерно распределены, и вы хотите найти расстояние Хэмминга между двумя независимо выбранными случайно выбранными точками, наиболее эффективным расположением является упакованный массив бит.

Этот упакованный массив идеально будет разбит на самый большой размер блока, над которым работает ваша инструкция popcnt: 64 бит. Расстояние от помех составляет popcnt(x_blocks[i]^y_blocks[i]). На процессорах с эффективными неравномерными доступами, выравнивание байтов с негладными чтениями, вероятно, будет наиболее эффективным. На процессорах, в которых неуравновешенные чтения подвергаются штрафу, следует подумать о том, стоит ли надбавка на память выровненных строк быстрее.

Answer 3

Я написал простую программу для заполнения и смежно доступ к структуре данных с бинарными данными:

1. std::vector<int>
2. std::vector<char>
3. std::vector<bool>
4. std::bitset

Я использовал свой Time measurements. Я использовал -O3 оптимизации флаг, N = 1 мил и D = 100.

Это код для векторов:

#include <vector> 
#include <iostream> 
#include <random> 
#include <cmath> 
#include <numeric> 
#include <functional> //plus, equal_to, not2 

#include <ctime> 
#include <ratio> 
#include <chrono> 

#define T int 

unsigned int hd(const std::vector<T>& s1, const std::vector<T>::iterator s2) 
{ 
    return std::inner_product(
     s1.begin(), s1.end(), s2, 
     0, std::plus<unsigned int>(), 
     std::not2(std::equal_to<std::vector<T>::value_type>()) 
    ); 
} 


std::uniform_int_distribution<int> uni_bit_distribution(0, 1); 
std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count()); 

// g++ -Wall -O3 bitint.cpp -o bitint 
int main() 
{ 
    const int N = 1000000; 
    const int D = 100; 
    unsigned int hamming_dist[N] = {0}; 
    unsigned int ham_d[N] = {0}; 

    std::vector<T> q; 
    for(int i = 0; i < D; ++i) 
     q.push_back(uni_bit_distribution(generator)); 

    using namespace std::chrono; 
    high_resolution_clock::time_point t1 = high_resolution_clock::now(); 


    std::vector<T> v; 
    v.resize(N * D); 
    for(int i = 0; i < N; ++i) 
     for(int j = 0; j < D; ++j) 
      v[j + i * D] = uni_bit_distribution(generator); 


    high_resolution_clock::time_point t2 = high_resolution_clock::now(); 

    duration<double> time_span = duration_cast<duration<double> >(t2 - t1); 

    std::cout << "Build " << time_span.count() << " seconds.\n"; 

    t1 = high_resolution_clock::now(); 

    for(int i = 0; i < N; ++i) 
     for(int j = 0; j < D; ++j) 
     hamming_dist[i] += (v[j + i * D] != q[j]); 

    t2 = high_resolution_clock::now(); 
    time_span = duration_cast<duration<double> >(t2 - t1); 
    std::cout << "No function hamming distance " << time_span.count() << " seconds.\n"; 

    t1 = high_resolution_clock::now(); 

    for(int i = 0; i < N; ++i) 
     ham_d[i] = hd(q, v.begin() + (i * D)); 

    t2 = high_resolution_clock::now(); 
    time_span = duration_cast<duration<double> >(t2 - t1); 
    std::cout << "Yes function hamming distance " << time_span.count() << " seconds.\n"; 

    return 0; 
} 

Код для std::bitset могут быть найдены в: XOR bitset when 2D bitset is stored as 1D

Для std::vector<int> Я получил:

Build 3.80404 seconds. 
No function hamming distance 0.0322335 seconds. 
Yes function hamming distance 0.0352869 seconds. 

Для std::vector<char> я получил:

Build 8.2e-07 seconds. 
No function hamming distance 8.4e-08 seconds. 
Yes function hamming distance 2.01e-07 seconds. 

Для std::vector<bool> я получил:

Build 4.34496 seconds. 
No function hamming distance 0.162005 seconds. 
Yes function hamming distance 0.258315 seconds. 

Для std:bitset я получил:

Build 4.28947 seconds. 
Hamming distance 0.00385685 seconds. 

---

std::vector<char> кажется победителем.