我试图编写一个遍历字符串列表并返回列表中最常见的前10个字符串的函数。我正在尝试针对这个问题提出多种解决方案
这是我的第一个解决方案
const list = [
"this",
"is",
"a",
"test",
"which",
"word",
"wins",
"top",
"i",
"don't",
"know",
"off",
"hand",
"do",
"you",
"this",
"a",
"a",
"this",
"test",
"a",
"a",
"do",
"hand",
"hand",
"a",
"whatever",
"what",
"do",
"do"
];
function fn1(strArr) {
const map = new Map()
for(const str of strArr) {
if(map.has(str)) {
map.set(str, map.get(str) + 1)
} else {
map.set(str, 1)
}
}
const sortedMap =[...map.entries()].sort(([_,a], [__,b]) => a < b ? 1 : -1)
return sortedMap.slice(0 , 10).map(([str]) => str)
}
但是我似乎找不到其他解决方案。有人可以提出替代建议吗？
另外，要注意的一件事是列表可能很大，可能包含一百万个字符串。所以我们需要尽量减少运行时的复杂性
我相信以下解决方案在实践中是最快的：
n正如已经完成的，将字符串映射到其频率。O(n)O(n)⌊n/2⌋ - 1低到0的索引调用max-heapify ）。O(n)k时间。（对于您而言，k=10。）O(k log n)（我这里没有提供任何代码，因为它基本上是由调用二进制堆库组成的（高度优化的实现请参见此处）。）
渐近复杂度O(n + k log n)小于O(n log k)混沌猴子提供的解决方案。对于较小的对象k（例如10），可能不会有任何显着差异。越大，差异越明显k（只要k ≪ n；更大k，请参见下面的“替代”）。另请注意，步骤1和2的常数因子为1，而步骤3的常数因子也平均较小（1.8814），因此总常数因子小于4。
有一种解决方案可以O(n)平均地解决该问题，而且还具有较小的常数因子，对于较大的因子k（即k接近时n/2），效率更高。缺点是（极不可能）最坏情况下的复杂度是O(n²)：
n正如已经完成的，将字符串映射到其频率。O(n)O(n)k最大频率。左侧的所有元素甚至更大，因此结果是kQuickselected数组的第一个元素。O(n)平均，O(n²)最坏的情况。可以O(n)使用中位数枢轴选择来实现具有保证复杂性的Quickselect变体，但这在实际中并不是那么好，因为恒定因子非常高。但是从学术角度来看，这将是渐近最优解。
（这是一个用于Quickselect的JavaScript库，尽管乍一看，该实现似乎不适用于这种情况：一个好的实现应该执行Dijkstra风格的3路分区。）
一个快速和肮脏的基准用n = 10^6，k = 10，仅测量运行时步骤2后（由于步骤1/2全部5种方法之间共享）：
Average time for Sort: 7.5 ms
Average time for ChaosMonkey: 10.25 ms
Average time for CountingSort: 5.25 ms
Average time for Mo B. Max-Heap: 4 ms
Average time for Mo B. Alternative (Quickselect): 3.25 ms
https://dotnetfiddle.net/oHRMsp
我的结论是，对于给定的参数，不同方法之间没有太大差异。为简单起见，我将坚持使用排序方法，该方法对于n和都可以很好地扩展k。
（很多警告：它是用C＃（而不是JavaScript）编写的（草率的）；尚未经过正确性测试；未优化单个方法；运行时也可能取决于频率的分布，实现的Quickselect天真，因为未对其进行优化对于（这里）很多频率相等的常见情况等）
所有基准测试方法都使用一个额外的O(n)空间，因为它们首先创建频率图（而计数排序方法O(n)在频率图的顶部使用一个额外的最坏情况空间进行计数）。可以仅用O(1)额外的空间来解决该问题，但要以时间复杂度为代价O(kn²)。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句