空间高效(De)可串行化URI查找数据结构

Question

哪些数据结构具有比普通集更好的下列属性：

method

• memory-efficient

• (de)serialisable (memory-efficient)

• exact

• fast包含方法

• fast添加

隶属函数->无概率数据结构

上下文:我们试图用公共部分在内存中存储一堆URI字符串(+1.000.000)，例如：

• http://marineregions.org/mrgid/52969?t=1638014401
• http://marineregions.org/mrgid/57554?t=1638014414
• ...

Answer 1

我能想到的最好的方法是减少输入到不同的部分(删除公共部分)，然后使用Set。内置快速查找的选项是普通对象、Set或Map上的属性。否则，您必须为您自己的哈希查找实现或找到一个实现，这不太可能比内置实现更快。

所以，根据你提供的一些信息，我会在不同的部分选择一个集合。对于您提供的两个示例，我假设http://marineregions.org/mrgid/是公共部分，52969?t=1638014401和57554?t=1638014414是不同的部分，因此我们只能将不同的部分放到集合中。

下面是一个实现：

class CommonSet extends Set {
    constructor(commonPrefix) {
        super();
        this.commonPrefix = commonPrefix;
    }
    add(url) {
        super.add(this._removePrefix(url));
    }
    has(url) {
        let token = this._removePrefix(url);
        return super.has(token);
    }
    _removePrefix(url) {
        if (url.indexOf(this.commonPrefix) !== 0) {
            throw new Error("url does not start with commonPrefix");
        }
        return url.slice(this.commonPrefix.length);
    }
    _addPrefix(token) {
        return this.commonPrefix + token;
    }
    // serialize existing data to JSON string
    serialize() {
        return JSON.stringify({ commonPrefix: this.commonPrefix, data: Array.from(this) })
    }
    // populate existing object from JSON string
    _deserialize(json) {
        const obj = JSON.parse(json);
        this.commonPrefix = obj.commonPrefix;
        if (!this.commonPrefix) {
            throw new Error("didn't find .commonPrefix property");
        }
        if (!Array.isArray(obj.data)) {
            throw new Error("didn't find .data array property");
        }
        for (let url of obj.data) {
            super.add(url);
        }
    }
    // create new CommonSet from previously serialized data
    static deserialize(json) {
        let s = new CommonSet();
        s._deserialize(json);
        return s;
    }
}

关于您的需求的注释：

快速包含方法

使用来自Set对象的.has()方法。内部散列，100%可靠

快速加法

使用来自Set对象的.add()方法。内部哈希。

内存高效

删除URL的公共部分以节省空间。

(De)可串行化(内存高效)

可以将其序列化为一个数据数组(加上commonPrefix)，以实现高效存储，然后从该数组中反序列化。请参见序列化为JSON的.serialize()方法以及从以前序列化的JSON创建新CommonSet的静态`.deserialize()。这种序列化格式(URL的不同部分的数组)相当有效，因为没有冗余对象边界的重复属性名称。为了提高纯空间效率，您可以放弃纯JSON，然后可以使用假定的字符串格式删除引号。这将为每个URL节省两个字符，但在读取它时会使解析变得复杂，因为它不再是合法的JSON，因此您必须构建自己的解析器。

精确隶属函数->无概率数据结构

这组的.has()是精确的。哈希冲突在内部以可靠的方式处理。

其他备注：

如果需要，您可以快速添加对其他Set方法(如.delete() )的支持。.clear()已经可以正常工作了。