时间戳

首页 > 解决方案 > 将 C 函数转换为 Javascript

javascript - 将 C 函数转换为 Javascript

问题描述

最后编辑：我错了。Redis 文档中没有任何内容表明该计数器仅达到 255 大约 100 万。只是在达到 100 万次点击时，计数器为 255。案件已结案。不要再看了。

我正在尝试将Redis 的 LFU 算法从 C 移植到 JS。它使用莫里斯计数器。

常数：

LFU_INIT_VAL = 5. 看到这里。

lfu_log_factor = 10. 在这里看到

C 函数，可在此处找到。

/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

我的 JS 端口：

LFU_INIT_VAL = 5
lfu_log_factor = 10

function LFULogIncr(counter) {
    if (counter == 255) return 255;
    let r = Math.random();
    let baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    let p = 1.0/(baseval*lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

运行算法 100 万次，并记录计数器递增时的迭代索引：

let hitFreq = 5
for (let i = 0; i < 1000000; i++) {
    let newHitFreq = LFULogIncr(hitFreq)
    if (newHitFreq > hitFreq) {
        console.log(`New counter: ${newHitFreq}, i = ${i}`)
    }
    hitFreq = newHitFreq
}

基于此表，可在链接中找到...

+--------+------------+------------+------------+------------+------------+
| factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
+--------+------------+------------+------------+------------+------------+
| 0      | 104        | 255        | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 1      | 18         | 49         | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 10     | 10         | 18         | 142        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 100    | 8          | 11         | 49         | 143        | 255        |
+--------+------------+------------+------------+------------+------------+

根据上表，当 alfu_log_factor为 10 时，当达到 100 万次点击时，计数器应该是 255。但是，当运行我的 JS 代码时，计数器在大约 30 万次点击中始终达到 255。我究竟做错了什么？

这是一次运行 JS 代码的结果，将实际命中数与预期命中数进行比较，afactor为 10：

编辑：嗯...我在 C 中得到与在 JS 中相同的结果。255 的计数器最终会产生约 30 万次点击。

https://onlinegdb.com/Sy8Y8-SJN

表格错误/过时，或者我进行错误的测试，或者代码正确并且我误解了结果。

标签： javascriptcalgorithm

解决方案

推荐阅读