V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Sponsored by
LinkedIn
2000 个不用坐班的远程好工作在召唤你 · 弹性上班不打卡,工作和生活都能拥有
2000 个不用坐班的全球远程工作,帮助 V2EX 的小伙伴开启全新的工作方式。
Promoted by LinkedIn
xzour
V2EX  ›  程序员

为什么在暴力遍历中,为什么数组转字典是优化计算速度?

  •  
  •   xzour · 2020-12-18 09:04:33 +08:00 · 3982 次点击
    这是一个创建于 645 天前的主题,其中的信息可能已经有所发展或是发生改变。
    自己数据结构比较薄弱,但我没想通 ArrayList<T> or List<T> 会比 Dic<int,T>慢? 联动前贴: https://www.v2ex.com/t/736445
    31 条回复    2020-12-18 18:43:25 +08:00
    xdeng
        1
    xdeng  
       2020-12-18 09:15:23 +08:00
    哈希表
    Aoang
        2
    Aoang  
       2020-12-18 09:16:58 +08:00 via Android
    例:
    arr1, arr2, arr3
    for range arr1{
    for range arr2{
    for range arr3{
    // 处理
    }
    }
    }

    字典的话可能是
    map1, map2, map3
    for range map1{}
    for range map1{}
    for range map1{}

    算法的复杂度比比就知道了
    Aesyt
        3
    Aesyt  
       2020-12-18 09:17:08 +08:00
    O(n) 和 O(1) 的区别?
    aijam
        4
    aijam  
       2020-12-18 09:17:09 +08:00
    1L 正解!!!
    sagaxu
        5
    sagaxu  
       2020-12-18 09:18:06 +08:00 via Android
    arraylist 遍历比 dict 更快才对
    weixiangzhe
        6
    weixiangzhe  
       2020-12-18 09:27:35 +08:00   ❤️ 1
    空间换时间,O(n^2) 和 O(2n) 的区别
    xx6412223
        7
    xx6412223  
       2020-12-18 09:33:10 +08:00
    抛开上下文,遍历 array 比 list 更快,array 是内存连续,list 一般不连续。而 map 的结构一般都是 list 来实现的
    xuanbg
        8
    xuanbg  
       2020-12-18 09:40:12 +08:00
    顺序遍历 array 肯定最快啊,查询才是 hashMap 快
    Moyudawang
        9
    Moyudawang  
       2020-12-18 09:43:33 +08:00
    遍历的目的是为了精确查询???
    NexTooo
        10
    NexTooo  
       2020-12-18 09:45:05 +08:00
    字典走 hash,碰撞不多的情况下单次查询基本上是 O(1),基本上就是空间换时间
    no1xsyzy
        11
    no1xsyzy  
       2020-12-18 09:48:40 +08:00
    因为你是嵌套遍历,而转字典的话内层改为查哈希表,就不用遍历了
    raaaaaar
        12
    raaaaaar  
       2020-12-18 10:29:11 +08:00 via Android   ❤️ 1
    如果都是指查询的话,那么本质上就是顺序查找和 hash 查找的区别。顺序查找 O(n),hash O(n),自然 hash 快许多了。

    原因是什么?因为无论是顺序查找,二分,索引,还是二叉平衡树,二叉查找树,甚至更高的红黑树这些,它们查找都是基于一个原则:比较。它们在查找的过程中会比较值和待查找值的情况,这个过程非常的大,也要算进时间复杂度,而 hash 是一种特殊的方法,它并没有比较这个过程,它参考了数组随机存取的思路,直接拿到目标内存的地址,直接查表。

    那么这个地址是怎么拿到的?这就是 hash 函数的作用,但是有时候地址冲突怎么办?这就是 hash 冲突,所以怎么选取 hash 函数,怎么解决冲突,对时间复杂度都有很大的影响。
    raaaaaar
        13
    raaaaaar  
       2020-12-18 10:31:11 +08:00 via Android
    楼上打错了,hash 是 o(1),是平衡二叉树
    qwerthhusn
        14
    qwerthhusn  
       2020-12-18 10:34:31 +08:00   ❤️ 2
    简单说,查字典,是先看偏旁部首快,还是从第一页 啊阿吖嗄 开始一个一个找得快?
    xzour
        15
    xzour  
    OP
       2020-12-18 10:34:34 +08:00
    @raaaaaar 哈希查找 一般查找比对的值一般是在<T>里面的吧?哈希表也有优化吗?还是对 KEY 的优化?这是我疑惑的地方。
    zvl0reqglvd
        16
    zvl0reqglvd  
       2020-12-18 10:57:33 +08:00
    hash 吧,空间换时间
    raaaaaar
        17
    raaaaaar  
       2020-12-18 11:01:19 +08:00
    @xzour #15

    现在有一个 array,是这样的 [1,2,5,67,7,8,9],要查看 7 这个值,如果我顺序查找,那么就只能遍历,先 1 和 7 比较,然后 2 和 7 比较,一直到 7 和 7 相等,这有比较的过程。

    由于 hash table 是 key-value 的,现在假设我们最终的 hash table 就是 [1,2,5,67,7,8,9] 这个样子,我们要查看 7,假设 7 的 key 是 aaa,那么我们在 hash_table["aaa"] 这个过程发生了什么呢?

    首先,hash_func("aaa") 进行处理,得到一个地址,就是 4,然后就变成 hash_table[4] 直接查找了。这个过程就是 array 的顺序查找,显然是没有比较过程的。

    建议你自己实现一个 hash table,这是个很重要的数据结构。
    xzour
        18
    xzour  
    OP
       2020-12-18 11:40:17 +08:00
    @raaaaaar array 如果知道 index.是不是等同于哈希的速度呢? 如果不知道 key 是 aaa,查找 7,是不是等同于顺序查找呢?
    raaaaaar
        19
    raaaaaar  
       2020-12-18 11:43:44 +08:00
    @xzour #18 如果知道 index 是多少,那还能叫查找么,肯定就是 O(1) 呀,这就是数组比链表的优点所在嘛。

    第二个问题你问得就有问题了,甚至不是一个问题。你需要自己学一下相关的知识。。建议直接用 c 实现一下,其实不难,一个下午就能理解个大概,但是对以后的帮助很大的。
    xzour
        20
    xzour  
    OP
       2020-12-18 11:47:00 +08:00
    @raaaaaar 看来第二个问题确实很重要,关于数据结构的理解,谢谢,我会抽空实现一下的!
    zhlssg
        21
    zhlssg  
       2020-12-18 11:59:46 +08:00
    @weixiangzhe 为啥你这时间复杂度和 3l 不一样啊
    weixiangzhe
        22
    weixiangzhe  
       2020-12-18 12:01:01 +08:00 via Android
    @zhlssg 我看成双层 for 循环了
    Nerv
        23
    Nerv  
       2020-12-18 12:38:17 +08:00
    买本算法第四版,各种复杂度给你分析得透透得
    tlday
        24
    tlday  
       2020-12-18 13:10:51 +08:00   ❤️ 2
    这个帖子是完美的 X-Y 问题的例子。
    建议回答的人先去看看楼主贴出的原帖,在"""""""暴力遍历"""""""(加粗加重)中,数组转字典可以优化计算速度是不存在的。

    什么是 X-Y 问题: https://coolshell.cn/articles/10804.html
    tlday
        25
    tlday  
       2020-12-18 13:15:50 +08:00
    看了这么多楼都给我整懵了,看了原帖才发现,根本不是这么回事儿。
    Still4
        26
    Still4  
       2020-12-18 13:25:46 +08:00
    遍历每个客户
    读取该客户的收款及发票
    遍历收款,取发票一条一条核销,一条销完,换另一张发票,未销完,记录发票 INDEX 及剩余金额
    最后将结果批量插入数据库。 大概 6000 多条核销明细花了我 30 分钟+ 不可忍受。

    看了原贴,根源在于第二步和第三步有过滤
    以第二步为例,你要遍历每个客户的数据,对应主楼的 arr2 和 map2 会进行筛选,当然是 map 更快
    jimliang
        27
    jimliang  
       2020-12-18 15:38:35 +08:00
    一看就没学过数据结构的,转 Dic 的复杂度为 n,以后每次获取的复杂度就是 1 了。
    wangchonglie
        28
    wangchonglie  
       2020-12-18 16:56:49 +08:00
    @tlday #24 感谢让我学会了什么叫 X-Y 问题
    fishenal
        29
    fishenal  
       2020-12-18 17:21:11 +08:00
    我这个半调子程序员都知道,字典是 hash table,hash table 就是把值做 hash,放到 hash 过后这个内存位置,直接去寻址就找到了,array 遍历至少 o ( n )
    786375312123
        30
    786375312123  
       2020-12-18 18:26:08 +08:00
    hash table 的底层实现也是 array 。
    你的问题描述有点问题
    raaaaaar
        31
    raaaaaar  
       2020-12-18 18:43:25 +08:00
    @tlday #24 我今天才和别人说类似的情况,不过没有术语这么精准,没想到自己就完美体验了一次。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1045 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 45ms · UTC 22:01 · PVG 06:01 · LAX 15:01 · JFK 18:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.