在 Javascript 中实现 GroupBy 最有效的方法是什么？

问题描述 投票：0回答：3

我正在尝试使用这些参数实现一个

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 测试，并创建了一个不使用比较器且仅适用于平面类型的方法。 （此处输出测试）

其他库（例如 underscore 和 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"]
    }
]

关于如何实施有什么想法吗？

赏金

对于赏金，我希望您考虑：

  • 密钥可以是一个对象
  • 如果某些属性相等，两个对象可以相等
  • 它应该与现有解决方案一样快或更快
  • 结果可以是数组或对象，只要我能得到按键分组的元素就没关系

好吧，我期待一个完整的答案。

javascript performance grouping
3个回答
5
投票

我使用你的 jsperf 作为参考，了解脚本的一些细节。我真的非常喜欢你的“哈希”代码，所以我完全偷了它。根据“browserscope”图表，我的方法使用不同的方法来生成用于生成哈希的字符串，这似乎更快一些，从而提高了性能。我在测试中包含了“太多递归”概念证明，以表明它具有递归保护，例如 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
));
0
投票

我设法以这种方式实现：

我需要从对象中获取哈希码。

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 上的示例，现在使用 Jedi。

但是，根据我的测试，我的

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
0
投票

我最简单的实现使用

Map
：

function groupByObjectKey(array, callback) {
    const groups = new Map();

    array.forEach(item => {
        const key = callback(item);

        if (!groups.has(key)) {
            groups.set(key, []);
        }

        groups.get(key).push(item);
    });

    return Object.fromEntries(groups.entries());
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.