5
\$\begingroup\$

i'm wondering is there any way to optimize this code? It must be able to work with big files, for example, formatting raw 140kb .txt file (12.5k words) takes 2 seconds (measured with Stopwatch class). Text example http://pastebin.com/2p88v8EN Maybe i used here some bad techniques or there is some part to simplify? Maybe multithreading? I'm not familiar with this yet. Would be grateful for help!

Code below:

class TextManipulations                                                         
{
    public string[] wordsDist;                                                  // main array, contains words in alphabetic order and output lines 

    public void TextFormat(string sourcePath)                                   // creating method that will format our source text according to task
    {
        string textInput = System.IO.File.ReadAllText(sourcePath).ToLower();    // reading text from file, lowercased at start for precise search
        MatchCollection m = Regex.Matches(textInput, @"\b[\w']+\b");            // exact search of all alphanumeric "words" including words with apostrophe
        List<string> words = new List<string>();                                // creating List<T> for containing unknown amount of words

        foreach (Match match in m)                                              // assigning all matches to List<string>
        {
            words.Add(match.ToString());
        }
        words.Sort();                                                           // sorting words in alphabetic order
        wordsDist = words.Distinct().ToArray();                                 // assigning words to main array without duplicates
        System.IO.File.WriteAllLines(@"D:\output.txt", wordsDist);      // writing words into txt file to edit in setLineNumbers method
    }

    public void setLineNumbers(string sourcePath)                               // creating method for adding line numbers
    {
        string[] linesOutput = new string[wordsDist.Count()];                   // creating array that will contain line numbers
        string[] lines = System.IO.File.ReadAllLines(sourcePath);               // assigning source text by lines

        for (int j = 0; j < wordsDist.Count(); j++)                             // main cycle checking each word for presence in each line 
        {
            for (int i = 0; i < lines.Count(); i++)
            {
                if (Regex.IsMatch(lines[i].ToLower(), "\\b" + wordsDist[j] + "\\b"))   // using ToLower() here, because we can't use it in line 33
                {
                    linesOutput[j] += (i + 1).ToString() + ", ";                // adding line numbers according to word
                }

            }
        }

        for (int i = 0; i < wordsDist.Count(); i++)                             // connection of two relative arrays
        {
            wordsDist[i] += "_______________________________" + linesOutput[i];
            wordsDist[i] = wordsDist[i].Remove(wordsDist[i].Length - 2);        // removing last ',' char
        }

        System.IO.File.WriteAllLines(@"D:\output.txt", wordsDist);      // writing final output result into txt file

    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you tried profiling the code? \$\endgroup\$ – svick Nov 17 '13 at 12:38
  • \$\begingroup\$ Also, could you post a link to an example of the txt file? \$\endgroup\$ – svick Nov 17 '13 at 12:46
  • \$\begingroup\$ Hey, here is the text example pastebin.com/2p88v8EN I didn't profiled code before, i will try now, thanks! \$\endgroup\$ – nuclearpeace Nov 17 '13 at 12:55
2
\$\begingroup\$

I posted the basis of this answer to your question when you first asked it on StackOverflow.

The best answer is to remove both the Distinct() and the Regex and process everything by character.

class TextManipulations
{
    public string[] WordsDist;

    public void TextFormat(string sourcePath)
    {
        HashSet<string> Words = new HashSet<string>();
        foreach (string line in File.ReadLines(sourcePath))
        {
            int wordStart = 0;
            for (int i = 0; i < line.Length; i++)
            {
                char c = line[i];
                if (c == ' ')
                {
                    string word = line.Substring(wordStart, i - wordStart).Trim().ToLower();
                    Words.Add(word);
                    wordStart = i + 1;
                }
            }
            if (wordStart < line.Length)
            {
                string word = line.Substring(wordStart, line.Length - wordStart).Trim().ToLower();
                Words.Add(word);
            }
        }
        WordsDist = Words.OrderBy(word => word).ToArray();
        File.WriteAllLines("output.txt", WordsDist);
    }

    public void SetLineNumbers(string sourcePath)
    {
        Dictionary<string, List<int>> wordLineNumbers = WordsDist.ToDictionary(word => word, word => new List<int>());
        int lineNo = 0;
        foreach (string line in File.ReadLines(sourcePath))
        {
            lineNo++;
            int wordStart = 0;
            for (int i = 0; i < line.Length; i++)
            {
                char c = line[i];
                if (c == ' ')
                {
                    string word = line.Substring(wordStart, i - wordStart).Trim().ToLower();
                    wordLineNumbers[word].Add(lineNo);

                    wordStart = i + 1;
                }
            }
            if (wordStart < line.Length)
            {
                string word = line.Substring(wordStart, line.Length - wordStart).Trim().ToLower();
                wordLineNumbers[word].Add(lineNo);
            }
        }
        File.WriteAllLines("output.txt", wordLineNumbers.Select(kvp => string.Format("{0}, {1}", kvp.Key, string.Join(", ", kvp.Value))));
    }
}

However this changes the functionality slightly as it doesn't strip out punctuation and the like (and only splits on white spaces), but if you want to keep the exact same output then this will do the job:

class TextManipulations : ITextManipulations
{
    private const string AlphanumericWords = @"\b[\w']+\b";
    private static readonly Regex wordRegex = new Regex(AlphanumericWords, RegexOptions.Compiled);
    public string[] WordsDist;

    public void TextFormat(string sourcePath)
    {
        HashSet<string> Words = new HashSet<string>();

        foreach (string line in File.ReadLines(sourcePath))
        {
            foreach (Match wordMatch in wordRegex.Matches(line))
            {
                Words.Add(wordMatch.Value.Trim().ToLower());
            }
        }
        WordsDist = Words.OrderBy(word => word).ToArray();
        File.WriteAllLines("output.txt", WordsDist);
    }

    public void SetLineNumbers(string sourcePath)
    {
        Dictionary<string, List<int>> wordLineNumbers = WordsDist.ToDictionary(word => word, word => new List<int>());
        int lineNo = 0;
        foreach (string line in File.ReadLines(sourcePath))
        {
            lineNo++;
            foreach (string word in wordRegex.Matches(line).OfType<Match>().Select(wordMatch => wordMatch.Value.Trim().ToLower()).Distinct())
            {
                wordLineNumbers[word].Add(lineNo);
            }
        }
        File.WriteAllLines("output.txt", wordLineNumbers.Select(kvp => string.Format("{0}_______________________________{1}", kvp.Key, string.Join(", ", kvp.Value))));
    }
}

Some tests...While your Pastebin link is no longer available I created a suitable 172KB file with 4.2k unique words.

Performance of calling TextFormat followed by SetLineNumbers

Your code total runtime: 8689ms
Code by Peter Kiss total runtime: 440ms
My split only on white space code: 61ms
My code using a single Compiled Regex: 87ms

Additionally my code reads the file line-by-line and reuses the same memory rather than loading the entire file into memory. This means that for very large files (say 100 MB+) my code will continue to scale better due to not copying around of additional arrays all over the place.

Testing with much larger files this pattern continues, eg: 1446kb input file with 12100 unique words.

Your code total runtime: test not run (would take too long)
Code by Peter Kiss total runtime: 9079ms
My split only on white space code: 279ms
My code using a single Compiled Regex: 651ms

So with a larger file my 2nd set of code performs 13 times faster compared to 5 times faster with a 172KB file.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Rewritten code:

class TextManipulations
{
private const string AlphanumericWords = @"\b[\w']+\b";
public string[] WordsDist;

public void TextFormat(string sourcePath, string output)
{
    var textInput = File.ReadAllText(sourcePath).ToLower();
    var m = Regex.Matches(textInput, AlphanumericWords);
    var words = new SortedSet<string>();

    foreach (Match match in m)
    {
        words.Add(match.ToString());
    }

    WordsDist = words.ToArray();

    File.WriteAllLines(output, WordsDist);
}

public void SetLineNumbers(string sourcePath, string output)
{
    var lines = File.ReadAllLines(sourcePath).AsParallel().Select(x => x.ToLowerInvariant()).ToArray();

    var regExs = WordsDist.Select(word => new Regex("\\b" + word + "\\b")).ToArray();

    var wordsOut = new string[regExs.Length];

    Parallel.For(0, regExs.Length, j =>
        {
            var sb = new List<int>(15);
            var regEx = regExs[j];
            for (var i = 0; i < lines.Length; i++)
            {
                if (regEx.IsMatch(lines[i]))
                {
                    sb.Add(i + 1);
                }
            }

            wordsOut[j] = WordsDist[j] + "_______________________________" + string.Join(", ", sb);
        });

    File.WriteAllLines(output, wordsOut);
}

}

TextFormat

Using a SortedSet is better becouse we don't need additional Sort() or Distinct() calls becouse it will handle all these stuff by it's self.

SetLineNumbers

The main problem was is that the testing Regex was always created inside the second for loop instead of creating once and then using it in all the iterations. The parallel stuff isn't necessary but we can speed up the code a little bit with that.

Results

Your code was executed on my machine a little bit above 2 secs and my code is finishing around 0.25 secs.

Other things

Do not ever write comments at the line endings becouse they are really useless and annoying. I've added an additional parameter to each method which can be used to specify the output file. (But the code still isn't really reuseable or testable.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is awesome. Never tried sortedSet or AsParallel(), thanks! I will dig into your code \$\endgroup\$ – nuclearpeace Nov 17 '13 at 14:33
  • \$\begingroup\$ Why do you have wordsOut[j] += …? wordsOut[j] = … would be much clearer. Also, why are initializing the list to 15? Why exactly that number? \$\endgroup\$ – svick Nov 17 '13 at 14:46
  • \$\begingroup\$ One more thing: ToList() tends to be faster than ToArray() (because it can make one less copy). \$\endgroup\$ – svick Nov 17 '13 at 14:47
  • \$\begingroup\$ @svick: the += is a typo. I'm using 15 becouse in the result set most of the time the matching count is below 10 but there are significant number of result count more then 10 with a few match. Yes ToList() can be more effective but it doesn't matter in this case much. \$\endgroup\$ – Peter Kiss Nov 17 '13 at 16:31
  • \$\begingroup\$ This would be more efficient if you compile your regex \$\endgroup\$ – Jeff Vanzella Nov 19 '13 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.