Как преобразовать int в список, содержащий быстрое двоичное представление в python? - PullRequest
0 голосов
/ 06 ноября 2018

В настоящее время у меня есть следующая версия, но это мое основное узкое место, и она довольно медленная.

def intToBinary(Input):
    bStrInput = format(Input, "016b")
    bStrInput = list(bStrInput)
    bInput = list(map(int, bStrInput))
    return bInput

есть идеи, как ускорить этот код?

Я использую это в проекте Tensorflow для горячего кодирования преобразования целых чисел. Функция принимает 2-байтовое целое число (в диапазоне [0, 65536)) и выводит список целых чисел со значениями 0 и 1:

>>> intToBinary(50411)
[1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1]

Результат передается в тензор с tInput = torch.tensor(bInput, dtype=torch.uint8).

1 Ответ

0 голосов
/ 06 ноября 2018

Ваша версия, слегка улучшенная

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

def intToBinary(Input):
    return list(map(int, format(Input, "016b")))

Pure Python, опция бит-смещения

Тем не менее, вы можете сделать это быстрее, не преобразовывая в строку, а затем снова в целые числа Если вам нужны только биты, используйте битовую манипуляцию:

def int_to_binary(v):
    return [(v >> i) & 1 for i in range(15, -1, -1)]

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

Сравнение скорости с использованием 1000 случайных целых чисел для уменьшения дисперсии до приемлемых уровней:

>>> import sys, platform, psutil
>>> sys.version_info
sys.version_info(major=3, minor=7, micro=0, releaselevel='final', serial=0)
>>> platform.platform(), psutil.cpu_freq().current / 1000, psutil.cpu_count(), psutil.virtual_memory().total // (1024 ** 3)
('Darwin-17.7.0-x86_64-i386-64bit', 2.9, 8, 16)
>>> from timeit import Timer
>>> from random import randrange
>>> testvalues = [randrange(2**16) for _ in range(1000)]
>>> count, total = Timer("for i in tv: t(i)", "from __main__ import intToBinary as t, testvalues as tv").autorange()
>>> (total / count) * (10 ** 3)   # milliseconds
3.2812212200224167
>>> count, total = Timer("for i in tv: t(i)", "from __main__ import int_to_binary as t, testvalues as tv").autorange()
>>> (total / count) * (10 ** 3)   # milliseconds
2.2861225200176705

Так что int_to_binary() примерно в 1,5 раза быстрее, около 2,3 миллисекунды, чтобы получить 1000 результатов, по сравнению с чуть более 3,3 для оптимизированной версии для работы со строками.

На моей машине базовый цикл и вызов функции занимают 7,4 микросекунды:

>>> count, total = Timer("for i in tv: pass", "from __main__ import testvalues as tv; t = lambda i: None").autorange()
>>> (total / count) * (10 ** 3)
0.007374252940062434

, поэтому базовая синхронизация вызовов составляет около 3,27 микросекунд против 2,28 микросекунд для версии с битовой манипуляцией.

Что может сделать Numpy

Если вы используете Tensorflow, у вас также будут доступны простые операции, которые могут преобразовать uint8 в двоичный файл с помощью функции numpy.unpackbits() ; uint16 должен быть 'просмотренным' как uint8 первым:

import numpy as np

def int_to_bits_np(v):
    return np.unpackbits(np.array([v], dtype=np.uint16).view(np.uint8)).tolist()

Это преобразует в массив numy, снова в список целых чисел Python , так что это не так эффективно только для одного значения:

>>> count, total = Timer("for i in tv: t(i)", "from __main__ import int_to_bits_np as t, testvalues as tv").autorange()
>>> (total / count) * (10 ** 3)
2.654717969999183

Быстрее, чем ваша версия, медленнее, чем битовое смещение.

Numpy векторизованный вариант

Вы , вероятно, не хотите преобразовывать обратно в список, так как массив numpy уже имеет правильный тип dtype для вашего тензора. Вы также можете использовать это для большого числа значений ; например, целые 1000 целых чисел на входе:

def int_to_bits_array(varray):
    """Convert an array of uint16 values to binary"""
    return np.unpackbits(varray.reshape(varray.shape[0], 1).view(np.uint8), axis=1)

путь, путь, путь быстрее:

>>> testvalues_array = np.array(testvalues, dtype=np.uint16)
>>> int_to_bits_array(testvalues_array)
array([[1, 1, 0, ..., 1, 1, 0],
       [0, 1, 1, ..., 1, 0, 0],
       [1, 1, 1, ..., 0, 0, 0],
       ...,
       [1, 1, 1, ..., 0, 1, 0],
       [0, 0, 0, ..., 1, 1, 0],
       [0, 0, 0, ..., 0, 0, 0]], dtype=uint8)
>>> count, total = Timer("t(tva)", "from __main__ import int_to_bits_array as t, testvalues_array as tva").autorange()
>>> (total / count) * (10 ** 3)  # milliseconds
0.007919690339913358
>>> (total / count) * (10 ** 6)  # microseconds
7.919690339913359

Да, это 1000 значений, преобразованных в двоичный файл за один шаг, обработка всех значений за 8 микросекунд. Это масштабируется линейно до больших чисел; 1 миллион случайных значений конвертируется менее чем за 8 миллисекунд:

>>> million_testvalues_array = np.random.randint(2 ** 16, size=10 ** 6, dtype=np.uint16)
>>> count, total = Timer("t(tva)", "from __main__ import int_to_bits_array as t, million_testvalues_array as tva").autorange()
>>> (total / count) * (10 ** 3)  # milliseconds
7.9162722200271665
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...