Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >二进制一维Numpy数组到整数的快速一对一映射

二进制一维Numpy数组到整数的快速一对一映射
EN

Stack Overflow用户
提问于 2017-01-12 08:16:49
回答 2查看 551关注 0票数 2

将只包含01的一维Numpy数组转换为唯一整数的最快方法是什么?

到目前为止,我想出的最好方法是使用Cython,并将数组看作镜像的二进制数字*。

代码语言:javascript
运行
AI代码解释
复制
@cython.boundscheck(False)
@cython.wraparound(False)
def _map_binary(np.ndarray[np.int64_t, ndim=1] x):

    cdef int tot = 0
    cdef int i
    cdef int n = x.shape[0]

    for i in xrange(n):
        if x[i]:
            tot += 2**i
    return tot

由于这仍然是我算法的瓶颈,我想知道是否有一种更聪明、更快的方法来实现它。

*很明显,这种映射只对长度相同的数组是一对一的(因为在数组中添加零不会改变所产生的整数),但就我的目的而言,这是很好的。

EN

回答 2

Stack Overflow用户

发布于 2017-01-13 02:07:28

整理评论中的一些观点和我自己的一些观点

一些纯Python (+numpy)选项:

代码语言:javascript
运行
AI代码解释
复制
import numpy as np

def _map_binary_str_and_back(x):
    # from comment by @NickA
    return int("".join([str(c) for c in x]),2)

def _map_binary_np_dot(x):
    # from question http://stackoverflow.com/questions/41069825/convert-binary-01-numpy-to-integer-or-binary-string
    return np.dot(x,1 << np.arange(x.size))

def _map_binary_np_pack(x):
    # uses built in numpy function packbits, but unfortunately needs a bit of manipulation
    # afterwards
    x = np.packbits(x) # as np.int8
    x.resize((8,),refcheck=False)
    return x.view(dtype=np.int64)

一些Cython选项(请注意,我已经将输出更改为64位整数,以便它可以处理长达64个元素的数组):

代码语言:javascript
运行
AI代码解释
复制
cimport cython
cimport numpy as np

def _map_binary_original(np.ndarray[np.int64_t, ndim=1] x):

    cdef np.uint64_t tot = 0
    cdef np.uint64_t i
    cdef int n = x.shape[0]

    for i in xrange(n):
        if x[i]:
            tot += 2**i
    return tot

@cython.boundscheck(False)
@cython.wraparound(False)
def _map_binary_contig(np.ndarray[np.int64_t, ndim=1, mode="c"] x):

    cdef np.uint64_t tot = 0
    cdef np.uint64_t i
    cdef int n = x.shape[0]

    for i in xrange(n):
        if x[i]:
            tot += 2**i
    return tot

@cython.boundscheck(False)
@cython.wraparound(False)    
def _map_binary_shift(np.ndarray[np.int64_t, ndim=1, mode="c"] x):

    cdef np.uint64_t tot = 0
    cdef np.uint64_t i
    cdef int n = x.shape[0]

    for i in xrange(n):
        if x[i]:
            tot += 1<<i
    return tot

@cython.boundscheck(False)
@cython.wraparound(False)    
def _map_binary_times2(np.ndarray[np.int64_t, ndim=1, mode="c"] x):
    # @FranciscoCouzo

    cdef np.uint64_t tot = 0
    cdef np.uint64_t i
    cdef int n = x.shape[0]

    for i in xrange(n):
        tot *= 2
        if x[i]:            
            tot +=1 
    return tot

@cython.boundscheck(False)
@cython.wraparound(False)    
def _map_binary_times2_as_shift(np.ndarray[np.int64_t, ndim=1, mode="c"] x):

    cdef np.uint64_t tot = 0
    cdef np.uint64_t i
    cdef int n = x.shape[0]

    for i in xrange(n):
        tot *= 2
        if x[i]:            
            tot +=1 
    return tot

以及(供参考)一些计时代码

代码语言:javascript
运行
AI代码解释
复制
from map_binary import (_map_binary_original,_map_binary_contig,
                        _map_binary_shift,_map_binary_times2,
                        _map_binary_times2_as_shift)

test_array = np.random.randint(2,size=(60,)).astype(dtype=np.int64)

def time_function(name):
    from timeit import timeit

    num = 10000
    timed = timeit("f(x)","from __main__ import {} as f, test_array as x".format(name),number=num)/num
    print(name, timed)

for n in list(globals().keys()):
    if n.startswith('_map_binary'):
        time_function(n)

结果(为清晰起见略为修改格式):

代码语言:javascript
运行
AI代码解释
复制
_map_binary_str_and_back    9.774386967484043e-05
_map_binary_np_dot          7.402434574531678e-06
_map_binary_np_pack         1.5813756692768855e-06
_map_binary_original        7.462656716457738e-07
_map_binary_contig          7.208434833198e-07
_map_binary_shift           5.84043665719558e-07
_map_binary_times2          6.467991376011505e-07
_map_binary_times2_as_shift 6.412435894529889e-07

总结如下:

  • 在"no“版本中,使用np.packbits是最快的选择(但显然比Cython版本更糟糕)。然而,非Cython版本需要进一步的工作,以确保它们给出相同的答案(我认为点正在遭受整数溢出。packbits翻转了endianness,所以给出了一个有效但不同的答案)
  • 指定数组的连续性会使事情变得稍微快一些。
  • 移位似乎是最快的,其次是乘积,其次是幂(只有在使用无符号整数时,移位才是最快的)。
票数 3
EN

Stack Overflow用户

发布于 2017-01-12 08:45:47

我不确定您的解决方案是否是算法透视图中的最佳方法,但为了编写更优化的Cython代码,我建议进行以下更改:

  1. 在Cython中使用内存视图数组
  2. 在使用Cython时使用非pythonic代码,这样Cython可以从您的python代码中生成更小的C代码。因此,不使用shape和索引,因为您有一个一维数组,您可以使用size(),而不是使用xrange和索引只是在数组上循环并在每次迭代中增加变量i (或者至少只是使用range()),这是因为xrange是一个生成器,需要更多的工作来转换为C。
  3. 使用像pow这样的C库
  4. 预定义函数的类型
代码语言:javascript
运行
AI代码解释
复制
form ibc.math cimport pow

@cython.boundscheck(False)
@cython.wraparound(False)
cdef int _map_binary(np.int32_t[:] x):
    cdef int tot = 0
    cdef int i = 0
    cdef int n = x.size
    cdef int item
    for item in x:
        if item:
            tot = tot + pow(2, i)
        i = i + 1
    return tot
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/41618044

复制
相关文章
矩阵范数的等价性(原创)[通俗易懂]
设 F=R F = R \mathbb F=\mathbb R 或 C, C , \mathbb C, 对于任意两个 Fn×n F n × n \mathbb F^{n \times n} 上的范数 ∥⋅∥α ‖ ⋅ ‖ α \Vert \cdot\Vert_{\alpha} 与 ∥⋅∥β, ‖ ⋅ ‖ β , \Vert \cdot\Vert_{\beta}, 若存在常数 C1>0,C2>0, C 1 > 0 , C 2 > 0 , C_1 \gt 0, C_2 \gt 0, 使得 ∀X∈Fn×n, ∀ X ∈ F n × n , \forall \mathbf {X} \in \mathbb F^{n \times n},
全栈程序员站长
2022/09/29
1.3K0
Python中表达式与语句
Python中我暂时并未发现谁对着两个名词的明确定义;我对这两个名词的理解就是,表达式就是你想要执行的对象,语句就是你的具体执行操作。
py3study
2020/02/10
5640
门控时钟和逻辑等价性检查
每当问到“怎么降低动态功耗”,一般的答案就是插门控时钟。那为什么插门控时钟就能降低动态功耗呢?门控时钟一定能插得进去吗?对逻辑等价性检查(LEC)有什么影响?
ExASIC
2021/11/02
1.3K0
门控时钟和逻辑等价性检查
C++语言的表达式模板:表达式模板的入门性介绍
原标题:C++ Expression Templates: An Introduction to the Principles of Expression Templates 原作者:Klaus Kreft与Angelika Langer 原文链接: http://www.angelikalanger.com/Articles/Cuj/ExpressionTemplates/ExpressionTemplates.htm 翻译:Magi Su 翻译已经过原作者许可,转载请先征求原作者的许可。图片均取自原文,如果有水印为CSDN所打和老子没关系。出于清晰起见,文章中所有模板中的class都被改为typename。 模板(template)最早是以将类型(type)参数化为目的引入C++语言的。(译注1)链表 (list)是一个典型的例子。实际编码的时候,人们并不希望为保存不同类型变量的链表 分别编码,而是希望在编写的时候能够使用一个占位符(placeholder)来代替具体的类型 (即是模板参数),而让编译器来生成不同的链表类(模板的实例化)。 时至今日,模板的使用已经远远超过C++模板的发明者所预期的范畴。模板的使用已经涵盖 了泛型编程,编译时求值,表达式模板库,模板元编程,产生式编程(generative programming)等诸多领域。在这篇文章中,我们仅限于探讨一些表达式模板的编程知识, 侧重于编写表达式模板程序库这个方面。 我们必须指出:表达式模板库是相当复杂的。出于这个原因,我们读到过的关于表达式模 板的介绍都不是很容易理解的。因此,本文的作者希望能够通过本文为表达式模板提供一 个通俗的介绍,同时又不失对具体实现细节的阐述,从而对读者阅读模板库的代码能够起 到帮助。作者希望提取出表达式模板编码的一些原则性知识。有关于此领域的更多细节可 以参考其他著作。
sofu456
2019/07/09
2.6K0
C++语言的表达式模板:表达式模板的入门性介绍
C.163: 重载只用于基本等价的操作
Having the same name for logically different functions is confusing and leads to errors when using generic programming.
面向对象思考
2020/03/25
2860
【C语言笔记】数组与指针不等价
数组遍历方式一:使用指针遍历数组元素,p++等价于(p++),即指针指向的地址每次后移一个单位,然后再取地址上的值。这里的一个单位是sizeof(int)个字节。
正念君
2019/06/26
8030
对for循环中表达式和循环体的执行顺序详解
由上面的执行结果不难看出for循环中除了表达式1为了初始化变量,其的循环是表达式2——循环体——表达式3——表达式2这样的循环。
PHP开发工程师
2021/06/02
9920
【集合论】等价类 ( 等价类概念 | 等价类示例 | 等价类性质 | 商集 | 商集示例 )★
商集的本质 : 商集 本质是一个 集合 , 集合中的元素是 等价类 , 该等价类是基于
韩曙亮
2023/03/28
1.3K0
【集合论】等价类 ( 等价类概念 | 等价类示例 | 等价类性质 | 商集 | 商集示例 )★
Python中表达式int(&#39;0x10, 36)的值是。。。
在Python中,int()可用来把实数转换为整数,或者把数字字符串按指定进制转换为十进制数,详见文末的相关阅读。 然而,下面的代码又应该如何解释呢? >>> int('0x10', 36) 42804 按照传统意义的解释,0x开头表示十六进制,而试图把十六进制数看作36进制数并转换为十进制数,上面的代码应该出错,但是却又没有出错。把'0x10'当作36进制,那么x又表示什么呢?执行下面的代码试试: >>> import string >>> for ch in string.ascii_lowercase
Python小屋屋主
2018/04/16
9930
C++ 自由存储区是否等价于堆?
“free store” VS “heap” 当我问你C++的内存布局时,你大概会回答: “在C++中,内存区分为5个区,分别是堆、栈、自由存储区、全局/静态存储区、常量存储区”。 如果我接着问你自由存储区与堆有什么区别,你或许这样回答: “malloc在堆上分配的内存块,使用free释放内存,而new所申请的内存则是在自由存储区上,使用delete来释放。” 这样听起来似乎也没错,但如果我接着问: 自由存储区与堆是两块不同的内存区域吗?它们有可能相同吗? 你可能就懵了。 事实上,我在网上
Tencent JCoder
2018/07/02
3.5K0
机器学习中的基本问题——log损失与交叉熵的等价性
log\left ( 1+exp\left ( -m \right ) \right )
felixzhao
2019/01/31
1.3K0
等价域名
如果一个服务有多个域名入口,通过这些入口访问得到的内容一样,那么称这些域名为等价域名。 比如,通过等价域名,可以提供 3 个一模一样的文件或者接口服务。
陈少文
2022/07/17
3040
等价域名
【集合论】等价关系 ( 等价关系概念 | 等价关系示例 | 等价关系与闭包 )
由上边可以看出 , 等价关系是用于分类的 , 同一年出生的人可以划分到一个等价类中 ;
韩曙亮
2023/03/28
1.2K0
机器学习中的基本问题——log损失与交叉熵的等价性
1、log损失 image.png 2、交叉熵 image.png
felixzhao
2018/03/20
1.2K0
机器学习中的基本问题——log损失与交叉熵的等价性
黑盒测试的等价类划分法_黑盒测试等价类输出
等价类划分是一种典型的黑盒测试方法,这一设计方法完全不用考虑程序的内部结构,也就是说其只根据需求规格说明书。
全栈程序员站长
2022/11/10
6890
黑盒测试的等价类划分法_黑盒测试等价类输出
java OJ题目判断输入结束(与C语言的EOF结束等价)
/* * java 作Oj题目是会有输入若干数据的情况,不好判断输入结束符, * 类似于C语言中的EOF符号 * 在这里提供了一种方法 * */
用户3030674
2018/09/14
2.5K0
企业面试题: javascript中表达式parseInt("9")+parseFloat('7')的结果是什么?
parseFloat() 所解析的字符串中第一个小数点是有效的,而parseInt() 遇到小数点会停止解析,因为小数点并不是有效的数字字符。
舒克
2019/08/09
8900
html中表单提交
表单提交代码 1、源代码分析 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <meta http-equiv="X-UA-Compatible" content="ie=edge"> <title>Document</title> </head> <body
bamboo
2019/01/29
1.6K0
html中表单提交
论强化学习和概率推断的等价性:一种全新概率模型
选自arXiv 作者:Sergey Levine 机器之心编译 参与:张倩、刘晓坤 虽然强化学习问题的一般形式可以有效地推理不确定性,但强化学习和概率推断的联系并不是很明显。在本文中,UC Berkeley EECS 助理教授 Sergey Levine 提出了一种新的概率模型和理论框架,证明了强化学习的一般形式即最大熵强化学习与概率推断的等价性。在原则上,将问题形式化为概率推断,可以应用多种近似推断工具,将模型以灵活、强大的方式进行扩展。 概率图模型(PGM)为机器学习研究者提供了一种广泛适用的工具(K
机器之心
2018/06/08
7690
C++的lambda表达式
从C++11开始,C++也支持使用lambda表达式(匿名函数)。Lambda表达式是一种便捷的方式,可以定义一个函数对象,而无需使用显式的函数对象类型或函数指针语法。
叶茂林
2023/07/30
1820

相似问题

布尔表达式的等价性

23

正则表达式等价性

40

C中wstring的等价性

22

C std的等价性::查找

12

比较rpn (后缀)表达式的等价性

214
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文