CODEWITHSUNDEEP
c#performancesearchiofull-text-search
user1747467
user1747467

Reputation: 99

Searching large text file

I am trying to optimize the search for a string in a large text file (300-600mb). Using my current method, it is taking too long.

Currently I have been using IndexOf to search for the string, but the time it takes is way too long (20s) to build an index for each line with the string.

How can I optimize searching speed? I've tried Contains() but that is slow as well. Any suggestions? I was thinking regex match but I don't see that having a significant speed boost. Maybe my search logic is flawed

example 

while ((line = myStream.ReadLine()) != null)
{
    if (line.IndexOf(CompareString, StringComparison.OrdinalIgnoreCase) >= 0)
    {
        LineIndex.Add(CurrentPosition);
        LinesCounted += 1;
    }
}

Upvotes: 8

Views: 10948

Answers (5)

dynamicbutter
dynamicbutter

Reputation: 331

This post is the top stackoverflow hit when I search "searching large text files" tagged with c#. Although, the problem still exists, some things have changed since this post was originally made. Like 300-600 MB no longer being considered a large file, and like the performance of System.Text.RegularExpressions.Regex being greatly improved. For these reasons I feel it's fair to update the answer.

In short, using System.Text.RegularExpressions.Regex from the current version of dotnet is going to be very fast for just about any search you can come up with. It's gotten really fast.

Starting with .NET7 Regex incorporates 4 different engines depending on how it's instantiated. These engines provide highly optimized searching "in many cases, to the point where it ends up being significantly better than Boyer-Moore in all but the most corner of corner cases."

Of the 4 engines using RegexOptions.Compiled or GeneratedRegex will produce the fastest code (ie. the best best-case performance). For most cases this is a good solution.

However, if your use case needs maximum stability or is susceptible to input abuse then using RegexOptions.NonBacktracking will provide "the best worst-case performance" "in exchange for reduced best-case performance" by switching to an engine based on finite automata which "guarantees it’ll only ever do an ammortized-constant amount of work per character in the input."

Here is Stephen Toub's full blog about the many impressive optimizations added to Regex in .NET7.

To further boost the performance of System.Text.RegularExpressions.Regex through parallelism or to process files that exceed RAM you may also want to have a look at Gigantor.

Upvotes: 2

Jonathan Wood
Jonathan Wood

Reputation: 67195

Unfortunately, I don't think there's a whole lot you can do in straight C#.

I have found the Boyer-Moore algorithm to be extremely fast for this task. But I found there was no way to make even that as fast as IndexOf. My assumption is that this is because IndexOf is implemented in hand-optimized assembler while my code ran in C#.

You can see my code and performance test results in the article Fast Text Search with Boyer-Moore.

Upvotes: 5

Nicholas Carey
Nicholas Carey

Reputation: 74257

The brute force algorithm you're using performs in O(nm) time, where n is the length of the string being searched and m the length of the substring/pattern you're trying to find. You need to use a string search algorithm:

However, using a regular expression crafted with care might be sufficient, depending on what you are trying to find. See Jeffrey's Friedl's tome, Mastering Regular Expressions for help on building efficient regular expressions (e.g., no backtracking).

You might also want to consult a good algorithms text. I'm partial to Robert Sedgewick's Algorithms in its various incarnations (Algorithms in [C|C++|Java])

Upvotes: 13

Raghav
Raghav

Reputation: 9

You can user regexp.Match(String). RegExp Match is faster.

static void Main()

{

  string text = "One car red car blue car";
  string pat = @"(\w+)\s+(car)";

  // Instantiate the regular expression object.
  Regex r = new Regex(pat, RegexOptions.IgnoreCase);

  // Match the regular expression pattern against a text string.
  Match m = r.Match(text);
  int matchCount = 0;
  while (m.Success) 
  {
     Console.WriteLine("Match"+ (++matchCount));
     for (int i = 1; i <= 2; i++) 
     {
        Group g = m.Groups[i];
        Console.WriteLine("Group"+i+"='" + g + "'");
        CaptureCollection cc = g.Captures;
        for (int j = 0; j < cc.Count; j++) 
        {
           Capture c = cc[j];
           System.Console.WriteLine("Capture"+j+"='" + c + "', Position="+c.Index);
        }
     }
     m = m.NextMatch();
  }

}

Upvotes: 1

Austin Henley
Austin Henley

Reputation: 4633

Have you seen these questions (and answers)?

Doing it the way you are now seems to be the way to go if all you want to do is read the text file. Other ideas:

  • If it is possible to pre-sort the data, such as when it gets inserted into the text file, that could help.

  • You could insert the data into a database and query it as needed.

  • You could use a hash table

Upvotes: 1

Related Questions