7

javascript中是否有简单的不可变哈希和数组实现？我不需要最好的速度，比克隆更好的合理速度就可以了。

此外，如果有Java 或其他一些易于理解并移植到 JavaScript 的语言的简单实现，那也很好。

更新：

目标不仅仅是冻结散列（或数组），而是要有效地执行更新操作 - 不可变散列的更新应该返回一个新的不可变散列。它应该比“克隆原始并更新它”更有效。

原生 JS 类型的更新复杂度类似于 O(1)，克隆复杂度将是 O(n)，使用特殊的不可变数据结构（我要求的）它将是 0(log(n))

UPDATE2： JavaScript 已经有 Array / Hash ：

是的，但它们是可变的，我需要类似但不可变的东西，基本上可以通过克隆非常简单地完成，hash2 = hash1.clone(); hash2[key] = value但效率非常低，有些算法使其非常有效，无需使用clone.

hash1 = {}
hash2 = hash1.set('key', 'value2')
hash3 = hash1.set('key', 'value3)

console.log(hash1) // => {}
console.log(hash2) // => {key: 'value2'}
console.log(hash3) // => {key: 'value3'}

解决方案：

它不是不可变哈希的实现，但更像是我当前问题的破解，也许它也可以帮助某人。

关于为什么我需要不可变数据结构的更多信息——我使用 Node.js 和某种内存数据库。一个请求可以读取数据库，另一个更新它 - 更新可能需要很多时间（调用远程服务） - 所以我不能阻止所有读取进程并等到更新完成，更新可能会失败并且数据库应该回滚. 所以我需要以某种方式隔离（ACID）对内存数据库的读写操作。

这就是为什么我需要不可变数组和散列 - 来实现某种 MVCC。但似乎有一种更简单的方法可以做到这一点。而不是直接更新数据库 - 更新操作只记录对数据库的更改（但不直接执行） - 以“将 42 添加到数组 db.someArray”的形式。

最后 - 更新操作的产物将是一组这样的更改命令，并且因为它可以非常快速地应用 - 我们可以阻止数据库应用它。

但是，看看 javascript 中是否有不可变数据结构的实现仍然会很有趣，所以我将把这个问题留着。

4

4 回答 4

6

我知道这个问题很老，但我认为像我一样搜索的人应该指向 Facebook 的Immutable.js，它以非常有效的方式提供了许多不同类型的不可变数据结构。

于 2015-01-23T22:06:10.463 回答
4

我对 JS 的持久数据结构有相同的要求，所以前段时间我实现了一个持久映射.. https://github.com/josef-jelinek/cofy/blob/master/lang/feat.js

它包含一个基于平衡树（排序）的映射和一个简单的写时复制映射（和未完成的持久向量/数组）的实现。

var map = FEAT.map();
var map1 = map.assoc('key', 'value');
var value = map1.get('key');
var map2 = map1.dissoc('key');
...

它支持其他方法，如count(), contains(key), keys(into = []), values(into = []), toObject(into = {}),toString()

实现不是太复杂，它是在公共领域。我也接受建议和贡献者:)。

更新：您可以在https://github.com/josef-jelinek/cofy/blob/master/tests/test-feat.html找到单元测试（使用示例）

更新 2：持久向量实现现在也有以下操作：count(), get(i), set(i, value), push(value), pop(), toArray(into = []),toString()

于 2012-11-10T13:15:56.923 回答
0

我知道在 Javascript 中克隆对象的最佳方法是包含在underscore.js中的方法

不久：

_.clone = function(obj) {
  if (!_.isObject(obj)) return obj;
  return _.isArray(obj) ? obj.slice() : _.extend({}, obj);
};

_.extend = function(obj) {
  each(slice.call(arguments, 1), function(source) {
    for (var prop in source) {
      obj[prop] = source[prop];
    }
  });
  return obj;
};
于 2012-11-09T19:21:50.353 回答
0

使对象不可变的唯一方法是将其隐藏在函数中。然后，您可以使用该函数返回默认哈希或更新版本，但您实际上不能在全局范围内存储不可变哈希。

function my_hash(delta) {
    var default = {mykey: myvalue};
    if (delta) {
        for (var key, value in delta) {
            if (default.hasOwnProperty(key)) default[key] = value;
        }
    }
    return default;
}

我不认为这是一个好主意。

于 2012-11-09T19:16:08.077 回答