• 2006-08-04

    mask和index

    Tag:向下走

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/dreamhead-logs/2983512.html

    一个用来从一个数组中取内容的功能,比如说,对于数组[1, 2, 3],得到2和3,怎么做呢?很容易想到的两个解决方案,mask和index。

    mask方法:设置mask,这里是[0, 1, 1],如果对应位置是0,就丢弃该元素,1就留下。
    index方法:设置index,这里是[2, 3],根据index得到相应元素。

    这是一个很简单的功能,相信会编程的人都能很快的用自己熟悉的语言把程序写出来,所以,我并不打算讨论如何具体实现这个函数。我更关注的是这两种实现方法的差别,当然,从功能的角度来说,它们没有任何区别。实际上,截至今天之前,我也实在不觉得它们有什么区别。

    我最近正在写一个处理图像的程序,稍微了解一点图像编程编程知识的朋友对于ROI(Region of Interest)的概念一定不陌生,它表示我们要处理的区域。我要做的就是把这个区域的图像提取出来。在这种程序中,图像通常是以数组的形式存放,所以,这就变成了从一个数组中取元素的工作,可选的方法就是上面提到的两个:mask和index。

    正是认为二者没有区别,所以,随机选择的结果是mask担当重任。程序写出来了,经过简单调试就跑了起来。好消息是我得到了很多休息时间,因为坏消息是程序运行得非常慢。原本打算暂时视而不见,因为我这个程序首先需要正确,性能的优先级不是最高。结果吃中午饭的时候,突然想起来导致性能下降的原因可能就是选择mask,因为在这个程序中,会有大量的提取ROI的操作,如果这个操作的性能不高,则会导致程序整体的性能下降。按耐不住自己的冲动,翻出了提取ROI的代码,把相关的代码用index的方法重新实现一遍,果不其然,性能大幅度提升。原来拥有的长时间休息就这样随风而去了。

    怎么会有这么大的差别呢?

    如果使用这两种,除了提取元素的操作外,还需要有一个设置mask或index的过程。如果使用mask,需要为数组的每个元素都设置一个相应的mask,换句话说,也就是mask数组的长度要等于待提取数组的长度。而使用index,我们只需要表示出要提取的元素即可,也就是index数组的长度等于要提取的元素的个数。或许,这么说不足以说明问题。拿我正在做的一个程序举个例子,要处理的图像大小是720×480,而ROI的大小是16×16,对比上面所说的,如果使用mask的方法,那么mask数组的长度就是720×480,而使用index的方法,index数组长是16×16,所以,对于同一个处理而言,mask数组的长度是index数组的1350倍。这里还没有包括具体的提取操作,单是一个设置的工作,差别就是上千倍,而且我在前面提到过,这个操作在我程序中需要大量的出现,所以,性能上会出现很大的差异。

    在上面的讨论中,我故意忽略了具体的元素提取函数,因为在不同的实现中,它们可能会有差别。我现在做的是一个关于并行的程序,通常我们会把这种函数看做相同的复杂度:O(1),所以,我假定它们的执行性能相同。实际上,如果实现一个串行的版本,上面讨论的差异同样存在于元素提取操作中。

    似乎这个讨论的结果倾向于index的方法,但事实上,这个讨论并不完整。既然我提到了元素提取的函数可以并行,那设置mask和index的函数是不是也可以并行呢?而且,mask操作并不是无缘无故冒出来的,因为很多机器在硬件一级是支持mask操作的,所以,mask有其适用的范围。孰优孰劣的结论还是需要用实际的测试结果来支持。

    mask还是index,当数据量很小的时候,我们不会看到差别,当数据量增大的时候,一些意想不到的问题就会随之而来。之前的一个例子就是前面说过的内存管理的bug。实际上,那个库大家都在用,不过除了我,没人的程序崩掉,所以,那个bug也就心安理得的一直存在者。我之所以能把它挖出来,主要的原因是我的程序占用了更多的资源。再远一点的例子是从前的binary search都有错

    分享到:
    引用地址:

    评论

  • 很奇怪,你的随机选择为什么是mask呢.照常理来看,似乎用index更符合直觉
    回复LOGOS说:
    原因是我先知道有接口里有mask,后知道有index。^_^
    2006-08-05 22:42:37