What is the best 'Trial and Error' algorithm to find first row with specific date in large text file in c#?

This is a typical indexing problem.

Let me start with saying there are better systems for this: storing your data in a database would make this problem real easy.

But, just for fun, Ill give it a try.

Since your date structure is ordered, alphabetically, if you find any valid point within the set (date range), you have found the set and you can proceed.

A typical way to accomplish:

• start at half point
• if you're not in the target set, go half of the half up or down, depending on the value you have hit. (if it's too big, go up, if it's too small, go down)
• repeat until you hit the set; from there you can loop both way's to get the full set (the target range)

As @Cid pointed out, this will only work correctly if you have an index of some sort.

You can accomplish this (depending on how often you need to run the query) by creating an index upfront, either in memory or on disk.

If it is a 1 time task, you can still do this binary search, but not on the index but on the file bytes, by using Stream.Seek, it will not give an optimal result, but it will on average still be faster than going through the whole file.

Do note: it will be hard to get it right. It might be best to close in into an actual data point and start reading if the distance is within a specific range.

If your stream is not Seekable (like a network stream or such), and it's a one time query, you will need to iterate over the whole file and optimization options are minimal.

Example

Disclaimer

Code will contain bugs and is not suited for production.

3 issues:

1. It's not suited for variable bit encoding (due to the seeking)
2. It's will not find the first index yet (trying to work on it)
3. Not sure how it behaves if the index is not there, most likely a stackoverflowexception.
4. its not suited for a range yet, I think I read the question wrong XD

Consist of 3 functions: 1 main to call it, a recursive search and a "starter".

Used a 10MB log file, which actually contains a lot of errors due to an issue.

The log:

2020-11-08 23:10:06,201 [24] ERROR Unity.SelfHostWebApiOwin.UnityHelpers [(null)] - Error while requesting stats.
System.IO.IOException: The handle is invalid.

   at System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
   at System.Console.GetBufferInfo(Boolean throwOnNoConsole, Boolean& succeeded)
   at ShowStatsService.LogSource() in ShowStatsService.cs:line 109
LogSource

2020-11-08 23:10:16,209 [32] ERROR Unity.SelfHostWebApiOwin.UnityHelpers [(null)] - Error while requesting stats.
System.IO.IOException: The handle is invalid.

   at System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
   at System.Console.GetBufferInfo(Boolean throwOnNoConsole, Boolean& succeeded)
   at ShowStatsService.LogSource() in ShowStatsService.cs:line 109
LogSource

First the main:

static void Main(string[] args)
{
    using FileStream bigFile = new FileStream(".\\testdata\\log.txt", FileMode.Open);

    var indexToFind = "2020-11-10 01:31";

    //searches for YYYY-MM-DD HH:MM date/time format
    var regexPatternLocator = @"^\d{4}-\d{2}-\d{2} \d{2}:\d{2}";

    Func<string, bool> comparer = rawInput => new Regex(regexPatternLocator).IsMatch(rawInput);

    var result = FindByIndex(bigFile,comparer,
    indexValue => string.Compare(indexValue.Substring(0,indexToFind.Length), indexToFind));

    Console.WriteLine($"Result: {result}");
}

The starter:

/// <summary>
/// Retrieves a value by index, including index
/// </summary>
/// <param name="seekableStream">Target text based stream</param>
/// <param name="indexLocator">Expression to identify an index</param>
/// <param name="compareFunction">Expression to compare an index</param>
/// <returns></returns>
public static string FindByIndex(Stream seekableStream, Func<string, bool> indexLocator,
    Func<string, int> compareFunction)
{
    return FindByNonUniqueIndexInternal(seekableStream, indexLocator, 
        compareFunction, 
        seekableStream.Length / 2, 0,0,0);
}

The searcher:

/// <summary>
/// Some additional parameters t keep track of stats & counts
/// </summary>
/// <returns></returns>
private static string FindByNonUniqueIndexInternal(Stream seekableStream, Func<string, bool> indexLocator,
        Func<string, int> compareFunction, long position, long previousPosition, int nIteration, int nReadedLines)
{
    Console.WriteLine($"Attempts: {nIteration}");
    Console.WriteLine($"Lines Read: {nReadedLines}");
    Console.WriteLine($"Position: {position}");

    nIteration++;
    seekableStream.Seek(position, SeekOrigin.Begin);

    //using using declaration, see https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/proposals/csharp-8.0/using
    //Note: if using variable bit UTF encoding, this is going to be harder, with
    //subtle issues relating to the fact that a char can have various byte widths
    using var reader = new StreamReader(seekableStream,Encoding.ASCII);
    string line;
    while ((line = reader.ReadLine()) != null)
    {
        position+= line.Length;
        nReadedLines++;

        if (indexLocator(line)) //index type found
        {
            var indexComparerValue = compareFunction(line);

            var length = Math.Abs(position - previousPosition);
            var jump = length / 2;

            if (indexComparerValue < 0) //found index value is to big
            {
                //recursive call 
                return FindByNonUniqueIndexInternal(seekableStream, 
                    indexLocator,
                    compareFunction, 
                    position + jump,
                    position, 
                    nIteration, 
                    nReadedLines);
            }

            if (indexComparerValue > 0) //found index value is to small
            {
                //recursive call 
                return FindByNonUniqueIndexInternal(seekableStream,
                    indexLocator,
                    compareFunction,
                    position - jump,
                    position,
                    nIteration,
                    nReadedLines);
            }

            else
            {
                //reverse find
                //jump back
                // needs to be implemented

                var sb = new StringBuilder(line);
                //read until end or next index
                while ((line = reader.ReadLine()) != null)
                {
                    if (indexLocator(line) && compareFunction(line) != 0)
                        break; //hit a new index, so break.

                    sb.AppendLine(line);
                }

                return sb.ToString();
            }

        }
    }
    return string.Empty;
}

The output (removed sensitive data):

Attempts: 8
Lines Read: 50
Position: 5943268
Result: 2020-11-10 01:31:21,045 [38] ERROR Unity.SelfHostWebApiOwin.UnityHelpers [(null)] - Error while requesting stats.System.IO.IOException: The handle is invalid.

   at System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
   at System.Console.GetBufferInfo(Boolean throwOnNoConsole, Boolean& succeeded)

2020-11-10 01:31:31,057 [42] ERROR Unity.SelfHostWebApiOwin.UnityHelpers [(null)] - Error while requesting stats.
System.IO.IOException: The handle is invalid.

   at System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
   at System.Console.GetBufferInfo(Boolean throwOnNoConsole, Boolean& succeeded)
   
2020-11-10 01:31:41,063 [38] ERROR Unity.SelfHostWebApiOwin.UnityHelpers [(null)] - Error while requesting stats.
System.IO.IOException: The handle is invalid.

   at System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
   at System.Console.GetBufferInfo(Boolean throwOnNoConsole, Boolean& succeeded)

2020-11-10 01:31:51,064 [29] ERROR Unity.SelfHostWebApiOwin.UnityHelpers [(null)] - Error while requesting stats.
System.IO.IOException: The handle is invalid.

   at System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
   at System.Console.GetBufferInfo(Boolean throwOnNoConsole, Boolean& succeeded)
   at ShowStatsService.LogSource in ShowStatsService.cs:line 109
ShowStatsService.LogSource

I had a similar issue where I had to process TB size csv files and being faced with the issue of processing them, there was no way to use ReadLines etc as one would instantly get out of memory exceptions.

I'm sure you're able to use my code after altering it a bit to fit your use case.

I created a File Map to create a structure that I could use to jump in the file the map is working with line data, here is the structure for it. the below sample only uses the "from" property, but rather than altering the code I will leave it in so you can use it to store the date element from the line you process

public struct LineData
{
    /// <summary>
    /// Line number
    /// </summary>
    public long Line { get; set; }
    /// <summary>
    /// Starting position of the file in the file
    /// </summary>
    public long From { get; set; }
    /// <summary>
    /// End position of the line in the file
    /// </summary>
    public long Till { get; set; }
    /// <summary>
    /// Flag that indicates the line is processed used by parallel processing indicting the line is processed
    /// </summary>
    public bool IsRead { get; set; }
    /// <summary>
    /// The length of the line in the file
    /// </summary>
    public long Length => Till - From;
}

I then process the file by reading the file in the same way File.ReadLines() would do only I do not keep the lines in memory, only the discovered LineData, here is my extension method

public static List<LineData> FileMap(this FileInfo file, int? initialSize = null)
{

    if (!file.Exists)
    {
        return default;
    }

    const char CR = '\r';
    const char LF = '\n';
    const char NULL = (char)0;

    List<LineData> result = initialSize.HasValue
                            ? new List<LineData>(initialSize.Value)
                            : new List<LineData>();
    byte[] byteBuffer = new byte[1024 * 1024];
    char detectedEOL = NULL;
    char currentChar = NULL;
    var line = new LineData() { From = 0, Line = 0 };
    int bytesRead;

    using (var stream = new FileStream(path: file.FullName
                                        , mode: FileMode.Open
                                        , access: FileAccess.Read
                                        , share: FileShare.Read))
    {
        while ((bytesRead = stream.Read(byteBuffer, 0, byteBuffer.Length)) > 0)
        {

            for (int i = 0; i < bytesRead; i++)
            {
                currentChar = (char)byteBuffer[i];

                if (detectedEOL != NULL)
                {
                    if (currentChar == detectedEOL)
                    {
                        line.Till += i;
                        result.Add(line);
                        line = new LineData() { Line = line.Line + 1, From = line.Till + 2 };
                    }
                }
                else if (currentChar == LF || currentChar == CR)
                {
                    detectedEOL = currentChar;
                    line.Till += i;
                    result.Add(line);
                    line = new LineData() { Line = line.Line + 1, From = line.Till + 2 };
                }
            }
        }
    }

    if (currentChar != LF && currentChar != CR && currentChar != NULL)
    {
        line.Till = Array.IndexOf(byteBuffer, NULL);
        if (line.Till == -1)
            line.Till = byteBuffer.Length;
    }
    return result;
}

having the data you can now read sections of the file like this:

public static string ReadLine(this FileInfo file, LineData line)
{
    if (!file.Exists) return default;

    using (var stream = new StreamReader(new FileStream(path: file.FullName, mode: FileMode.Open, access: FileAccess.Read, share: FileShare.Read)))
    {
        stream.BaseStream.Seek(line.From, SeekOrigin.Begin);
        return stream.ReadLine();
    }
}

public static string[] ReadLines(this FileInfo file, LineData[] lines)
{
    if (!file.Exists) return default;
    var result = new string[lines.Length];
    using (var stream = new StreamReader(new FileStream(path: file.FullName, mode: FileMode.Open, access: FileAccess.Read, share: FileShare.Read)))
    {
        for(uint i =0;i< lines.Length;i++)
        {
            stream.BaseStream.Seek(lines[i].From, SeekOrigin.Begin);
            result[i]= stream.ReadLine();
        }
    }
    return result;
}

Having processed the file you now have structured data that can be used to process the file. We used this code to generate balanced training files for machine learning algorithms making sure the training models had the right data to train with.

I know it does not answer your question to the "t" but I guess there are quite a few developers trying to solve this issue with their own "twist"

Stefan, Please take a look at the code below. It does the work (still didn't handle the out-of-range issue) but the performance are pretty bad (it took almost 12 seconds just to find the first relvant row in a 10k rows txt file):

long firstRow = FindFirstRow(file, total_lines);

private long FindFirstRow(FileInfo file, long total_lines)
        {
            long current_line = total_lines / 2;
            Result result = Result.NOT_FOUND;
            while (result != Result.IN_RANGE)
            {
                result = IsLineInTimeFrame(file.FullName, ref current_line);
                if (result.Equals(Result.LARGER))
                {
                    current_line = current_line - ((total_lines - current_line) / 2);
                }
                else if(result.Equals(Result.SMALLER))
                {
                    current_line = current_line + ((total_lines - current_line) / 2);
                }
                else if (result.Equals(Result.NOT_FOUND))
                {
                    current_line = current_line - ((total_lines - current_line) / 2);
                }
            }
            /*
             * After finding the first row with the start datetime, we now search for the first row coming befor it.
             * The row will not necessarily be one row above. For example:
             * If we're looking for 16:42:00, we can have dozens of records under that time, 
             * so we'll go back until we find 16:41:59 or less. 
             * Since we don't want to iterate each row (performance issue),
             * we will jump 1% back. Once we found the '16:41:59' time, we move fwd one row at a time until its in range.
             */
            while (result != Result.SMALLER)
            {
                result = IsLineInTimeFrame(file.FullName, ref current_line);
                int percentJump = (int)Math.Round((double)(100 * current_line) / total_lines);
                current_line = current_line - percentJump;
            }
            while (result != Result.IN_RANGE)
            {
                result = IsLineInTimeFrame(file.FullName, ref current_line);
                current_line = current_line + 1;
            }
            current_line--;
            return current_line;
        }
private Result IsLineInTimeFrame(string filePath, ref long lineNumber)
        {
            Result result = Result.NOT_FOUND;
            Regex regex = new Regex(@"\b\d{2}\.\d{2}.\d{4}\b-[012]{0,1}[0-9].[0-6][0-9].[0-6][0-9]");
            string content = ReadSpecificLine(filePath, lineNumber);
            if (regex.IsMatch(content))
            {
                List<string> content_list = content.Split(' ').ToList();
                foreach (string piece in content_list)
                {
                    try
                    {
                        foreach (Match m in regex.Matches(piece))
                        {
                            DateTime dt;
                            if (DateTime.TryParseExact(m.Value, "dd.MM.yyyy-HH.mm.ss", null, DateTimeStyles.None, out dt))
                            {
                                Logger.LogWriter.LogInstance.LogWrite($"{m.Value}");
                                if (dt >= Convert.ToDateTime(SelectedDateFrom) && dt <= Convert.ToDateTime(SelectedDateTo))
                                {
                                    result = Result.IN_RANGE;
                                }
                                else if (dt < Convert.ToDateTime(SelectedDateFrom))
                                {
                                    result = Result.SMALLER;
                                }
                                else if (dt > Convert.ToDateTime(SelectedDateTo))
                                {
                                    result = Result.LARGER;
                                }
                            }
                        }
                    }
                    catch (Exception ex) { }
                }
            }
            return result;
        }
enum Result
        {
            LARGER,
            SMALLER,
            IN_RANGE,
            NOT_FOUND
        }