V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lithium148
V2EX  ›  编程

数组里有百万个值,如何加快速度?

  •  
  •   lithium148 · 2021-04-05 18:44:40 +08:00 · 3592 次点击
    这是一个创建于 406 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Android 中,我有一个 int[] a,里面大约有两百万个 int

    每一个 a[i],经过一些简单的加减后,得到新的值

    实测这样的操作将会花费惊人的数分钟时间,

    请问如何加快这个速度?

    目前想到的是每几个 a[i]开一个新的线程,改用 synchronizedList,

    因为我看到耗时很长但是 CPU 占用率很低。

    还有别的方法吗?

    谢谢各位大佬不吝赐教,在下不尽感激

    35 条回复    2021-04-13 03:41:12 +08:00
    aheadlead
        1
    aheadlead  
       2021-04-05 18:45:42 +08:00
    ……最好的办法就是少存点

    不过楼主可以详细描述下,或者直接贴代码
    des
        2
    des  
       2021-04-05 18:49:37 +08:00 via iPhone
    每次更新两百万个数据,想快也快不起来吧?
    建议先想想,为啥每次需要更新这么多数据
    lithium148
        3
    lithium148  
    OP
       2021-04-05 18:56:09 +08:00 via Android
    @des 具体的场景是,有一个 bitmap (图片),读取每一个像素点的 rgb 值,修改后回去。这里的应用是修改图片亮度。
    xupefei
        4
    xupefei  
       2021-04-05 18:57:33 +08:00 via iPhone
    不要每几个值就开线程,把整个数组等分为 cpu 核数会更快。
    kera0a
        5
    kera0a  
       2021-04-05 19:00:33 +08:00 via iPhone   ❤️ 1
    安卓能调 gpu 算吗?
    lithium148
        6
    lithium148  
    OP
       2021-04-05 19:00:35 +08:00 via Android
    我看到其他人的代码,这一块是用 Ndk ( c++)实现的,但我不会 c++……
    lithium148
        7
    lithium148  
    OP
       2021-04-05 19:05:24 +08:00 via Android
    @xupefei 最后又要从 n 个合成 1 个数组,多了复制的开销吧
    aheadlead
        8
    aheadlead  
       2021-04-05 19:06:48 +08:00
    @lithium148 #3 这应该算是典型的用 native 的场景吧。。

    (不过我不是 app developer…
    akira
        9
    akira  
       2021-04-05 19:06:58 +08:00   ❤️ 1
    提交给服务器端,处理完成后返回给客户端 @@
    aheadlead
        10
    aheadlead  
       2021-04-05 19:07:21 +08:00
    没有封装好的库可以用吗?
    lithium148
        11
    lithium148  
    OP
       2021-04-05 19:10:46 +08:00 via Android
    @aheadlead native 是指 ndk 吗,方便展开说说不
    Muniesa
        12
    Muniesa  
       2021-04-05 19:11:29 +08:00   ❤️ 1
    用 opencv 不好吗,直接算矩阵不比你循环算数组快……
    xmumiffy
        13
    xmumiffy  
       2021-04-05 19:12:04 +08:00 via Android   ❤️ 2
    建议用 colorMatrix
    des
        14
    des  
       2021-04-05 19:12:55 +08:00 via iPhone
    首先图像计算建议用图像库
    要自己搞的话,你这明显有可以优化的地方
    一是颜色一般只需要存 255,你这浪费了好多
    然后黑白图又可以省好多
    还有是可以用 gpu 加速
    aheadlead
        15
    aheadlead  
       2021-04-05 19:15:50 +08:00
    @lithium148 #11 我以前是做手机的 framework native 和 kernel 的… app 的 NDK 不算太熟

    不过我觉得你这个场景 100%有成熟的 library 可以用
    areless
        16
    areless  
       2021-04-05 19:17:33 +08:00
    gpu.js 或者 webgl2 走 GPU 加速的。你只需要一个 headless 浏览器
    Mithril
        17
    Mithril  
       2021-04-05 19:22:43 +08:00 via iPhone   ❤️ 1
    图像处理不是这么搞的。。。
    用 C++主要是因为可以用 SIMD 指令,但是一般来说如果只是做你说的亮度处理,不应该在图像本身上面搞。
    通常会做一个类似管道的东西,把图像数据通过一系列操作映射成显示用的 view 数据,一般就是 rgb256 数组。你这个操作应该在管道上去搞,换句话说就是 view 层面的东西。
    你还是找个图像库去弄吧。。。
    aheadlead
        18
    aheadlead  
       2021-04-05 19:38:30 +08:00
    我想起了以前有个 skia 库,曾经还跟他斗智斗勇来着
    xupefei
        19
    xupefei  
       2021-04-05 19:40:08 +08:00 via iPhone
    @lithium148 内存复制快还是你的锁快?
    nlzy
        20
    nlzy  
       2021-04-05 20:49:46 +08:00   ❤️ 7
    虽说图像处理一律建议使用现成的库,但是两百万个整数,每个元素仅仅是简单的加减,那这数据量一点都不多,运行时间几分钟肯定是代码写错了。别听楼上说的整什么多线程、SIMD 、GPU,我看还是先把代码写对吧。
    chocovon
        21
    chocovon  
       2021-04-05 21:05:51 +08:00
    @nlzy 确实,200w 个 int 应该是秒算的
    hahasong
        22
    hahasong  
       2021-04-05 22:49:30 +08:00   ❤️ 1
    你不会是在视图线程上算的吧 卡 UI 了
    xiadong1994
        23
    xiadong1994  
       2021-04-05 23:48:35 +08:00 via iPhone
    单纯 200w 个 int 循环一次加减应该还到不了秒级的时间,几十~几百 ms
    mekingname
        24
    mekingname  
       2021-04-05 23:58:00 +08:00 via iPad   ❤️ 1
    图片的 RGB 是通过一个二组数组来储存的,这就提示你,可以使用矩阵运算来加速;但是楼主你却把这个二维数组拉成一个一组的数组,一个一个像素点来运算,速度慢是应该的。图像处理领域需要大量的矩阵运算.需要丰富的线性代数的知识储备。
    mxT52CRuqR6o5
        25
    mxT52CRuqR6o5  
       2021-04-06 00:07:10 +08:00 via Android
    同意楼上的说法,才几百万就算个几分钟是代码就没写对,还没到需要折腾乱七八糟技巧的时候
    across
        26
    across  
       2021-04-06 00:16:08 +08:00
    图片亮度就是统一加 rgb,交给 gpu 做很快( OpenGL ES )。
    但我记得 android 上有一类 api,专门封装了针对图片的 gpu 操作(不是 GPUImage ),忘了叫啥了····
    across
        27
    across  
       2021-04-06 00:19:51 +08:00   ❤️ 1
    搜了下是 import android.graphics.Bitmap;
    一搜就看到了 https://blog.csdn.net/gf771115/article/details/40778091
    BugenZhao
        28
    BugenZhao  
       2021-04-06 00:31:54 +08:00 via iPhone
    Marszm
        29
    Marszm  
       2021-04-06 08:40:21 +08:00   ❤️ 1
    我怀疑他代码,每计算一次加减,就重排列一次数组...所以计算量是 n*200 万次..
    tairan2006
        30
    tairan2006  
       2021-04-06 10:17:20 +08:00
    原地修改的话不可能这么慢
    honeyshine75
        31
    honeyshine75  
       2021-04-06 10:36:13 +08:00
    矩阵计算
    dadachen1997
        32
    dadachen1997  
       2021-04-06 13:20:29 +08:00
    矩阵运算库找找看?
    takato
        33
    takato  
       2021-04-06 13:57:24 +08:00
    对于这个情况比较合理的性能情况应该是多少呢?
    我做了一个小测试,randn 一个 shape 为 7000,1000 的 f32 array 做 sum(axis=1)运算
    numpy 跑了 4.6ms
    rust 手写跑了 6ms,并行化后 2ms
    gpu 性能不能看,运算本身很快,但是把数据扔进 cuda 慢得要死。。。

    比较想知道这样的情形在使用单台 PC 的情况下大概能优化到什么程度?
    ReputationZh
        34
    ReputationZh  
       2021-04-06 14:28:44 +08:00
    real 0m0.023s
    user 0m0.016s
    sys 0m0.000s
    domodomo
        35
    domodomo  
       2021-04-13 03:41:12 +08:00
    time ./test
    ./test 0.02s user 0.00s system 87% cpu 0.022 total

    我的哥,你写的啥程序啊,200 万 int 随机加减,0.022 秒就完成了啊
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4145 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 02:01 · PVG 10:01 · LAX 19:01 · JFK 22:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.