Checking for duplicate materials

Question

This is a follow up question of Importing different type of files into Lists. Where the original lists are acquired.

In this script I am processing the obtained lists, and comparing them with each other to determine whether or not a used material has duplicate functions. This using their most commonly known traits, which are: Shader name, Color property and a texture property

I have the feeling my script is far from optimal, and currently takes roughly 120 seconds to compare 1200 materials. Making the rough iteration time per material 0.10 Where 200 of them are unique.

In the future this script will be expanded to process more different details besides the color/name/texture as well, so advice on how to to keep the process more 'open for change' is appreciated as well.

public void InitShaderSorting()
{
    //wipe data so it won't duplicate if button is pressed again
    unique = new List<Material>();
    broken = new List<Material>();
    duplicate = new List<Material>();
    dupof = new List<Material>();

    for (int i = 1; i < TotalMaterial; i++)
    {
        //Filter broken shaders out first so they can never be a unique one
        if (allMat[i].shader.name == "Hidden/InternalErrorShader")
            broken.Add(allMat[i]);
        //If no unique material has been assigned to compare with, assign one first
        else if (unique.Count == 0)
            unique.Add(allMat[i]);
        //If it aint broken, and there is a unique one. Go and compare the shader properties
        else
            CompareShader(allMat[i], allMat[i].shader.name, allMat[i].HasProperty("_Color"), allMat[i].HasProperty("_MainTex"));
    }
}

/// <param name="sn">Shader Name</param>
/// <param name="hc">Has Color Property</param>
/// <param name="ht">Has Texture Property</param>
void CompareShader(Material mat, string sn, bool hc, bool ht)
{
    bool finished = false;

    for (int i = 0; i < unique.Count; i++)
    {
        //Check if shader names are identical, if not continue as it can't be a duplicate
        if (sn != unique[i].shader.name)
        {
            if (i == unique.Count - 1)
            {
                finished = true;
                break;
            }
            else continue;
        }

        //Check if this material even uses a color
        if (hc)
        {
            //If the color is a match and there is no texture to compare, mark as duplicate
            if (unique[i].color == mat.color && !ht)
            {
                duplicate.Add(mat);
                dupof.Add(unique[i]);
                break;
            }
            else
            {
                if (i == unique.Count - 1)
                {
                    finished = true;
                    break;
                }
                else continue;
            }
        }

        if (ht)
        {
            //If the texture is a match, mark as duplicate
            if (unique[i].mainTexture == mat.mainTexture)
            {
                duplicate.Add(mat);
                dupof.Add(unique[i]);
                break;
            }
        }

        if (i == unique.Count - 1) finished = true;
    }

    //If we reached the end without a match, then this material is unique.
    if (finished) unique.Add(mat);
}

Answer 1

Correctness

At first, I'm afraid your code doesn't find all duplicates: If the compared materials don't use a texture or a color, they won't be marked as duplicates. In your code, if (hc) checks if the material has a color. If not, it is jumped over. If the other material has no color either, this could still be a duplicate.

Performance

The performance of your code is \$O(n^2)\$: For each additional item in allMat, the unique collection will be iterated one time. As this collection grows, this will take longer and longer. This can be certainly improved:

What you actually want to do, is "group" your Texture objects by equality. The groups with size == 1 will be your unique textures, the groups with size > 1 will contain your duplicates.

We can do this very easily using LINQ. All we need to do is implement a custom comparer, that knows how to compare two Texture instances:

public class MaterialComparer : IEqualityComparer<Material> 
{
    public bool Equals(Material x, Material y)
    {
        if (ReferenceEquals(x, y)) return true;

        if (x.shader.name != y.shader.name) return false;

        var xHasColor = x.HasProperty("_Color");
        var yHasColor = y.HasProperty("_Color");

        if (xHasColor != yHasColor) return false;
        if (xHasColor && x.color != y.color) return false;

        var xHasTexture = x.HasProperty("_MainTex");
        var yHasTexture = y.HasProperty("_MainTex");

        if (xHasTexture != yHasTexture) return false;
        if (xHasTexture && x.mainTexture != y.mainTexture) return false;

        return true;
    }

    public int GetHashCode(Material mat)
    {
        unchecked
        {
            var hasColor = mat.HasProperty("_Color");
            var hasTexture = mat.HasProperty("_MainTex");

            var hashCode = mat.shader.name.GetHashCode();
            hashCode = (hashCode * 397) ^ (hasTexture ? mat.mainTexture.GetHashCode() : 0);
            hashCode = (hashCode * 397) ^ (hasColor ? mat.color.GetHashCode() : 0);

            return hashCode;
        }
    }
}

The important thing here is to get GetHashCode right: This method is supposed to return two integers that MUST be equal when the compared objects are equal.

We can use it like that:

var groups = allMat.GroupBy(m => m, new MaterialComparer())
                .GroupBy(g => g.Count() == 1)
                .ToArray();

var unique = (groups.SingleOrDefault(g => g.Key) ?? Enumerable.Empty<IEnumerable<Material>>())
    .SelectMany(m => m).ToArray();

var duplicates = (groups.SingleOrDefault(g => !g.Key) ?? Enumerable.Empty<IEnumerable<Material>>())
    .SelectMany(m => m).ToArray();

I put this in a Unit Test to measure the performance for 20,000 random materials:

[TestMethod]
public void TestMaterials()
{
    var random = new Random();
    IEnumerable<Material> allMat = from i in Enumerable.Range(0, 20000)
                                let shader = random.Next(100)
                                let color = random.Next(50)
                                let texture = random.Next(50)
                                select new Material(shader.ToString(),
                                                    color == 0 ? null : color.ToString(),
                                                    texture == 0 ? null : texture.ToString());

    var comparator = new YourImplementation(allMat.ToArray());

    var stopwatch = Stopwatch.StartNew();

    comparator.InitShaderSorting();

    Console.WriteLine(stopwatch.Elapsed);
    stopwatch.Restart();

    var groups = allMat.GroupBy(m => m, new MaterialComparer())
                    .GroupBy(g => g.Count() == 1)
                    .ToArray();

    var unique = (groups.SingleOrDefault(g => g.Key) ?? Enumerable.Empty<IEnumerable<Material>>())
        .SelectMany(m => m).ToArray();

    var duplicates = (groups.SingleOrDefault(g => !g.Key) ?? Enumerable.Empty<IEnumerable<Material>>())
        .SelectMany(m => m).ToArray();

    Console.WriteLine(stopwatch.Elapsed);
}

Result:

00:00:14.0328998  // your custom implementation
00:00:00.0712459  // LINQ

Answer 2

Naming

• if you need xml documentation for explaining what a input parameter should be, then you name the parameter poorly.

• variables, fields or parameter names should not be shortened. Shortening these names removes readability.

General

• You really should consider to use braces {} for single if statements to make your code less errorprone.

• instead of creating new instances to "wipe data" you can call Clear() method on the list.

CompareShader

Instead of using the CompareShader() method, you should add a implementation of the IEqualityComparer<T> interface to use your shaders with a dictionary, because a dictionary is the right tool for this job.