Array
- Array는 고정된 수의 요소를 관리하기 좋은 자료구조임.
- initialize 될 때, 값 타입은
default value, 참조 타입은null이 됨.
Collections
- 연관있는 오브젝트를 그룹지어 관리하고 싶은 경우, array와 collection 중에 방식을 고를 수 있음.
ArrayList
- ArrayList는필요에 따라 사이즈가 가변적으로 변하는 자료구조임.
- C#에서는
ArrayList대신List<Object>를 권장함.- ArrayList에서는 값타입의 경우에도 박싱이 일어나기 때문.
const int _COUNT = 10000000;
var current = Environment.TickCount;
List<int> list = new();
for (int i = 0; i < _COUNT; i++)
{
list.Add(i);
}
Console.WriteLine($"{Environment.TickCount - current} milliseconds");
current = Environment.TickCount;
ArrayList arrayList = new();
for (int i = 0; i < _COUNT; i++)
{
arrayList.Add(i);
}
Console.WriteLine($"{Environment.TickCount - current} milliseconds");
// output
// 71 milliseconds
// 772 milliseconds
- List를 참조 타입을 저장하게 만들면 값 타입을 이용할 때 보다 훨씬 느려짐. (70 밀리초 -> 700 밀리초 이상)
Generic
- Collection이 딱 하나의 데이터타입만을 다루는 경우 사용.
- 타입이 강제되기 때문에 타입에 대한 안정성이 보장됨.
- IList, IEnumerable의 구현 클래스는 foreach를 사용할 수 있음.
- sort를 사용하기 위해서 제네릭 타입은 IComparable
을 구현해야함. - 구현하지 않은 경우,
Unhandled exception이 발생함.
- 구현하지 않은 경우,
List<Fruit> fruit = new List<Fruit>();
for (int i = 0; i < 1000; i++)
{
fruit.Add(new Fruit(1000 - i));
}
Console.WriteLine(fruit[0].Count);
fruit.Sort();
Console.WriteLine(fruit[0].Count);
public class Fruit : IComparable<Fruit>
{
private int _count;
public int Count
{
get => _count;
}
public Fruit(int count)
{
_count = count;
}
public int CompareTo(Fruit? fruit)
{
if (_count == fruit?.Count)
return 0;
if (_count > fruit?.Count)
return 1;
return -1;
}
}
// output
// 1000
// 1
Generic Type
- Generic
- Class, Struct, Record는 복수개의 type parameter를 통해 정의될 수 있음.
CustomList<string> list = new CustomList<string>();
list.Add("element 1");
list.Add("element 2");
list.Add("element 3");
list.Add("element 4");
list.Add("element 5");
List<int> l = new List<int>();
public class CustomList<T>
{
private const int _INITIAL_ALLOCATION_SIZE = 4;
private T[] list;
private int _size;
public CustomList()
{
list = new T[0];
_size = 0;
}
public CustomList(int size)
{
list = new T[size];
_size = 0;
}
public int Count
{
get => _size;
}
/// indexer
public T this[int index]
{
get => list[index];
set => list[index] = value;
}
public void Add(T input)
{
if (_size >= list.Length)
{
var isFirstAllocation = list.Length == 0;
var newSize = isFirstAllocation ? _INITIAL_ALLOCATION_SIZE : list.Length * 2;
AllocateMemory(newSize);
}
list[_size] = input;
_size++;
}
private void AllocateMemory(int size)
{
Array.Resize<T>(ref list, size);
}
}
List
- List는 인덱스로 접근할 수 있는 목록 자료구조임. 검색, 정렬 기능을 제공함.
- Type Parameter를 받아서 list에서 다룰 자료형을 정의함.
- 중복 값을 허용하며, 참조 타입의 경우 null을 허용함.
성능
- 참조 형식의 경우 ArrayList와 List의 동작은 동일함.
- List는 요소에 대해 불필요한 boxing이 일어나지 않음. 그래서 값 타입의 경우, ArrayList와 성능 차이가 발생함.
용량
- list는 아이템이 추가되었을 경우, Capacity(resizing없이 아이템을 추가할 수 있는 용량)가 부족하면 그의 배가 되는 용량을 확보함.
- ex. 가장 처음 할당된 용량이 10인 경우, 다음 resizing 시에는 20을 확보함.
- 그러나 아이템이 Remove 되었다고 확보한 Capacity가 줄어들지는 않음.
List<int> list = new();
var currentCapacity = list.Capacity;
Console.WriteLine(currentCapacity);
for (int i = 0; i < 100; i++)
{
list.Add(i);
if (list.Capacity > currentCapacity)
{
currentCapacity = list.Capacity;
Console.WriteLine(currentCapacity);
}
}
// output
// 0
// 4
// 8
// 16
// 32
// 64
// 128
Dictionary
- Dictionary는 키와 값을 이용해 Collection을 표현하는 자료구조임.
- Type Parameter로 키와 값의 타입을 지정할 수 있음.
- 키 집합에서 값 집합으로 매핑을 제공하며, 키가 유일함을 보장함.
- 중복 키 Add를 시도할 시에는
ArgumentException이 발생함.
- 중복 키 Add를 시도할 시에는
- 키는 null일 수 없으나, 값은 참조 타입의 경우, null일 수 있음.
const int _COUNT = 1000000;
var current = Environment.TickCount;
Dictionary<string, int> emptyDict = new();
for (int i = 0; i < _COUNT; i++)
{
emptyDict.Add($"KEY{i}", i);
}
Console.WriteLine($"Zero Capacity: {Environment.TickCount - current} milliseconds");
current = Environment.TickCount;
Dictionary<string, int> dict = new(_COUNT);
for (int i = 0; i < _COUNT; i++)
{
dict.Add($"KEY{i}", i);
}
Console.WriteLine($"Const Capacity: {Environment.TickCount - current} milliseconds");
// output
// Zero Capacity: 237 milliseconds
// Const Capacity: 200 milliseconds
- 미리 capacity를 지정해주는 편이 조금 더 빠름.
