6

Estou tentando implementar um GroupBy com estes parâmetros

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:... }
}

Entretanto eu não sei um modo eficiente de implementar isto.

Eu criei um teste no jsPerf aqui com linq.js e um método que criei que não utiliza um comparer, logo este só funciona em tipos 'normais'. (Teste destes métodos aqui)

Outras bibliotecas como underscore e Lo-Dash não tem o parametro comparer então a implementação deles não é relevante.

A chave de cada grupo pode ser até uma classe, preciso de um comparer para saber se o valor da chave é igual entre objetos.

Basicamente estou tentando copiar o C# Linq GroupBy documentado aqui.

Exemplo de entrada:

var arrComplex =
[
    { N: { Value: 10 }, Name: "Foo" },
    { N: { Value: 10 }, Name: "Bar" },
    { N: { Value: 20 }, Name: "Foo" },
    { N: { Value: 20 }, Name: "Bar" }
];

Exemplo de saída (ou algo assim):

[
    {
       "Key": {"Value":10},
       "Elements":["Foo","Bar"]
    },
    {
        "Key": {"Value":20},
        "Elements":["Foo","Bar"]
    }
] 

Alguma ideia de como implementar isto?

4
  • Deixa eu ver se entendi, você quer comparar se keySelector (que é igual ao id de um elemento) é igual ao elementSelector (que é o name de outro elemento)? Commented 17/12/2013 às 13:48
  • Basicamente estou tentando copiar o GroupBy do c# msdn.microsoft.com/en-us/library/bb534304(v=vs.110).aspx . keySelector é o que vai extrair a chave de um objeto para ser a chave do grupo. elementSelector é o que vai extrair o objeto a ser colocado na lista de elementos do grupo.
    – BrunoLM
    Commented 17/12/2013 às 13:57
  • Então você quer criar um array associativo, é isso? Commented 17/12/2013 às 14:22
  • @KennyRafael O group by faz isso, var arr= [{ Chave: 1, Valor: 2}, { Chave: 1, Valor: 3}]... Agrupando o resultado fica [{ Key: 1, Elements: [2,3] }]. Tambem poderia ser um array assosiativo... { 1: [2,3] }...
    – BrunoLM
    Commented 17/12/2013 às 15:30

2 Respostas 2

5

Muitas bibliotecas que implementam GroupBy colocam como requisito adicional que a entrada já esteja ordenada por chave. Uma ordenação por chave é O(N*log(N)), mas uma vez realizada é possível agrupar listas de qualquer tamanho rapidamente, em O(N), pois basta comparar a chave de um elemento com a chave do último grupo encontrado:

function GroupBySimples(a, keySelector, elementSelector, comparer)
{
    if ( a.length == 0 )
        return [];
    elementSelector = elementSelector || function(e) { return e; };
    comparer = comparer ||
        {
            Equals: function(a,b) { return a==b },
            GetHashCode: function(e) { return e.GetHashCode(); }
        };

    var ultimaChave = keySelector(a[0]);
    var ultimoElemento = { Key: ultimaChave, Elements: [elementSelector(a[0])] };
    var ret = [ultimoElemento];
    for (var i = 1, n = a.length; i < n; ++i)
    {
        var key = keySelector(a[i]);
        if ( comparer.Equals(key, ultimaChave) )
            ultimoElemento.Elements.push(elementSelector(a[i]));
        else {
            ultimaChave = keySelector(a[i]);
            ultimoElemento = { Key: key, Elements: [elementSelector(a[i])] };
            ret.push(ultimoElemento);
        }
    }

    return ret;
}

var arrComplexOrdenado = arrComplex.sort(function(a, b) {
    return a.N.Value - b.N.Value;
});
var resultArray = GroupBySimples(arrComplexOrdenado
        , function(e) { return e.N; }
        , function(e) { return e.Name; }
        , {
              Equals: function(a,b) { return a.Value == b.Value },
              GetHashCode: function(e) { return e.Value.GetHashCode(); }
          }
);

Como você pode observar nesse teste de performance, esse método é mais de 3x eficiente que as alternativas apresentadas (usando hashes).

Notas:

  1. Eu aumentei o tamanho do array de entrada de 4 para 100.000, pro teste ficar mais relevante.

  2. Você tem certeza que o linq.js está produzindo um resultado correto? A performance dele continuou mais ou menos a mesma, com uma entrada vinte e cinco mil vezes maior, alguma coisa só pode estar errada...

0

Eu consegui implementar desta forma:

Primeiro preciso de uma forma de pegar o HashCode dos objetos.

Object.prototype.GetHashCode = function () {
    var s = this instanceof Object ? JSON.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(); };

Agora meu GroupBy ficou assim

function GroupBy(a, keySelector, elementSelector, comparer)
{
    // seta os valores padrões para os parâmetros opicionais
    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;

    // agrupa elementos pelo hashcode
    var hashs = {};
    for (var i = 0, n = a.length; i < n; ++i)
    {
        // para caso do hash ser igual, mas retornar false no Equals
        reHashKey = undefined;

        // obtêm a chave do objeto
        key = keySelector(a[i]);
        // pega o hashcode do objeto
        hashKey = comparer.GetHashCode(key);

        // se o hash já existe na lista
        // compara os valores com Equals
        // caso retorne falso, gera um hash unico
        if (typeof hashs[hashKey] !== "undefined")
            reHashKey = comparer.Equals(key, hashs[hashKey].Key) ? hashKey : hashKey + " " + i;

        // se foi gerado um hash novo, utiliza-se esse
        if (typeof reHashKey !== "undefined" && reHashKey !== hashKey)
            hashKey = reHashKey;

        // pega ou cria um grupo e adiciona os elementos
        hashs[hashKey] = hashs[hashKey] || { Key: key, Elements: [] };
        hashs[hashKey].Elements.push(a[i]);
    }

    return hashs;
}

Para testar

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);

Exemplo no jsFiddle

Mas, de acordo com meus testes, a minha implementação do GroupBy é mais lenta que a do linq.js. Só é mais rápido quanto converto o resultado para um array.

Resultados do teste

Nome                         op/s
---------------------------------
GroupBy                   163,261
GroupByToArray            152,382
linq.js groupBy           243,547
linq.js groupBy toArray    26,309
3
  • Tem certeza que você não está comparando maçãs com laranjas? O seu GetHashCode por exemplo é terrivelmente ineficiente (e à primeira vista, incorreto), o método "linq" está fazendo uso dele? Se o seu método estiver usando ele, e o linq não, isso explicaria a diferença de performance...
    – mgibsonbr
    Commented 17/12/2013 às 14:56
  • Esse método GetHashCode eu copiei de alguma resposta no Stack Overflow, eu não sei como implementar isto, como seria mais eficiente?
    – BrunoLM
    Commented 17/12/2013 às 14:58
  • Pra começar, é importante que o GetHashCode seja coerente com o Equals: se o seu comparer diz que duas chaves são iguais se os Values são iguais, o hash da chave (de acordo com o comparer) só deve fazer o hash de Value - não do objeto inteiro. Por que? Simplesmente porque dois objetos com o mesmo Value e alguma outra propriedade diferente teriam hashes diferentes mas o mesmo valor. Quanto a um método de propósito geral para fazer hashes de qualquer objeto, precisaria de um tempo pra pensar em algo, mas converter pra JSON e fazer o hash disso não me parece uma boa ideia.
    – mgibsonbr
    Commented 17/12/2013 às 15:01

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .