Тайм-аут функции для большого списка (запрос LINQ в C #)

Question

Я использую следующий запрос

var queryList1Only = (from file in list1
                                  select file).Except(list2, myFileCompare);

, а myFileCompare сравнивает 2 файла на основе имени и длины.

Запрос возвращал результаты, если list1 и list2 были маленькими (скажем, 100 файлов во время тестирования), затем я увеличил list1 до 30000 файлов и list2 до 20000 файлов, и теперь запрос говорит "Function Evaluation Timed Out".

Я искал в Интернете и обнаружил, что отладка может вызвать его, поэтому я удалил все точки останова и запустил код, теперь программа просто зависла без вывода queryList1Only Я пытаюсь распечатать, чтобы проверить это.

EDIT: Это код для myFileCompare

class FileCompare : System.Collections.Generic.IEqualityComparer<System.IO.FileInfo>
    {

        public FileCompare() { }

        public bool Equals(System.IO.FileInfo f1, System.IO.FileInfo f2)
        {
            return (f1.Name == f2.Name && f1.Directory.Name == f2.Directory.Name && 
                    f1.Length == f2.Length);
        }

        // Return a hash that reflects the comparison criteria. According to the 
        // rules for IEqualityComparer<T>, if Equals is true, then the hash codes must
        // also be equal. Because equality as defined here is a simple value equality, not
        // reference identity, it is possible that two or more objects will produce the same
        // hash code.
        public int GetHashCode(System.IO.FileInfo fi)
        {
            string s = String.Format("{0}{1}", fi.Name, fi.Length);
            return s.GetHashCode();
        }

    }

Answer 1

Что нужно сделать с элементами, возвращенными запросом?В принципе, такие тяжелые операции было бы здорово выполнять одновременно в отдельном потоке, чтобы избежать ситуаций, с которыми вы только что столкнулись.

РЕДАКТИРОВАТЬ: Идея

В этом случае выможно попробовать следующий алгоритм:

• Сортировать элементы в обоих массивах, используя QuickSort (List<T>.Sort() использует его по умолчанию ), это будет довольно быстро с хорошей реализацией GetHashCode()
• Затем в хорошо известном for() списке обхода цикла и сравнивать элементы с одинаковым индексом
• Когда счетчик любого массива достигает максимального индекса другого списка - выберите все элементы из последнего списка какразные (в основном их вообще нет в предыдущем списке).

Я считаю, что с отсортированными массивами вы получите гораздо лучшую производительность.Я считаю, что сложность Кроме () равна O (м * п) .

РЕДАКТИРОВАТЬ: другая идея, должна быть очень быстрой

• С одного сервера храните элементы в Set<T>
• Затем переберите второй массив и выполните поиск в пределах Set<T>, это будет ОЧЕНЬ быстро!В основном O (mlogm) + O (n) , потому что вам нужно пройти только по одному массиву и искать в наборе с хорошей хэш-функцией (используйте GetHashCode(), который я предоставил с обновленной логикой) очень быстро,Попробуйте!

// some kind of C# pseudocode ;)
public IEnumerable<FileInfo> GetDifference()
{           
    ISet<FileInfo> firstServerFilesMap = new HashSet<FileInfo>();

    // adding items to set
    firstServerFilesMap.Add();

    List<FileInfo> secondServerFiles = new List<FileInfo>();

    // adding items to list
    firstServerFilesMap.Add();

    foreach (var secondServerFile in secondServerFiles)
    {
        if (!firstServerFilesMap.Contains(secondServerFile))
        {
            yield return secondServerFile;
        }
    }
}

РЕДАКТИРОВАТЬ: Более подробную информацию о логике равенства были предоставлены в комментариях

Попробуйте это побуждение

public bool Equals(System.IO.FileInfo f1, System.IO.FileInfo f2)
{
      if ( f1 == null || f2 == null)
      {
          return false;
      }

      return (f1.Name == f2.Name && f1.Directory.Name == f2.Directory.Name && 
             f1.Length == f2.Length);
}

public int GetHashCode(System.IO.FileInfo fi)
{
    unchecked
    {
        int hash = 17;    
        hash = hash * 23 + fi.Name.GetHashCode();
        hash = hash * 23 + fi.Directory.Name.GetHashCode();
        hash = hash * 23 + fi.Length.GetHashCode();

        return hash;
    }
}

Полезные ссылки:

• Рекомендации GetHashCode в C #
• Какой лучший алгоритм для переопределенного System.Object.GetHashCode?

Answer 2

Я сам не пробовал, но вот идея: Реализуйте list1 как HashSet следующим образом:

HashSet<FileInfo> List1 = new HashSet<FileInfo>(myFileCompare);

Добавить все файлы:

foreach(var file in files)
{
    List1.Add(file);
}

Затем удалите элементы:

List1.ExceptWith(list2);

Затем перечислите:

foreach(var file in List1)
{
    //do something
}

Я думаю, что это быстрее, но, как я уже сказал, я не пробовал. Вот ссылка с общей информацией о HashSet.

Edit: Или еще лучше, вы можете инициализировать и добавить данные за один шаг:

HashSet<FileInfo> List1 = new HashSet<FileInfo>(files, myFileCompare);

Answer 3

Я бы порекомендовал удалить длину из хеш-кода и просто сделать fi.FullName. Это по-прежнему соответствует принципу уникальности, хотя могут (в некоторых случаях, когда вы считаете, что длина необходима для различения) хеш-коллизий. Но это, вероятно, предпочтительнее, чем более длительное выполнение, за исключением выполнения. Аналогично, измените сравнение на равенство с именем и каталогом на полное имя, что, вероятно, также будет более производительным.