Radix Tree算法效率的问题

[NewFuture]

最开始是被这个算法吸引的，但是思考之后，似乎不是一个最优的方案。

Radix Tree 的搜索长度基本上对应了子网掩码的位数

对于CN Ipv4 地址区间统计：

lines items 19460
IPv4 cidrs items 7030
mask_counter Counter({22: 1831, 24: 1317, 23: 855, 21: 653, 20: 423, 19: 321, 16: 256, 18: 201, 15: 189, 31: 155, 14: 152, 17: 141, 30: 115, 13: 102, 32: 90, 12: 73, 29: 43, 11: 31, 28: 22, 27: 19, 10: 15, 26: 14, 25: 12})
min_mask 10 min_mask count 15
max_mask 32 max_mask count 90
avg_mask 21.588762446657185

也就是说，平均需要 21.6次查询，最少10次，最多31 次。

如果对于7030个区间（有序且d不重叠）采用二分查找，那么最多只有需要13次比较(2^13 = 8192)。
这个最差情况基本上相当于Radix Tree的最好情况了。
数据构建也非常简单，整个数组大数组可直接静态生成。而且查询过程也只需要一次内置函数convert_addr进行转换。
核心算法的GPT实现

// 二分查找查找目标值是否在区间内
// 查询函数：检查目标 IP 是否在 CIDR 区间内
function isInCidr(cidrList, ip) {
    const ipInt = convert_addr(ip);  // 将目标 IP 转换为整数
    let left = 0;
    let right = cidrList.length - 1;

    // 使用二分查找查找 IP 所属的 CIDR 区间
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const [startIp, endIp] = cidrList[mid];

        if (ipInt < startIp) {
            right = mid - 1;
        } else if (ipInt > endIp) {
            left = mid + 1;
        } else {
            return true;  // IP 在当前 CIDR 区间内
        }
    }
    
    return false;  // 未找到匹配的 CIDR 区间
}

// 示例 CIDR 区间，已经是预处理后的整数形式
const cidrRanges = [];

// 示例用法
console.log(isInCidr(cidrRanges, '10.1.1.1'));     // 输出 true
console.log(isInCidr(cidrRanges, '192.168.1.1'));  // 输出 false

对于IPv6 范围大概是 (12430)，二分最多也就14次。
(IPV6 只需要比较64位的，可能需要拆成两个32位数，或者两个块但是算法效果一样)。

[zhiyi7]

加上ipv6，一共19500个地址段，从次数上看确实是二分法次数少。有两个问题：
1、使用二分法生成静态数组，需要包含网络起始和结束地址，生成的最终文件会超过iOS可正确执行的大小，这个有什么办法解决么。
2、如果加上js对数组和map的处理时间因素，二分和树的查询实际时间可以做个测试么（这一点仅从纯查找算法执行时间考虑，实际上两种算法导致的时间差，一个网络小波动就都覆盖掉了）

[NewFuture]

IPv4和 IPv6应该分开处理

对于IPv4

1. 如果要节省字符空间的话可以使用[有效位数值+移位数]的方式存储。

例如 103.212.109.0/24

• 转换数字

01100111 11010100 01101101 00000000 (1741974784)，掩码24位，剩余后补8位

• 右移动8位得到

01100111 11010100 01101101(6804589)

• 存储:
  js字符 [7280973,8]
• 运行时展开 [7280973<<8,7280973<<8|(2**8-1)]即 (1741974784,1863929343)

这个存储空间和展开效率应该比现在树的实现更高。

2. 这个和实现pac的js引擎有关，但是根个人经验，几乎所有语言数组的索引访问，会比对象的key查询效率要高的多。

[zhiyi7]

IPv6拆成多个32位后，怎么处理更好

[NewFuture]

对于IPv6, 根据CN CIDR的数据

IPv6 cidrs items 12429
ipv6_mask_counter Counter({64: 6527, 32: 1868, 48: 1707, 63: 994, 47: 306, 62: 180, 44: 79, 40: 76, 46: 75, 43: 62, 45: 53, 41: 44, 42: 43, 39: 40, 61: 39, 38: 34, 55: 24, 56: 23, 36: 21, 37: 17, 35: 17, 60: 16, 52: 16, 58: 14, 59: 14, 34: 13, 31: 12, 57: 12, 29: 12, 33: 12, 54: 11, 24: 8, 50: 7, 51: 7, 53: 7, 20: 7, 30: 6, 28: 6, 21: 5, 49: 4, 22: 4, 25: 2, 26: 2, 23: 1, 27: 1, 18: 1})
ipv6_min_mask 18 ipv6_min_mask count 1
ipv6_max_mask 64 ipv6_max_mask count 6527
ipv6_avg_mask 55.08351436157374

掩码最短是18位，最长是64位。
2001:250::/30 - 2c0f:f7a8:9220::/48

64位系统js里面一个安全整数的最大值是 2**53 - 1 (52位)，因此一个整数无法完整存储这个ipv6前缀

目前想到两种思路：

1. 分块区间查询(前12位)，三维数组
   前12位拆成分块 [200~2c0]分成193个连续块，作为第一维度，后面52位转成整数和ipv4类似处理
   查找时

• 前12位值-512 映射带对应分块，
• 后52位在分块内部内二分查找

运行时的数据格式
2c0f:f7a8:9010::/48 =>

[
// 192 列
[...,[1097272467968,1097272533504]] //parseInt("ff7a890100000",16),parseInt("ff7a89010FFFF",16)
]

2. 二维数组，但是每个区间里用两个或者三个数表示

• 掩码不足32 [前32位,前32结束值], 掩码超过32 [前32位，随后32位，随后32位结束值]，
• 每个输入ip可转成两个数二分查找[前32，随后32位]，找到前32位之后开始比较后32位

2c0f:f7a8:9010::/48 =>

[
[739243944,2416967680,2417033215]
//[parseInt("2c0ff7a8",16),parseInt("90100000",16),parseInt("90100000",16)-1+2**16]
]

[NewFuture]

请教一下，这PAC是怎么Debug的？

[zhiyi7]

请教一下，这PAC是怎么Debug的？

用Firefox，工具-浏览器工具-浏览器控制台（不是web控制台）。PAC文件里的alert会出现在这里。