оптимизация — вес Хэмминга для вектора & lt; int & gt; Переполнение стека

Question

оптимизация — вес Хэмминга для вектора & lt; int & gt; Переполнение стека

Я работаю над весом Хэмминга для вектора, и что я делаю, так это линейно считая все 1 в векторе, есть ли более эффективный способ?

int HammingWeight(vector<int> a){
int HG=0;

for(int i=0; i<a.size(); i++){
if(a[i] == 1)
HG++;
}
return HG;
}

0

c++hamming-distance optimization

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Чтобы рассчитать вес Хэмминга, вам нужно посетить каждый элемент, предоставив вам O (n) лучший случай, чтобы сделать ваш цикл таким же эффективным, каким он становится при дисконтировании микрооптимизаций.

Однако сам вызов вашей функции крайне неэффективен: вы передаете вектор по значению, в результате чего получается копия всего его содержимого. Эта копия может быть более дорогой, чем остальные функции вместе взятые. Кроме того, в вашей функции нет ничего, что действительно нуждается в этой копии. Так что меняя подпись на int HammingWeight(const std::vector<int>& a) должно сделать вашу функцию намного более эффективной.

На ум приходит еще одна (возможная) оптимизация, если предположить, что vector содержит только единицы и нули (иначе я не понимаю, как ваш код имеет смысл). В этом случае вы можете просто добавить соответствующий элемент вектора к HG, избавляясь от if (сложение обычно намного быстрее, чем ветвление):

 for(size_t i=0; i<a.size(); ++i)
HG+=a[i];

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

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

Также обратите внимание, что оба подхода (прямое суммирование и версия if) также могут быть выражены с использованием стандартной библиотеки:

int HG=std::count(a.begin(), a.end(), 1); делает в основном то же самое, что и ваш код
int HG=std::accumulate(a.begin(), a.end(), 0); будет эквивалентно петле I, упомянутой выше

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

1