title: Most efficient method to store 3D-indexed coordinate data pair in a dynamic, variable-sized 2D data structure?
body: <p>Here's an interesting data structure conundrum that perhaps you all can help me with, for context I am writing C#.</p>
  
  <h2>Context/Constraints:</h2>
  
  <p>I'm using a library (the new Unity ECS preview package, specifically) that allows me to store data in a very compact/efficient/native fashion for lightning-fast access and manipulation with no garbage collection. For some time it supported storing data in <code>FixedArray</code>s:</p>
  
  <pre><code>ComponentType.FixedArray&lt;T&gt;(int fixedCapacity) //pseudo-code
  </code></pre>
  
  <p>The API does not allow for any sort of managed data to be stored in these arrays, for performance and safety reasons, which means they must all be linear (no nested arrays or multiple dimensions) and the data elements themselves must be extremely simple (primitives or directly serializable structs, no fancy LinkedLists or references to other data structures). <strong>I cannot use a <code>HashTable</code> or <code>Dictionary</code> or any other similar data high-level data structure to solve this problem</strong>, I must use the provided data structure!</p>
  
  <h2>Problem:</h2>
  
  <p>I am trying to store a basic "Entity" object in the array which has an associated 3D point integer coordinate. I want to access the structure with this coordinate in-hand and retrieve/modify/delete my object from said coordinate. So it was a simple problem of accessing a linear indexed, fixed-width array using 3D coordinates, made possible using a hashing function.</p>
  
  <pre><code>//Pseudo-Code, this is not the actual code itself.
  //In actuality the Fixed Arrays are associated with Entities in an ECS system.
  
  var myStructure = new ComponentType.FixedArray&lt;Entity&gt;(512);//define array
  struct DataPair {
    Entity entity;//the element we're storing
    Vector3 threeDIntegerCoordinate;//from 1x1x1 to 8x8x8
  }
  
  //...
  int lookupFunction(Vector3 coordinate) {...} //converts 3D coord to 2D linear index
  
  DataPair exampleDataPair = new DataPair(...);
  //Data WAS stored like this:
  myStructure[lookupFunction(exampleDataPair.threeDIntegerCoordinate)] = exampleDataPair.entity;
  //Extremely fast access/lookup time due to using coordinate as index value.
  </code></pre>
  
  <p>Basically, I generated a variable amount (1 to 512, one 8x8x8 cube) Entities and store them by index into the <code>FixedArray</code> using a translation function that correlates a linear index value with every single 3D point coordinate. Lookup in a fixed array for a coordinate value was extremely fast, as simple as accessing an index.</p>
  
  <p><strong>However</strong>!</p>
  
  <p>The package has been updated and they replaced the <code>FixedArray</code> with a new <code>DynamicBuffer</code> data structure, which is now variable-width. The same constraints apply on what data can be stored, but now, if the cube of Entities is sparse (not entirely full) then it does not need to reserve space for that non-existent Entity reference in the structure. This will drastically cut down on my memory usage considering most cubes of Entities are not entirely full, and I'm storing literally millions of these buffers in memory at a time. The buffer elements are indexed by integer. It is possible to use multiple <code>DynamicBuffer</code>s at once (which means we could store the coordinates alongside the elements in two parallel buffers if necessary).</p>
  
  <pre><code>//New data structure provided. Variable-width! Also indexed linearly.
  var myStructure = new ComponentType.DynamicBuffer&lt;Entity&gt;();
  //Is very similar to C# List or ArrayList in Java, for example, contains functions:
  myStructure.Add(T element);
  myStructure.AddRange(...);
  myStructure.Length();
  myStructure.resizeUninitialized(int capacity);
  myStructure.Clear();
  </code></pre>
  
  <p><strong><em>In essence,</em></strong> what is the most efficient way to store these variable number of elements in a dynamic, dimensionless data structure (similar to a List) while maintaining 3D coordinate-based indexing, without using complex nested data structures to do so? My system is more performance-bound by the lookup/access time than it is by memory space.</p>
  
  <h2>Possible Solutions:</h2>
  
  <p>The naive solution is just to make all the <code>DynamicBuffer</code>s length equal to the max number of elements I would ever want to store (512 Entity volume), simulating <code>FixedArray</code>s. This would require minimal changes to my codebase, and would allow me to access them by-coordinate using my current translation function, but would not take advantage of the space-saving features of the dynamic data structure. It would look like this:</p>
  
  <pre><code>//Naive Solution:
  myStructure.resizeUninitialized(512); //resize buffer to 512 elements
  //DynamicBuffer is now indexed identically to FixedArray
  Entity elementToRetrieve = myStructure[exampleDataPair.threeDIntegerCoordinate];
  </code></pre>
  
  <p>My projected solution is to use two <em>parallel</em> <code>DynamicBuffer</code>s: one with all the Entities, the other with all the 3D points. Then when I want to find an Entity by coordinate, I lookup the 3D point in the coordinate buffer, and use the index of that element to find the appropriate Entity in the primary buffer.</p>
  
  <pre><code>//Possible better solution:
  myStructure1 = new ComponentType.DynamicBuffer&lt;Entity&gt;();
  myStructure2 = new ComponentType.DynamicBuffer&lt;Vector3&gt;();
  //to access an element:
  Entity elementToRetrieve = myStructure1[myStructure2.Find(exampleDataPair.threeDIntegerCoordinate)];
  //I would have to create this theoretical Find function.
  </code></pre>
  
  <p>Cons of this solution: </p>
  
  <ul>
  <li>Requires searching which means it would probably also require sorting.</li>
  <li>Sorting would need to be performed every time the structure is significantly modified, which is going to add a LARGE amount of computational overhead.</li>
  <li>Would need to write my own search/sort algorithms on top of an already extremely complicated data structure, which is not designed to be searched/sorted (it is possibly not stored linearly in memory).</li>
  <li>Locality of reference? It is very important that processor caching/speculative execution is preserved for high-performance.</li>
  </ul>
  
  <hr>
  
  <p>How can I find a happy medium between the naive solution and a complex solution involving searching/sorting? Are there any theoretical data structures or algorithms to solve this problem that I'm just completely missing? Basically I need to efficiently use a List like a Map.</p>
  
  <p>Sorry if this is a really long question, but I wanted to get this right, this is my first ever post here on StackExchange. Please be gentle! Thanks for all your help!</p>