OffsetExistenceIndex.cs

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

namespace GeoEngine
{
    public class OffsetExistenceIndex
    {
        public const int ChunkSize = sizeof(long) * 8; // Размер элемента буфера (количество бит в Int64)
        public const int AbsChunkSize = ChunkSize - 1;
        public static readonly int ChunkSizeCubeRoot = (int)Math.Ceiling(Math.Pow(ChunkSize, 1.0 / 3.0));

        public readonly Offset3 Size; // Размеры буфера
        public readonly Offset3 Zero; // Центр пространства

        public long[,,] Data;

        public OffsetExistenceIndex(int SizeX, int SizeY, int SizeZ)
        {
            int x = (int)Math.Ceiling((double)SizeX / (double)ChunkSizeCubeRoot);
            int y = (int)Math.Ceiling((double)SizeY / (double)ChunkSizeCubeRoot);
            int z = (int)Math.Ceiling((double)SizeZ / (double)ChunkSizeCubeRoot);

            if (x < 2) x = 2;
            if (y < 2) y = 2;
            if (z < 2) z = 2;

            Size = new Offset3(x, y, z);
            Zero = new Offset3(x / 2, y / 2, z / 2);
            Data = new long[x, y, z];

            Debug.Log(Size.ToString());
        }

        //

        public void Set(int x, int y, int z, bool bit)
        {
            Position posX = new Position(x);
            Position posY = new Position(y);
            Position posZ = new Position(z);

            long chunk = GetChunk(posX.index, posY.index, posZ.index);
            int offset = GetOffset(posX.offset, posY.offset, posZ.offset);

            if (bit)
                chunk |= 1L << offset;    // Заполняем бит
            else
                chunk &= ~(1L << offset); // Зануляем бит

            SetChunk(posX.index, posY.index, posZ.index, chunk);
        }

        public void Set(Offset3 offset, bool bit)
        {
            Set(offset.x, offset.y, offset.z, bit);
        }

        public bool Get(int x, int y, int z)
        {
            Position posX = new Position(x);
            Position posY = new Position(y);
            Position posZ = new Position(z);

            long chunk = GetChunk(posX.index, posY.index, posZ.index);
            int offset = GetOffset(posX.offset, posY.offset, posZ.offset);

            bool b = (chunk & (1L << offset)) != 0;
            return b;
        }

        public bool Get(Offset3 offset)
        {
            return Get(offset.x, offset.y, offset.z);
        }

        //

        private long GetChunk(int x, int y, int z)
        {
            x += Zero.x;
            y += Zero.y;
            z += Zero.z;

            if (x >= 0 &&
                y >= 0 && 
                z >= 0 && 
                x < Data.GetLength(0) && 
                y < Data.GetLength(1) && 
                z < Data.GetLength(2))
                return Data[x, y, z];
            else
                return 0;
        }

        private void SetChunk(int x, int y, int z, long chunk)
        {
            x += Zero.x;
            y += Zero.y;
            z += Zero.z;

            if (x >= 0 &&
                y >= 0 &&
                z >= 0 &&
                x < Data.GetLength(0) &&
                y < Data.GetLength(1) &&
                z < Data.GetLength(2))
                Data[x, y, z] = chunk;
        }

        private int GetOffset(int offsetX, int offsetY, int offsetZ)
        {
            return offsetX * ChunkSizeCubeRoot * ChunkSizeCubeRoot + offsetY * ChunkSizeCubeRoot + offsetZ;
        }

        struct Position
        {
            public int index;
            public int offset;

            public Position(int n)
            {
                offset = n % ChunkSizeCubeRoot;
                index = (n - offset) / ChunkSizeCubeRoot;

                if (n < 0)
                {
                    offset += ChunkSizeCubeRoot - 1;
                    --index;
                }
            }
        }

        //

        public int GetCount()
        {
            long count = 0;

            for (int x = 0; x < Data.GetLength(0); x++)
            {
                for (int y = 0; y < Data.GetLength(1); y++)
                {
                    for (int z = 0; z < Data.GetLength(2); z++)
                    {
                        long chunk = Data[x, y, z];

                        char[] ch = Convert.ToString(chunk, 2).ToCharArray();
                        foreach (char c in ch)
                        {
                            if (c == '1') count++;
                        }

                        /*int bits = 0;

                        if (chunk < 0) chunk = -chunk;

                        while (chunk > 0)
                        {
                            bits++;
                            count += chunk & 1L;
                            chunk >>= 1;
                        }

                        count += ChunkSize - bits - 1;*/
                    }
                }
            }

            return (int)count;
        }

        public void Clear()
        {
            Data = null;
            Data = new long[Size.x, Size.y, Size.z];
        }

        //

        public static void Test()
        {
            TestPosition();
            MainTest();
        }

        static void MainTest()
        {
            Dictionary<Offset3, int> Control = new Dictionary<Offset3, int>();
            Dictionary<Offset3, int> Control2 = new Dictionary<Offset3, int>();
            Dictionary<Offset3, int> Control3 = new Dictionary<Offset3, int>();
            Dictionary<Offset3, int> Control4 = new Dictionary<Offset3, int>();
            FastOffsetDictionary<Offset3, int> Concept = new FastOffsetDictionary<Offset3, int>(new Offset3(200, 200, 200));
            FastOffsetDictionary<Offset3, int> Concept2 = new FastOffsetDictionary<Offset3, int>(new Offset3(200, 200, 200));
            FastOffsetDictionary<Offset3, int> Concept3 = new FastOffsetDictionary<Offset3, int>(new Offset3(200, 200, 200));
            FastOffsetDictionary<Offset3, int> Concept4 = new FastOffsetDictionary<Offset3, int>(new Offset3(200, 200, 200));

            TimeMachine.Start("test_creation");

            for (int i = 0; i < 20000; i++)
            {
                int x = UnityEngine.Random.Range(-99, 99);
                int y = UnityEngine.Random.Range(-99, 99);
                int z = UnityEngine.Random.Range(-99, 99);
                Offset3 Key = new Offset3(x, y, z);

                if (i < 5000)
                {
                    TimeMachine.Start("fill_1");
                    if (!Control.ContainsKey(Key)) Control.Add(Key, i);
                    TimeMachine.Pause("fill_1");
                    TimeMachine.Start("fill_1_new");
                    if (!Concept.ContainsKey(Key)) Concept.Add(Key, i);
                    TimeMachine.Pause("fill_1_new");
                }
                if (i < 10000)
                {
                    TimeMachine.Start("fill_2");
                    if (!Control2.ContainsKey(Key)) Control2.Add(Key, i);
                    TimeMachine.Pause("fill_2");
                    TimeMachine.Start("fill_2_new");
                    if (!Concept2.ContainsKey(Key)) Concept2.Add(Key, i);
                    TimeMachine.Pause("fill_2_new");
                }
                if (i < 15000)
                {
                    TimeMachine.Start("fill_3");
                    if (!Control3.ContainsKey(Key)) Control3.Add(Key, i);
                    TimeMachine.Pause("fill_3");
                    TimeMachine.Start("fill_3_new");
                    if (!Concept3.ContainsKey(Key)) Concept3.Add(Key, i);
                    TimeMachine.Pause("fill_3_new");
                }

                TimeMachine.Start("fill_4");
                if (!Control4.ContainsKey(Key)) Control4.Add(Key, i);
                TimeMachine.Pause("fill_4");
                TimeMachine.Start("fill_4_new");
                if (!Concept4.ContainsKey(Key)) Concept4.Add(Key, i);
                TimeMachine.Pause("fill_4_new");
            }
            TimeMachine.Stop("test_creation");

            TimeMachine.Stop("fill_1");
            TimeMachine.Stop("fill_1_new");
            TimeMachine.Stop("fill_2");
            TimeMachine.Stop("fill_2_new");
            TimeMachine.Stop("fill_3");
            TimeMachine.Stop("fill_3_new");
            TimeMachine.Stop("fill_4");
            TimeMachine.Stop("fill_4_new");

            //

            // Датасеты в дефолтных словарях
            Dictionary<Offset3, int>[] A = new Dictionary<Offset3, int>[] { Control, Control2, Control3, Control4 };
            // Обертки дефолтных словарей с 1-битным 3D-индексом
            FastOffsetDictionary<Offset3, int>[] B = new FastOffsetDictionary<Offset3, int>[] { Concept, Concept2, Concept3, Concept4 };

            int control_count = 0;
            int concept_count = 0;

            for (int i = 0; i < A.Length; i++)
            {
                TimeMachine.Start("contains_" + i);
                foreach (KeyValuePair<Offset3, int> Pair in A[i])
                {
                    if (A[i].ContainsKey(Pair.Key)) control_count++;
                }
                TimeMachine.Stop("contains_" + i);

                TimeMachine.Start("contains_" + i + "_new");
                foreach (KeyValuePair<Offset3, int> Pair in A[i])
                {
                    if (B[i].ContainsKey(Pair.Key)) concept_count++;
                }
                TimeMachine.Stop("contains_" + i + "_new");
            }

            Debug.Log(control_count + " vs " + concept_count);
        }

        static void TestPosition()
        {
            Position pos;

            TimeMachine.Start("position_negative");

            for (int i = -100000; i < 0; i++)
            {
                pos = new Position(i);
            }

            TimeMachine.Stop("position_negative");

            TimeMachine.Start("position_positive");

            for (int i = 0; i < 100000; i++)
            {
                pos = new Position(i);
            }

            TimeMachine.Stop("position_positive");
        }

        static void FindAllSets(OffsetExistenceIndex OEX)
        {
            for (int x = 0; x < OEX.Data.GetLength(0); x++)
            {
                for (int y = 0; y < OEX.Data.GetLength(1); y++)
                {
                    for (int z = 0; z < OEX.Data.GetLength(2); z++)
                    {
                        if (OEX.Data[x, y, z] != 0)
                            Debug.Log(string.Format("FindAllSets: {0},{1},{2} - {3}", x, y, z, OEX.Data[x, y, z]));
                    }
                }
            }
        }
    }

    // Демка для похожести синтаксиса в тестах
    public class FastOffsetDictionary<TKey, TValue> where TKey : IOffset // Все Offset3 можно заменить на TKey и получится универсал
    {
        private Dictionary<TKey, TValue> Data;
        private OffsetExistenceIndex Index;

        public TValue this[TKey key]
        {
            get
            {
                return Data[key];
            }
            set
            {
                Data[key] = value;
            }
        }

        public int Count { get { return Data.Count; } }
        public int IndexCount { get { return Index.GetCount(); } }

        public FastOffsetDictionary(Offset3 size)
        {
            Data = new Dictionary<TKey, TValue>();
            Index = new OffsetExistenceIndex(size.x, size.y, size.z);
        }

        public bool ContainsKey(TKey key)
        {
            return Index.Get(key.AsOffset3());
        }

        public void Add(TKey key, TValue value)
        {
            Data.Add(key, value);
            Index.Set(key.AsOffset3(), true);
        }

        public bool Remove(TKey key)
        {
            if (Data.Remove(key))
            {
                Index.Set(key.AsOffset3(), false);
                return true;
            }
            return false;
        }

        public void Clear()
        {
            Data.Clear();
            Index.Clear();
        }

        public Dictionary<TKey, TValue> GetData()
        {
            return Data;
        }
    }
}