Pergunta

Eu tenho o que é essencialmente uma matriz irregular de pares de valores nome - eu preciso para gerar um conjunto de valores de nome únicas deste. a matriz recortada é de aproximadamente 86.000 x 11 valores. Não importa para mim que forma eu tenho que armazenar um valor nome par (um único string "name = value" ou uma classe especializada, por exemplo KeyValuePair).
Informação adicional:. Existem 40 nomes distintos e um maior número de valores distintos - provavelmente na região 10.000 valores

Eu estou usando C # e .NET 2.0 (e o desempenho é tão pobre Estou a pensar que pode ser melhor para empurrar toda a minha matriz denteada em um banco de dados SQL e fazer um distinto seleto de lá).

A seguir é o atual código Im usando:

List<List<KeyValuePair<string,string>>> vehicleList = retriever.GetVehicles();
this.statsLabel.Text = "Unique Vehicles: " + vehicleList.Count;

Dictionary<KeyValuePair<string, string>, int> uniqueProperties = new Dictionary<KeyValuePair<string, string>, int>();
foreach (List<KeyValuePair<string, string>> vehicle in vehicleList)
{
    foreach (KeyValuePair<string, string> property in vehicle)
    {
        if (!uniqueProperties.ContainsKey(property))
        {
            uniqueProperties.Add(property, 0);
        }
    }
}
this.statsLabel.Text += "\rUnique Properties: " + uniqueProperties.Count;
Foi útil?

Solução

Tenho que correr em 0,34 segundos abaixo dos 9 + minutos

O problema é quando se comparam as estruturas KeyValuePair. Eu trabalhei em torno dele por escrever um objeto comparer, e passando uma instância dele ao dicionário.

De que eu posso determinar, a KeyValuePair.GetHashCode () retorna o hashcode dela do objeto Key (neste exemplo, o objeto menos exclusivo).

Como o dicionário acrescenta (e verifica existência de) cada item, ele usa ambos Equals e funções GetHashCode, mas tem de contar com a função Igual quando o hashcode é menos único.

Ao fornecer uma função GetHashCode mais original, é excerises Iguais funcionar com muito menos freqüência. Eu também otimizou o Equals funcionar para comparar os valores mais originais antes que as chaves menos unqiue.

86.000 * 11 itens com 10.000 propriedades únicas corridas em 0,34 segundo, usando o objecto comparador abaixo (sem o objeto comparador que leva 9 minutos, 22 segundos)

Espero que isso ajude:)

    class StringPairComparer
        : IEqualityComparer<KeyValuePair<string, string>>
    {
        public bool Equals(KeyValuePair<string, string> x, KeyValuePair<string, string> y)
        {
            return x.Value == y.Value && x.Key == y.Key;
        }
        public int GetHashCode(KeyValuePair<string, string> obj)
        {
            return (obj.Key + obj.Value).GetHashCode();
        }
    }

Editar : Se fosse apenas uma string (em vez de um KeyValuePair, onde string = Nome + Value) seria de aproximadamente duas vezes mais rápido. É um intresting problema legal, e eu passei faaaaaar muito tempo nele (eu aprendi acalmar um pouco embora)

Outras dicas

Se você não precisa de nenhuma correlação específica entre cada par chave / valor e os valores exclusivos você está gerando, você pode simplesmente usar um GUID? Estou assumindo que o problema é que o seu actual 'Key' não é único nesta matriz irregulares.

Dictionary<System.Guid, KeyValuePair<string, string>> myDict 
   = new Dictionary<Guid, KeyValuePair<string, string>>();


foreach of your key values in their current format
   myDict.Add(System.Guid.NewGuid(), new KeyValuePair<string, string>(yourKey, yourvalue))

Parece que iria armazenar o que você precisa, mas eu não sei como você puxar para trás os dados deste, pois não haveria nenhuma relação semântica entre a gerar Guid & o que você tinha originalmente ...

Você pode fornecer mais informações na sua pergunta?

Use KeyValuePair como uma classe de mensagens publicitárias e, em seguida, criar um dicionário com a criar um conjunto talvez? Ou implementar seu próprio invólucro que substitui o Equals e GetHashCode.

Dictionary<KeyValuePair, bool> mySet;

for(int i = 0; i < keys.length; ++i)
{
    KeyValuePair kvp = new KeyValuePair(keys[i], values[i]);
    mySet[kvp] = true;
}

Em vez de usar um Dictionary por que não estender KeyedCollection<TKey, TItem> ? De acordo com a documentação:

Fornece a classe base abstrata para uma coleção cujas chaves são incorporadas nos valores.

Você precisa então de substituir o href="http://msdn.microsoft.com/en-us/library/ms132454.aspx" rel="nofollow noreferrer"> protected TKey GetKeyForItem(TItem item) função . Como é um híbrido entre IList<T> e IDictionary<TKey, TValue> Eu acho que é provável que seja muito rápido

Como sobre: ??

Dictionary<NameValuePair,int> hs = new Dictionary<NameValuePair,int>();
foreach (i in jaggedArray)
{
    foreach (j in i)
    {
        if (!hs.ContainsKey(j))
        {
            hs.Add(j, 0);
        }
    }
}
IEnumerable<NameValuePair> unique = hs.Keys;

é claro, se você estivesse usando C # 3.0, .NET 3.5:

var hs = new HashSet<NameValuePair>();
hs.UnionWith(jaggedArray.SelectMany(item => item));

faria o truque.

Você perfilado seu código? Você está certo de que os foreach loops são o gargalo, e não retriever.GetVehicles ()?

Eu fiz criar um pequeno projeto de teste onde eu falso do retriever e deixá-lo voltar 86.000 X 11 valores. Meu primeiro correu tentativa de 5 segundos, criando os dados incluídos.

Eu usei o mesmo valor para a chave e valor onde a primeira chave foi "0 # 0" eo último "85999 # 10".

Então eu mudei para guids. Mesmo resultado.

Então eu fiz a chave mais longa, como este:

        var s = Guid.NewGuid().ToString();
        return s + s + s + s + s + s + s+ s + s + s;

Agora que demorou quase 10 segundos.

Então eu fiz as chaves insanamente longa e tem uma exceção de memória. Eu não tenho um arquivo de swap no meu computador, então eu tenho essa exceção imediatamente.

Quanto tempo são as suas chaves? São o seu consumo de memória virtual a razão para o seu mau desempenho?

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top