Эффективный анализ большого текстового файла в C #

Question

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

A7PS A8PN A6PP23 ...

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

Полагаю, я мог бы просто открыть StreamReader и проходить построчно, разбивая символ пробела. Посмотрим, встречался ли код, и добавив 1 к счетчику этого кода. Однако это, вероятно, довольно наивно, учитывая размер данных.

Кто-нибудь знает эффективный алгоритм для обработки такого рода обработки?

ОБНОВЛЕНИЕ:

ОК, так что консенсус, кажется, мой подход в правильном направлении

Мне было бы интересно услышать такие вещи, как - что более эффективно - StreamReader. TextReader, BinaryReader

Какова лучшая структура для хранения моего словаря результатов? HashTable, SortedList, HybridDictionary

Если нет разрывов строк в файле (мне еще не дали образец), будет просто неэффективно разбивать все это на пробел?

По сути, я стремлюсь сделать его максимально быстрым

еще раз спасибо

Answer 1

Ваш подход выглядит хорошо.

1. Чтение в строке в строке
2. Разделение каждой строки на пробел
3. Добавление записи в словарь, если это не таксуществует, и если он существует, введите значение ++

Answer 2

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

Редактировать : вот схема решения.

1. Допустим, мы обработаем M кусков из N символов в то время (потому что мы хотим ограничить объем памяти необходимо и количество используемых потоков).
2. Выделить N * M символьный буфер. Мы будем использовать этот буфер циклически.
3. Будет использоваться шаблон производитель-потребитель. Производитель заполнит буфер. Это постараюсь найти границу слова рядом граница куска (т.е. около каждого N-го персонаж). Таким образом, у нас будет М кусков из примерно N символов с начала и конец индекса в буфере
4. Теперь запустите M рабочих потоков для обработки каждого чанка. Каждый работник будет использовать свой словарь для подсчета слов - это избавит от необходимости синхронизации потоков.
5. Будет агрегировать результаты в конце итерации. Процесс необходимо повторять до тех пор, пока не будет прочитан весь файл.

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

Answer 3

Сто тысяч записей не так много. Я бы использовал Dictionary<string,int>. Для хранения ключа и счета.

Но если у вас возникают проблемы с памятью, почему бы не использовать базу данных, даже такую ​​базу данных, как SQL Compact или SQLite. Создайте таблицу с записью, содержащей ключ и количество.

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

Answer 4

Если вы хотите попробовать что-то другое, вы можете попробовать использовать BinaryReader, и читать поток за байтом, и увеличивать счетчик на единицу каждый раз, когда вы встречаете пробел.

Answer 5

Я согласен с комментарием PoweRoy: почему бы не попробовать? Может быть, на практике проблем нет.

Если вам нужно что-то еще, вы можете попробовать написать код, который принимает Stream и возвращает IEnumerable<string>. Он будет читать символы из своего ввода по одному - если вам нужна буферизация для эффективности, вы всегда можете обернуть FileStream, который вы фактически даете этому коду, в BufferStream - и проверить, является ли это пробелом (или, возможно, EOL? ). Если это не так, он добавит символ в строковый буфер (возможно, StringBuilder?), Но если это так, он yield return изменит текущий буфер строки и очистит его.

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

Затем можно использовать некую структуру данных, например Dictionary<string,int>, для подсчета количества вхождений для каждого кода, сохранения кода в качестве ключа и подсчета в качестве значения. Но этот шаг будет таким же, если вы читаете файл построчно и используете string.Split, чтобы разделить их на пробелы.

Answer 6

    static string LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    static string NUMBERS = "1234567890";
    static Random rdGen = new Random();
    static Dictionary<string, int> myDic = new Dictionary<string, int>();
    static void WriteTest(int max)
    {
        myDic = new Dictionary<string, int>();
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < max; i++)
        {
            string code = LETTERS[rdGen.Next(0, 26)].ToString() + NUMBERS[rdGen.Next(0, 10)].ToString() + LETTERS[rdGen.Next(0, 26)].ToString() + LETTERS[rdGen.Next(0, 26)].ToString();
            if (myDic.ContainsKey(code)) myDic[code]++;
            else
            {
                myDic[code] = 1;
            }
        }
        sw.Stop();
        Console.WriteLine(max.ToString() + " itérations : " + sw.ElapsedMilliseconds.ToString());

    }

WriteTest (10000000);// Занимает 7,5 секунд.

Мне кажется, это довольно эффективно.

Answer 7

Если других ограничений нет, вам необходимо прочитать весь файл, как вы описали.

Чтобы сохранить коды и количество, вы должны использовать структуру данных, которая позволяет выполнять поиск и вставку за O (log n) времени. SortedDictionary сделает это в C #.

EDIT:

Какова лучшая структура для хранения моего словаря результатов? HashTable, SortedList, HybridDictionary

Поскольку сортированный порядок, по-видимому, не требуется, HybridDictionary или Словарь будут работать лучше в большинстве случаев. SortedList, вероятно, будет самым медленным решением, потому что вставки принимают O (n). Вам следует провести несколько тестов с различными реализациями, если производительность так важна.

Answer 8

На самом базовом уровне я бы начал с Dictionary<string, int>, string.split документа на пробелы, и продолжал считать с помощью простого анализа этих данных.

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

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

Ian