첨부 실행 코드는 나눔고딕코딩 폰트를 사용합니다.
유용한 소스 코드가 있으면 icodebroker@naver.com으로 보내주시면 감사합니다.
블로그 자료는 자유롭게 사용하세요.

■ 대용량 정렬 리스트 사용하기

------------------------------------------------------------------------------------------------------------------------


TestProject.zip


Program.cs

 

 

using System;

using System.Diagnostics;

 

namespace TestProject

{

    /// <summary>

    /// 프로그램

    /// </summary>

    class Program

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method

        ////////////////////////////////////////////////////////////////////////////////////////// Static

        //////////////////////////////////////////////////////////////////////////////// Private

 

        #region 프로그램 시작하기 - Main()

 

        /// <summary>

        /// 프로그램 시작하기

        /// </summary>

        private static void Main()

        {

            Random random = new Random(DateTime.Now.Millisecond);

 

            int itemCount = 10000000;

 

            Stopwatch stopwatch = new Stopwatch();

 

            WriteLog("BEGIN GET LIST");

 

            stopwatch.Start();

 

            SplitSortedList<TestData> list = TestData.GetList(itemCount);

 

            stopwatch.Stop();

 

            WriteLog("LIST COUNT : {0}", list.Count);

 

            WriteLog("END GET LIST : {0}", stopwatch.Elapsed.ToString());

 

            stopwatch.Reset();

 

            WriteLog("BEGIN FIND DATA");

 

            stopwatch.Start();

 

            TestData dataToFind = new TestData { ID = random.Next(1, itemCount) };

 

            TestData dataFound = list.GetItem(dataToFind);

 

            Console.WriteLine(dataFound != null ? dataFound.NAME : "DATA NOT FOUND");

 

            stopwatch.Stop();

 

            WriteLog("END FIND DATA : {0}", stopwatch.Elapsed.ToString());

 

            stopwatch.Reset();

        }

 

        #endregion

        #region 로그 쓰기 - WriteLog(format, parameterArray)

 

        /// <summary>

        /// 로그 쓰기

        /// </summary>

        /// <param name="format">포맷 문자열</param>

        /// <param name="parameterArray">매개 변수 배열</param>

        private static void WriteLog(string format, params object[] parameterArray)

        {

            string message;

 

            if(parameterArray.Length == 0)

            {

                message = format;

            }

            else

            {

                message = string.Format(format, parameterArray);

            }

 

            string log = string.Format("[{0}] {1}", DateTime.Now.ToString("HH:mm:ss"), message);

 

            Console.WriteLine(log);

        }

 

        #endregion

    }

}

 

 

TestData.cs

 

 

using System;

 

namespace TestProject

{

    /// <summary>

    /// 테스트 데이터

    /// </summary>

    public class TestData

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Property

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region ID - ID

 

        /// <summary>

        /// ID

        /// </summary>

        public int ID { get; set; }

 

        #endregion

        #region 성명 - NAME

 

        /// <summary>

        /// 성명

        /// </summary>

        public string NAME { get; set; }

 

        #endregion

        #region 점수 - SCORE

 

        /// <summary>

        /// 점수

        /// </summary>

        public int SCORE { get; set; }

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method

        ////////////////////////////////////////////////////////////////////////////////////////// Static

        //////////////////////////////////////////////////////////////////////////////// Public

 

        #region 리스트 구하기 - GetList(count)

 

        /// <summary>

        /// 리스트 구하기

        /// </summary>

        /// <param name="count">카운트</param>

        /// <returns>리스트</returns>

        public static SplitSortedList<TestData> GetList(int count)

        {

            Random random = new Random(DateTime.Now.Millisecond);

 

            SplitSortedList<TestData> list = new SplitSortedList<TestData>(new IDComparer());

 

            for(int i = 1; i <= count; i++)

            {

                TestData data = new TestData();

 

                data.ID    = i;

                data.NAME  = $"항목 {i}";

                data.SCORE = random.Next(50, 60);

 

                list.Add(data);

            }

 

            return list;

        }

 

        #endregion

    }

}

 

 

IDComparer.cs

 

 

using System.Collections.Generic;

 

namespace TestProject

{

    /// <summary>

    /// ID 비교자

    /// </summary>

    public class IDComparer : IComparer<TestData>

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region 비교하기 - Compare(x, y)

 

        /// <summary>

        /// 비교하기

        /// </summary>

        /// <param name="x">테스트 데이터 X</param>

        /// <param name="y">테스트 데이터 Y</param>

        /// <returns>비교 결과</returns>

        public int Compare(TestData x, TestData y)

        {

            if(x.ID == y.ID)

            {

                return 0;

            }

 

            if(x.ID < y.ID)

            {

                return -1;

            }

 

            return 1;

        }

 

        #endregion

    }

}

 

 

SplitSortedList.cs

 

 

using System;

using System.Collections;

using System.Collections.Generic;

using System.Data;

using System.Linq;

 

namespace TestProject

{

    /// <summary>

    /// 분리된 정렬 리스트

    /// </summary>

    /// <typeparam name="TItem">항목 타입</typeparam>

    public class SplitSortedList<TItem> : IEnumerable<TItem>

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Class

        ////////////////////////////////////////////////////////////////////////////////////////// Internal

 

        #region 수직 인덱스 노드 - VerticalIndexNode<TNode>

 

        /// <summary>

        /// 수직 인덱스 노드

        /// </summary>

        /// <typeparam name="TNode">노드 타입</typeparam>

        internal sealed class VerticalIndexNode<TNode>

        {

            //////////////////////////////////////////////////////////////////////////////////////////////////// Field

            ////////////////////////////////////////////////////////////////////////////////////////// Public

 

            #region Field

 

            /// <summary>

            /// 첫 번째 항목

            /// </summary>

            public TNode FirstItem;

 

            /// <summary>

            /// 리스트

            /// </summary>

            public List<TNode> List = new List<TNode>();

 

            /// <summary>

            /// 시작 인덱스

            /// </summary>

            public int BeginIndex;

 

            #endregion

        }

 

        #endregion

        #region 첫번째 항목 비교자 - FirstItemComparer

 

        /// <summary>

        /// 첫번째 항목 비교자

        /// </summary>

        internal sealed class FirstItemComparer : IComparer<VerticalIndexNode<TItem>>

        {

            //////////////////////////////////////////////////////////////////////////////////////////////////// Field

            ////////////////////////////////////////////////////////////////////////////////////////// Public

 

            #region Field

 

            /// <summary>

            /// 비교자

            /// </summary>

            public IComparer<TItem> Comparer = null;

 

            #endregion

 

            //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor

            ////////////////////////////////////////////////////////////////////////////////////////// Public

 

            #region 생성자 - FirstItemComparer(comparer)

 

            /// <summary>

            /// 생성자

            /// </summary>

            /// <param name="comparer">비교자</param>

            public FirstItemComparer(IComparer<TItem> comparer)

            {

                Comparer = comparer;

            }

 

            #endregion

 

            //////////////////////////////////////////////////////////////////////////////////////////////////// Method

            ////////////////////////////////////////////////////////////////////////////////////////// Public

 

            #region 비교하기 - Compare(x, y)

 

            /// <summary>

            /// 비교하기

            /// </summary>

            /// <param name="x">수직 인덱스 노드 X</param>

            /// <param name="y">수직 인덱스 노드 Y</param>

            /// <returns>비교 결과</returns>

            public int Compare(VerticalIndexNode<TItem> x, VerticalIndexNode<TItem> y)

            {

                return Comparer.Compare(x.FirstItem, y.FirstItem);

            }

 

            #endregion

        }

 

        #endregion

        #region 시작 인덱스 비교자 - BeginIndexComparer

 

        /// <summary>

        /// 시작 인덱스 비교자

        /// </summary>

        internal sealed class BeginIndexComparer : IComparer<VerticalIndexNode<TItem>>

        {

            //////////////////////////////////////////////////////////////////////////////////////////////////// Method

            ////////////////////////////////////////////////////////////////////////////////////////// Public

 

            #region 비교하기 - Compare(x, y)

 

            /// <summary>

            /// 비교하기

            /// </summary>

            /// <param name="x">수직 인덱스 노드 X</param>

            /// <param name="y">수직 인덱스 노드 Y</param>

            /// <returns>비교 결과</returns>

            public int Compare(VerticalIndexNode<TItem> x, VerticalIndexNode<TItem> y)

            {

                return x.BeginIndex - y.BeginIndex;

            }

 

            #endregion

        }

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////////////////////////// Field

        ////////////////////////////////////////////////////////////////////////////////////////// Private

 

        #region Field

 

        /// <summary>

        /// 항목 비교자

        /// </summary>

        private readonly IComparer<TItem> itemComparer;

 

        /// <summary>

        /// 첫번째 항목 비교자

        /// </summary>

        private readonly FirstItemComparer firstItemComparer;

 

        /// <summary>

        /// 깊이

        /// </summary>

        private readonly int depth;

 

        /// <summary>

        /// 수직 인덱스 노드 리스트

        /// </summary>

        private readonly List<VerticalIndexNode<TItem>> verticalIndexNodeList = new List<VerticalIndexNode<TItem>>();

 

        /// <summary>

        /// 시작 인덱스 비교자

        /// </summary>

        private readonly BeginIndexComparer beginIndexComparer = new BeginIndexComparer();

 

        /// <summary>

        /// 카운트

        /// </summary>

        private int count;

 

        /// <summary>

        /// 오염 여부

        /// </summary>

        private bool isDirty;

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////////////////////////// Property

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region 인덱서 - this[index]

 

        /// <summary>

        /// 인덱서

        /// </summary>

        /// <param name="index">인덱스</param>

        /// <returns>항목</returns>

        public TItem this[int index]

        {

            get

            {

                if(index < 0)

                {

                    throw new IndexOutOfRangeException("index");

                }

 

                RecalculateBeginIndex();

 

                int j = GetNodeIndex(default(TItem), index, null);

 

                int beginIndex = this.verticalIndexNodeList[j].BeginIndex;

 

                List<TItem> currentList = this.verticalIndexNodeList[j].List;

 

                return currentList[index - beginIndex];

            }

        }

 

        #endregion

        #region 카운트 - Count

 

        /// <summary>

        /// 카운트

        /// </summary>

        public int Count

        {

            get

            {

                return this.count;

            }

        }

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region 생성자 - SplitSortedList(itemComparer, depth)

 

        /// <summary>

        /// 생성자

        /// </summary>

        /// <param name="itemComparer">항목 비교자</param>

        /// <param name="depth">깊이</param>

        public SplitSortedList(IComparer<TItem> itemComparer, int depth = 1000)

        {

            if(itemComparer == null)

            {

                throw new ArgumentNullException();

            }

 

            this.itemComparer = itemComparer;

 

            this.firstItemComparer = new FirstItemComparer(this.itemComparer);

 

            this.depth = depth;

        }

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region 열거자 구하기 - GetEnumerator()

 

        /// <summary>

        /// 열거자 구하기

        /// </summary>

        /// <returns>열거자 인터페이스</returns>

        public IEnumerator<TItem> GetEnumerator()

        {

            return this.verticalIndexNodeList.SelectMany(verticalIndexNode => verticalIndexNode.List).GetEnumerator();

        }

 

        #endregion

        #region 열거자 구하기 - IEnumerable.GetEnumerator()

 

        /// <summary>

        /// 열거자 구하기

        /// </summary>

        /// <returns>열거자 인터페이스</returns>

        IEnumerator IEnumerable.GetEnumerator()

        {

            return GetEnumerator();

        }

 

        #endregion

 

        #region 추가하기 - Add(item)

 

        /// <summary>

        /// 추가하기

        /// </summary>

        /// <param name="item">항목</param>

        public void Add(TItem item)

        {

            if(this.verticalIndexNodeList.Count == 0)

            {

                this.verticalIndexNodeList.Add(new VerticalIndexNode<TItem>());

 

                this.verticalIndexNodeList[0].List.Add(item);

 

                this.verticalIndexNodeList[0].FirstItem = item;

            }

            else

            {

                AddInternally(item);

            }

 

            this.count++;

 

            this.isDirty = true;

        }

 

        #endregion

        #region 제거하기 - Remove(item)

 

        /// <summary>

        /// 제거하기

        /// </summary>

        /// <param name="item">항목</param>

        public void Remove(TItem item)

        {

            bool deletedNode = false;

 

            int nodeIndex = GetNodeIndex(item, -1, null);

 

            List<TItem> list = this.verticalIndexNodeList[nodeIndex].List;

 

            int removeIndex = FastBinarySearch(list, item, this.itemComparer);

 

            if(removeIndex >= 0)

            {

                list.RemoveAt(removeIndex);

 

                if(list.Count == 0)

                {

                    this.verticalIndexNodeList.RemoveAt(nodeIndex);

 

                    deletedNode = true;

                }

                else

                {

                    if(nodeIndex > 0 && (this.verticalIndexNodeList[nodeIndex - 1].List.Count + list.Count) < this.depth)

                    {

                        this.verticalIndexNodeList[nodeIndex - 1].List.AddRange(list);

 

                        list.Clear();

 

                        this.verticalIndexNodeList.RemoveAt(nodeIndex);

 

                        deletedNode = true;

                    }

                }

 

                if(deletedNode == false && removeIndex == 0)

                {

                    this.verticalIndexNodeList[nodeIndex].FirstItem = this.verticalIndexNodeList[nodeIndex].List[0];

                }

 

                this.count--;

 

                this.isDirty = true;

            }

            else

            {

                throw new DeletedRowInaccessibleException("삭제할 항목을 찾을 수 없습니다.");

            }

        }

 

        #endregion

        #region 모두 제거하기 - RemoveAll(predicate)

 

        /// <summary>

        /// 모두 제거하기

        /// </summary>

        /// <param name="predicate">판정자</param>

        public void RemoveAll(Predicate<TItem> predicate)

        {

            for(int i = Count - 1; i >= 0; i--)

            {

                TItem item = this[i];

 

                if(predicate(item))

                {

                    Remove(item);

 

                    this.isDirty = false;

                }

            }

 

            this.isDirty = true;

        }

 

        #endregion

        #region 지우기 - Clear()

 

        /// <summary>

        /// 지우기

        /// </summary>

        public void Clear()

        {

            foreach(VerticalIndexNode<TItem> node in this.verticalIndexNodeList)

            {

                node.List.Clear();

            }

 

            this.verticalIndexNodeList.Clear();

 

            this.verticalIndexNodeList.TrimExcess();

 

            this.count = 0;

 

            this.isDirty = true;

        }

 

        #endregion

        #region 이진 탐색하기 - BinarySearch(findItem, comparer)

 

        /// <summary>

        /// 이진 탐색하기

        /// </summary>

        /// <param name="findItem">찾을 항목</param>

        /// <param name="comparer">비교자</param>

        /// <returns>탐색 결과</returns>

        public int BinarySearch(TItem findItem, IComparer<TItem> comparer = null)

        {

            RecalculateBeginIndex();

 

            int nodeIndex = GetNodeIndex(findItem, -1, comparer ?? this.itemComparer);

 

            if(nodeIndex < 0)

            {

                return nodeIndex;

            }

 

            int beginIndex = this.verticalIndexNodeList[nodeIndex].BeginIndex;

 

            List<TItem> list = this.verticalIndexNodeList[nodeIndex].List;

 

            int index = FastBinarySearch(list, findItem, comparer ?? this.itemComparer);

 

            return (index >= 0) ? index + beginIndex : index - beginIndex;

        }

 

        #endregion

        #region 부분적으로 열거하기 - EnumeratePartially(findItem, comparer)

 

        /// <summary>

        /// 부분적으로 열거하기

        /// </summary>

        /// <param name="findItem">찾을 항목</param>

        /// <param name="comparer">비교자</param>

        /// <returns>열거 가능형</returns>

        public IEnumerable<TItem> EnumeratePartially(TItem findItem, IComparer<TItem> comparer = null)

        {

            IComparer<TItem> currentComparer = comparer ?? this.itemComparer;

 

            int index = BinarySearch(findItem, comparer);

 

            if(index >= 0)

            {

                for(; index > 0 && currentComparer.Compare(findItem, this[index-1]) == 0; index--);

 

                for(; index < Count && currentComparer.Compare(findItem, this[index]) == 0; index++)

                {

                    yield return this[index];

                }

            }

        }

 

        #endregion

        #region 항목 구하기 - GetItem(findItem, comparer)

 

        /// <summary>

        /// 항목 구하기

        /// </summary>

        /// <param name="findItem">찾을 항목</param>

        /// <param name="comparer">비교자</param>

        /// <returns>항목</returns>

        public TItem GetItem(TItem findItem, IComparer<TItem> comparer = null)

        {

            int index = BinarySearch(findItem, comparer ?? this.itemComparer);

 

            if(index >= 0)

            {

                return this[index];

            }

 

            return default(TItem);

        }

 

        #endregion

 

        ////////////////////////////////////////////////////////////////////////////////////////// Private

 

        #region 시작 인덱스 재계산하기 - RecalculateBeginIndex()

 

        /// <summary>

        /// 시작 인덱스 재계산하기

        /// </summary>

        private void RecalculateBeginIndex()

        {

            if(this.isDirty)

            {

                int beginIndex = 0;

 

                foreach(VerticalIndexNode<TItem> node in this.verticalIndexNodeList)

                {

                    node.BeginIndex = beginIndex;

 

                    beginIndex += node.List.Count;

                }

 

                this.isDirty = false;

            }

        }

 

        #endregion

        #region 노드 인덱스 구하기 - GetNodeIndex(item, itemIndex, comparer)

 

        /// <summary>

        /// 노드 인덱스 구하기

        /// </summary>

        /// <param name="item">항목</param>

        /// <param name="itemIndex">항목 인덱스</param>

        /// <param name="comparer">비교자</param>

        /// <returns>노드 인덱스</returns>

        private int GetNodeIndex(TItem item, int itemIndex, IComparer<TItem> comparer)

        {

            VerticalIndexNode<TItem> node = new VerticalIndexNode<TItem>

            {

                FirstItem  = item,

                BeginIndex = itemIndex

            };

 

            if(comparer != null)

            {

                this.firstItemComparer.Comparer = comparer;

            }

 

            int index = this.verticalIndexNodeList.BinarySearch

            (

                node,

                (itemIndex < 0) ? this.firstItemComparer : (IComparer<VerticalIndexNode<TItem>>)this.beginIndexComparer

            );

 

            if(comparer != null)

            {

                this.firstItemComparer.Comparer = this.itemComparer;

            }

 

            if(index < 0)

            {

                if(~index < this.verticalIndexNodeList.Count)

                {

                    if(~index <= 1)

                    {

                        return 0;

                    }

 

                    return ~index - 1;

                }

 

                return this.verticalIndexNodeList.Count - 1;

            }

 

            return index;

        }

 

        #endregion

        #region 추가하기 (내부용) - AddInternally(item)

 

        /// <summary>

        /// 추가하기 (내부용)

        /// </summary>

        /// <param name="item">항목</param>

        private void AddInternally(TItem item)

        {

            int index = GetNodeIndex(item, -1, null);

 

            List<TItem> currentList = this.verticalIndexNodeList[index].List;

 

            int position = FastBinarySearch(currentList, item, this.itemComparer);

 

            if(position < 0)

            {

                if(~position < currentList.Count)

                {

                    position = ~position;

                }

                else

                {

                    position = -1;

                }

            }

 

            if(currentList.Count < this.depth)

            {

                if(position == 0)

                {

                    this.verticalIndexNodeList[index].FirstItem = item;

 

                    currentList.Insert(position, item);

                }

                else if(position > 0)

                {

                    currentList.Insert(position, item);

                }

                else

                {

                    currentList.Add(item);

                }

 

                return;

            }

 

            int median = this.depth >> 1;

 

            if(position >= 0 && position <= median)

            {

                if(index == this.verticalIndexNodeList.Count - 1 || this.verticalIndexNodeList[index + 1].List.Count > median)

                {

                    this.verticalIndexNodeList.Insert(index + 1, new VerticalIndexNode<TItem>());

                }

 

                this.verticalIndexNodeList[index + 1].List.InsertRange(0, currentList.GetRange(median, currentList.Count - median));

 

                currentList.RemoveRange(median, currentList.Count - median);

 

                currentList.Insert(position, item);

 

                this.verticalIndexNodeList[index + 1].FirstItem = this.verticalIndexNodeList[index + 1].List[0];

 

                if(position == 0)

                {

                    this.verticalIndexNodeList[index].FirstItem = this.verticalIndexNodeList[index].List[0];

                }

            }

            else

            {

                if(index == this.verticalIndexNodeList.Count - 1 || this.verticalIndexNodeList[index + 1].List.Count > median)

                {

                    this.verticalIndexNodeList.Insert(index + 1, new VerticalIndexNode<TItem>());

                }

 

                if(position > 0)

                {

                    currentList.Insert(position, item);

                }

                else

                {

                    currentList.Add(item);

                }

 

                this.verticalIndexNodeList[index + 1].List.InsertRange

                (

                    0,

                    currentList.GetRange(median, currentList.Count - median)

                );

 

                currentList.RemoveRange(median, currentList.Count - median);

 

                this.verticalIndexNodeList[index + 1].FirstItem = this.verticalIndexNodeList[index + 1].List[0];

 

                if(position == 0)

                {

                    this.verticalIndexNodeList[index].FirstItem = this.verticalIndexNodeList[index].List[0];

                }

            }

        }

 

        #endregion

        #region 고속 이진 탐색하기 - FastBinarySearch(list, findItem, comparer)

 

        /// <summary>

        /// 고속 이진 탐색하기

        /// </summary>

        /// <param name="list">리스트</param>

        /// <param name="findItem">찾을 항목</param>

        /// <param name="comparer">비교자</param>

        /// <returns>처리 결과</returns>

        private int FastBinarySearch(List<TItem> list, TItem findItem, IComparer<TItem> comparer)

        {

            int index1 = 0;

            int index2 = list.Count - 1;

 

            while(index1 <= index2)

            {

                int index3 = index1 + ((index2 - index1) >> 1);

                

                int index4 = comparer.Compare(list[index3], findItem);

 

                if(index4 == 0)

                {

                    return index3;

                }

 

                if(index4 < 0)

                {

                    index1 = index3 + 1;

                }

                else

                {

                    index2 = index3 - 1;

                }

            }

 

            return ~index1;

        }

 

        #endregion

    }

}

 

------------------------------------------------------------------------------------------------------------------------

Posted by 사용자 icodebroker
TAG

댓글을 달아 주세요