Самый быстрый способ зациклить каждое число с условиями - PullRequest
Новая
       23

Самый быстрый способ зациклить каждое число с условиями

9 голосов
/ 14 октября 2010

Учитывая 64-битное целое число, где последние 52 бита, подлежащие оценке, и первые 12 бит должны игнорироваться, каков самый быстрый способ зацикливания каждой отдельной комбинации, состоящей из 7 бит и всех остальных битов?

Пример:

Первая перестановка: 

0[x57]1111111

Последняя перестановка 

00000000000011111110[x45]

Где 0[xn] означает n отключение (ноль) битов.

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

Рабочее решениене требуется, но некоторый псевдокод подойдет просто:)

Ответы [ 3 ]

10 голосов
/ 14 октября 2010

Думаю, вам будет интересна эта статья: http://realtimecollisiondetection.net/blog/?p=78

Она решит вашу проблему очень эффективно.

4 голосов
/ 14 октября 2010

Вам нужен хороший алгоритм, который перенесет вас от одной перестановки к другой за минимальное время.

Теперь первый алгоритм, который приходит на ум, - это пройти все комбинации с помощью семи циклов.

  • Первый цикл проходит через 52 бита, устанавливая один для следующего цикла.
  • Второй цикл проходит через биты после установленного, устанавливая один для третьего цикла.
  • ... ЭСТ

Это даст вам самую быструю итерацию. Вот некоторый псевдо-код C ++: 

__int64 deck;
int bit1, bit2, bit3, ...;
for (bit1=0;bit1<52-6;bit1++) {
  for (bit2=bit1+1;bit2<52-5;bit2++) {
    ...
      for (bit7=bit6+1;bit7<52;bit7++) {
        deck = (1<<bit1)+(1<<bit2)+(1<<bit3)+...;  // this could be optimized.
        // do whatever with deck
      }
    ...
  }
}

// примечание: 52-6, 52-5, будут предварительно рассчитаны компилятором и доступны для удобства. Вам не нужно беспокоиться об оптимизации этого.

Здесь есть ваше решение. Если вы хотите проверить, что это работает, я всегда уменьшаю его. Например, следование этому алгоритму для 4-битного числа, в котором необходимо установить 2 бита, будет выглядеть так: 

1100
1010
1001
0110
0101
0011
1 голос
/ 14 октября 2010

Я думаю, что есть связь между каждой перестановкой.

alt text

Мы видим, что число увеличивается с перестановкой # с шаблоном.

Эта математика не верна для всех решений, но, возможно, работает для некоторых, надеюсь, для некоторыхуказывая на то, что я имею в виду: 

Permutation 3 difference = ((3%7+1)^2) * (roundUp(3/7) = 16
Permutation 10 difference = ((10%7+1)^2) * (roundUp(10/7) = 32

Таким образом, мы бы зациклились на абсолютных значениях: 

int perm = 1;
for int64 i = 127; perm < totalPermutations
{
    i = i + ((perm%7+1)^2) * (roundUp(perm/7);
    perm++;
}

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

...