Какой самый быстрый способ создать уникальный набор в .net 2

StackOverflow https://stackoverflow.com/questions/232997

Вопрос

У меня есть то, что по сути является зубчатым массивом пар имя-значение - мне нужно сгенерировать набор уникальных значений имени из этого. Зубчатый массив составляет приблизительно 86 000 x 11 значений. Мне не важно, каким образом я должен хранить пару «имя-значение» (одна строка & Quot; имя = значение & Quot; или специализированный класс, например KeyValuePair).
Дополнительная информация . Существует 40 различных имен и большее количество различных значений - вероятно, в районе 10000 значений.

Я использую C # и .NET 2.0 (а производительность настолько низкая, что я думаю, что может быть лучше перенести весь мой зубчатый массив в базу данных sql и сделать выборку, отличную от нее).

Ниже приведен текущий код, который я использую: 

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;
Это было полезно?

Решение

У меня он работает за 0,34 секунды по сравнению с 9+ минутами

Проблема заключается в сравнении структур KeyValuePair. Я решил эту проблему, написав объект сравнения и передав его экземпляр в Словарь.

Из того, что я могу определить, KeyValuePair.GetHashCode () возвращает хеш-код своего объекта Key (в данном примере это наименее уникальный объект).

Поскольку словарь добавляет (и проверяет наличие) каждого элемента, он использует функции Equals и GetHashCode, но должен полагаться на функцию Equals, когда хеш-код менее уникален.

Предоставляя более уникальную функцию GetHashCode, она превосходит функцию Equals гораздо реже. Я также оптимизировал функцию Equals, чтобы сравнить более уникальные значения до менее простых ключей.

86 000 * 11 элементов с 10 000 уникальных свойств выполняются за 0,34 секунды с использованием объекта сравнения ниже (без объекта сравнения это занимает 9 минут 22 секунды)

Надеюсь, это поможет:) 

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

РЕДАКТИРОВАТЬ : если бы это была всего одна строка (вместо KeyValuePair, где string = Name + Value), это было бы примерно в два раза быстрее. Это интересная проблема, и я потратил faaaaaar слишком много времени на нее (хотя я немного научился молчать)

Другие советы

если вам не нужна какая-либо конкретная корреляция между каждой парой ключ / значение и уникальными значениями, которые вы генерируете, вы можете просто использовать GUID? Я предполагаю, что проблема в том, что ваш текущий «Ключ» не уникален в этом зубчатом массиве. 

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

Звучит так, будто в нем будет храниться то, что вам нужно, но я не знаю, как вы могли бы извлечь данные из этого, поскольку между генерирующим Guid & amp; что у тебя изначально было ...

Можете ли вы предоставить больше информации по вашему вопросу?

Использовать KeyValuePair как класс-обертку, а затем создать словарь для создания набора, возможно? Или реализуйте свою собственную оболочку, которая переопределяет Equals и GetHashCode. 

Dictionary<KeyValuePair, bool> mySet;

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

Как насчет: 

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;

конечно, если вы использовали C # 3.0, .NET 3.5: 

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

сделает свое дело.

Вы профилировали свой код? Вы уверены, что циклы foreach являются узким местом, а не retriever.GetVehicles ()?

Я создал небольшой тестовый проект, в котором я подделал ретривер и позволил ему вернуть 86.000 X 11 значений. Моя первая попытка длилась 5 секунд, создавая включенные данные.

Я использовал одно и то же значение и для ключа, и для значения, где первый ключ был " 0 # 0 " и последнее " 85999 # 10 ".

Затем я переключился на гидов. Тот же результат.

Затем я сделал ключ длиннее, например: 

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

Теперь это заняло почти 10 секунд.

Потом я сделал ключи безумно длинными и получил исключение нехватки памяти. У меня нет файла подкачки на моем компьютере, поэтому я сразу получил это исключение.

Как долго ваши ключи? Является ли использование виртуальной памяти причиной низкой производительности?

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top