Оптимизация I/O операций для работы с большими текстовыми файлами (1Гб+)

@Gekr · Регистрация: 01.10.2012

Студворк — интернет-сервис помощи студентам

Доброго времени суток.
Подскажите каким образом можно оптимизировать I/O операций для работы с большими текстовыми файлами (1Гб+)

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

Человек давший задание предложил мне использовать другую структуру данных, чтобы оптимизировать чтение/запись. Какая из структур данных справиться с этой задачей лучше List<T>?

Буду благодарен за ссылки на статьи и литературу про оптимизацию I/O для текстовых файлов.

Класс представляющий слово

C#
1
2
3
4
5
6
7
8
9
10
public class Word
    {
        public string Text { get; set; }
        public List<int> LineNumbers { get; set; }
 
        public Word()
        {
            LineNumbers = new List<int>();
        }
    }

Вот метод в котором я построчно считываю файл и создаю список слов

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<Word> ReadFileAsync(string filePath)
        {
          //  var watch = System.Diagnostics.Stopwatch.StartNew();
 
            List<Word> words = new List<Word>();
            int lineCount = 1;
 
            try
            {
                using (StreamReader sr = new StreamReader(filePath))
                {
                    string nextLine;
                    while ((nextLine = sr.ReadLine()) != null)
                    {
                        AddWordFromLineToWordList(SplitLineIntoWords(nextLine), words, lineCount);
                        lineCount++;
                    }
                }
            }
            catch (Exception ex)
            {
            }
 
          //  watch.Stop();
          //  var elapsedMs = watch.ElapsedMilliseconds;
          // Console.WriteLine(elapsedMs);
 
            return words;
        }

Метод с помощью которого я записываю результат в другой файл

C#
1
2
3
4
5
6
7
8
9
10
public async Task WriteAsync(string path, List<Word> words)
        {
            DeleteFile(path);
            CreateFile(path);
            words.Sort(new WordComparer());
            foreach (Word word in words)
            {
                await WriteWordsAndLineNumbersAsync(path, word);
            }
        }

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
private async Task WriteWordsAndLineNumbersAsync(string path, Word word)
        {
            try
            {
                using (FileStream fs = new FileStream(path, FileMode.Append,
                    FileAccess.Write, FileShare.Write, 4096, useAsync: true))
                {
                    using (StreamWriter sw = new StreamWriter(fs))
                    {
                        await sw.WriteAsync(word.Text + " ");
 
                        int size = word.LineNumbers.Count;
                        for (int i = 0; i < size; i++)
                        {
                            if (i < size - 1)
                            {
                                await sw.WriteAsync(word.LineNumbers[i] + ", ");
                            }
                            else
                            {
                                await sw.WriteAsync(word.LineNumbers[i].ToString());
                            }
                        }
                        sw.Write(Environment.NewLine);
                    }
                }
            }
            catch (Exception ex)
            {
 
            }
        }

@Fleder · 30.08.2017, 22:05

Gekr, хотелось бы взглянуть на методы AddWordFromLineToWordList и SplitLineIntoWords.

Добавлено через 1 минуту
А также на фрагмент исходного файла (несколько строк).

@RunningMan · 30.08.2017, 22:19

Сообщение от Gekr

Человек давший задание предложил мне использовать другую структуру данных, чтобы оптимизировать чтение/запись. Какая из структур данных справиться с этой задачей лучше List<T>?

Ассоциативные массивы удобнее (IMHO). Скорость не измерял.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
            var words = new Dictionary<string, HashSet<int>>();
 
            using (StreamReader sr = new StreamReader(filePath))
                {
                    var delimiters = " ,.!?()".ToCharArray();
                    string nextLine;
                    int lineCount = 0;
                    while ((nextLine = sr.ReadLine()) != null)
                    {
                        string[] parts = nextLine.Split(delimiters, StringSplitOptions.RemoveEmptyEntries);
 
                        foreach (var word in parts)
                        {                        
                            if (words.TryGetValue(word, out HashSet<int> ret))
                            {
                                words[word].Add(lineCount);
                            }
                            else
                            {
                                words[word] = new HashSet<int> { lineCount };
                            }
                        }
                  
                        lineCount++;
                    }
                }
            
 
            foreach (var pair in words)
            {
                Console.Write(pair.Key);
                foreach (var numlines in pair.Value)
                    Console.Write(" {0}",numlines);
 
                Console.WriteLine();
            }

Добавлено через 6 минут

Сообщение от Gekr

while ((nextLine = sr.ReadLine()) != null)

По скорости считывания текстового файла StreamReader.ReadLine должен быть самый
быстрый способ. На stackoverflow где-то есть замеры, не искал.

@Gekr · 30.08.2017, 22:45 **[ТС]**

Действительно не в самом чтении файла проблема скорости, а в методе где используется Regex

C#
1
2
3
4
5
pattern = new Regex(
                @"( [A-Za-z0-9]
                ([A-Za-z0-9])*
                [A-Za-z0-9])",
                RegexOptions.IgnorePatternWhitespace);

C#
1
2
3
4
5
6
7
8
9
10
11
 public List<string> SplitLineIntoWords(string lineText)
        {
            List<string> lineWords = new List<string>();
            
            foreach (Match m in pattern.Matches(lineText))
            {
                lineWords.Add(m.Groups[1].Value.ToLower());
            }
 
            return lineWords;
        }

20 секунд уходит на выполнение метода для файла размером 350 мб.

@nicolas2008 · 31.08.2017, 00:13

Сообщение от Gekr

Действительно не в самом чтении файла проблема скорости, а в методе где используется Regex

Не только, про Dictionary вместо List вам очень правильно написали.
Вычислительная сложность поиска по ключу в Dictionary - O(1), поиска в List - O(n).
При больших обьемах данных и частом использовании поиска использовать List - плохое решение.

@Gekr · 31.08.2017, 01:00 **[ТС]**

Никогда не использовал Dictionary теперь вижу в чем его польза. И класс Word теперь можно убрать.

Все равно, большая часть времени исполнения уходит на метод SplitLineIntoWords.
Я поменял паттерн на [a-zA-Z0-9]{2,} и выиграл несколько секунд, но все равно он забирает большую часть времени.

@Fleder · 31.08.2017, 01:01

Сообщение от Gekr

Действительно не в самом чтении файла проблема скорости, а в методе где используется Regex

Этот метод можно сделать быстрее. Примерно раза в три, навскидку.

@Fleder · 31.08.2017, 01:47

Если заменить регулярку на конечный автомат аналогичного действия, то получается быстрее:

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
      static void Main(string[] args)
      {
         string str = "1 The the quick, brown fox. r fox jumped over the lazy dog dog.The1 the1 quick1, brown1 fox1.  fox1 jumped1 over1 the1 lazy1 dog1 dog1.";
 
         Regex pattern = new Regex(
                @"( [A-Za-z0-9]
                ([A-Za-z0-9])*
                [A-Za-z0-9])",
                RegexOptions.IgnorePatternWhitespace);
 
         List<string> list1 = SplitLineIntoWords(str, pattern);
         List<string> list2 = SplitLineIntoWords2(str);
 
         for(int i = 0; i < list1.Count; ++i)
         {
            if(!list1[i].SequenceEqual(list2[i])) throw new Exception();
         }
 
 
         Stopwatch sw1 = Stopwatch.StartNew();
         list1 = SplitLineIntoWords(str, pattern);
         sw1.Stop();
         Console.WriteLine($"SplitLineIntoWords {sw1.ElapsedTicks}");
 
         Stopwatch sw2 = Stopwatch.StartNew();
         list2 = SplitLineIntoWords2(str);
         sw2.Stop();
         Console.WriteLine($"SplitLineIntoWords2 {sw2.ElapsedTicks}");
 
         Console.ReadKey();
         GC.KeepAlive(list1);
         GC.KeepAlive(list2);
      }
 
      public static unsafe List<string> SplitLineIntoWords2(string str)
      {
         List<string> list = new List<string>();
         int index = 0;
         bool flag = false;
         int i = 0;
         fixed (char* ptr = str)
         {
            for(i = 0; i < str.Length; ++i)
            {
               int n = ptr[i];
               if((n >= 'a' && n <= 'z') || (n >= 'A' && n <= 'Z') || (n >= '0' && n <= '9'))
               {
                  if(!flag)
                  {
                     flag = true;
                     index = i;
                  }
               }
               else
               {
                  if(flag && i - index > 1)
                  {
                     list.Add(new string(ptr, index, i - index).ToLower());
                  }
                  flag = false;
                  index = i;
               }
            }
            if(flag && i - index > 1)
            {
               list.Add(new string(ptr, index, i - index).ToLower());
            }
         }
         return list;
      }
 
      public static List<string> SplitLineIntoWords(string lineText, Regex pattern)
      {
         List<string> lineWords = new List<string>();
         foreach(Match m in pattern.Matches(lineText))
         {
            lineWords.Add(m.Groups[1].Value.ToLower());
         }
         return lineWords;
      }
   }

Оптимизация I/O операций для работы с большими текстовыми файлами (1Гб+)

@Diamante · 31.08.2017, 19:43

а чем Split() не угодил?

@Gekr · 31.08.2017, 20:27 **[ТС]**

Тем, что мне нужна только последовательность символов английского алфавита и цифр, которая состоит из 2 и более символов, а в Split() нужно передавать разделитель - всю таблицу Unicode кроме [A-Za-z0-9], это медленнее чем Regex + нужно следить за изменением количества символов в таблице Unicode.

@Shamil1 · 02.03.2018, 14:25

Сообщение от Fleder

заменить регулярку на конечный автомат

Зачем использовать unsafe код? В Вашем коде вместо ptr можно использовать str (и вместо new string использовать Substring). На скорость работы это не влияет.

з.ы. Можно немного улучшить скорость, если убрать флаг... но тогда это уже будет не автомат?

@Fleder · 02.03.2018, 15:42

Сообщение от Shamil1

Зачем использовать unsafe код?

Спасибо за замечание. unsafe здесь явно лишний.
Добавил метод без указателей, и он отрабатывает даже быстрее (вот это поворот!).

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
      static void Main(string[] args)
      {
         string str = "1 The the quick, brown fox. r fox jumped over the lazy dog dog.The1 the1 quick1, brown1 fox1.  fox1 jumped1 over1 the1 lazy1 dog1 dog1.";
 
         Regex pattern = new Regex(
                @"( [A-Za-z0-9]
                ([A-Za-z0-9])*
                [A-Za-z0-9])",
                RegexOptions.IgnorePatternWhitespace);
 
         List<string> list1 = SplitLineIntoWords(str, pattern);
         List<string> list2 = SplitLineIntoWords2(str);
         List<string> list3 = SplitLineIntoWords3(str);
 
         for(int i = 0; i < list1.Count; ++i)
         {
            if(!list1[i].SequenceEqual(list2[i])) throw new Exception();
            if(!list1[i].SequenceEqual(list3[i])) throw new Exception();
         }
 
 
         Stopwatch sw1 = Stopwatch.StartNew();
         list1 = SplitLineIntoWords(str, pattern);
         sw1.Stop();
         Console.WriteLine($"SplitLineIntoWords {sw1.ElapsedTicks}");
 
         Stopwatch sw2 = Stopwatch.StartNew();
         list2 = SplitLineIntoWords2(str);
         sw2.Stop();
         Console.WriteLine($"SplitLineIntoWords2 {sw2.ElapsedTicks}");
 
         Stopwatch sw3 = Stopwatch.StartNew();
         list3 = SplitLineIntoWords3(str);
         sw3.Stop();
         Console.WriteLine($"SplitLineIntoWords3 {sw3.ElapsedTicks}");
 
 
         Console.ReadKey();
         GC.KeepAlive(list1);
         GC.KeepAlive(list2);
         GC.KeepAlive(list3);
      }
 
      public static List<string> SplitLineIntoWords(string lineText, Regex pattern)
      {
         List<string> lineWords = new List<string>();
         foreach(Match m in pattern.Matches(lineText))
         {
            lineWords.Add(m.Groups[1].Value.ToLower());
         }
         return lineWords;
      }
 
      public static unsafe List<string> SplitLineIntoWords2(string str)
      {
         List<string> list = new List<string>();
         int index = 0;
         bool flag = false;
         int i = 0;
         fixed (char* ptr = str)
         {
            for(i = 0; i < str.Length; ++i)
            {
               int n = ptr[i];
               if((n >= 'a' && n <= 'z') || (n >= 'A' && n <= 'Z') || (n >= '0' && n <= '9'))
               {
                  if(!flag)
                  {
                     flag = true;
                     index = i;
                  }
               }
               else
               {
                  if(flag && i - index > 1)
                  {
                     list.Add(new string(ptr, index, i - index).ToLower());
                  }
                  flag = false;
                  index = i;
               }
            }
            if(flag && i - index > 1)
            {
               list.Add(new string(ptr, index, i - index).ToLower());
            }
         }
         return list;
      }
 
      public static List<string> SplitLineIntoWords3(string str)
      {
         List<string> list = new List<string>();
         int index = 0;
         bool flag = false;
         int i = 0;
         for(i = 0; i < str.Length; ++i)
         {
            int n = str[i];
            if((n >= 'a' && n <= 'z') || (n >= 'A' && n <= 'Z') || (n >= '0' && n <= '9'))
            {
               if(!flag)
               {
                  flag = true;
                  index = i;
               }
            }
            else
            {
               if(flag && i - index > 1)
               {
                  list.Add(str.Substring(index, i - index).ToLower());
               }
               flag = false;
               index = i;
            }
         }
         if(flag && i - index > 1)
         {
            list.Add(str.Substring(index, i - index).ToLower());
         }
         return list;
      }

Сообщение от Shamil1

Можно немного улучшить скорость, если убрать флаг...

Интересно посмотреть это решение.

@Shamil1 · 02.03.2018, 16:01

Сообщение от Fleder

Интересно посмотреть это решение.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static List<string> SplitLineIntoWords3(string str)
{
    List<string> list = new List<string>();
    int i = 0;
    while (i < str.Length)
    {
        // skip delimiters
        while(i < str.Length)
        {
            int n = str[i];
            if ((n >= 'a' && n <= 'z') || (n >= 'A' && n <= 'Z') || (n >= '0' && n <= '9'))
                break;
            else
                i++;
        }
 
        // read word
        int index = i;
        while (i < str.Length)
        {
            int n = str[i];
            if ((n >= 'a' && n <= 'z') || (n >= 'A' && n <= 'Z') || (n >= '0' && n <= '9'))
                i++;
            else
                break;
        }
        if (i - index > 1)
            list.Add(str.Substring(index, i - index).ToLower());
    }
    return list;
}

@Fleder · 02.03.2018, 16:11

Shamil1, согласен, без флагов логика выглядит куда понятнее/приятнее.
Быстродействие аналогичное. Плюс - минус.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Fleder 263 / 224 / 108 Регистрация: 09.12.2015 Сообщений: 652
	30.08.2017, 22:05
	Gekr, хотелось бы взглянуть на методы `AddWordFromLineToWordList` и `SplitLineIntoWords`. Добавлено через 1 минуту А также на фрагмент исходного файла (несколько строк). 1

@Gekr 45 / 45 / 32 Регистрация: 01.10.2012 Сообщений: 185
	31.08.2017, 01:00 [ТС]
	Никогда не использовал Dictionary теперь вижу в чем его польза. И класс Word теперь можно убрать. Все равно, большая часть времени исполнения уходит на метод SplitLineIntoWords. Я поменял паттерн на [a-zA-Z0-9]{2,} и выиграл несколько секунд, но все равно он забирает большую часть времени. 0

@Diamante 3566 / 2507 / 1174 Регистрация: 14.08.2016 Сообщений: 8,219
	31.08.2017, 19:43
	а чем Split() не угодил? 0

@Gekr 45 / 45 / 32 Регистрация: 01.10.2012 Сообщений: 185
	31.08.2017, 20:27 [ТС]
	Тем, что мне нужна только последовательность символов английского алфавита и цифр, которая состоит из 2 и более символов, а в Split() нужно передавать разделитель - всю таблицу Unicode кроме [A-Za-z0-9], это медленнее чем Regex + нужно следить за изменением количества символов в таблице Unicode. 0

@Fleder 263 / 224 / 108 Регистрация: 09.12.2015 Сообщений: 652
	02.03.2018, 16:11
	Shamil1, согласен, без флагов логика выглядит куда понятнее/приятнее. Быстродействие аналогичное. Плюс - минус. 0