All geek questions in one place

C # Fastest string search in all files

Problem (check change for explanation)

I have a list of about 1,500 lines, and for each of these lines I have to check if any of the files in the directory (and subdirectories) contain this line (there are about 4000 files).

the code

Now I have two options:

Original

foreach(var str in stringList)
{
    allFiles.Any(f => File.ReadAllText(f).Contains(str));
}

Second option (using ReadLines instead of ReadAllText, as suggested by VladL in this question )

foreach(var string in stringList)
{
    allFiles.SelectMany(File.ReadLines).Any(line => line.Contains(str));
}

I just checked the full execution of the program of the original version, and it took 21 minutes. Then I tested one statement (check if there is 1 line in any file), looking for a line that I knew that it wasn’t contained to check the worst case scenario, and these are my timings (executed every 3 times):

Original: 1285, 1369, 1336 ms

: 2718, 2804, 2831

ReadAllText ReadAllLines Original ( - ), .

, ( )?

Edit

, , , , . csv, , ( ). , , , - .

foreach(var csvFile in csvFiles)
{
    var lines = File.ReadAllLines(csvFile);
    foreach(var line in lines)
    {
        if (IsHeader(line)) continue;
        var str = ComposeString(line);
        var bool = allFiles.Any(f => File.ReadAllText(f).Contains(str));
        // do stuff with the line and bool
     }
 }

2

public void ExecuteAhoCorasick()
{
    var table = CreateDataTable();
    var allFiles = GetAllFiles();
    var csvFiles = GetCsvFiles();
    var resList = new List<string>();

    foreach(var csvFile in csvFiles)
    {
        if (file.Contains("ValueList_")) continue;
        var lines = File.ReadAllLines(file);
        foreach (var line in lines)
        {
            if (line == HeaderLine) continue;
            var res = line.Split(';');
            if (res.Length <= 7) continue;
            var resPath = $"{res[0]}.{res[1]}.{res[2]}".Trim('.');
            resList.Add(resPath);

            var row = table.NewRow();
            row[0] = res[0]; // Group
            row[1] = res[1]; // Type
            row[2] = res[2]; // Key
            row[3] = res[3]; // Global
            row[4] = res[4]; // De
            row[5] = res[5]; // Fr
            row[6] = res[6]; // It
            row[7] = res[7]; // En
            row[8] = resPath; // Resource Path
            row[9] = false;
            row[10] = ""; // Comment
            row[11] = file; // File Path

            table.Rows.Add(row);
        }
    }

    var foundRes = new List<string>();

    foreach (var file in allFiles)
    {
        // var chars = File.ReadLines(file).SelectMany(line => line);
        var text = File.ReadAllText(file);

        var trie = new Trie();
        trie.Add(resList);

        foundRes.AddRange(trie.Find(text));
        // foundRes.AddRange(trie.Find(chars));
    }

    // update row[9] to true foreach res in foundRes
}
+5
5

, :

Aho-Corasick .

, Github, ( , ), Aho-Corasick Contains()):

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using ConsoleApp1;

namespace Demo
{
    class Program
    {
        static void Main()
        {
            string[] needles = createNeedles(1500).ToArray();
            string haystack = createHaystack(100000);

            var sw = Stopwatch.StartNew();
            anyViaContains(needles, haystack);
            Console.WriteLine("anyViaContains() took " + sw.Elapsed);

            sw.Restart();
            anyViaAhoCorasick(needles, haystack);
            Console.WriteLine("anyViaAhoCorasick() took " + sw.Elapsed);
        }

        static bool anyViaContains(string[] needles, string haystack)
        {
            return needles.Any(haystack.Contains);
        }

        static bool anyViaAhoCorasick(string[] needles, string haystack)
        {
            var trie = new Trie();
            trie.Add(needles);
            trie.Build();
            return trie.Find(haystack).Any();
        }

        static IEnumerable<string> createNeedles(int n)
        {
            for (int i = 0; i < n; ++i)
                yield return n + "." + n + "." + n;
        }

        static string createHaystack(int n)
        {
            var sb = new StringBuilder();

            for (int i = 0; i < n; ++i)
                sb.AppendLine("Sample Text Sample Text Sample Text Sample Text Sample Text Sample Text Sample Text Sample Text");

            return sb.ToString();
        }
    }
}

, 64- RELEASE ( ), :

anyViaContains() 00: 00: 09.8216836

anyViaAhoCorasick() 00: 00: 00.4002765

, Aho-Corasick 25 , Contains(). , . , , .

, Aho-Corasick, Find() IEnumerable<char>.

IEnumerable<char> :

var chars = File.ReadLines(filename).SelectMany(line => line);

, , , . , :

IEnumerable<char> newline = Enumerable.Repeat('\n', 1);
var chars = File.ReadLines(filename).SelectMany(line => Enumerable.Concat(line, newline));

( ), , . .

+3

, - ?

private static bool ContainsLine(string file, List<string> wordsToFind) {
  return File
    .ReadLines(file)
    .Any(line => wordsToFind.Any(word => line.Contains(word))); 
}

, ?

bool result = allFiles
  .AsParallel() // worth trying: we have a lot of files to be proceed
  .Any(file => ContainsLine(file, stringList));

: .AsParallel() ( ), , AsParallel() , :

bool result = allFiles
  //.AsParallel() // comment out in case of no gain
  .Any(file => ContainsLine(file, stringList));
+3

.

? :

bool exists = 
    allFiles.SelectMany(File.ReadLines).Any(l=> stringList.Any(str=> l.Contains(str));

OP:

, CSV, , :

var stringList =
  csvFiles.SelectMany(f=>File.ReadAllLines(f).Where(l=>!IsHeader(l)).Select(ComposString))
          .ToList();

, .Distinct, , , . , .

var stringList =
  csvFiles.SelectMany(f=>File.ReadAllLines(f).Where(l=>!IsHeader(l)).Select(ComposString))
          .Distinct()
          .ToList();
+2

. , , - (, Dictionary<string, WhatEver>), . - - .

,

class FileReference
{
    // elided 

    string File { get; } // may be set in constructor
    IEnumerable<int> Indices { get; } // will get the contents of _index

    public void Add(int index)
    {
        _indices.Add(index);
    }
}

class ReferenceIndex
{
    Dictionary<string, FileReference> _fileReferences = new Dictionary<string, FileReference>();

    public void Add(string fileName, string index)
    {
        if(!_fileReferences.ContainsKey(fileName))
        {
            _fileReferences.Add(fileName, new FileReference(fileName));
        }
        _fileReferences[fileName].Add(index);
    }

    // elided
}

FileReferencekeeps track of the indices of row a in a single file, ReferenceIndexcontains FileReferencefor one row. For Dictionary<TKey, TValue>hashed access to it quickly. You can use these classes to create Dictionary<string, ReferenceIndex>that keeps track of all lines in files and links to files of these lines

Dictionary<string, ReferenceIndex> stringIndex = BuildIndex(fileName);
foreach(var s in searchStrings)
{
    if(stringIndex.ContainsKey(s))
    {
        // do something
    }
}
+1
source

I recently encountered a similar problem. Imagine each searchable file as follows:

public class SearchableFile {
    private readonly HashSet<string> _uniqueLines;
    //private readonly HashSet<string> _uniqueString;

    public string FilePath { get; }

    public SearchableFile(string filePath) {
        _uniqueLines = new HashSet<string>(File.ReadAllLines(filePath));
        //↑You can also split each line if you have many repeating words in each line.
        //_uniqueString = File.ReadAllLines(filePath).SelectMany(singleLine => singleLine.Split(' '));
        FilePath = filePath;
    }

    public bool ContainsCompositeString(string compositeString) {
        return _uniqueLines.Any(singleLine => singleLine.Contains(compositeString));
        //return _uniqueString.Contains(compositeString);
    }
}

Then you can use it as is:

    private static void Main(string[] args) {
        var filePaths = new List<string> { "c://temp.txt" };

        foreach (var filePath in filePaths) {
            FilesOnHdd.Add(new SearchableFile(filePath));
        }
        var csvFiles = new List<string> { "c://temp.csv" };
        foreach (var csvFile in csvFiles) {
            var lines = File.ReadAllLines(csvFile);
            foreach (var line in lines) {
                if (IsHeader(line)) {
                    continue;
                }
                var str = ComposeString(line);

                foreach (var singleFileOnHdd in FilesOnHdd) {
                    var result = singleFileOnHdd.ContainsCompositeString(str);
                    if (result) {
                        // do stuff with the line and bool
                    }
                }
            }
        }
    }
0
source

Source: https://habr.com/ru/post/1686104/

More articles:


All Articles