Как перебрать и сравнить миллионы значений в двух текстовых файлах?

Question

У меня есть два файла текстовых файлов (TXT), которые содержат более 2 миллионов различных имен файлов. Я хочу просмотреть все имена в первом файле и найти те, которые также присутствуют во втором текстовом файле.

Я пробовал перебирать StreamReader, но это занимает много времени. Я также попробовал приведенный ниже код, но он все еще занимает слишком много времени.

StreamReader first = new StreamReader(path);
string strFirst = first.ReadToEnd();
string[] strarrFirst = strFirst.Split('\n');

 bool found = false;

StreamReader second = new StreamReader(path2);
string str = second.ReadToEnd();
string[] strarrSecond = str.Split('\n');

for (int j = 0; j < (strarrFirst.Length); j++)
{
          found = false;

    for (int i = 0; i < (strarrSecond .Length); i++)
    {
        if (strarrFirst[j] == strarrSecond[i])
        {
            found = true;
            break;
        }
    }

    if (!found)
    {
        Console.WriteLine(strarrFirst[j]);
    }
}

Какой хороший способ сравнить файлы?

Answer 1

Как насчет этого:

var commonNames = File.ReadLines(path).Intersect(File.ReadLines(path2));

Это O (N + M) вместо вашего текущего решения, которое проверяет каждую строку в первом файле с каждую строку во втором файле - O (N * M).

Предполагается, что вы используете .NET 4. В противном случае вы можете использовать File.ReadAllLines, но это приведет к считыванию всего файла в память. Или вы можете написать эквивалент File.ReadLines самостоятельно - это не очень сложно.

В конечном счете вы, вероятно, будете ограничены файловым вводом-выводом к тому времени, как вы избавитесь от проблемы O (N * M) в своем текущем коде - не так много способов обойти это.

РЕДАКТИРОВАТЬ: Для .NET 2, сначала давайте реализуем что-то вроде ReadLines:

public static IEnumerable<string> ReadLines(string file)
{
    using (TextReader reader = File.OpenText(file))
    {
        string line;
        while ((line = reader.ReadLine()) != null)
        {
            yield return line;
        }
    }
}

Теперь мы действительно хотим использовать HashSet<T>, но этого не было в .NET 2 - поэтому давайте вместо этого используем Dictionary<TKey, TValue>:

Dictionary<string, string> map = new Dictionary<string, string>();
foreach (string line in ReadLines(path))
{
    map[line] = line;
}

List<string> intersection = new List<string>();
foreach (string line in ReadLines(path2))
{
    if (map.ContainsKey(line))
    {
        intersection.Add(line);
    }
}

Answer 2

Попробуйте что-нибудь подобное, чтобы немного ускорить процесс ...

            var path = string.Empty;
            var path2 = string.Empty;
            var strFirst = string.Empty;
            var str = string.Empty;
            var strarrFirst = new List<string>();
            var strarrSecond = new List<string>();

            using (var first = new StreamReader(path))
            {
                strFirst = first.ReadToEnd();
            }

            using (var second = new StreamReader(path2))
            {
                str = second.ReadToEnd();
            }


            strarrFirst.AddRange(strFirst.Split('\n'));

            strarrSecond.AddRange(str.Split('\n'));
            strarrSecond.Sort();

            foreach(var value in strarrFirst)
            {
                var found = strarrSecond.BinarySearch(value) >= 0;
                if (!found) Console.WriteLine(value);
            }

Answer 3

Ради интереса, я попробовал метод Джона Скита и владею им:

    var guidArray = Enumerable.Range(0, 1000000).Select(x => Guid.NewGuid().ToString()).ToList();
        string path = "first.txt";
        File.WriteAllLines(path, guidArray);
        string path2 = "second.txt";
        File.WriteAllLines(path2, guidArray.Select(x=>DateTime.UtcNow.Ticks % 2 == 0 ? x : Guid.NewGuid().ToString()));

        var start = DateTime.Now;

        var commonNames = File.ReadLines(path).Intersect(File.ReadLines(path2)).ToList();

        Console.WriteLine((DateTime.Now - start).TotalMilliseconds);

        start = DateTime.Now;

        var lines = File.ReadAllLines(path);
        var hashset = new HashSet<string>(lines);

        var lines2 = File.ReadAllLines(path2);

        var result = lines2.Where(hashset.Contains).ToList();

        Console.WriteLine((DateTime.Now - start).TotalMilliseconds);
        Console.ReadKey();

А метод Скита был чуть-чуть быстрее (1453.0831 против 1488.0851, метод iDevForFun был довольно медленным - 12791.7316), поэтому я думаю, что под слоями должно происходить то же самое, что я пытался сделать вручную с помощью хэш-набора.