首页 > 代码库 > 【原创】一个支持极限大小的数组MaxArray,且节省内存

【原创】一个支持极限大小的数组MaxArray,且节省内存

    大家好,我写了一个支持极限大小的数组MaxArray,很有用的,希望大家喜欢~~

 

问:.net类库不是自带了一个吗,干嘛还要自己写一个?好在哪里?

答:数组可以在创建后立即访问范围内的任意索引位置,而不需要依次添加,可以跳跃添加,但它的缺点就是创建时立即分配全部内存,比如你连续新建几个int[] arr=new int[int.maxvalue]这样的极限大的数组,会遇到内存溢出异常。

 

问:要节省内存,可以用ArrayList或List<T>这些,干嘛非得自己写一个?

答:arraylist或者List<T>虽然节省内存,但是它们缺少数组的一个功能:初始化后立即可以随机存取访问任意索引位置,而只能从索引0开始一个一个添加元素

 

问:这个极限数组的独到之处和使用场景是怎样的呢?

答:我的这个极限数组就是结合这两种类的优点,既可以象数组一样创建后所有索引项立即可用,可以跳跃存取,又可以象arraylist和list<T>一样节省内存,没有实际使用过的索引位置并不实际分配内存,但这个索引确实存在,可以任意存取使用。

它的适用场合就和数组的适用场合是重合的--可惜性能不太好,存取速度大约是数组的5倍到6倍的样子,所以,被排挤到只适合一些极限大的数组的场合,代替数组。
这很有用,在一些别扭的业务场景,或者脑洞大开的奇葩算法中,有了这个可以让以前数组力不从心的设计方案也能实现。
或者你可以反过来想:有了这个东东,以前一些只停留在想象中的业务处理方式、软件的类架构、设计模式、算法,必须要用到数组的随机访问特点,但极限大的数组又做不到的,只好换种别扭的方式实现,现在好了,有了我写的这个极限数组,不用曲里拐弯的实现了,可以平推过去。是设计上、思路上的一个豁然开朗的重要东东。

我有许多原创的东东,以后会陆续发上来。太多人太多文章是属于“跟随、学习、使用"类型的,我这样的”创建“型的人很少,希望大家多多关注本博客。

 

以下是代码,类源代码、使用示例、性能测试代码都有:

 

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{

    class Program
    {

        static void Main(string[] args)
        {


            //---------以下是---功能展示区--------------------------------------------------------------

            MaxArray<int> arrInt = new MaxArray<int>(int.MaxValue);
            int i1 = arrInt[8];
            arrInt[8] = 133;
            int i2 = arrInt[8];

            //这是初始化时指定的大小,初始化时实际并未分配内存,是一个“不存在的索引”。
            //但是在这个范围内你都可以把它当作已分配内存的一样任意直接赋值。
            int count = arrInt.Count_Inited;

            //这个是实际赋值过的有意义的元素个数。
            int count_userd = arrInt.Count_RealUserd;


            arrInt.RemovValueAt(8);
            int i3 = arrInt[8];

            
            int count2 = arrInt.Count_Inited;

            //这里可以看到,经过前面RemovValueAt(8)操作后,实际有意义元素减少了一个,但初始化指定的元素个数并没有变化
            //在移除一个实际有意义的元素的时候,请使用RemovValueAt()方法,因为这样会同时维护count_userd值。
            int count_userd2 = arrInt.Count_RealUserd;




            MaxArray<Student> arrStudents = new MaxArray<Student>(int.MaxValue);
            Student stu1 = arrStudents[5];
            arrStudents[5] = new Student();
            Student stu2 = arrStudents[5];

            arrStudents.RemovValueAt(5);
            Student stu3 = arrStudents[5];



            //这是一个奇葩用法,int索引值和char索引值混合使用.
            //是的,你没有看错,这其实可以看做支持int值key或char值key的一个奇葩字典,可惜性能干不过正版字典。
            MaxArray<object> arrchar = new MaxArray<object>(char.MaxValue);
            object o1 =  arrchar[a];
            arrchar[a] = new object();
            object o2 = arrchar[a];

            object o3 = arrchar[76];
            arrchar[76] = new object();
            object o4 = arrchar[76];



            //--------以下是----性能测试区------------------------------------------------------------------


            System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
            stopwatch.Start();
            
            MaxArray<Student> arrStudents2 = new MaxArray<Student>(2000000);
            for(int idx=0;idx< 2000000; idx++)
            {
                arrStudents2[idx] = new Student();
            }
            stopwatch.Stop();
            string 极限数组的赋值耗时 = stopwatch.Elapsed.TotalSeconds.ToString();
            


            stopwatch.Restart();
            Student[] arrStudent3 = new Student[2000000];
            for (int idx = 0; idx < 2000000; idx++)
            {
                arrStudent3[idx] = new Student();
            }
            stopwatch.Stop();
            string 原生数组的赋值耗时 = stopwatch.Elapsed.TotalSeconds.ToString();



            stopwatch.Restart();
            Dictionary<int, Student> dicStudent = new Dictionary<int,Student>();
            for (int idx = 0; idx < 2000000; idx++)
            {
                dicStudent.Add(idx, new Student());
            }
            stopwatch.Stop();
            string 字典的赋值耗时 = stopwatch.Elapsed.TotalSeconds.ToString();

            


        }



        public class MaxArray<T>
        {
            //作者博客http://www.cnblogs.com/bkyguestwc/。2017年6月8日
            public int Count_Inited;
            public int Count_RealUserd;
            private int startidx;
            private int step;

            private int group0maxIdx;
            private int group1maxIdx;
            private int group2maxIdx;
            private int group3maxIdx;

            private MaxArray<T> Groups0;
            private MaxArray<T> Groups1;
            private MaxArray<T> Groups2;
            private MaxArray<T> Groups3;

            //只用在末级,存储最终对象值
            private T Objs0;
            private T Objs1;
            private T Objs2;
            private T Objs3;

            public MaxArray(int getlenthe)
            {
                Count_Inited = getlenthe;
                Count_RealUserd = 0;
                int initlengthe = getlenthe;

                if (initlengthe <= 4)
                {
                    initlengthe = 4;
                }
                else
                {
                    if (initlengthe <= 16)
                    {
                        initlengthe = 16;
                    }
                    else
                    {
                        if (initlengthe <= 64)
                        {
                            initlengthe = 64;
                        }
                        else
                        {
                            if (initlengthe <= 256)
                            {
                                initlengthe = 256;
                            }
                            else
                            {
                                if (initlengthe <= 1024)
                                {
                                    initlengthe = 1024;
                                }
                                else
                                {
                                    if (initlengthe <= 4096)
                                    {
                                        initlengthe = 4096;
                                    }
                                    else
                                    {
                                        if (initlengthe <= 16384)
                                        {
                                            initlengthe = 16384;
                                        }
                                        else
                                        {
                                            if (initlengthe <= 65536)
                                            {
                                                initlengthe = 65536;
                                            }
                                            else
                                            {
                                                if (initlengthe <= 262144)
                                                {
                                                    initlengthe = 262144;
                                                }
                                                else
                                                {
                                                    if (initlengthe <= 1048576)
                                                    {
                                                        initlengthe = 1048576;
                                                    }
                                                    else
                                                    {
                                                        if (initlengthe <= 4194304)
                                                        {
                                                            initlengthe = 4194304;
                                                        }
                                                        else
                                                        {
                                                            if (initlengthe <= 16777216)
                                                            {
                                                                initlengthe = 16777216;
                                                            }
                                                            else
                                                            {
                                                                if (initlengthe <= 67108864)
                                                                {
                                                                    initlengthe = 67108864;
                                                                }
                                                                else
                                                                {
                                                                    if (initlengthe <= 268435456)
                                                                    {
                                                                        initlengthe = 268435456;
                                                                    }
                                                                    else
                                                                    {
                                                                        if (initlengthe <= 1073741824)
                                                                        {
                                                                            initlengthe = 1073741824;
                                                                        }
                                                                        else
                                                                        {
                                                                            initlengthe = 2147483647;
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }

                if (initlengthe == 2147483647)
                {//这些就只能分两份了
                    startidx = 0;
                    step = 1073741824;
                    group0maxIdx = 1073741823;
                    group1maxIdx = 2147483647;
                    group2maxIdx = 0;
                    group3maxIdx = 0;

                    Groups0 = new MaxArray<T>(0, 1073741823);
                    Groups1 = new MaxArray<T>(1073741824, 2147483647);
                    Groups2 = null;
                    Groups3 = null;
                }
                else
                {//这之下的都是可以正常分四份的
                    startidx = 0;
                    step = initlengthe / 4;
                    group0maxIdx =step - 1;
                    group1maxIdx = group0maxIdx + step;
                    group2maxIdx = group1maxIdx + step;
                    group3maxIdx = group2maxIdx + step;

                }



                string mm = string.Empty;


            }

            private MaxArray(int getstartidx, int maxidx)
            {
                Count_Inited = 0;
                Count_RealUserd = 0;
                startidx = getstartidx;
                int lanth = maxidx - (startidx - 1);
                step = lanth / 4;
                group0maxIdx = startidx + step - 1;
                group1maxIdx = group0maxIdx + step;
                group2maxIdx = group1maxIdx + step;
                group3maxIdx = group2maxIdx + step;


            }

            public T this[int index]
            {
                get
                { //检查索引范围  
                    if (index < 0 || index >= Count_Inited)
                    {
                        throw new Exception("索引越界");
                    }
                    else
                    {
                        T needValue;
                        needValue = FindNeedValue(index);
                        return needValue;
                    }
                }
                set
                {//设置指定节点值
                    if (index < 0 || index >= Count_Inited)
                    {
                        throw new Exception("索引越界");
                    }
                    else
                    {
                        Count_RealUserd++;
                        SetNeedValue(index, value);
                    }
                }
            }

            public void RemovValueAt(int idx)
            {
                Count_RealUserd--;
                RemovValue(idx);
            }
            private void RemovValue(int idx)
            {
                if (step == 1)
                {//这就是末级,不用再往下级找了
                    if (idx == group0maxIdx)
                    {
                        Objs0 = default(T);
                    }
                    else
                    {
                        if (idx == group1maxIdx)
                        {
                            Objs1 = default(T);
                        }
                        else
                        {
                            if (idx == group2maxIdx)
                            {
                                Objs2 = default(T);
                            }
                            else
                            {
                                if (idx == group3maxIdx)
                                {
                                    Objs3 = default(T);
                                }
                                else
                                {
                                    throw new Exception("意外值");
                                }
                            }
                        }
                    }
                }
                else
                {//不是末级,要去下级找
                    if (idx <= group0maxIdx)
                    {//决定进入Group0
                        Groups0.RemovValue(idx);
                    }
                    else
                    {
                        if (idx <= group1maxIdx)
                        {//决定进入Group1
                            Groups1.RemovValue(idx);
                        }
                        else
                        {
                            if (idx <= group2maxIdx)
                            {//决定进入Group2
                                Groups2.RemovValue(idx);
                            }
                            else
                            {
                                if (idx <= group3maxIdx)
                                {//决定进入Group3
                                    Groups3.RemovValue(idx);
                                }
                                else
                                {
                                    throw new Exception("意外值");
                                }
                            }
                        }
                    }
                }

            }

            private void SetNeedValue(int idx, T getValue)
            {
                if (step == 1)
                {//这就是末级,不用再往下级找了
                    if (idx == group0maxIdx)
                    {
                        Objs0 = getValue;
                    }
                    else
                    {
                        if (idx == group1maxIdx)
                        {
                            Objs1 = getValue;
                        }
                        else
                        {
                            if (idx == group2maxIdx)
                            {
                                Objs2 = getValue;
                            }
                            else
                            {
                                if (idx == group3maxIdx)
                                {
                                    Objs3 = getValue;
                                }
                                else
                                {
                                    throw new Exception("意外值");
                                }
                            }
                        }
                    }
                }
                else
                {//不是末级,要去下级找
                    if (idx <= group0maxIdx)
                    {//决定进入Group0
                        if (Groups0 == null)
                        {
                            Groups0 = new MaxArray<T>(startidx, group0maxIdx);
                        }
                        Groups0.SetNeedValue(idx, getValue);
                    }
                    else
                    {
                        if (idx <= group1maxIdx)
                        {//决定进入Group1
                            if (Groups1 == null)
                            {
                                Groups1 = new MaxArray<T>(group0maxIdx + 1, group1maxIdx);
                            }
                            Groups1.SetNeedValue(idx, getValue);
                        }
                        else
                        {
                            if (idx <= group2maxIdx)
                            {//决定进入Group2
                                if (Groups2 == null)
                                {
                                    Groups2 = new MaxArray<T>(group1maxIdx + 1, group2maxIdx);
                                }
                                Groups2.SetNeedValue(idx, getValue);
                            }
                            else
                            {
                                if (idx <= group3maxIdx)
                                {//决定进入Group3
                                    if (Groups3 == null)
                                    {
                                        Groups3 = new MaxArray<T>(group2maxIdx + 1, group3maxIdx);
                                    }
                                    Groups3.SetNeedValue(idx, getValue);
                                }
                                else
                                {
                                    throw new Exception("意外值");
                                }
                            }
                        }
                    }
                }

            }

            private T FindNeedValue(int idx)
            {
                T needValue;
                needValue = default(T);

                if (step == 1)
                {//这就是末级,不用再往下级找了
                    if (idx == group0maxIdx)
                    {
                        needValue = Objs0;
                    }
                    else
                    {
                        if (idx == group1maxIdx)
                        {
                            needValue = Objs1;
                        }
                        else
                        {
                            if (idx == group2maxIdx)
                            {
                                needValue = Objs2;
                            }
                            else
                            {
                                if (idx == group3maxIdx)
                                {
                                    needValue = Objs3;
                                }
                                else
                                {
                                    throw new Exception("意外值");
                                }
                            }
                        }
                    }
                }
                else
                {//不是末级,要去下级找
                    if (idx <= group0maxIdx)
                    {//决定进入Group0
                        if (Groups0 == null)
                        {
                            needValue = default(T);
                        }
                        else
                        {
                            needValue = Groups0.FindNeedValue(idx);
                        }
                    }
                    else
                    {
                        if (idx <= group1maxIdx)
                        {//决定进入Group1
                            if (Groups1 == null)
                            {
                                needValue = default(T);
                            }
                            else
                            {
                                needValue = Groups1.FindNeedValue(idx);
                            }
                        }
                        else
                        {
                            if (idx <= group2maxIdx)
                            {//决定进入Group2
                                if (Groups2 == null)
                                {
                                    needValue = default(T);
                                }
                                else
                                {
                                    needValue = Groups2.FindNeedValue(idx);
                                }
                            }
                            else
                            {
                                if (idx <= group3maxIdx)
                                {//决定进入Group3
                                    if (Groups3 == null)
                                    {
                                        needValue = default(T);
                                    }
                                    else
                                    {
                                        needValue = Groups3.FindNeedValue(idx);
                                    }
                                }
                                else
                                {
                                    throw new Exception("意外值");
                                }
                            }
                        }
                    }
                }


                return needValue;
            }
        }



        public class Student
        {
            public string name;
            public int age;
        }





    }
}

 

【原创】一个支持极限大小的数组MaxArray,且节省内存