Удалите все элементы, которые имеют хотя бы одну копию полностью из списка в C #

Question

Введение

Я бельгийский инженер-программист, работающий в компании, которая производит пресс-тормоза. Теперь у меня есть интересная проблема, где я хотел бы знать лучшее решение, производительность действительно важна в моем рабочем контексте. Я думаю, что это может быть интересно и другим программистам.

Данные

• У меня есть список с кучей объектов типа класса "CS3DLine".

  List <CS3DLine> ListParallelLines = new List<CS3DLine>();
  

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

  public static bool IsSameLineIn3D(CS3DLine povleft, CS3DLine povright)
  

Требуются

Я бы хотел получить FilteredListParallelLines, где равные * CS3DLines полностью отфильтрованы из списка.

Примечания

• В Интернете я нашел примеры (например, на этой странице dotNetPerls ) с Distinct-методом и IEqualityComparer, но в этих случаях удалялись только дубликаты, а не оригиналы, которые имели дубликаты.
• Я знаю, что я также могу попытаться решить это итеративно, но я боюсь, что, если список содержит огромное количество объектов, это приведет к плохой производительности.

Answer 1

На первом шаге вам нужно создать класс, который реализует IEqualityComparer для вашего CS3DLines класса.

Это может выглядеть примерно так:

public class CS3DComparer : IEqualityComparer {
    public bool Equals(CS3DLines a, CS3DLines b) {
        return IsSameLineIn3D(a, b);
    }
    public int GetHashCode(CS3DLines line){
        // You do not need to use all properties of line to calculate the 
        // hashCode. If performance is not good enough you can experiment by 
        // adding and removing properties from the hash code calculation.

        var hashCode = line.Property1?.GetHashCode() ?? 0;
        hashCode = (hashCode * 397) ^ (line.Property2?.GetHashCode() ?? 0);
        hashCode = (hashCode * 397) ^ (line.Property3?.GetHashCode() ?? 0);
        return hashCode;
    }
}

Далее, чтобы получить несортированный список всех элементов в вашей коллекции ListParallelLines, вы можете вызвать этот код:

var singles = ListParallelLines
    .GroupBy(line => line, new CS3DComparer())
    .Where(group => group.Count() == 1)
    .Select(group => group.Key)
    .ToList();

singles теперь представляет собой список всех строк, которые не имеют дубликатов в ListParallelLines.

Для возможного ускорения при распараллеливании вы можете попробовать использовать PLINQ, запустив LINQ Query с вызовом AsParallel().

var singles = ListParallelLines
    .AsParallel()
    .GroupBy(line => line, new CS3DComparer())
    .Where(group => group.Count() == 1)
    .Select(group => group.Key)
    .ToList();

Answer 2

Для сложных объектов вам нужно переопределить Equals и GetHashCode, после этого вы можете просто сравнить его

http://www.loganfranken.com/blog/687/overriding-equals-in-c-part-1/

Answer 3

В связи с вашим требованием полностью исключить из списка элементы, в которых есть дубликаты, один из подходов состоит в том, чтобы сначала сгруппировать набор, а затем выполнить фильтрацию по группам, имеющим более одного элемента.

Производительность для этого вида фильтрации всегда ограничивает, но для экономии времени при группировании и необходимости выполнения сравнений на равенство, если ваш объект поддерживает свой собственный хэш для группировки заранее, это уменьшит нагрузку во время желания фильтровать и хэш должен был бы постоянно обновляться посредством изменений в данном экземпляре. Соображения могут быть другими, если ваше оборудование ограничено, поэтому вам не нужно хранить хэши для всех элементов в памяти или если вас беспокоит скорость. Хранение хешей и не вычисление их не идеальны из-за возможных движущихся частей в вашем коде, которые могут непреднамеренно не вызвать обновление хеша, но если производительность является значительным фактором, это может помочь при тщательном внедрении.

var results = ListParallelLines.GroupBy(x => x.EqualityHash).Where(x => x.Count() == 1);

Это даст вам хэш, который вернет вам список элементов, которые не имеют дубликатов.

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

https://docs.microsoft.com/en-us/dotnet/api/system.object.gethashcode?redirectedfrom=MSDN&view=netframework-4.7.2#remarks

Answer 4

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

Может быть упрощено, если упорядочение списка не имеет значения.

В отсутствие определения CS3DLine я привел пример для моего собственного класса Line.

Как всегда, при использовании основанных на множестве методов лучше всего, чтобы класс line был неизменным.

void Main()
{
    List<Line> lines = new List<Line>();
    var comparer = LineEqualityComparer.Instance;
    var filtered = lines
        .Select((line, idx) => new { line, idx })
        .GroupBy(x => x.line, comparer)
        .Where(g => g.Count() == 1)
        .SelectMany(g => g)
        .OrderBy(x => x.idx)
        .Select(x => x.line);
}

class Line
{
    public int X1 { get; }
    public int Y1 { get; }
    public int X2 { get; }
    public int Y2 { get; }
}

class LineEqualityComparer : IEqualityComparer<Line>
{
    public static IEqualityComparer<Line> Instance { get; } = new LineEqualityComparer();
    public bool Equals(Line x, Line y)
    {
        //fill-in the blanks
    }

    public int GetHashCode(Line obj)
    {
        //fill-in the blanks
    }
}

В большом наборе данных вы могли бы иметь возможность повысить производительность запроса, стратегически разместив .AsParallel() где-то в цепочке методов linq.