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

Question

У меня есть то, что по сути является зубчатым массивом пар имя-значение - мне нужно сгенерировать набор уникальных значений имени из этого. Зубчатый массив составляет приблизительно 86 000 x 11 значений. Для меня не имеет значения, каким образом я должен хранить пару «имя-значение» (отдельная строка «имя = значение» или специализированный класс, например, 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;

Answer 1

У меня он работает за 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 слишком много времени на это (хотя я немного научился тихо)

Answer 2

Профилировали ли вы свой код? Вы уверены, что циклы foreach являются узким местом, а не ретривером. 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 секунд.

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

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

Answer 3

Как насчет:

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

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

Answer 4

Вместо использования Dictionary почему бы не расширить KeyedCollection<TKey, TItem>? Согласно документации:

Предоставляет абстрактный базовый класс для коллекции, ключи которой встроены в значения.

Затем необходимо переопределить функцию protected TKey GetKeyForItem(TItem item). Поскольку это гибрид между IList<T> и IDictionary<TKey, TValue> Я думаю, что это будет довольно быстро.

Answer 5

Использовать 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;
}

Answer 6

если вам не нужна какая-либо конкретная корреляция между каждой парой ключ / значение и уникальными значениями, которые вы генерируете, вы могли бы просто использовать 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 и тем, что у вас изначально было ...

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