GLibで連結リスト(リスト構造)にデータを追加する方向とその時間について

先頭からデータを逆順に追加すると処理が少ない?

GTK+をはじめとして広く利用されているライブラリのGLibにはリスト構造(自己参照構造体)のデータ型が標準で用意されていて

単方向(手前の要素をたどれない): GSList
双方向(手前にも後ろにもたどれる): GList

の2種類がある。いずれもデータを新しく追加する際には

先頭に追加する「_prepend()」系関数
末尾に追加する「_append()」系関数

など*1を使用するのだが
http://web.archive.org/web/20070113170119/www.gnome.gr.jp/docs/glib-2.8.x-refs/glib/glib-Singly-Linked-Lists.html#g-slist-append
を見ると、(リスト構造の性質により)後者の「_append()」系関数ではリストの終端を捜すためにリスト全体をたどる必要があるということなので、代わりに「_prepend()」系関数を使用して先頭から逆順にデータを入れた場合と比べて処理時間がどれだけ異なるのかを試してみた。

処理時間の計測について

http://web.archive.org/web/20070328022443/www.gnome.gr.jp/docs/glib-2.8.x-refs/glib/glib-Timers.html
のGTimer型を使用することにより、ストップウォッチ感覚で開始の位置と終了の位置をそれぞれ指定することで簡単に間の処理時間を得られる。

g_timer_new(): タイマー生成と同時に計測開始
g_timer_stop(): 計測停止
g_timer_elapsed(): 経過時間(double型)を取得
g_timer_destroy(): GTimerの解放

コード例

下の例では1,000個の整数を単方向リスト(GSList)に入れる処理を行い、その処理時間を最後に表示している。
[任意]ファイル名: slist_bench.c

#include <stdlib.h>
#include <glib.h>

/*
 * リスト構造へデータを追加するのにかかる時間を
 * 先頭に追加するのと末尾に追加するのとでそれぞれ測定する
 *
 * 先頭に追加するバージョン:
 * gcc -DPREPEND -Wall -Wextra slist_bench.c -o slist_bench_prepend $(pkg-config --cflags --libs glib-2.0)
 * 末尾に追加するバージョン:
 * gcc -DAPPEND -Wall -Wextra slist_bench.c -o slist_bench_append $(pkg-config --cflags --libs glib-2.0)
 * それぞれ-DVERBOSEを付けると各データを表示する
 * gcc -DVERBOSE -DPREPEND -Wall -Wextra slist_bench.c -o slist_bench_prepend_verbose $(pkg-config --cflags --libs glib-2.0)
 * gcc -DVERBOSE -DAPPEND -Wall -Wextra slist_bench.c -o slist_bench_append_verbose $(pkg-config --cflags --libs glib-2.0)
 */

#ifdef PREPEND
# ifdef APPEND
#  error "PREPENDとAPPENDの両方を定義することはできません"
# endif
#else
# ifndef APPEND
#  error "PREPENDとAPPENDのいずれかを定義する必要があります"
# endif
#endif

#define CNT 1000  /* データの数(かつ内容) */

#ifdef VERBOSE
void
display_data (gpointer data)
{
  g_print ("%d\n", GPOINTER_TO_INT (data));
}
#endif

int
main ()
{
  gint i;
  GSList *slist = NULL;  /* 空のリストに初期化する */
  /* 開始 */
  GTimer *t = g_timer_new ();  /* タイマー生成と同時に計測開始 */
#ifdef PREPEND
  /* 先頭に追加する場合・データは逆順に入れる */
  for (i = CNT - 1; i > -1; i--)
    slist = g_slist_prepend (slist, GINT_TO_POINTER (i));
#else
# ifdef APPEND
  /* 末尾に追加する場合 */
  for (i = 0; i < CNT; i++)
    slist = g_slist_append (slist, GINT_TO_POINTER (i));
# endif
#endif
  /* 停止 */
  /* 停止後の再開はg_timer_continue()、最初から開始し直すにはg_timer_start() */
  g_timer_stop (t);
#ifdef VERBOSE
  /* 内容を表示 */
  g_slist_foreach (slist, (GFunc) display_data, NULL);
#endif
  /* 計測した経過時間を表示 */
  g_print ("elapsed time: %.5f\n", g_timer_elapsed (t, NULL));  /* double型 */
  /* 後始末 */
  g_slist_free (slist);
  g_timer_destroy (t);
  return EXIT_SUCCESS;
}

コンパイルのコマンド行はコメントに書いている。下は詳細出力を行うようにした実行ファイルの実行例。

$ ./slist_bench_append_verbose
0
1
(中略)
998
999
elapsed time: 0.00232
$ ./slist_bench_prepend_verbose
0
1
(中略)
998
999
elapsed time: 0.00019

この例ではfor文の中を書き換えることでデータを逆順に入れることができているが、データを入れるときに順番を逆転できなくてもリスト側を逆順にするg_slist_reverse()を呼ぶことにより順番を戻すことができる。
下の例では本来の順番でデータをリストに格納した後、その(逆並びの)リストを逆順にしている。
[任意]ファイル名: slist_bench2.c

#include <stdlib.h>
#include <glib.h>

/*
 * リスト構造へデータを追加するのにかかる時間を
 * 先頭に追加するのと末尾に追加するのとでそれぞれ測定する
 *
 * 先頭に追加するバージョン:
 * gcc -DPREPEND -Wall -Wextra slist_bench2.c -o slist_bench2_prepend $(pkg-config --cflags --libs glib-2.0)
 * 末尾に追加するバージョン:
 * gcc -DAPPEND -Wall -Wextra slist_bench2.c -o slist_bench2_append $(pkg-config --cflags --libs glib-2.0)
 * それぞれ-DVERBOSEを付けると各データを表示する
 * gcc -DVERBOSE -DPREPEND -Wall -Wextra slist_bench2.c -o slist_bench2_prepend_verbose $(pkg-config --cflags --libs glib-2.0)
 * gcc -DVERBOSE -DAPPEND -Wall -Wextra slist_bench2.c -o slist_bench2_append_verbose $(pkg-config --cflags --libs glib-2.0)
 */

#ifdef PREPEND
# ifdef APPEND
#  error "PREPENDとAPPENDの両方を定義することはできません"
# endif
#else
# ifndef APPEND
#  error "PREPENDとAPPENDのいずれかを定義する必要があります"
# endif
#endif

#define CNT 1000  /* データの数(かつ内容) */

#ifdef VERBOSE
void
display_data (gpointer data)
{
  g_print ("%d\n", GPOINTER_TO_INT (data));
}
#endif

int
main ()
{
  gint i;
  GSList *slist = NULL;  /* 空のリストに初期化する */
  /* 開始 */
  GTimer *t = g_timer_new ();  /* タイマー生成と同時に計測開始 */
#ifdef PREPEND
  /* 先頭に追加する場合 */
  for (i = 0; i < CNT; i++)  /* 本来の順番で入れるものとする */
    slist = g_slist_prepend (slist, GINT_TO_POINTER (i));
  /* 「逆順の逆順」にして方向を戻す */
  slist = g_slist_reverse (slist);
#else
# ifdef APPEND
  /* 末尾に追加する場合 */
  for (i = 0; i < CNT; i++)
    slist = g_slist_append (slist, GINT_TO_POINTER (i));
# endif
#endif
  /* 停止 */
  g_timer_stop (t);
#ifdef VERBOSE
  /* 内容を表示 */
  g_slist_foreach (slist, (GFunc) display_data, NULL);
#endif
  /* 計測した経過時間を表示 */
  g_print ("elapsed time: %.5f\n", g_timer_elapsed (t, NULL));  /* double型 */
  /* 後始末 */
  g_slist_free (slist);
  g_timer_destroy (t);
  return EXIT_SUCCESS;
}

結果の処理時間については最初のコード(逆の順番で格納した場合)のときとほとんど差がなかった*2ため、具体的な出力は省略する。もちろん詳細に値を出力したときに出てくるものは同じ。
結果についての注意点として、リストの長さを今回1000としたが、これよりも長さの桁数を多くしていくと末尾に追加する形ではかなり遅くなるため、「データは先頭に追加する形が望ましい」ということは間違いないのだが、十分に短い場合には差が小さくなるという点がある。しかし、同じことをするのに少しでも無駄をなくしたいのであれば、先頭から追加するほうが高速に動作するということを知っていて損はない気もする。
(2010/5/16)リンク先をInternet ArchiveのWayback Machineのものにした

参考URL:

試験運用中なLinux備忘録・旧記事

はてなダイアリーで公開していた2007年5月-2015年3月の記事を保存しています。

GLibで連結リスト(リスト構造)にデータを追加する方向とその時間について

先頭からデータを逆順に追加すると処理が少ない?

処理時間の計測について

コード例