Какой самый быстрый способ создать уникальный набор в .net 2
-
04-07-2019 - |
Вопрос
У меня есть то, что по сути является зубчатым массивом пар имя-значение - мне нужно сгенерировать набор уникальных значений имени из этого. Зубчатый массив составляет приблизительно 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
почему бы не расширить KeyedCollection<TKey, TItem>
а>? Согласно документации:
Предоставляет абстрактный базовый класс для коллекции, ключи которой встроены в значения.
Затем вам нужно переопределить функцию protected TKey GetKeyForItem(TItem item)
. Поскольку это гибрид между IList<T>
и IDictionary<TKey, TValue>
Я думаю, что это будет довольно быстро.
Как насчет:
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 секунд.
Потом я сделал ключи безумно длинными и получил исключение нехватки памяти. У меня нет файла подкачки на моем компьютере, поэтому я сразу получил это исключение.
Как долго ваши ключи? Является ли использование виртуальной памяти причиной низкой производительности?