Member Avatar for Smith5646

I am trying to find an efficient way to build a cross reference in C# and I am at a loss so I thought I would ask for ideas. I have tried using a list view, concatenating the source and associated values into a single dimension array, and several other things. My problem is the list of source values is dynamic and can be quite large and everything I have tried has had performance issues.

The only requirements I have are
1) It is must be a memory option because I don't have a database in this program.
2) I can't add a source value multiple times.
3) I need to be able to retrieve the associated value later in the program.

So I don't disclose the true nature of my program, I am going to provide a ficticiuos example.
As I read a file, I need to process each letter by first seeing if it is already in the list and if not, add it and the next available number.
"this is sample data" cross references to t=1, h=2, i=3, s=4, a=5, m=6, p=7, l=8, e=9, d=10
Now I also need to be able to search for a letter such as p to retrieve the cross reference value of 7.

I will disclose that the source values are 3 dimensions coordinates (x, y, z) and there can easily be 200K+ values (many of which are duplicates) so sorting and retrieving values is not as simple as the example makes it look.

Maybe the nature of what I am trying to do will always have performance issues but I am hoping someone comes up with something that I don't know about (I'm not a C# newbie but there still are a lot of thing I don't know about) or a different way of doing it so it doesn't have performance issues.

Edited by Smith5646
  • 3 Contributors
  • 2 Replies
  • 307 Views
  • 23 Hours Discussion Span
  • Latest Post Latest Post by tinstaafl

Dani AI

Generated

pointed you in the right direction and correctly expanded on the idea. For a memory-only, fast lookup where duplicates are common and you need an integer id per unique 3D point, a hash-based map is the simplest, most performant approach in practice. Use a value-type key (an immutable struct) that implements correct equality and hash-code logic, and a Dictionary-like map from that key to the assigned integer. Lookup + insert with a hash map is expected O(1), and with sensible sizing it handles 200K+ unique entries easily.

A minimal, robust pattern:

  • Make the coordinate an immutable struct and implement IEquatable<T> + GetHashCode (avoid mutable structs).
  • Pre-size the dictionary with an estimated unique count to avoid repeated resizing.
  • Use TryGetValue (or the equivalent single-call pattern) so you do not do two lookups when adding a new key.
  • Assign ids incrementally: if key not present, assign nextId++ and add.

Example implementation pattern:

struct Coordinate : IEquatable<Coordinate>
{
    public readonly int X, Y, Z;
    public Coordinate(int x,int y,int z){ X=x; Y=y; Z=z; }
    public bool Equals(Coordinate other) => X==other.X && Y==other.Y && Z==other.Z;
    public override bool Equals(object obj) => obj is Coordinate c && Equals(c);
    public override int GetHashCode()
    {
        unchecked { int h = 17; h = h*31 + X; h = h*31 + Y; h = h*31 + Z; return h; }
    }
}

// usage: TryGetValue, assign nextId if missing

Extra tips and cautions: if coordinates are floating-point, canonicalize them first (quantize or use bitwise representation) so hashing and equality are deterministic. If you need ordering later, keep the map for id lookup and maintain a separate sorted index only when required (sorting every insert is costly). For multi-threaded ingestion use ConcurrentDictionary or partition the input and merge maps. If memory becomes tight, consider packing X/Y/Z into a single integer key (when ranges allow) or using a compact open-addressing table; those are more advanced but save overhead per entry. Finally, measure with a profiler and tune initial capacity before optimizing further.

Recommended Answers

All 2 Replies

Member Avatar for Reverend Jim

How about a dictionary? If you're unfamiliar with dictionaries (also called associative arrays), a dictionary is a hash table of key-value pairs. Keys and values may be just about any type. In your fictitious example the key would be a char or string and the value would be an integer.

Edited by Reverend Jim
Member Avatar for tinstaafl

Along with what Reverend Jim is saying, since you real data is a more complex type, create a class to represent that data, it could be called Coordinates,and your dictionary would be Dictionary<string,Coordinates> If you need them sorted you can use a SortedDictionary<string,Coordinates>. The links go to the MSDN document page for each.

Edited by tinstaafl
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.