如何获得多个 immutable.js 列表的并集
How to get union of several immutable.js Lists
所以,我有清单 a:
let a = Immutable.List([1])
和列表 b:
let b = Immutable.List([2, 3])
我想从他们那里得到列表 union === List([1, 2, 3])
。
我试着merge他们拳头:
let union = a.merge(b); // List([2, 3])
似乎 merge
方法使用索引而不是值操作,因此用 List b
的第一项覆盖 List a
的第一项。所以,我的问题是获得多个列表并集的最简单方法是什么(理想情况下无需迭代它们和其他额外操作)。
关于合并你是正确的。 Merge 将使用合并列表的当前值更新索引。所以在你的情况下你有
[0] = 1
并与
合并
[0] = 2
[1] = 3
最终用 [0]=2
覆盖了 [0]=1
,然后设置 [1]=3
导致合并后观察到的 [2,3]
数组。
解决这个问题的一个非常简单的方法是使用 concat
var a = Immutable.List([1]);
var b = Immutable.List([2,3]);
var c = a.concat(b);
它适用于这种情况。但是,如果情况更复杂,这可能是不正确的。例如,
var a = Immutable.List([1,4]);
var b = Immutable.List([2,3,4]);
这会给你两个 4,这在技术上不再是联合。不幸的是,Immutable 中没有包含联合。实现它的一种简单方法是将每个列表中的每个值设置为对象的键,然后将这些键作为结果联合。
function union(left,right){
//object to use for holding keys
var union = {};
//takes the first array and adds its values as keys to the union object
left.forEach(function(x){
union[x] = undefined;
});
//takes the second array and adds its values as keys to the union object
right.forEach(function(x){
union[x] = undefined;
});
//uses the keys of the union object in the constructor of List
//to return the same type we started with
//parseInt is used in map to ensure the value type is retained
//it would be string otherwise
return Immutable.List(Object.keys(union).map(function(i){
return parseInt(i,10);
}));
}
这个过程是O(2(n+m))
。任何使用 contains
或 indexOf
的进程最终都会成为 O(n^2)
,所以这就是为什么在此处使用密钥的原因。
后期编辑
超高性能
function union(left,right){
var list = [], screen = {};
for(var i = 0; i < left.length; i++){
if(!screen[left[i]])list.push(i);
screen[left[i]] = 1;
}
for(var i = 0; i < right.length; i++){
if(!screen[right[i]])list.push(i);
screen[right[i]] = 1;
}
return Immutable.List(list);
}
实际上 Immutable.js 确实有一个联合 - 它用于 Set 数据结构:
https://facebook.github.io/immutable-js/docs/#/Set/union
Immutable.js 的伟大之处在于它有助于将更多的函数式编程结构引入 JS - 在本例中是一个通用接口和抽象数据类型的能力。因此,为了在您的列表上调用 union - 将它们转换为集合,使用 union 然后将它们转换回列表:
var a = Immutable.List([1, 4]);
var b = Immutable.List([2, 3, 4]);
a.toSet().union(b.toSet()).toList(); //if you call toArray() or toJS() on this it will return [1, 4, 2, 3] which would be union and avoid the problem mentioned in Travis J's answer.
List#merge
的实现在发布此问题后发生了变化,在当前版本中 4.0.0-rc-12
List#merge
按预期工作并解决了问题。
所以,我有清单 a:
let a = Immutable.List([1])
和列表 b:
let b = Immutable.List([2, 3])
我想从他们那里得到列表 union === List([1, 2, 3])
。
我试着merge他们拳头:
let union = a.merge(b); // List([2, 3])
似乎 merge
方法使用索引而不是值操作,因此用 List b
的第一项覆盖 List a
的第一项。所以,我的问题是获得多个列表并集的最简单方法是什么(理想情况下无需迭代它们和其他额外操作)。
关于合并你是正确的。 Merge 将使用合并列表的当前值更新索引。所以在你的情况下你有
[0] = 1
并与
合并[0] = 2
[1] = 3
最终用 [0]=2
覆盖了 [0]=1
,然后设置 [1]=3
导致合并后观察到的 [2,3]
数组。
解决这个问题的一个非常简单的方法是使用 concat
var a = Immutable.List([1]);
var b = Immutable.List([2,3]);
var c = a.concat(b);
它适用于这种情况。但是,如果情况更复杂,这可能是不正确的。例如,
var a = Immutable.List([1,4]);
var b = Immutable.List([2,3,4]);
这会给你两个 4,这在技术上不再是联合。不幸的是,Immutable 中没有包含联合。实现它的一种简单方法是将每个列表中的每个值设置为对象的键,然后将这些键作为结果联合。
function union(left,right){
//object to use for holding keys
var union = {};
//takes the first array and adds its values as keys to the union object
left.forEach(function(x){
union[x] = undefined;
});
//takes the second array and adds its values as keys to the union object
right.forEach(function(x){
union[x] = undefined;
});
//uses the keys of the union object in the constructor of List
//to return the same type we started with
//parseInt is used in map to ensure the value type is retained
//it would be string otherwise
return Immutable.List(Object.keys(union).map(function(i){
return parseInt(i,10);
}));
}
这个过程是O(2(n+m))
。任何使用 contains
或 indexOf
的进程最终都会成为 O(n^2)
,所以这就是为什么在此处使用密钥的原因。
后期编辑
超高性能
function union(left,right){
var list = [], screen = {};
for(var i = 0; i < left.length; i++){
if(!screen[left[i]])list.push(i);
screen[left[i]] = 1;
}
for(var i = 0; i < right.length; i++){
if(!screen[right[i]])list.push(i);
screen[right[i]] = 1;
}
return Immutable.List(list);
}
实际上 Immutable.js 确实有一个联合 - 它用于 Set 数据结构:
https://facebook.github.io/immutable-js/docs/#/Set/union
Immutable.js 的伟大之处在于它有助于将更多的函数式编程结构引入 JS - 在本例中是一个通用接口和抽象数据类型的能力。因此,为了在您的列表上调用 union - 将它们转换为集合,使用 union 然后将它们转换回列表:
var a = Immutable.List([1, 4]);
var b = Immutable.List([2, 3, 4]);
a.toSet().union(b.toSet()).toList(); //if you call toArray() or toJS() on this it will return [1, 4, 2, 3] which would be union and avoid the problem mentioned in Travis J's answer.
List#merge
的实现在发布此问题后发生了变化,在当前版本中 4.0.0-rc-12
List#merge
按预期工作并解决了问题。