这是一个创建于 1471 天前的主题，其中的信息可能已经有所发展或是发生改变。
自己数据结构比较薄弱，但我没想通 ArrayList<T> or List<T> 会比 Dic<int,T>慢？ 联动前贴： https://www.v2ex.com/t/736445
 |
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 @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 @raaaaaar array 如果知道 index.是不是等同于哈希的速度呢？ 如果不知道 key 是 aaa，查找 7，是不是等同于顺序查找呢?
|
|
19
raaaaaar 2020-12-18 11:43:44 +08:00
@xzour #18 如果知道 index 是多少，那还能叫查找么，肯定就是 O(1) 呀，这就是数组比链表的优点所在嘛。
第二个问题你问得就有问题了，甚至不是一个问题。你需要自己学一下相关的知识。。建议直接用 c 实现一下，其实不难，一个下午就能理解个大概，但是对以后的帮助很大的。 |
 |
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 更快 |
 |
27
jimliang 2020-12-18 15:38:35 +08:00
一看就没学过数据结构的，转 Dic 的复杂度为 n，以后每次获取的复杂度就是 1 了。
|
 |
28
wangchonglie 2020-12-18 16:56:49 +08:00
@tlday #24 感谢让我学会了什么叫 X-Y 问题
|
 |
29
fishenal 2020-12-18 17:21:11 +08:00
我这个半调子程序员都知道，字典是 hash table，hash table 就是把值做 hash，放到 hash 过后这个内存位置，直接去寻址就找到了，array 遍历至少 o （ n ）
|
 |
30
786375312123 2020-12-18 18:26:08 +08:00
hash table 的底层实现也是 array 。
你的问题描述有点问题 |
Select Language