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

Question

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

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

Ниже текущий код Im используя:

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() возвращает hashcode своего Key объекта (в этом примере наименее уникальный объект).

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

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

86000 * 11 элементов с 10000 уникальными свойствами работают в 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(); 
     } 
    } 

EDIT: Если это была только одна строка (вместо KeyValuePair, где string = Name + Value), она будет примерно в два раза быстрее. Это хорошая интересная проблема, и я потратил на это большое количество времени. (я немного научился)

Answer 2

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

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

Answer 3

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

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

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

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

Answer 5

Как насчет:

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 6

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

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

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