8000 fix: update big-data solutions (#61) · enixdark/advanced-java@f710d10 · GitHub
[go: up one dir, main page]

Skip to content

Commit f710d10

Browse files
committed
fix: update big-data solutions (doocs#61)
See doocs#61 (comment) for details.
1 parent 85603e3 commit f710d10

File tree

2 files changed

+4
-2
lines changed

2 files changed

+4
-2
lines changed

docs/big-data/find-a-number-if-exists.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212

1313
#### 方法二:位图法
1414

15-
40 亿个不重复整数,我们用 40 亿个 bit 来表示,初始位均为 0,那么总共需要内存:4, 000, 000, 000b≈512M。
15+
由于 unsigned int 数字的范围是 `[0, 1 << 32)`,我们用 `1<<32=4,294,967,296` bit 来表示每个数字。初始位均为 0,那么总共需要内存:4,294,967,296b≈512M。
1616

1717
我们读取这 40 亿个整数,将对应的 bit 设置为 1。接着读取要查询的数,查看相应位是否为 1,如果为 1 表示存在,如果为 0 表示不存在。
1818

docs/big-data/find-no-repeat-number.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -56,6 +56,8 @@ for i in range(8):
5656

5757
遍历 2.5 亿个整数,查看位图中对应的位,如果是 00,则变为 01,如果是 01 则变为 10,如果是 10 则保持不变。遍历结束后,查看位图,把对应位是 01 的整数输出即可。
5858

59+
当然,本题中特别说明:**内存不足以容纳这 2.5 亿个整数**,2.5 亿个整数的内存大小为:2.5e8/1024/1024/1024=0.93G,也即是说内存不足 1G,而位图法所需要的内存大小为 1G,因此,本题并不适合用位图法解决。
60+
5961
### 方法总结
6062

61-
**判断数字是否重复的问题**,位图法是一种非常高效的方法。
63+
**判断数字是否重复的问题**,位图法是一种非常高效的方法,当然前提是:内存要满足位图法所需要的存储空间

0 commit comments

Comments
 (0)
0