首页 注册 登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  3dwelcome  ›  全部回复第 13 页 / 共 155 页
回复总数  3084
1 ... 9  10  11  12  13  14  15  16  17  18 ... 155  
❮ ❯
2022-04-18 23:34:26 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？
@hitmanx 别人不知道，我代码里很多这种“缝合数组”。

原因就是在长度增加同时，能避免旧数组失效，这特性对我挺重要的。
2022-04-18 23:30:07 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@est “除了故意构造，真实世界不存在 md5 或者 sha1 冲突的两个天然的文件。”

第一，存 MD5 值太大了，但很多人理解不了，我只能以常见的 MD5 来举例。基本上 java/linux 的 hash 函数，都不可能选用 MD5 算法.

第二，生日悖论实验告诉我们，千万不要小看数据量上去后，潜在冲突的概率。编程不能靠直觉，要靠公式。
2022-04-18 23:26:26 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@documentzhangx66 说了存原数据不现实。

硬盘文件对比的情况下，只能算一次文件 hash ，而且无论数据量多少，必须保证算出来的文件 hash 之间没有冲突。这就意味着需要预处理。

预处理的结果就是一组 bitmap 数据集合。有了这个集合的辅助，数学函数定义就失效了，你让我怎么回复嘛。
2022-04-18 22:49:09 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@013231 "用新的散列算法算一遍不是比逐字節對比更慢嗎？"

还是那句话，使用场景不一样。你比对两块硬盘上所有文件是否有内容重复，比对 hash 是最简单直接的方法。

把两块硬盘硬凑一起，挨个字节对比，有点不现实。
2022-04-18 22:44:53 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@mrgeneral “因为算法变了，这个时候 sha1(A)=sha1(C) 又冲突了怎么办？”

漏斗过滤有个特性，第一层元素最多冲突最多。

往后每下一层的元素数量，都要远远少于上一层的。

只要元素变少了，冲突的概率就自然会下降很多。
2022-04-18 22:39:44 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？
@Mystery0 "况且多个小数组怎么拼起来？用指针链起来？"

用二维指针就可以，比如 int** array 就能把数组缝合起来。或者更简单的形式，用 vector<int*>这种。

你面向硬件编程，把大数组切分成小数组是必然的。操作系统是有 4k 之类内存区块概念的，分配的数组不能太大，不能太小，性能才最好。
2022-04-18 22:00:30 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@XiLingHost "Talk is cheap. Show me the code"

建个和所有元素相等长度的 bitset 。
查询时，bit 为 1 就用 MD5, bit 为 0 就用 SHA1 。那么简单的原理，上 CODE 没必要吧。
2022-04-18 20:47:26 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@duke807 如果遍历本地硬盘所有文件，py 的 dict 肯定不能保证没有哈希冲突，我这个就可以。
2022-04-18 20:45:46 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@newtype0092 保存结果就仅仅是 bitmap 里的一个 bit 而已，代表着需要用第几层 hash 算法。基本不占多少存储空间。
2022-04-18 19:33:18 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@cxtrinityy 应用场景不一样，java 的 hashmap 冲突后，会进一步对比原始数据。
我这种完美 hash ，保证没冲突，就自然不需要保存原始数据了。
2022-04-18 19:24:06 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
我说一下使用场景，比如用户上传海量的图片，你单用 md5 或者 sha1 ，都不能保证完美无冲突。
有冲突的话，只能挨个字节对比两张图片是否一模一样，效率是很低的。
这时候，引入砂砾过滤层，如果 md5 有冲突，就把 bitmap 设置成 1 ，那么 hash 算法就会切换到 sha1 。还冲突，就再升一层变成 sha256 ，直到完全无冲突。
2022-04-18 18:35:09 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@XiLingHost "所以你的查找需要用原始数据来查原始数据......?"

这里的 bitmap 相当于 AI 网络的训练数据，对于可预测的原始数据，是最精确的。

如果没有事先插入元素的话，map 是查不到 key 的。
2022-04-18 18:29:55 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。
@oneisall8955 查找算法和插入一样的，先用多层 bitmap 前置过滤一次，有可能会计算多次 hash 函数。

计算后得到不冲突的沙砾层数，这时候对应的 map ，在当前层内查找 key ，就是无冲突的。
2022-04-18 16:46:59 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？
@msaionyc

“需要重新申请空间，原来的 delete 掉。”， 旧空间也可以不删除的，多个子数组拼成一个大数组就可以不用删掉了。

“数组必须要提前申请内存空间，没用满时等于空了的部分是浪费了的。”
这句话也不对，操作系统对于应用程序申请了，但没有实际使用的内存，是不会真实分配的。只有第一次赋值或者初始化时，才会分配物理内存。

总的来说，还是链表占用内存更多。一个 next 指针需要 8 字节，对比一个 1M 大小的数组，链表比数组要整整多出 8M 额外内存。
2022-04-18 16:21:18 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？
@msaionyc 内存空间利用率具体指什么？没太搞懂，按理说数组比链表要节约内存。

链表你还要多一个 next 指针才行。
2022-04-18 15:54:44 +08:00
回复了 MTMT 创建的主题 › 问与答 › 大家怎么面对工作压力
不加班就没有压力了。

加班很晚，状态不好的时候，写的代码大概率是需要返工的。

还不如先吃饱，睡好。在白天状态好的时候，听听背景歌曲，静下心，慢慢堆代码。
2022-04-18 15:49:04 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？
@msaionyc “我一直认为，发表这种“xxx 过时”，“a 不如 b”这种话题应该非常慎重，尤其是技术方面”

以前是面向对象编程，现在时代变了，是面向硬件编程。

举个例子，有个叫 Odin 的新编程语言（ http://odin-lang.org/），这个就是为了优化硬件，而诞生的编程语言，所谓的 Data-Oriented Language 。

你可以照本宣科，表示大学书本数据结构里，链表 O(1)插入性能好。可真实高性能编程中，SoA （ array of structures ）的地位，要远高于 AoS 。你说为什么，就是因为 SoA 设计成面向 CPU 编程，有更好缓存亲和性，自然就有更好的性能。
2022-04-18 15:35:20 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？
@msaionyc "这时如果是在增删条件比较多的情况下难道也要用数组替换链表吗？"

不回复一些楼，又不是代表我持反对意见。

我只想讨论大概率使用场景。你如果写一个只有中间 insert 的对比场景，那肯定是链表比数组更占优势。

链表在数据结构里地位，和数组一样重要，我没怀疑这点。发帖的主要目的，只是想说明在现代 CPU 硬件设计上，对链表不友好，对数组更友好。相同场景下，优先考虑数组，仅此而已。
2022-04-18 14:12:01 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？
@northernlights0 "比如要通过线性表实现一个队列，有大量的 push_back, pop_front 操作，就肯定是链表占优"

可以分而治之的，把一个超级大链表，转换成 N 个固定大小的数组集合。只对小数组进行局部操作，感觉也不会太慢。

理论上大家都知道链表插入快，而实际上 CPU 设计的高速缓存，天然就对数组有极强的亲和性。

而且在大部分情况下，查询的操作频率，要远远高于插入和删除。
2022-04-18 10:55:31 +08:00
回复了 3dwelcome 创建的主题 › 算法 › 链表快还是数组快？
@duke807 “現有元素的引用者也會受到影響，因為引用可能會失效”

所以我数组一般都是存指针，指针不会失效。

而且数组还有一点好处，可以排序后二分法查找，查找元素速度比 rbtree 还要快。
1 ... 9  10  11  12  13  14  15  16  17  18 ... 155  
❮ ❯
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1559 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 21ms · UTC 17:15 · PVG 01:15 · LAX 09:15 · JFK 12:15
Developed with CodeLauncher
♥ Do have faith in what you're doing.