How to remove duplicate lines from a large text file efficiently?

Question

I want to edit a text as each line exists once in it. Each lines contains constantly 10 characters. I am generally working on 5-6 million of lines. So the code i am using currently is consuming too much RAM.

My code:

File.WriteAllLines(targetpath, File.ReadAllLines(sourcepath).Distinct())

So how can I make it less RAM consumer and less time-consumer at the same time?

Answer 1

Taking into account how much memory a string will take in C#, and assuming 10 characters length for 6 million records we get:

• size in bytes ~= 20 + (length / 2 ) * 4;
• total size in bytes ~= (20 + ( 10 / 2 ) * 4 )* 6000000 = 240 000 000
• total size in Mb ~= 230

Now, 230 MB of space is not really a problem, even on x86 (32 bit system), so you can load all that data in memory. For this, I would use a HashSet class which is obviously, a hash set that will let you easily eliminate the duplicates, by using lookup before adding an element.

In terms of big-O notation for time complexity, the average performance of a lookup in a hash set is O(1), which is the best you can get. In total, you would use lookup N times, totalling to N * O(1) = O(N)

In terms of big-O notation for space complexity, you would have O(N) space used, meaning that you use up memory proportional to number of elements, which is also the best you can get.

I'm not sure it is even possible to use up less space if you implement the algorithm in C# and not rely on any external components (that would also use at least O(N))

That being said, you can optimize for some scenarios by reading your file sequentially, line by line, see here. This would give a better result if you have lots of duplicates, but worst case scenario when all the lines are distinct would consume the same amount of memory.

On a final note, if you look how Distinct method is implemented, you will see it also uses an implementation of hash table, although it's not the same class, but the performance is still roughly the same, check out this question for more details.

Answer 2

As ironstone13 corrected me, HashSet is OK, but does store the data. Then this works fine too:

        string[] arr = File.ReadAllLines("file.txt");
        HashSet<string> hashes = new HashSet<string>();

        for (int i = 0; i < arr.Length; i++)
        {
            if (!hashes.Add(arr[i])) arr[i] = null;
        }

        File.WriteAllLines("file2.txt", arr.Where(x => x != null));

This implementation was motivated by memory performance and hash conflicts. The main idea was to keep just hashes, of course it would have to get back to file to get the line it sees as hash conflict/duplicit, to detect which one it is. (that part is not implemented).

class Program
{
    static string[] arr;
    static Dictionary<int, int>[] hashes = new Dictionary<int, int>[1]
    { new Dictionary<int, int>() }
    ;
    static int[] file_indexes = {-1};


    static void AddHash(int hash, int index)
    {
        for (int h = 0; h < hashes.Length; h++)
        {
            Dictionary<int, int> dict = hashes[h];
            if (!dict.ContainsKey(hash))
            {
                dict[hash] = index;
                return;
            }
        }
        hashes = hashes.Union(new[] {new Dictionary<int, int>() {{hash, index}}}).ToArray();
        file_indexes = Enumerable.Range(0, hashes.Length).Select(x => -1).ToArray();
    }

    static int UpdateFileIndexes(int hash)
    {
        int updates = 0;
        for (int h = 0; h < hashes.Length; h++)
        {
            int index;
            if (hashes[h].TryGetValue(hash, out index))
            {
                file_indexes[h] = index;
                updates++;
            }
            else
            {
                file_indexes[h] = -1;
            }
        }
        return updates;
    }

    static bool IsDuplicate(int index)
    {
        string str1 = arr[index];
        for (int h = 0; h < hashes.Length; h++)
        {
            int i = file_indexes[h];
            if (i == -1 || index == i) continue;
            string str0 = arr[i];
            if (str0 == null) continue;
            if (string.CompareOrdinal(str0, str1) == 0) return true;
        }
        return false;
    }


    static void Main(string[] args)
    {
        arr = File.ReadAllLines("file.txt");

        for (int i = 0; i < arr.Length; i++)
        {
            int hash = arr[i].GetHashCode();

            if (UpdateFileIndexes(hash) == 0) AddHash(hash, i);
            else if (IsDuplicate(i)) arr[i] = null;
            else AddHash(hash, i);
        }

        File.WriteAllLines("file2.txt", arr.Where(x => x != null));



        Console.WriteLine("DONE");
        Console.ReadKey();
    }
}

Answer 3

Before you write your data, if your data is in a list or dictionary, you could run LINQ query and use group by to group all like keys. Then for each write to the output file.

Your question is a little vague as well. Are you creating a next text file every time and do you have to store the data in text? There are better formats to use such as XML and json