5
\$\begingroup\$

I have a dictionary with about 4.2 millions of lines, each line contains a word (+some trash data I don't need) or whitespace. I need to convert this into a dictionary of anagrams (words that can be created from another words by changing positions of letters).

So far I came up with this solution:

class Program
{
    static void Main(string[] args)
    {
        List<wordModel> listAnagram = new List<wordModel>();
        string path = "D:\\words1.txt";
        string outputPath = "D:\\anagrams.txt";

        long count = 0;
        long total = 4302072;

        List<char> wordChars = new List<char>();
        StringBuilder sb = new StringBuilder();
        wordModel anagram = null;

        using (FileStream fs = File.Open(path, FileMode.Open, FileAccess.Read, FileShare.ReadWrite))
        using (BufferedStream bs = new BufferedStream(fs))
        using (StreamReader sr = new StreamReader(bs))
        {
            string line;
            while ((line = sr.ReadLine()) != null)
            {
                if (string.IsNullOrEmpty(line.Trim())) continue;
                string word = line.Split('|')[0].Trim();

                Console.SetCursorPosition(0, 0);
                Console.Write($"{++count}/{total}");

                wordChars.Clear();
                foreach (char c in word) { wordChars.Add(c); }
                wordChars.Sort();

                sb.Clear();
                foreach (char c in wordChars)
                {
                    sb.Append(c);
                }

                string wordLetters = sb.ToString();

                anagram = listAnagram.FirstOrDefault(x => x.length == wordLetters.Length && x.letters.Equals(wordLetters));
                if (anagram == null)
                {
                    listAnagram.Add(new wordModel()
                    {
                        letters = wordLetters,
                        listAnagram = new List<string>() { word },
                        length = wordLetters.Length
                    });
                }
                else
                {
                    if (!anagram.listAnagram.Any(x => x.Equals(word)))
                    {
                        anagram.listAnagram.Add(word);
                    }
                }
            }
        }

        Console.WriteLine("\n\nDone reading...");
        listAnagram.OrderBy(x => x.listAnagram.Count);

        using (FileStream fs = File.OpenWrite(outputPath))
        using (BufferedStream bs = new BufferedStream(fs))
        using (StreamWriter sr = new StreamWriter(bs))
        {
            total = listAnagram.Count;
            count = 0;
            foreach (wordModel word in listAnagram)
            {
                sr.WriteLine($"({word.listAnagram.Count}) {string.Join(", ", word.listAnagram)}");

                Console.SetCursorPosition(5, 0);
                Console.Write($"{++count}/{total}");
            }
        }

        Console.WriteLine("\nDone");
        Console.ReadKey();
    }

    public class wordModel
    {
        public int length { get; set; }
        public string letters { get; set; }
        public List<string> listAnagram { get; set; }
    }
}

Performance-wise it's pretty slow (worked through ~300k lines in 10 minutes, slows down later, worked through 2.2M lines in 8 hours). What can I do to make it run faster?

Small example of data I'm working with:

лань | сущ одуш ед жен им | 8831
  лани | сущ одуш ед жен род | 8832
  лани | сущ одуш ед жен дат | 8833
  лань | сущ одуш ед жен вин | 8834
  ланью | сущ одуш ед жен тв | 8835
  лани | сущ одуш ед жен пр | 8836
лани | сущ одуш мн им | 1430139
  ланей | сущ одуш мн род | 1430140
  ланям | сущ одуш мн дат | 1430141
  ланей | сущ одуш мн вин | 1430142
  ланями | сущ одуш мн тв | 1430143
  ланях | сущ одуш мн пр | 1430144

лаосец | сущ одуш ед муж им | 1212979
  лаосца | сущ одуш ед муж род | 1212980
  лаосцу | сущ одуш ед муж дат | 1212981
  лаосца | сущ одуш ед муж вин | 1212982
  лаосцем | сущ одуш ед муж тв | 1212983
  лаосце | сущ одуш ед муж пр | 1212984
лаосцы | сущ одуш мн им | 1305804
  лаосцев | сущ одуш мн род | 1305805
  лаосцам | сущ одуш мн дат | 1305806
  лаосцев | сущ одуш мн вин | 1305807
  лаосцами | сущ одуш мн тв | 1305808
  лаосцах | сущ одуш мн пр | 1305809

лаоска | сущ одуш ед жен им | 150572
  лаоски | сущ одуш ед жен род | 345790
  лаоске | сущ одуш ед жен дат | 345791
  лаоску | сущ одуш ед жен вин | 345792
  лаоскою | сущ одуш ед жен тв | 345795
  лаоской | сущ одуш ед жен тв | 345793
  лаоске | сущ одуш ед жен пр | 345794
лаоски | сущ одуш мн им | 1430145
  лаосок | сущ одуш мн род | 1430146
  лаоскам | сущ одуш мн дат | 1430147
  лаосок | сущ одуш мн вин | 1430148
  лаосками | сущ одуш мн тв | 1430149
  лаосках | сущ одуш мн пр | 1430150

лаосский | прл ед муж им | 107469
  лаосского | прл ед муж род | 498587
  лаосскому | прл ед муж дат | 498588
  лаосского | прл ед муж вин одуш | 498592
  лаосский | прл ед муж вин неод | 498589
  лаосским | прл ед муж тв | 498590
  лаосском | прл ед муж пр | 498591
лаосская | прл ед жен им | 684497
  лаосской | прл ед жен род | 684498
  лаосской | прл ед жен дат | 684499
  лаосскую | прл ед жен вин | 684500
  лаосскою | прл ед жен тв | 684503
  лаосской | прл ед жен тв | 684501
  лаосской | прл ед жен пр | 684502
лаосское | прл ед ср им | 866230
  лаосского | прл ед ср род | 866231
  лаосскому | прл ед ср дат | 866232
  лаосское | прл ед ср вин | 866233
  лаосским | прл ед ср тв | 866234
  лаосском | прл ед ср пр | 866235
лаосские | прл мн им | 1083295
  лаосских | прл мн род | 1083296
  лаосским | прл мн дат | 1083297
  лаосские | прл мн вин неод | 1083298
  лаосских | прл мн вин одуш | 1083301
  лаосскими | прл мн тв | 1083299
  лаосских | прл мн пр | 1083300

Solved: Thanks to paparazzo for idea with dictionaries. Here is my final version, it works much faster (completed in ~1.5 minutes).

class Program
{
    static void Main(string[] args)
    {
        Dictionary<int, Dictionary<string, List<string>>> dicAnagram = new Dictionary<int, Dictionary<string, List<string>>>();

        string path = "D:\\words1.txt";
        string outputPath = "D:\\anagrams.txt";

        long count = 0;
        long total = 4302072;

        using (FileStream fs = File.Open(path, FileMode.Open, FileAccess.Read, FileShare.ReadWrite))
        using (BufferedStream bs = new BufferedStream(fs))
        using (StreamReader sr = new StreamReader(bs))
        {
            string word;
            while ((word = sr.ReadLine()) != null)
            {
                if (string.IsNullOrEmpty(word.Trim())) continue;
                word = word.Split('|')[0].Trim();

                Console.SetCursorPosition(0, 0);
                Console.Write($"{++count}/{total}");

                byte[] wordContent = Encoding.Default.GetBytes(word);
                Array.Sort(wordContent);
                string key = System.Text.Encoding.Default.GetString(wordContent);

                if (!dicAnagram.ContainsKey(key.Length)) { dicAnagram.Add(key.Length, new Dictionary<string, List<string>>()); }

                Dictionary<string, List<string>> dicByLength = dicAnagram[key.Length];

                if (!dicByLength.ContainsKey(key)) { dicByLength.Add(key, new List<string>()); }
                if (!dicByLength[key].Any(x => x.Equals(word)))
                {
                    dicByLength[key].Add(word);
                }
            }
        }

        Console.WriteLine("\n\nDone reading...");

        using (FileStream fs = File.OpenWrite(outputPath))
        using (BufferedStream bs = new BufferedStream(fs))
        using (StreamWriter sr = new StreamWriter(bs))
        {
            foreach (Dictionary<string, List<string>> dic in dicAnagram.Values)
            {
                total = dic.Values.Count;
                count = 0;
                foreach (List<string> words in dic.Values)
                {
                    sr.WriteLine($"({words.Count}) {string.Join(", ", words)}");

                    Console.SetCursorPosition(0, 5);
                    Console.Write($"{++count}/{total}");
                }
            }
        }

        Console.WriteLine("\nDone");
        Console.ReadKey();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Could you add a couple of lines of sample data so that we can better visualize what you are dealing with? \$\endgroup\$ – t3chb0t Jun 19 '18 at 7:59
  • \$\begingroup\$ You are not writing to a dictionary. Don't write to console every line. \$\endgroup\$ – paparazzo Jun 19 '18 at 10:31
2
\$\begingroup\$

A big problem is you are not writing to Dictionary. You are storing in a List.

List<wordModel> listAnagram = new List<wordModel>();

This is going to be slow - O(n). No reason to search on Length.

anagram = listAnagram.FirstOrDefault(x => x.length == wordLetters.Length && x.letters.Equals(wordLetters));

Below will be be O(1).

Dictionary<string, List<string>> DicAnagram = new Dictionary<string, List<string>>(); 

List<string> words = DicAnagram[wordLetters];

Don't write to the console every line.

Console.SetCursorPosition(0, 0);
Console.Write($"{++count}/{total}");

Write out like every 1000 lines.

If this has several '|' then you would read char by char to stop at the first.

string word = line.Split('|')[0].Trim();
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1, but I'm one of those people who objects to HashTables being assumed O(1); however, string hashes are one thing that a lot of work has gone into, so hopefully it will perform as such. \$\endgroup\$ – VisualMelon Jun 19 '18 at 14:05

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.