Переменная пересечение и извлечение различных элементов?
https://stackoverflow.com/questions/1679258
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть линия, подобная следующей в моем коде:
potentialCollisionsX.Intersect(potentialCollisionsY).Distinct().ToList();
Который, посредством профилирования, я определил, что он ест приблизительно 56 процентов моего времени. Мне нужно выяснить, как обеспечить эффективную реализацию. Я старался
List<Extent> probableCollisions = new List<Extent>();
for (int j = 0; j < potentialCollisionsX.Count; j++)
{
if (potentialCollisionsY.Contains(potentialCollisionsX[j]) && !probableCollisions.Contains(potentialCollisionsX[j]))
{
probableCollisions.Add(potentialCollisionsX[j]);
}
}
Но это сбросит только 42 процента. Оптимизация или альтернативные идеи были бы очень оценены.
Редактировать: Кто -то запросил информацию о классе степени, и я не могу придумать лучшего способа предоставить им информацию, чем предоставление определения класса.
private enum ExtentType { Start, End }
private sealed class Extent
{
private ExtentType _type;
public ExtentType Type
{
get
{
return _type;
}
set
{
_type = value;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
}
private Nucleus _nucleus; //Nucleus is the main body class in my engine
public Nucleus Nucleus
{
get
{
return _nucleus;
}
set
{
_nucleus = value;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
}
private int _hashcode;
public Extent(Nucleus nucleus, ExtentType type)
{
Nucleus = nucleus;
Type = type;
_hashcode = 23;
_hashcode *= 17 + Nucleus.GetHashCode();
}
public override bool Equals(object obj)
{
return Equals(obj as Extent);
}
public bool Equals(Extent extent)
{
if (this.Nucleus == extent.Nucleus) //nucleus.Equals does an int comparison
{
return true;
}
return false;
}
public override int GetHashCode()
{
return _hashcode;
}
}
Edit2: Казалось бы, использование Hashsets делает эту часть моего кода такой же исполнительской, как мне нужно, так что спасибо за помощь вашего парня!
Решение
Попробуй это:
HashSet<Extent> result = new HashSet<Extent>();
HashSet<Extent> potentialSetY = new HashSet<Extent>(potentialCollisionsY);
foreach (Extent ex in potentialCollisionsX)
if (potentialSetY.Contains(ex))
result.Add(ex);
Хэш -наборы хорошо Contains быстро, но не сохраняйте порядок
Если вам нужно сохранить порядок, вот что -то немного сложнее: упорядоченный хэш -набор. Он использует нормальную семантику хеш -набора (ну, словарь, но это то же самое), но перед перечислением он переказывает элементы в соответствии с порядком вставки.
// Unchecked code
public class OrderedHashSet<T> : IEnumerable<T> {
int currentIndex = 0;
Dictionary<T, index> items = new Dictionary<T, index>();
public bool Add(T item) {
if (Contains(item))
return false;
items[item] = currentIndex++;
return true;
}
public bool Contains(T item) {
return items.ContainsKey(item);
}
public IEnumerator<T> GetEnumerator() {
return items.Keys.OrderBy(key => items[key]).GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
}
Теперь просто измените HashSet к OrderedHashSet В приведенном выше образе должен Работа.
Другие советы
Intersect В любом случае возвращает различные элементы, вызывая Distinct() ненужный. Это будет съесть хотя бы некоторое время.
Кроме того, вам действительно нужно позвонить ToList? Что вы тогда делаете с результатом?
Порядок имеет значение? Если нет, вам следует рассмотреть возможность использования HashSet<T> вместо List<T> для вашего «ручного» кода. (И, вероятно, создайте HashSet<T> за potentialCollisionsY также.) Это сделает Contains Позвоните быстрее, по крайней мере, если коллекции достаточно большие ...
Кстати, не верьте Документация для Intersect - это неправильно в отношении порядка операций (По крайней мере, в .net 3.5)
Хорошо, я вижу определение класса степени. Прежде всего, это нарушает правило, что если obj1.Equals(obj2)==true тогда obj1.GetHashCode()==obj2.GetHashCode(). Анкет Но это не так и может быть исправлено (если вы этого не сделаете, алгоритмы, которые зависят от хэширования, например HashSet не удастся).
Теперь, если единственная операция, которую можно выполнить в отношении объекта Extret, - это сравнение для равенства, то невозможно получить худшую производительность. O (n*m) (где n - это размер первой коллекции, а M - это размер второй коллекции). Это потому, что в конечном итоге вам придется сравнивать каждый элемент с каждым элементом.
Это может быть лучше с помощью использования GetHashCode() И тот факт, что объекты с различными хэш -кодами также будут разными. Другие люди предложили использовать HashSet Класс, это было бы таким решением. Лучший случай в этом случае будет O (n+m), и худший случай - O (n+n*m). Анкет В среднем, хотя вы должны победить, если только GetHashCode() Метод очень плохо реализован и возвращает те же хеш -коды для многих объектов.
Я сам предпочитаю более стабильное решение. Если бы класс степени мог быть отсортирован надежно (то есть, если бы вы могли сравнить два объекта степени, чтобы увидеть, какой из них был больше, а какой из них был меньше), то вы могли бы сортировать оба списка, и производительность может быть снижена до O (Сортировка+M+N). Анкет Идея состоит в том, что когда списки отсортированы, вы можете пройти через них обоих одновременно И ищите там равные элементы.
Теперь сортировка - это сложная вещь здесь. Если вы только реализуете операцию сравнения (как в, IComparable интерфейс), вы сможете сортировать оба списка вовремя O (n*logn+m*logm). Анкет Стандарт List.Sort() Метод должен сделать это для вас. В целом, общая производительность будет O (n*logn+m*logm+n+m). Анкет Однако вы должны отметить, что это использует алгоритм QuickSort, который плохо работает в почти сортированных списках. Худший случай - полностью отсортированный список, в этом случае он O (n*m). Анкет Если ваши списки близки к уже отсортированию, вам следует рассмотреть другой алгоритм сортировки (и реализовать его самостоятельно).
Конечно, в надежной скорости было бы, если бы вы могли преобразовать каждую степень в целое число (или, в целом, какую -то строку) со свойством, что если строки равны, то экстенты также равны, и если строки не равны, то тогда Степень тоже не равна. С ними состоит в том, что они могут быть отсортированы в линейное время с такими алгоритмами, как Radix sort, Радиксное дерево, и т. д., тогда сортировка займет только время O (n+m). Анкет На самом деле, если вы построили дерево Radix, вам придется только сортировать первый список, и вы можете найти строки напрямую (с каждым поиском O (1) время). В целом, общая производительность будет O (n+m) который является лучшим доступным.
Одна вещь, которую вы всегда должны помнить, хотя - большие алгоритмы имеют большие константы. Подход Radix может выглядеть лучше всего на бумаге, но будет довольно сложно реализовать и, как правило, медленнее, чем более простые подходы для небольших объемов данных. Только если ваши списки имеют элементы в диапазонах тысяч и десятков тысяч, вы должны начать думать об этом. Кроме того, эти алгоритмы требуют создания много новых объектов и стоимости каждого new() Операция также становится значительной. Вы должны тщательно подумать, чтобы минимизировать количество требуемых ассигнования.
Если вы не можете придумать лучшее решение, подумайте о том, чтобы использовать неуправляемый код в качестве последнего средства.
Два подхода:
Поместите предметы в хэшмап, если их еще нет, иначе отметьте их в хэшмапе как дублированные. Это о (n). Затем вы повторяете все элементы в HashMap и видите, отмечены ли они как дубликаты или нет - O (n) снова.
Другой подход:
Сортировать два списка. Это операция O (n Lg N), но, что важно, возможно, вы можете с радостью сохранить два списка, отсортированные в любое время, и, следовательно, стоимость не принимается при конкретном поиске пересечения и т. Д.
Затем пройдите два списка по порядку, найдя отдельные и дублированные записи и т. Д. Это о (n).
