Entry

本日の勝手にどう書く? - 『タブ区切りデータの処理』

2008年10月05日

どう書く?org のお題が久しぶりに実用的なもんだったので挑戦。けど,著作権とかアカウント作りとかいろいろ面倒そうなので,自分のところに書いておくことにします。今のところ,C で書いたもんがないようなので,C で書いてみました。

お題はこちら。

タブ区切りのデータを読み込んで操作をし書き出す方法を教えてください。 読み込み・書き出しの方法は任意とします。

与えられるデータは:

  • レコードの区切りは改行、カラムの区切りはタブです。
  • 最初のレコードはヘッダで、カラムの名前が書いてあります。
  • それ以降はデータで、第1,4カラムは整数値、第2,3カラムは文字列値です。

この入力データに対して以下の操作をしたものを書き出してください:

  • 第1カラムの値でデータを昇順にソートする。
  • 第2カラムと第3カラムをヘッダを含めて入れ替える。
  • 第4カラムの値にそれぞれ1を加える。

入力の例:

ID Surname Forename Age 
1 Sato Hanako 17 
0 Suzuki Taro 18 
... 

出力の例:

ID Forename Surname Age 
0 Taro Suzuki 19 
1 Hanako Sato 18 
...
タブ区切りデータの処理 どう書く?org

部分的な機能じゃなくて,総合的なお題だってところが,良問だと思います。ここで書くまでもありませんけど,少なくとも C の場合,お題に答えるには,次のような話を考えなくちゃいけない。

  • 入力データのデータ構造
  • TSV(Tab Separated Value)の解析方法
  • ソートの方法
  • カラムを入れ替える方法
  • カラムの数値を操作する方法

こういう総合的なお題になると,言語ごとの特性がよく出るんだと思います。C++ と C の違いにしても STL コンテナを使える C++ と,使えない C では,大きな違いが出る。

まぁ,ともあれ,こんな感じで書いてみました。長っ!所要時間は,大体1時間半くらいです。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#undef BUFSIZE
#define BUFSIZE (512)

typedef struct record_t_ {
    char *col_1;
    char *col_2;
    char *col_3;
    char *col_4;
    struct record_t_ *next;
} record_t;

typedef struct cell_t_ {
    int num;
    record_t *rec;
} cell_t;

typedef int (*compfunc_t)(const void *, const void *);

record_t *
create_record(void)
{
    record_t *rec;
    
    rec = (record_t *)malloc(sizeof(record_t));
    if (rec != NULL) {
        rec->col_1 = NULL;
        rec->col_2 = NULL;
        rec->col_3 = NULL;
        rec->col_4 = NULL;
    }

    return rec;
}

void
delete_record(record_t *rec)
{
    if (rec != NULL) {
        if (rec->col_1 != NULL) {
            free(rec->col_1);
            rec->col_1 = 0;
        }
        if (rec->col_2 != NULL) {
            free(rec->col_2);
            rec->col_2 = NULL;
        }
        if (rec->col_3 != NULL) {
            free(rec->col_3);
            rec->col_3 = NULL;
        }
        if (rec->col_4 != NULL) {
            free(rec->col_4);
            rec->col_4 = 0;
        }
        free(rec);
    }

    return;
}

void
delete_record_list(record_t *head)
{
    record_t *tmp;

    while (head != NULL) {
        tmp = head;
        head = head->next;
        delete_record(tmp);
    }

    return;
}

record_t *
parse_record(const char *str)
{
    record_t *rec;
    const char *ptr;

    char buf[BUFSIZE];
    char *end = buf + BUFSIZE - 1;
    char *bp = buf;

    int column = 0;
    int finish = 0;

    rec = create_record();
    memset(buf, 0, BUFSIZE);

    if (rec != NULL) {
        for (ptr = str; ; ptr++) {
            switch (*ptr) {
            case '\0': /* fall through */
                finish = 1;
            case '\t':
                column++;
                *bp = '\0';
                switch (column) {
                case 1:
                    rec->col_1 = strdup(buf);
                    if (rec->col_1 == NULL) {
                        assert(!"strdup error");
                    }
                    break;
                case 2:
                    rec->col_2 = strdup(buf);
                    if (rec->col_2 == NULL) {
                        assert(!"strdup error");
                    }
                    break;
                case 3:
                    rec->col_3 = strdup(buf);
                    if (rec->col_3 == NULL) {
                        assert(!"strdup error");
                    }
                    break;
                case 4:
                    rec->col_4 = strdup(buf);
                    if (rec->col_4 == NULL) {
                        assert(!"strdup error");
                    }
                    break;
                default:
                    assert(!"invalid column size");
                    break;
                }
                bp = buf;
                break;
            default:
                if (bp == end) {
                    assert(!"buffer overflow");
                }
                *bp = *ptr;
                bp++;
                break;
            }
            if (finish) {
                break;
            }
        }
    }

    if (column < 4) {
        assert(!"too few field error");
    }
    
    return rec;
}

int
compare_record(const cell_t *a, const cell_t *b)
{
    return (a->num - b->num);
}

void
sort_record(record_t *head)
{
    record_t *ptr = NULL;
    cell_t *cell = NULL;
    cell_t *cptr = NULL;
    size_t size = 0;
    size_t i;

    for (ptr = head->next; ptr != NULL; ptr = ptr->next) {
        size++;
    }
    if (size == 0) {
        assert(!"sort error");
    }
    cell = (cell_t *)malloc(size * sizeof(cell_t));
    if (cell == NULL) {
        assert(!"memory allocation error");
    }
    cptr = cell;
    for (ptr = head->next; ptr != NULL; ptr = ptr->next) {
        cptr->num = atoi(ptr->col_1);
        cptr->rec = ptr;
        cptr++;
    }

    qsort(cell, size, sizeof(cell_t), (compfunc_t)compare_record);

    ptr = head;
    cptr = cell;
    for (i = 0; i < size; i++) {
        ptr->next = cptr->rec;
        ptr = ptr->next;
        cptr++;
    }
    ptr->next = NULL;

    free(cell);
    return;
}

void
swap_column(record_t *head)
{
    record_t *ptr;
    char *tmp;

    for (ptr = head; ptr != NULL; ptr = ptr->next) {
        tmp = ptr->col_2;
        ptr->col_2 = ptr->col_3;
        ptr->col_3 = tmp;
    }

    return;
}

void
increment_column(record_t *head)
{
    record_t *ptr;
    int num;
    char buf[BUFSIZE];

    for (ptr = head; ptr != NULL; ptr = ptr->next) {
        num = atoi(ptr->col_4);
        num++;
        sprintf(buf, "%d", num);
        if (ptr->col_4 != NULL) {
            free(ptr->col_4);
        }
        ptr->col_4 = strdup(buf);
        if (ptr->col_4 == NULL) {
            assert(!"strdup error");
        }
    }

    return;
}

int
main(int argc, char *argv[])
{
    char line[BUFSIZE];
    record_t *head = NULL;
    record_t *last = NULL;
    record_t *rec  = head;
    record_t *ptr;
    size_t len;

    while (fgets(line, BUFSIZE, stdin) != NULL) {
        len = strlen(line);
        line[len - 1] = '\0';
        rec = parse_record(line);
        if (rec == NULL) {
            assert(!"parse error");
        }
        if (head == NULL) {
            head = rec;
            last = rec;
        } else {
            last->next = rec;
            last = rec;
        }
    }

    /* input data */
    puts("--------------------------------------------------");
    for (ptr = head; ptr != NULL; ptr = ptr->next) {
        printf("%s %s %s %s\n",
               ptr->col_1,
               ptr->col_2,
               ptr->col_3,
               ptr->col_4);
    }
    puts("--------------------------------------------------");
    /* processing */
    sort_record(head);
    increment_column(head->next);
    swap_column(head);
    /* result */
    for (ptr = head; ptr != NULL; ptr = ptr->next) {
        printf("%s %s %s %s\n",
               ptr->col_1,
               ptr->col_2,
               ptr->col_3,
               ptr->col_4);
    }
    puts("--------------------------------------------------");

    delete_record_list(head);

    return 0;
}

ためしに,こんなファイルを食べさせてみる(空白が入っているけど実際はタブです)。

ID  Surname Forename    Age
1   Sato    Hanako  17
7   Suzuki  Taro    18
3   Yamada  Jiro    20
9   Yamamoto    Hiroshi 16
8   Utsumi  Makoto  22
10  Inoue   Sayaka  31
2   Motoki  Fumie   43
5   Okamoto Tomoya  9
0   Shoji   Kanako  12
4   Ishii   Kazuhiro    8
6   Takahashi   Kana    27

こんな結果になる(追記:TSV を表示していないからお題に沿ってないんですけど,大目に見てください)。

aian@IBM-39B80170C23 ~
$ ./a.exe < tab.txt
--------------------------------------------------
ID Surname Forename Age
1 Sato Hanako 17
7 Suzuki Taro 18
3 Yamada Jiro 20
9 Yamamoto Hiroshi 16
8 Utsumi Makoto 22
10 Inoue Sayaka 31
2 Motoki Fumie 43
5 Okamoto Tomoya 9
0 Shoji Kanako 12
4 Ishii Kazuhiro 8
6 Takahashi Kana 27
--------------------------------------------------
ID Forename Surname Age
0 Kanako Shoji 13
1 Hanako Sato 18
2 Fumie Motoki 44
3 Jiro Yamada 21
4 Kazuhiro Ishii 9
5 Tomoya Okamoto 10
6 Kana Takahashi 28
7 Taro Suzuki 19
8 Makoto Utsumi 23
9 Hiroshi Yamamoto 17
10 Sayaka Inoue 32
--------------------------------------------------

まぁ,いろいろとツッコミは入りそうなんですが……。

まず,パーサがヘタレなので,環境によっては(というか CRLF の環境では),余計な改行(CR)が入っちゃいます。また,ここではリストで管理することにしたんですけど,単方向だとソートを作るのに難儀しちゃうもんで,データ構造を変換して,qsort(3) に任せることにしました。これは結構キモイよなぁ。

さらに,C の場合,型の融通が利かないもんで,まともにデータ構造を作ると,ヘッダ(全て文字列型)と TSV 本体(一部整数型)の型が分かれちゃう難もありました。ヘッダと本体を別々に管理するってのが正攻法なんでしょうけど,ここでは全部文字列型にして,整数としての操作が必要なときだけ,整数に戻して使っています。これもある意味キモイ処理だよなぁ。

まぁ,とりあえずはこんなところなのかな。今にして考えると,全部文字列型にするなら,下みたいな定義でいいじゃんよ,とも思うわけですけど(こうすればパーサの switch-文がなくなる分だけ,コードが短くなる),その場の思いつきで作っちゃったから,まぁ仕方ない。

typedef struct record_t_ {
    char *col[4];
    struct record_t_ *next;
} record_t;

改良を考える余地があるって点においても,ほんと良問だと思います。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN