Как ускорить процесс поиска совпадение в двух списках

#c_sharp #list

Есть два файла. Считываю из них оба значения в списки. Хочу взять уникальные значения
из обоих списков, однако процесс поиска и сравнения идет очееень долго(строк в обоих
списках ~300к). Подскажите как ускорить процесс поиска и сравнения*?

 var lst1 = File.ReadAllLines(@ "D:\test\1.csv").ToList();
 var lst2 = File.ReadAllLines(@ "D:\\test\2.csv").ToList();

 var rez = lst2.Where(x => !MySequenceContains(lst1, x)).
 Select(q => string.Join(";", q)).ToList();

 }

 private bool MySequenceContains(List < string > x, string y) {
  bool contains = false;
  index++;
  label2.Text = index.ToString();
  foreach(var a in x) {
   // ToDo: tweak the string comparison as needed
   if (string.Compare(a.Split(';')[0], y.Split(';')[0], StringComparison.InvariantCultureIgnoreCase)
== 0 &&
    string.Compare(a.Split(';')[14], y.Split(';')[14], StringComparison.InvariantCultureIgnoreCase)
== 0) {
    contains = true;
    break;
   }
  }
  return contains;
 }

    

Ответы

Ответ 1

Во-первых, ваш код возвращает строки, которые есть во втором файле, но нет в первом.
Он не возвращает строки, которые есть в первом, но нет во втором.

Во-вторых, вы используете Split внутри цикла, т.е. одни и те же строки сплитите много раз.

В-третьих, вы внутри цикла по одному файлу делаете цикл по другому (ищете это значение
в другом файле. Если объемы файлов одинаковые, то алгоритм медленный N^2.

Если предварительно выполнить Split для всех входных строк и отсортировать списки
по вашему критерию, то отобрать неповторяющиеся элементы можно в одном цикле сразу
по двум (отсортированным) спискам. Сложность получается 2N + 2NlogN(сортировка).

Вот пример, извиняюсь, что нелаконично:

private List my(List x, List y)
{
    var rez = new List();
    var lst1 = new List(x.Select(s => s.Split(';')));
    var lst2 = new List(y.Select(s => s.Split(';')));

    lst1.Sort(MyComarer.Comparer);
    lst2.Sort(MyComarer.Comparer);

    var isPresentInX = false;
    int j = 0;
    for (int i = 0; i < lst1.Count; i++)
    {
        if (j >= lst2.Count)
        {
            rez.Add(string.Join(";", lst1[i]));
            continue;
        }
        var comp = MyComarer.Comparer.Compare(lst1[i], lst2[j]);
        while (comp > 0 && j < lst2.Count)
        {
            if (!isPresentInX)
                rez.Add(string.Join(";", lst2[j]));
            j++;
            if (j < lst2.Count)
            {
                if (MyComarer.Comparer.Compare(lst2[j], lst2[j - 1]) != 0)
                    isPresentInX = false;
                comp = MyComarer.Comparer.Compare(lst1[i], lst2[j]);
            }
        }
        if (comp != 0)
            rez.Add(string.Join(";", lst1[i]));
        else
            isPresentInX = true;
    }
    return rez;
}

private class MyComarer : IComparer
{
    public static MyComarer Comparer { get; } = new MyComarer();

    public int Compare(string[] x, string[] y)
    {
        var res = string.Compare(x[0], y[0], StringComparison.InvariantCultureIgnoreCase);
        if (res == 0)
            res = string.Compare(x[14], y[14], StringComparison.InvariantCultureIgnoreCase);
        return res;
    }
}


Ответ 2

lst1.Concat(lst2).ToList()
.GroupBy(x=>x.Split(';')[0]+x.Split(';')[14])
.Select(g=>g.First())


Ответ 3

Альтернативный вариант: использовать HashSet вместе с его методом ExceptWith

При создании объекта HashSet ему можно передать IEqualityComparer, который
будет использоваться для сравнения элементов.

Он может выглядеть так:

class MySequenceEqualityComparer : IEqualityComparer
{

    public bool Equals(string x, string y)
    {
        var xSplit = x.Split(';');
        var ySplit = x.Split(';');
        return string.Compare(xSplit[0], ySplit[0], StringComparison.InvariantCultureIgnoreCase)
== 0 
            && string.Compare(xSplit[14], ySplit[14], StringComparison.InvariantCultureIgnoreCase)
== 0;
    }

    public int GetHashCode(string obj)
    {
        return -1;
    }
}


При этом основной код сведется к следующему:

var lst1 = File.ReadAllLines(@ "D:\test\1.csv");
var lst2 = new HashSet(File.ReadAllLines(@ "D:\\test\2.csv"), new MySequenceEqualityComparer());

lst2.ExceptWith(lst1);


Результат будет в переменной lst2