Compare adjacent list items

Question

I'm writing a duplicate file detector. To determine if two files are duplicates I calculate a CRC32 checksum. Since this can be an expensive operation, I only want to calculate checksums for files that have another file with matching size. I have sorted my list of files by size, and am looping through to compare each element to the ones above and below it. Unfortunately, there is an issue at the beginning and end since there will be no previous or next file, respectively. I can fix this using if statements, but it feels clunky. Here is my code:

    public void GetCRCs(List<DupInfo> dupInfos)
    {
        var crc = new Crc32();
        for (int i = 0; i < dupInfos.Count(); i++)
        {
            if (dupInfos[i].Size == dupInfos[i - 1].Size || dupInfos[i].Size == dupInfos[i + 1].Size)
            {
                dupInfos[i].CheckSum = crc.ComputeChecksum(File.ReadAllBytes(dupInfos[i].FullName));
            }
        }
    }

My question is:

1. How can I compare each entry to its neighbors without the out of bounds error?

2. Should I be using a loop for this, or is there a better LINQ or other function?

Note: I did not include the rest of my code to avoid clutter. If you want to see it, I can include it.

Answer 1

Compute the Crcs first:

// It is assumed that DupInfo.CheckSum is nullable
public void GetCRCs(List<DupInfo> dupInfos)
{
  dupInfos[0].CheckSum = null ;        
  for (int i = 1; i < dupInfos.Count(); i++)
    {
       dupInfos[i].CheckSum = null ;
       if (dupInfos[i].Size == dupInfos[i - 1].Size)
       {
         if (dupInfos[i-1].Checksum==null) dupInfos[i-1].CheckSum = crc.ComputeChecksum(File.ReadAllBytes(dupInfos[i-1].FullName));
         dupInfos[i].CheckSum = crc.ComputeChecksum(File.ReadAllBytes(dupInfos[i].FullName));
       }
    }
}

After having sorted your files by size and crc, identify duplicates:

public void GetDuplicates(List<DupInfo> dupInfos) 
{
  for (int i = dupInfos.Count();i>0 i++)
  { // loop is inverted to allow list items deletion
    if (dupInfos[i].Size     == dupInfos[i - 1].Size &&
        dupInfos[i].CheckSum != null &&
        dupInfos[i].CheckSum == dupInfos[i - 1].Checksum)
     { // i is duplicated with i-1
       ... // your code here
       ... // eventually, dupInfos.RemoveAt(i) ; 
     }
   }
}

Answer 2

I think the for loop should be : for (int i = 1; i < dupInfos.Count()-1; i++)

var grps= dupInfos.GroupBy(d=>d.Size);
grps.Where(g=>g.Count>1).ToList().ForEach(g=>
{
    ...
});

Answer 3

I have sorted my list of files by size, and am looping through to compare each element to the ones above and below it.

The next logical step is to actually group your files by size. Comparing consecutive files will not always be sufficient if you have more than two files of the same size. Instead, you will need to compare every file to every other same-sized file.

I suggest taking this approach

1. Use LINQ's .GroupBy to create a collection of files sizes. Then .Where to only keep the groups with more than one file.

2. Within those groups, calculate the CRC32 checksum and add it to a collection of known checksums. Compare with previously calculated checksums. If you need to know which files specifically are duplicates you could use a dictionary keyed by this checksum (you can achieve this with another GroupBy. Otherwise a simple list will suffice to detect any duplicates.

The code might look something like this:

var filesSetsWithPossibleDupes = files.GroupBy(f => f.Length)
                                      .Where(group => group.Count() > 1);

foreach (var grp in filesSetsWithPossibleDupes)
{
    var checksums = new List<CRC32CheckSum>(); //or whatever type
    foreach (var file in grp)
    {
        var currentCheckSum = crc.ComputeChecksum(file);
        if (checksums.Contains(currentCheckSum))
        {
            //Found a duplicate
        }
        else
        {
            checksums.Add(currentCheckSum);
        }
    }
}

Or if you need the specific objects that could be duplicates, the inner foreach loop might look like

var filesSetsWithPossibleDupes = files.GroupBy(f => f.FileSize)
                                      .Where(grp => grp.Count() > 1);

var masterDuplicateDict = new Dictionary<DupStats, IEnumerable<DupInfo>>();
//A dictionary keyed by the basic duplicate stats
//, and whose value is a collection of the possible duplicates

foreach (var grp in filesSetsWithPossibleDupes)
{
    var likelyDuplicates = grp.GroupBy(dup => dup.Checksum)
                              .Where(g => g.Count() > 1);
    //Same GroupBy logic, but applied to the checksum (instead of file size)

    foreach(var dupGrp in likelyDuplicates)
    {
        //Create the key for the dictionary (your code is likely different)
        var sample = dupGrp.First();
        var key = new DupStats() {FileSize = sample.FileSize, Checksum = sample.Checksum};
        masterDuplicateDict.Add(key, dupGrp);
    }
}

A demo of this idea.

Answer 4

Can you do a union between your two lists? If you have a list of filenames and do a union it should result in only a list of the overlapping files. I can write out an example if you want but this link should give you the general idea.

https://stackoverflow.com/a/13505715/1856992

Edit: Sorry for some reason I thought you were comparing file name not size.

So here is an actual answer for you.

using System;
using System.Collections.Generic;
using System.Linq;


public class ObjectWithSize
{
    public int Size {get; set;}
    public ObjectWithSize(int size)
    {
        Size = size;
    }
}

public class Program
{
    public static void Main()
    {
        Console.WriteLine("start");
        var list = new List<ObjectWithSize>();
        list.Add(new ObjectWithSize(12));
        list.Add(new ObjectWithSize(13));
        list.Add(new ObjectWithSize(14));
        list.Add(new ObjectWithSize(14));
        list.Add(new ObjectWithSize(18));
        list.Add(new ObjectWithSize(15));
        list.Add(new ObjectWithSize(15));
        var duplicates = list.GroupBy(x=>x.Size)
              .Where(g=>g.Count()>1);
        foreach (var dup in duplicates)
            foreach (var objWithSize in dup)
                Console.WriteLine(objWithSize.Size);
    }
}

This will print out

14
14
15
15

Here is a netFiddle for that. https://dotnetfiddle.net/0ub6Bs

Final note. I actually think your answer looks better and will run faster. This was just an implementation in Linq.