从头开始全面介绍DirectX12游戏编程（龙书DX版）
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
《从头开始全面介绍DirectX12游戏编程（龙书DX版）》是一本深度解析DirectX 12技术的游戏开发指南，旨在帮助开发者掌握高效图形渲染与游戏引擎构建技巧。
典型的 Top K 算法在这篇文章中有详细阐述，请参见《从头到尾彻底解析 Hash 表算法》。
文中给出的最终算法如下：
第一步：先对这批海量数据进行预处理，在 O(N) 的时间内使用哈希表完成统计。
第二步：借助堆这种数据结构，找出 Top K。时间复杂度为 NlogK。（之前写成了排序，特此订正。）
通过维护一个大小为 K（题目中是 10）的小根堆，并遍历所有查询，在 log 时间内查找和调整/移动元素，可以高效地找到频率最高的前 K 个元素。
因此，最终的时间复杂度为 O(N) + N*O(logK)，其中 N 是总的查询数量。详情请参考原文内容。
此外，还可以采用 Trie 树来实现：在关键字域中存储该查询串出现的次数（未出现则计数为0），然后使用大小为10的小根堆对频率进行排序。
对于一个 1G 大小文件的问题，其中每一行是一个词且每个词不超过 16 字节，并受内存限制 (大小是 1M)，需要返回频次最高的前 100个词。解决方案如下：
顺序读取文件中的每一个单词 x 并计算 hash(x)%5000 的值，然后将该结果对应的行数据存入到由这 5000 小文件组成的集合中（记为x_0, x_1,...,x_4999）。这样每个小文件的大小大约是200K。
如果某些子文件超过了1M，则可以继续使用相同的方法将其分解，直到所有的小文件都不超过内存限制。对于每一个小文件，统计其中出现的所有词以及相应的频率（可选用 Trie 树或 hash_map 等数据结构），并从中选取前 100 频率最高的词及其对应的频次存入新文件中。
最后一步是将这5000个子集进行归并操作以获取最终结果，类似于归并排序的过程。
对于有10个每个大小为1G的文件且其中每行存放用户查询的问题（这些查询可能重复），需要按照出现频率对它们进行排序。还是属于典型的 Top K 问题，解决方案如下：
方案一：顺序读取这十个文件，并根据 hash(query)%10 的结果将 query 写入到另外十个小文件中去。这样每个新的小文件大小大约也是1G（假设哈希函数是随机的）。
然后利用内存为2GB左右的机器，使用hash_map(query,query_count)来统计每一个查询出现的次数，并通过快速排序/堆排序或者归并排序等方法按照频率进行排列。最后得到一个包含每个查询和它对应的频次列表即可完成任务。
全部评论 (0)
