CODEWITHSUNDEEP
c#performancelistindexing
Shredder2500
Shredder2500

Reputation: 1085

Can I speed finding indexes of an array more than what I have?

I am keeping vertices in a list, I only want to add a vertices into the list if it does not already contain it. if it doesnt contain it I will add it to the list then add the index to a list called tris. However if the list does contain the vertices already it should find the index of where its located and then just add that index to the tris list. Here is the fastest way of doing this that I have figured out. is there any faster way?

Hashtable vertIndexes;
List<Vector3> verts;
List<int> tris;

foreach (var vert in vertsOutput)
{
    Vector3 p = point + vert;
    if(!vertIndexes.Contains(p))
    {
        vertIndexes.Add(p, verts.Count);
        tris.Add(verts.Count);
        verts.Add(p);
    }
    else
    {
        tris.Add((int)vertIndexes[p]);
    }
}

Upvotes: 0

Views: 162

Answers (2)

Erik Funkenbusch
Erik Funkenbusch

Reputation: 93424

There are many kinds of containers, and they all have different performance, resource, and utilization characteristics.

A List is not the fastest container for lookups. A dictionary or Hashset may be better. But it depends on how you need to use it.

If you need to look up the vertex by a key, then use a dictionary. If the vertex is itself the key then use a hashtable for that as well. Then you don't need the separate hashtable for indexes.

Do you actually need the count? If not, then just use a hashtable for the vertexes, if you need the count then use a dictionary keyed on the vertex with count. Dictionary<Vertex3,int>

Upvotes: 1

usr
usr

Reputation: 171178

At the moment you are performing two hashtable operations per items. You can save one:

Dictionary<Vector3, int> vertIndexes;
...

int index;
if(vertIndexes.TryGetValue(p, out index))
 //present at given index
else
 //not present

TryGetValue simultaneously tests for existence and returns the stored value.

You can probably go faster with a custom hash table. Dictionary has some overheads in it that are required for generality and that you don't need. For example, the modulus operator it uses is surprisingly expensive and unnecessary with a good hash code. This is beyond the scope of this answer, though.

Upvotes: 3

Related Questions