Эффективный способ выполнения битовых перестановок на основе вектора целых чисел?

Question

У меня есть набор 64-битных целых чисел, к которым мне нужно применить определенное количество «операций симметрии».Операция симметрии - это просто серия битовых перестановок, хранящихся в векторе типа int как {i0, i1, i2, ..}, где bit [0] -> bit [i0], bit [1] -> bit [i1]] и т. д. На самом деле я просто использую N первых битов, где N определяется во время выполнения, но в принципе может доходить до 64.

Например, я работаю сN = 4, входное значение - целое число 3 или 0011, и у меня есть 4 операции симметрии, сохраненные в векторе vector symbry_ops

symmetry_ops[0] = {0,1,2,3};
symmetry_ops[1] = {1,2,3,0};
symmetry_ops[2] = {2,3,0,1};
symmetry_ops[4] = {3,0,1,2};

Я хочу функцию, которая возвращает мне 4 целых числа, полученных путем применения этихоперации до 3, то есть 0011, 0110, 1100 и 1001. Пример тривиален, но на практике перестановки могут быть гораздо более сложными, чем просто перемещение влево.

Я написал следующее простое (наивно?)код:

std::vector<unsigned long> apply_symmetries(const std::vector<std::vector<unsigned> > &symmetry_ops, unsigned long state)
{
   unsigned N = symmetry_ops[0].size();
   std::vector<unsigned long> s_moved(symmetry_ops.size(),0);
   for (unsigned i = 0; i < N; i++) {
     unsigned long s_i = (state&(1UL<<i))>>i; // extracts bit i in state
     for (unsigned op = 0; op != symmetry_ops.size(); op++)
       s_moved[op] = s_moved[op]|(s_i<<symmetry_ops[op][i]);
   }
   return s_moved;
}

, который выполняет все операции симметрии для целочисленного «состояния».Я просто иду один за другим в цикле над i, сначала сохраняя его в s_i, а затем перемещая его для каждой операции симметрии.

Правильно знаете, это одна из самых трудоемких частеймоя программа, поскольку типичные размеры - это ~ 100-200 операций симметрии для применения к ~ 10 ^ 10 целым числам, где N около 40. Код работает правильно, но мне интересно, можно ли оптимизировать эту функцию?

Заранее спасибо.

Answer 1

Во-первых, было бы полезно, если бы вы добавили комментарии к своему коду, чтобы объяснить, что к чему.Также выберите описательные имена переменных, не выбирайте 's_i' или 's_moved' для имени переменной, это делает код нечитаемым.«symbry_ops» был хорошим выбором для имени, как и «state», остальные не так уж и много.и следующая операция симметрии отправляет бит x в бит y, объединение этих двух значений аналогично отправке бита i в бит y в одной операции.

Так что начните с циклического выполнения одних операций.

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

identity_op = {0, 1, 2, 3, 4, 5, 6, 7} //vector of int, maps each bit to same bit
previous_op = identity_op
for each op { //op is vector of ints, op[i] maps bit i to op[i]
    //combine op with prev_op to make a new prev_op
    for each i in op { 
        prev_op[i] = op[prev_op[i]] //bit i is mapped by prev_op and then mapped again by op, giving new value for prev_op
    }
} 
combined_op = previous_op
apply combined_op to the bits, this is only place you need to to bit shifting

Ваш код C ++ выглядит хорошо, просто переписайте, чтобы использовать этот новый алгоритм.