Частота слов в большом текстовом файле

Ответ 1

Лучший короткий ответ, который я могу дать, - измерить, измерить, измерить. Stopwatch приятно чувствовать, что время, потраченное, но в конечном итоге вы в конечном итоге разбрызгиваете большие слова вашего кода, или вам нужно будет найти лучший инструмент для этой цели. Я бы предложил получить специальный инструмент профилирования для этого, есть много доступных для С# и .NET.

Мне удалось сфокусировать около 43% общей продолжительности выполнения в три этапа.

Сначала я измерил ваш код и получил следующее:

Это, по-видимому, указывает на то, что здесь есть две горячие точки, с которыми мы можем бороться:

• Разделение строк (SplitInternal)
• Поддержка словаря (FindEntry, Insert, get_Item)

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

Первое, разделение строк, несколько легкое, но включает переписывание очень простого вызова string.Split в немного больше кода. Цикл, который обрабатывает одну строку, я переписал:

while ((line = streamReader.ReadLine()) != null)
{
    int lastPos = 0;
    for (int index = 0; index <= line.Length; index++)
    {
        if (index == line.Length || line[index] == ' ')
        {
            if (lastPos < index)
            {
                string word = line.Substring(lastPos, index - lastPos);
                // process word here
            }
            lastPos = index + 1;
        }
    }
}

Затем я переписал обработку одного слова:

int currentCount;
wordCount.TryGetValue(word, out currentCount);
wordCount[word] = currentCount + 1;

Это зависит от того, что:

• TryGetValue дешевле, чем проверять, существует ли слово, а затем восстановить его текущий счетчик
• Если TryGetValue не удается получить значение (ключ не существует), он инициализирует здесь переменную currentCount значением по умолчанию, равным 0. Это означает, что нам действительно не нужно проверять, слово действительно существовало.
• Мы можем добавлять новые слова в словарь с помощью индексатора (он либо перезапишет существующее значение, либо добавит новый ключ + значение в словарь)

Конечный цикл выглядит следующим образом:

while ((line = streamReader.ReadLine()) != null)
{
    int lastPos = 0;
    for (int index = 0; index <= line.Length; index++)
    {
        if (index == line.Length || line[index] == ' ')
        {
            if (lastPos < index)
            {
                string word = line.Substring(lastPos, index - lastPos);
                int currentCount;
                wordCount.TryGetValue(word, out currentCount);
                wordCount[word] = currentCount + 1;
            }
            lastPos = index + 1;
        }
    }
}

Новое измерение показывает это:

Подробнее:

• Мы отправились с 6876 мс до 5013 мс
• Мы потеряли время, потраченное на SplitInternal, FindEntry и get_Item
• Мы получили время, потраченное на TryGetValue и Substring

Здесь подробности разметки:

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

Однако мы можем сделать лучше. Здесь мы делаем 2 словарных поиска, которые включают вычисление хеш-кода слова и сравнение его с ключами в словаре. Первый поиск является частью TryGetValue, а второй является частью wordCount[word] = ....

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

Мы можем использовать трюк Xanatos для хранения счетчика внутри объекта, чтобы мы могли удалить этот поиск второго словаря:

public class WordCount
{
    public int Count;
}

...

var wordCount = new Dictionary<string, WordCount>();

...

string word = line.Substring(lastPos, index - lastPos);
WordCount currentCount;
if (!wordCount.TryGetValue(word, out currentCount))
    wordCount[word] = currentCount = new WordCount();
currentCount.Count++;

Это приведет только к получению счетчика из словаря, добавление 1 дополнительного события не предполагает словарь. Результат метода также изменится, чтобы вернуть этот тип WordCount как часть словаря, а не только int.

Чистый результат: ~ 43% экономии.

Заключительный фрагмент кода:

public class WordCount
{
    public int Count;
}

public static IDictionary<string, WordCount> Parse(string path)
{
    var wordCount = new Dictionary<string, WordCount>();

    using (var fileStream = new FileStream(path, FileMode.Open, FileAccess.Read, FileShare.None, 65536))
    using (var streamReader = new StreamReader(fileStream, Encoding.Default, false, 65536))
    {
        string line;
        while ((line = streamReader.ReadLine()) != null)
        {
            int lastPos = 0;
            for (int index = 0; index <= line.Length; index++)
            {
                if (index == line.Length || line[index] == ' ')
                {
                    if (lastPos < index)
                    {
                        string word = line.Substring(lastPos, index - lastPos);
                        WordCount currentCount;
                        if (!wordCount.TryGetValue(word, out currentCount))
                            wordCount[word] = currentCount = new WordCount();
                        currentCount.Count++;
                    }
                    lastPos = index + 1;
                }
            }
        }
    }

    return wordCount;
}

Ответ 2

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

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

http://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem

edit: также посмотрите ConcurrentDictionary

Ответ 3

Я получил довольно много (от 25 секунд до 20 секунд по файлу 200 Мб), просто меняя:

int cnt;

if (wordCount.TryGetValue(word, out cnt))
{
    wordCount[word] = cnt + 1;
}
else
....

Вариант, основанный на ConcurrentDictionary<> и Parallel.ForEach (с использованием перегрузки IEnumerable<>). Обратите внимание, что вместо int я использую InterlockedInt, который использует Interlocked.Increment для увеличения. Являясь ссылочным типом, он корректно работает с ConcurrentDictionary<>.GetOrAdd...

public class InterlockedInt
{
    private int cnt;

    public int Cnt
    {
        get
        {
            return cnt;
        }
    }

    public void Increment()
    {
        Interlocked.Increment(ref cnt);
    }
}

public static IDictionary<string, InterlockedInt> Parse(string path)
{
    var wordCount = new ConcurrentDictionary<string, InterlockedInt>();

    Action<string> action = line2 =>
    {
        var words = line2.Split(separators, StringSplitOptions.RemoveEmptyEntries);

        foreach (var word in words)
        {
            wordCount.GetOrAdd(word, x => new InterlockedInt()).Increment();
        }
    };

    IEnumerable<string> lines = File.ReadLines(path);
    Parallel.ForEach(lines, action);

    return wordCount;
}

Обратите внимание, что использование Parallel.ForEach менее эффективно, чем использование непосредственно одного потока для каждого физического ядра (вы можете видеть, как в истории). В то время как для обоих решений требуется менее 10 секунд "настенных" часов на моем ПК, Parallel.ForEach использует 55 секунд процессорного времени против 33 секунд решения Thread.

Существует еще один трюк, который оценивается около 5-10%:

public static IEnumerable<T[]> ToBlock<T>(IEnumerable<T> source, int num)
{
    var array = new T[num];
    int cnt = 0;

    foreach (T row in source)
    {
        array[cnt] = row;
        cnt++;

        if (cnt == num)
        {
            yield return array;
            array = new T[num];
            cnt = 0;
        }
    }

    if (cnt != 0)
    {
        Array.Resize(ref array, cnt);
        yield return array;
    }
}

Вы "группируете" строки (выбираете число от 10 до 100) в пакетах, чтобы было меньше внутрипоточной связи. Затем рабочие должны сделать foreach в полученных строках.

Ответ 4

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

Ответ 5

Я рекомендую устанавливать размеры буфера потока больше и сопоставлять:

    using (var fileStream = new FileStream(path, FileMode.Open, FileAccess.Read, FileShare.Read, 8192))
    using (var streamReader = new StreamReader(fileStream, Encoding.UTF8, false, 8192))

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

Когда размеры буфера совпадают, буфер потока никогда не будет использоваться - на самом деле он никогда не будет выделен.

Ответ 6

Используя текстовый файл на 200 МБ, следующее заняло чуть больше 5 секунд на моей машине.

    class Program
{
    private static readonly char[] separators = { ' ' };
    private static List<string> lines;
    private static ConcurrentDictionary<string, int> freqeuncyDictionary;

    static void Main(string[] args)
    {
        var stopwatch = new System.Diagnostics.Stopwatch();
        stopwatch.Start();

        string path = @"C:\Users\James\Desktop\New Text Document.txt";
        lines = ReadLines(path);
        ConcurrentDictionary<string, int> test = GetFrequencyFromLines(lines);

        stopwatch.Stop();
        Console.WriteLine(@"Complete after: " + stopwatch.Elapsed.TotalSeconds);
    }

    private static List<string> ReadLines(string path)
    {
        lines = new List<string>();
        using (var fileStream = File.Open(path, FileMode.Open, FileAccess.Read))
        {
            using (var streamReader = new StreamReader(fileStream))
            {
                string line;
                while ((line = streamReader.ReadLine()) != null)
                {
                    lines.Add(line);
                }
            }
        }
        return lines;            
    }

    public static ConcurrentDictionary<string, int> GetFrequencyFromLines(List<string> lines)
    {
        freqeuncyDictionary = new ConcurrentDictionary<string, int>();
        Parallel.ForEach(lines, line =>
        {
            var words = line.Split(separators, StringSplitOptions.RemoveEmptyEntries);

            foreach (var word in words)
            {
                if (freqeuncyDictionary.ContainsKey(word))
                {
                    freqeuncyDictionary[word] = freqeuncyDictionary[word] + 1;
                }
                else
                {
                    freqeuncyDictionary.AddOrUpdate(word, 1, (key, oldValue) => oldValue + 1);
                }
            }
        });

        return freqeuncyDictionary;
    }
}