在Javascript中实现GroupBy最有效的方法是什么
What is the most efficient way to implement GroupBy in Javascript?
我正在尝试用这些参数实现GroupBy方法
function GroupBy(keySelector, elementSelector, comparer)
{
// keySelector = function(e) { return e.ID }
// elementSelector = function(e) { return e.Name }
// comparer = { Equals: function(a,b) { return a==b }, GetHashCode:... }
}
然而，我不知道一个有效的方法来实现它
我用linq.js创建了一个jsPerf测试，并创建了一种不使用比较器、只处理平面类型的方法。（此处为输出测试）
其他库（如下划线和Lo Dash）不接受comparer参数。因此，它们的实现是无关紧要的。
我的键可能是一个类，所以我需要一些东西来确定TKey在不同的实例中是否相同。
所以基本上，我要做的是复制这里记录的C#Linq GroupBy行为。
样本输入：
var arrComplex =
[
{ N: { Value: 10 }, Name: "Foo" },
{ N: { Value: 10 }, Name: "Bar" },
{ N: { Value: 20 }, Name: "Foo" },
{ N: { Value: 20 }, Name: "Bar" }
];
样本输出（或类似的东西）：
[
{
"Key": {"Value":10},
"Elements":["Foo","Bar"]
},
{
"Key": {"Value":20},
"Elements":["Foo","Bar"]
}
]
关于如何实施，有什么想法吗？
Bounty
对于赏金，我希望你考虑一下：
- 密钥可能是一个对象
- 如果某个属性相等，则两个对象可以相等
- 它应该与现有解决方案一样快或更快
- 结果可以是一个数组或对象，只要我能得到按键分组的元素就没关系
好吧，我期待一个完整的答案。
为了脚本的一些细节，我使用了您的jsperf作为参考。我真的非常喜欢你的"hash"代码，所以我完全偷了它。根据"browserscope"图表，我的代码使用了一种不同的方法来生成用于生成hash的字符串，这似乎更快了一点，从而提高了性能。我在测试中包含了一个"太多递归"的概念证明，以表明它具有递归保护，如JSON.stringify和.toSource（）.
我的jsfiddle显示代码返回您需要的格式。我的jsperf似乎表明它的性能优于发布的解决方案。我也包含了linq.js解决方案，但它在FireFox中的表现对我来说相当糟糕。它在Safari、Chrome和IE中的工作效果相当，但除了在IE中，它的速度并不比我的快。我甚至在手机上尝试过它，但我仍然有相同的性能差异。我亲自在所有浏览器的最新版本中测试了它，并与发布的解决方案并排使用，我的每种浏览器的性能都提高了约40%。每个人的想法是什么？
这是我的代码：
var arr = [
{ N: 10, Name: "Foo" },
{ N: 10, Name: "Bar" },
{ N: 20, Name: "Foo" },
{ N: 20, Name: "Bar" }
];
var poc = { name:'blah', obj:{} };
poc.obj = poc;
var arrComplex = [
{ N: { Value: 10, TooMuchRecursionProofPOC:poc }, Name: "Foo" },
{ N: { Value: 10, TooMuchRecursionProofPOC:poc }, Name: "Bar" },
{ N: { Value: 20, TooMuchRecursionProofPOC:poc }, Name: "Foo" },
{ N: { Value: 20, TooMuchRecursionProofPOC:poc }, Name: "Bar" }
];
var eArr = Enumerable.From(arr);
var eArrComplex = Enumerable.From(arrComplex);
function setup_hashers() {
// recursion protection idea
var rp = '_rp'+(Math.random()*10000000);
function tstr() {
var out = '', i = '';
if (this[rp]) { this[rp] = undefined; return out; }
for (i in this)
if (i != rp && this.hasOwnProperty(i))
out += this[i] instanceof Object
? ((this[rp] = true) && this[i] != this && !this[i][rp] ? tstr.call(this[i]) : '')
: (this[i].toString || tstr).call(this[i]);
return out;
};
Number.prototype.GetHashCode = function() {
return this.valueOf();
};
Object.prototype.GetHashCode = function() {
var s = (this instanceof Object ? tstr : this.toString || tstr).call(this),
h = 0;
if (s.length)
for (var i = 0; i < s.length; i++)
h = ((h << 5) - h) + s.charCodeAt(i);
return h;
};
}
function group_by(a, keyFunc, valFunc, comp, as_array) {
if (!a.length) return as_array ? [] : {};
var keyFunc = keyFunc || function (e) { return e; },
valFunc = valFunc || function (e) { return e; };
var comp = comp || {
Equals: function (a, b) { return a == b; },
Hash: function (e) { return e.GetHashCode(); }
};
var hashs = {}, key = '', hash = '';
for (var i = 0; i < a.length; i++) {
key = keyFunc(a[i]);
hash = comp.Hash(key);
if (typeof hashs[hash] != 'undefined')
hash = comp.Equals(key, hashs[hash].Key)
? hash
: hash + '-' + i;
hashs[hash] = hashs[hash] || { Key: key, Elements: [] };
hashs[hash].Elements.push(valFunc(a[i]));
}
if (as_array) {
var out = [], j = '', keys = Object.keys(hashs);
for (var j = 0; j < keys.length; j++)
out.push(hashs[keys[j]]);
return out;
}
return hashs;
};
function group_by_control(a, keyFunc, valFunc) {
if (!a.length) return as_array ? [] : {};
var keyFunc = keyFunc || function (e) { return e; },
valFunc = valFunc || function (e) { return e; };
var hashs = {}, key = '', hash = '';
for (var i = 0; i < a.length; i++) {
key = keyFunc(a[i]);
hashs[key] = hashs[key] || { Key: key, Elements: [] };
hashs[key].Elements.push(valFunc(a[i]));
}
var out = [], j = '', keys = Object.keys(hashs);
for (var j = 0; j < keys.length; j++)
out.push(hashs[keys[j]]);
return out;
};
setup_hashers();
console.log(group_by_control(
arr,
function(e) { return e.N },
function(e) { return e.Name }
));
console.log(group_by(
arrComplex, function(e) { return e.N; },
function(e) { return e.Name; },
{
Equals: function(a, b) { return a.Value == b.Value },
Hash: function(e) { return e.GetHashCode(); }
}
));
console.log(group_by(
arrComplex, function(e) { return e.N; },
function(e) { return e.Name; },
{
Equals: function(a, b) { return a.Value == b.Value },
Hash: function(e) { return e.GetHashCode(); }
},
true
));
我设法实现了这种方式：
我需要从对象中获取哈希代码。
Object.prototype.GetHashCode = function () {
var s = this instanceof Object ? stringify(this) : this.toString();
var hash = 0;
if (s.length === 0) return hash;
for (var i = 0; i < s.length; ++i) {
hash = ((hash << 5) - hash) + s.charCodeAt(i);
}
return hash;
};
Number.prototype.GetHashCode = function () { return this.valueOf(); };
由于JSON.stringify在循环引用时会失败，我创建了另一种方法来字符串化它，这样我就可以将对象的大部分内容作为字符串，并计算其上的哈希代码，如下所示：
function isPlainObject(obj)
{
if ((typeof (obj) !== "object" || obj.nodeType || (obj instanceof Window))
|| (obj.constructor && !({}).hasOwnProperty.call(obj.constructor.prototype, "isPrototypeOf"))
)
{
return false;
}
return true;
}
function stringify(obj, s)
{
s = s || "";
for (var i in obj)
{
var o = obj[i];
if (o && (o instanceof Array || isPlainObject(o)))
{
s += i + ":" + JSON.stringify(o);
}
else if (o && typeof o === "object")
{
s += i + ":" + "$ref#" + o;
}
else
{
s += i + ":" + o;
}
}
return s;
}
对性能没有太大影响。对于大的物体来说，它是一样的，对于小的物体来说它会丢失，但仍然非常快速和安全。此处为性能测试。
Name op/s
---------------------------------
JSON.stringify large 62
stringify large 62
JSON.stringify small 1,690,183
stringify small 1,062,452
我的GroupBy方法
function GroupBy(a, keySelector, elementSelector, comparer)
{
// set default values for opitinal parameters
elementSelector = elementSelector || function(e) { return e; };
comparer = comparer ||
{
Equals: function(a,b) { return a==b },
GetHashCode: function(e) { return e.GetHashCode(); }
};
var key, hashKey, reHashKey;
// keep groups separated by hash
var hashs = {};
for (var i = 0, n = a.length; i < n; ++i)
{
// in case of same hash, but Equals returns false
reHashKey = undefined;
// grabs the key
key = keySelector(a[i]);
// grabs the hashcode
hashKey = comparer.GetHashCode(key);
// if a hash exists in the list
// compare values with Equals
// in case it return false, generate a unique hash
if (typeof hashs[hashKey] !== "undefined")
reHashKey = comparer.Equals(key, hashs[hashKey].Key) ? hashKey : hashKey + " " + i;
// if a new hash has been generated, update
if (typeof reHashKey !== "undefined" && reHashKey !== hashKey)
hashKey = reHashKey;
// get/create a new group and add the current element to the list
hashs[hashKey] = hashs[hashKey] || { Key: key, Elements: [] };
hashs[hashKey].Elements.push(a[i]);
}
return hashs;
}
测试
var arrComplex =
[
{ N: { Value: 10 }, Name: "Foo" },
{ N: { Value: 10 }, Name: "Bar" },
{ N: { Value: 20 }, Name: "Foo" },
{ N: { Value: 20 }, Name: "Bar" }
];
//
var x = GroupBy(arrComplex
, function(e) { return e.N; }
, function(e) { return e.Name; }
, {
Equals: function(a,b) { return a.Value == b.Value },
GetHashCode: function(e) { return e.GetHashCode(); }
}
);
//
console.log(x);
jsFiddle的例子，现在是绝地武士。
但是，根据我的测试，我对GroupBy的实现比linq.js的GroupBy慢。当我转换ToArray()时，它只会更快。也许linq.js只有在我转换为数组时才真正执行，这就是为什么不同，我不确定这一部分。
测试结果
Name op/s
---------------------------------
GroupBy 163,261
GroupByToArray 152,382
linq.js groupBy 243,547
linq.js groupBy toArray 26,309
相关文章：
- 在jQuery中创建向下滑动子菜单的最有效方法
- 使用Underscore.js修改json数组中所选元素的更有效方法
- 选择具有值数组的所有元素的最有效方法
- 将JSON存储和恢复到此Ionic应用程序的最有效方法
- 将javascript数组中的项移动到特定位置的有效方法
- 将JS对象数组转换为嵌套形式的最有效方法
- 隐藏具有特定类$.each、for等的元素的有效方法
- 什么's是调用具有可变参数的函数的有效方法
- 选择具有特定数据的所有 html 标记的最有效方法是什么 - [适当性]，无论值如何
- 使用 jQuery 调用 PHP 端点的最有效方法
- 这是解析 Int 的有效方法吗?
- 在JavaScript中搜索数组映射的最有效方法
- 获取字符串中最后一个换行符的最有效方法是什么
- 什么's是在两个(或多个）阵列中找到匹配的细胞序列的最有效方法
- 什么's是在IE8+中添加元素的最有效方法
- 从任何jquery选择器字符串创建元素的最有效方法
- 在日期范围内查找丢失日期的最有效方法是什么
- 对区间[1,10^12]中的整数进行编码/解码的快速有效方法是什么
- 在条件(if）结构的条件语句中是否有定义变量的有效方法
- 在ASP.NET中使用JQuery UI自动完成的有效方法
