Равномерная рекомбинация двоичного представления двух целых чисел - PullRequest
Новая
       6

Равномерная рекомбинация двоичного представления двух целых чисел

1 голос
/ 13 марта 2019

Мне нужно быстро реализовать следующую задачу, желательно в виде функции numba.Я беру два случайных целых числа a & b из списка с именем integerlist и рассматриваю их двоичное представление длины l, например, a=10->1010, b=6->0110.После этого я выполняю равномерное пересечение между двоичными представлениями, и целочисленное значение полученного двоичного числа сохраняется в случайной позиции в integerlist.Равномерная рекомбинация означает, что каждая запись двоичного представления целого числа c берется либо из записи двоичного представления a или b с равной вероятностью, например, 

a=10->1010
b=6 ->0110
      1110 ->c=14

Для этого я пришелсо следующим кодом, который не очень быстрый.В данный момент я пытаюсь получить версию этой функции, но пока не удалось.Не могли бы вы помочь? 

def recombination(integerlist, l):
    N = len(integerlist)
    for x1 in range(N):
        a = integerlist[random.randint(0, N-1)]
        b = integerlist[random.randint(0, N-1)]
        binary_a = list(map(int, numpy.binary_repr(a, width=l)))
        binary_b = list(map(int, numpy.binary_repr(b, width=l)))
        binary_c = [0]*l
        for x2 in range(l):
            if random.random() <= 0.5:
                binary_c[x2] = binary_a[x2]
            else:
                binary_c[x2] = binary_b[x2]
        c = 0
        for bit in binary_c:
            c = (c << 1) | bit
        integerlist[random.randint(0, N-1)] = c

Редактировать: Если я заменю list(map(int, numpy.binary_repr(a, width=l))) на следующую функцию 

@nb.njit
def dec_to_binary_fct(a, l):
    bin_temp = []
    for i in range(l):
        i = l-i-1
        k = a >> i
        if (k & 1):
            bin_temp.append(1)
        else:
            bin_temp.append(0)
    return bin_temp

Я могу поставить @nb.njit перед def recombination(integerlist, l):, которые уже немного повышают производительность.Мне все еще интересно, можно ли увеличить производительность.

1 Ответ

3 голосов
/ 13 марта 2019

Вот способ расчета кроссовера, который, я уверен, быстрее: 

def xover(a, b):
    l = max(a.bit_length(), b.bit_length())
    return a^((a^b)&random.randint(0, (1<<l)-1))

Пояснение:

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