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

遍历

dic

arraylist

int

31 条回复 • 2020-12-18 18:43:25 +08:00

1

xdeng

2020-12-18 09:15:23 +08:00

哈希表

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{}

算法的复杂度比比就知道了

3

Aesyt

2020-12-18 09:17:08 +08:00

O(n) 和 O(1) 的区别？

4

aijam

2020-12-18 09:17:09 +08:00

1L 正解！！！

5

sagaxu

2020-12-18 09:18:06 +08:00 via Android

arraylist 遍历比 dict 更快才对

6

weixiangzhe

2020-12-18 09:27:35 +08:00

1

空间换时间，O(n^2) 和 O(2n) 的区别

7

xx6412223

2020-12-18 09:33:10 +08:00

抛开上下文，遍历 array 比 list 更快，array 是内存连续，list 一般不连续。而 map 的结构一般都是 list 来实现的

8

xuanbg

2020-12-18 09:40:12 +08:00

顺序遍历 array 肯定最快啊，查询才是 hashMap 快

9

Moyudawang

2020-12-18 09:43:33 +08:00

遍历的目的是为了精确查询？？？

10

NexTooo

2020-12-18 09:45:05 +08:00

字典走 hash，碰撞不多的情况下单次查询基本上是 O(1)，基本上就是空间换时间

11

no1xsyzy

2020-12-18 09:48:40 +08:00

因为你是嵌套遍历，而转字典的话内层改为查哈希表，就不用遍历了

12

raaaaaar

2020-12-18 10:29:11 +08:00 via Android

1

如果都是指查询的话，那么本质上就是顺序查找和 hash 查找的区别。顺序查找 O(n)，hash O(n)，自然 hash 快许多了。

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

那么这个地址是怎么拿到的？这就是 hash 函数的作用，但是有时候地址冲突怎么办？这就是 hash 冲突，所以怎么选取 hash 函数，怎么解决冲突，对时间复杂度都有很大的影响。

13

raaaaaar

2020-12-18 10:31:11 +08:00 via Android

楼上打错了，hash 是 o(1)，是平衡二叉树

14

qwerthhusn

2020-12-18 10:34:31 +08:00

2

简单说，查字典，是先看偏旁部首快，还是从第一页啊阿吖嗄开始一个一个找得快？

15

xzour

OP

2020-12-18 10:34:34 +08:00

@raaaaaar 哈希查找一般查找比对的值一般是在<T>里面的吧？哈希表也有优化吗？还是对 KEY 的优化？这是我疑惑的地方。

16

zvl0reqglvd

2020-12-18 10:57:33 +08:00

hash 吧，空间换时间

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，这是个很重要的数据结构。

18

xzour

OP

2020-12-18 11:40:17 +08:00

@raaaaaar array 如果知道 index.是不是等同于哈希的速度呢？如果不知道 key 是 aaa，查找 7，是不是等同于顺序查找呢?

19

raaaaaar

2020-12-18 11:43:44 +08:00

@xzour #18 如果知道 index 是多少，那还能叫查找么，肯定就是 O(1) 呀，这就是数组比链表的优点所在嘛。

第二个问题你问得就有问题了，甚至不是一个问题。你需要自己学一下相关的知识。。建议直接用 c 实现一下，其实不难，一个下午就能理解个大概，但是对以后的帮助很大的。

20

xzour

OP

2020-12-18 11:47:00 +08:00

@raaaaaar 看来第二个问题确实很重要，关于数据结构的理解，谢谢，我会抽空实现一下的！

21

zhlssg

2020-12-18 11:59:46 +08:00

@weixiangzhe 为啥你这时间复杂度和 3l 不一样啊

22

weixiangzhe

2020-12-18 12:01:01 +08:00 via Android

@zhlssg 我看成双层 for 循环了

23

Nerv

2020-12-18 12:38:17 +08:00

买本算法第四版，各种复杂度给你分析得透透得

24

tlday

2020-12-18 13:10:51 +08:00

2

这个帖子是完美的 X-Y 问题的例子。
建议回答的人先去看看楼主贴出的原帖，在"""""""暴力遍历"""""""（加粗加重）中，数组转字典可以优化计算速度是不存在的。

什么是 X-Y 问题： https://coolshell.cn/articles/10804.html

25

tlday

2020-12-18 13:15:50 +08:00

看了这么多楼都给我整懵了，看了原帖才发现，根本不是这么回事儿。

26

Still4

2020-12-18 13:25:46 +08:00

遍历每个客户
读取该客户的收款及发票
遍历收款，取发票一条一条核销，一条销完，换另一张发票，未销完，记录发票 INDEX 及剩余金额
最后将结果批量插入数据库。大概 6000 多条核销明细花了我 30 分钟+ 不可忍受。

看了原贴，根源在于第二步和第三步有过滤
以第二步为例，你要遍历每个客户的数据，对应主楼的 arr2 和 map2 会进行筛选，当然是 map 更快