Numpy: установка n последних элементов мантисс в двойном массиве - PullRequest
Новая
       59

Numpy: установка n последних элементов мантисс в двойном массиве

0 голосов
/ 10 июля 2019

Вопрос

Предположим, нам дан простой массив arr с двойными числами и небольшим положительным целым числом n.Я ищу эффективный способ установить n наименее значимые записи каждого элемента от arr до 0 или 1.Есть ли ufunc для этого?Если нет, то есть ли подходящие функции C, которые я мог бы применить к элементам из Cython?

Мотивация

Ниже я приведу мотивацию для вопроса.Если вы обнаружите, что ответ на поставленный выше вопрос не нужен для достижения конечной цели, я с удовольствием получу соответствующие комментарии.Затем я создам отдельный вопрос для сортировки.

Мотивация для этого вопроса состоит в том, чтобы реализовать версию np.unique(arr, True), которая принимает параметр относительной толерантности.Таким образом, второй аргумент np.unique важен: мне нужно знать индексы уникальных элементов (первое вхождение!) В исходном массиве.Таким образом, не важно, что элементы отсортированы.

Мне известны вопросы и решения по np.unique с допуском .Однако я не нашел решения, которое также возвращает индексы первых появлений уникальных элементов в исходном массиве.Кроме того, решения, которые я видел, были основаны на сортировке, которая выполняется в O (arr.size log (arr.size)) .Тем не менее, решение с постоянным временем возможно с хэш-картой.

Идея состоит в том, чтобы округлить каждый элемент в arr вверх и вниз и поместить эти элементы в хэш-карту.Если любое из значений уже есть в хэш-карте, запись игнорируется.В противном случае элемент включается в результат.Поскольку вставка и поиск выполняются с постоянным средним временем для хеш-карт, этот метод должен быть быстрее, чем метод, основанный на сортировке в теории.

Ниже найдите мою реализацию на Cython: 

import numpy as np
cimport numpy as np
import cython
from libcpp.unordered_map cimport unordered_map

@cython.boundscheck(False)
@cython.wraparound(False)
def unique_tol(np.ndarray[DOUBLE_t, ndim=1] lower,
               np.ndarray[DOUBLE_t, ndim=1] higher):
    cdef long i, count
    cdef long endIndex = lower.size
    cdef unordered_map[double, short] vals = unordered_map[double, short]()
    cdef np.ndarray[DOUBLE_t, ndim=1] result_vals = np.empty_like(lower)
    cdef np.ndarray[INT_t, ndim=1] result_indices = np.empty_like(lower, 
                                                                  dtype=int)

    count = 0
    for i in range(endIndex): 
        if not vals.count(lower[i]) and not vals.count(higher[i]):

            # insert in result
            result_vals[count] = lower[i]
            result_indices[count] = i

            # put lowerVal and higherVal in the hashMap
            vals[lower[i]]
            vals[higher[i]]

            # update the index in the result
            count += 1

    return result_vals[:count], result_indices[:count]

Этот метод называетсяс соответствующим округлением делает работу.Например, если различия менее 10 ^ -6 будут игнорироваться, мы напишем 

unique_tol(np.round(a, 6), np.round(a+1e-6, 6))

Теперь я хотел бы заменить np.round процедурой относительного округления, основанной на манипулировании мантиссой.Мне известны альтернативные способы относительного округления , но я думаю, что манипулирование мантиссой напрямую должно быть более эффективным и элегантным.(Правда, я не думаю, что увеличение производительности является значительным. Но я был бы заинтересован в решении.)

EDIT

Решение Уоррена Векессера работает какочарование.Однако результат не применим, как я надеялся, поскольку два числа с очень малой разницей могут иметь разные показатели.Объединение мантиссы не приведет к аналогичным числам.Я думаю, что я должен придерживаться относительных решений округления, которые существуют.

Ответы [ 2 ]

2 голосов
/ 10 июля 2019

"Я ищу эффективный способ установить n наименее значимых записей каждого элемента arr на 0 или на 1."

Вы можете создать представление массива с типом данных numpy.uint64, а затем при необходимости манипулировать битами в этом представлении.

Например, я установлю младшие 21 бит в мантиссе этого массива равными 0. 

In [46]: np.set_printoptions(precision=15)                                                            

In [47]: x = np.array([0.0, -1/3, 1/5, -1/7, np.pi, 6.02214076e23])                                   

In [48]: x                                                                                            
Out[48]: 
array([ 0.000000000000000e+00, -3.333333333333333e-01,
        2.000000000000000e-01, -1.428571428571428e-01,
        3.141592653589793e+00,  6.022140760000000e+23])

Создать представление данных в x с типом данных numpy.uint64: 

In [49]: u = x.view(np.uint64)

Взгляните на двоичное представление значений. 

In [50]: [np.binary_repr(t, width=64) for t in u]                                                     
Out[50]: 
['0000000000000000000000000000000000000000000000000000000000000000',
 '1011111111010101010101010101010101010101010101010101010101010101',
 '0011111111001001100110011001100110011001100110011001100110011010',
 '1011111111000010010010010010010010010010010010010010010010010010',
 '0100000000001001001000011111101101010100010001000010110100011000',
 '0100010011011111111000011000010111001010010101111100010100010111']

Установите младшие n биты в 0 и посмотрите еще раз. 

In [51]: n = 21                                                                                       

In [52]: u &= ~np.uint64(2**n-1)                                                              

In [53]: [np.binary_repr(t, width=64) for t in u]                                                     
Out[53]: 
['0000000000000000000000000000000000000000000000000000000000000000',
 '1011111111010101010101010101010101010101010000000000000000000000',
 '0011111111001001100110011001100110011001100000000000000000000000',
 '1011111111000010010010010010010010010010010000000000000000000000',
 '0100000000001001001000011111101101010100010000000000000000000000',
 '0100010011011111111000011000010111001010010000000000000000000000']

Поскольку u представляет собой те же данные, что и в x, x также был изменен на месте. 

In [54]: x                                                                      
Out[54]: 
array([ 0.000000000000000e+00, -3.333333332557231e-01,
        1.999999999534339e-01, -1.428571428405121e-01,
        3.141592653468251e+00,  6.022140758954589e+23])
1 голос
/ 10 июля 2019

Похоже на @ WarrenWeckesser's, но без черной магии вместо этого используются «официальные» ufuncs.Недостаток: я почти уверен, что это медленнее, возможно, значительно так: 

>>> a = np.random.normal(size=10)**5
>>> a
array([ 9.87664561e-12, -1.79654870e-03,  4.36740261e-01,  7.49256141e+00,
       -8.76894617e-01,  2.93850753e+00, -1.44149959e-02, -1.03026094e-03,
        3.18390143e-03,  3.05521581e-03])
>>> 
>>> mant,expn = np.frexp(a)
>>> mant
array([ 0.67871792, -0.91983293,  0.87348052,  0.93657018, -0.87689462,
        0.73462688, -0.92255974, -0.5274936 ,  0.81507877,  0.78213525])
>>> expn
array([-36,  -9,  -1,   3,   0,   2,  -6,  -9,  -8,  -8], dtype=int32)
>>> a_binned = np.ldexp(np.round(mant,5),expn)
>>> a_binned
array([ 9.87667590e-12, -1.79654297e-03,  4.36740000e-01,  7.49256000e+00,
       -8.76890000e-01,  2.93852000e+00, -1.44150000e-02, -1.03025391e-03,
        3.18390625e-03,  3.05523437e-03])
...