GList

GList 활용법

GLib에는 GList, GSList, GPtrArray, GArray 데이터 집합 컨테이너 형식이 있습니다.

과거에 이 방식은 저장해야 할 데이터가 있는 모든 경우에 한해 GList를 활용하는 일반 방식이었지만, 이젠 별로 권할 바가 못됩니다. 대부분의 경우 GPtrArray를 대신 사용하는게 좋습니다. 적은 메모리를 차지하고(동일한 리스트 자료구조의 1/3에서 절반수준), 우월한 캐시 지역성을 확보하며, 모든 일반적 상황에서 동일한 또는 적은 알고리즘 복잡도를 보입니다. GList가 더 적절한 전형적인 유일한 경우는, 배열에서는 임의 색인 위치에 데이터를 삽입하려면 많은 노력을 들여야 하는데 반해 정렬 데이터를 취급할 경우일 뿐입니다.

연결 리스트를 사용한다면 표준 CS 복잡도 해석 기법을 활용하여 처리 복잡도를 낮게 유지하도록 만전을 기하십시오. g_list_nth() 함수 또는 g_list_nth_data()함수를 사용하는 어떤 동작의 경우는 거의 확실히 제대로 된 게 아닙니다. 예를 들어 GList를 순회한다면, 색인 값을 증가하기 보다, 연결 포인터를 활용하여 구현해야합니다:

GList *some_list, *l;

for (l = some_list; l != NULL; l = l->next)
  {
    gpointer element_data = l->data;

    /* Do something with @element_data. */
  }

색인 값 증가 방식을 활용하면 성능이 훨씬 더 떨어지는 결과를 초개합니다(O(N)이 아니라 O(N^2)임):

GList *some_list;
guint i;

/* This code is inefficient and should not be used in production. */
for (i = 0; i < g_list_length (some_list); i++)
  {
    gpointer element_data = g_list_nth_data (some_list, i);

    /* Do something with @element_data. */
  }

리스트를 순차적으로 살펴보는(O(N)) g_list_length() 함수 및 g_list_nth_data() 함수를 실행하면 성능상 불이익을 가져옵니다.

GPtrArray를 구현체의 동작상 복잡도는 처음(올바른) GList 구현제와 동일하지만, 캐시 지역성을 개선하며, 메모리를 덜 소모하여 더 많은 구성 항목을 저장할 때 성능상 우위를 점합니다:

GPtrArray *some_array;
guint i;

for (i = 0; i < some_array->len; i++)
  {
    gpointer element_data = some_array->pdata[i];

    /* Do something with @element_data. */
  }