←検索窓の楽しみ方
  ショッピングモール  掲示板ランキング


【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板1こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.4583

NULLと末尾を返さないbsearch()
投稿者---chu-(2005/08/30 12:02:06)


テスト環境:Win98,LSI-C

・電圧値 → テーブル探索により前後の2点取得 → 2点から直線補間 → 温度値
ということをしようとしています。
このうち、テーブル探索の部分で標準関数のbsearch()を使えないかと検討しています。
NULLや末尾を返されると都合が悪いのですが、テーブルと比較関数の工夫で解決できそうに思えました。
いろいろ試行錯誤した結果、下記のようなコードを書きました。
実行してみると、アサートは出ず、出力も期待通りのものでした。

しかし、どの環境に使いまわしても期待通りに動くコードなのかどうか確信が持てません。
規格準拠のコンパイラ(というかライブラリ?)であっても、
環境によっては下記コードでNULLや末尾が返ることはあるでしょうか。
もし環境に依存してしまうのであればbsearch()を使うのはやめて自分で2分探索を実装しようと考えています。

[test.c]
#include    <stdio.h>
#include    <stdlib.h>
#include    <limits.h>
#include    <assert.h>

#define     ARRAYSIZE(array)    (sizeof(array)/sizeof(array[0]))

typedef     short   conv_t[2];

const   conv_t  conv_table[/*記述不可*/] = {
    /*  電圧            温度            */
    /*  (0.001V単位)    (0.01℃単位)    */
    {   SHRT_MIN,       15000,          },  /* 0    */
    {   143,            15000,          },  /* 1    */
    {   146,            14900,          },  /* 2    */
    {   149,            14800,          },  /* 3    */
    /*投稿用省略*/
    {   4338,           -1800,          },  /* 169  */
    {   4366,           -1900,          },  /* 170  */
    {   4393,           -2000,          },  /* 171  */
    {   SHRT_MAX,       -2000,          },  /* 172  */
};
const   void    *const  convtable_check = ARRAYSIZE(conv_table) - 8/*投稿用変更*//*173*/;
const   short   convtable_size = ARRAYSIZE(conv_table);

int     conv_compare(const void *vp_key, const void *vp_item)
{
    conv_t  *key = (conv_t *)vp_key;
    conv_t  *item = (conv_t *)vp_item;
    conv_t  *next = item + 1;

    if ( (*key)[0] < (*item)[0] ) return -1;
    if ( (*key)[0] > (*next)[0] ) return 1;
    return 0;
}

short   volt;       /* 電圧(0.001V単位) */
short   temp;       /* 温度(0.01℃単位) */

int     main(void)
{
    conv_t  key;
    conv_t  *item;
    conv_t  *next;
    long    i;

    printf("電圧(V),温度(℃)\n");

    for ( i = SHRT_MIN; i <= SHRT_MAX; i++ ) {
        volt = (short)i;

        /* テーブル探索 */
        key[0] = volt;
        item = (conv_t *)bsearch(&key, conv_table, convtable_size, sizeof(conv_table[0]), conv_compare);
        assert( item != NULL );                                 /* NULLはダメ   */
        assert( item != &conv_table[convtable_size-1] );        /* 末尾はダメ   */
        next = item + 1;

        /* 直線補間 */
        temp = (short)( (long)((*next)[1] - (*item)[1]) * (volt - (*item)[0])
                                        / ((*next)[0] - (*item)[0]) + (*item)[1] );

        printf("%.3f,%.2f\n", volt*0.001, temp*0.01);
    }

    return 0;
}

[実行]
C:\WINDOWS\デスクトップ>lcc test

C:\WINDOWS\デスクトップ>test>out.csv

C:\WINDOWS\デスクトップ>

[out.csv]
電圧(V),温度(℃)
-32.767,150.00
-32.766,150.00
-32.765,150.00
...
32.765,-20.00
32.766,-20.00
32.767,-20.00



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:NULLと末尾を返さないbsearch() 4596 επιστημη 2005/08/30 21:27:24


No.4596

Re:NULLと末尾を返さないbsearch()
投稿者---επιστημη(2005/08/30 21:27:24)


> しかし、どの環境に使いまわしても期待通りに動くコードなのかどうか確信が持てません。
> 規格準拠のコンパイラ(というかライブラリ?)であっても、
> 環境によっては下記コードでNULLや末尾が返ることはあるでしょうか。

だからこそ assert してるんでしょ?
このassertにひっかかったとき、改めて考えればいいんじゃないかと。



この投稿にコメントする

削除パスワード

No.4597

Re:NULLと末尾を返さないbsearch()
投稿者---chu-(2005/08/31 09:59:39)


返信ありがとうございます。

> このassertにひっかかったとき、改めて考えればいいんじゃないかと。

それだと、別の環境へ使いまわす度に、前回の投稿のようなコードによって
全ての値でアサートが出ないことをテストすることになります。
気にしているのは、そのテストを強制できないことです。
ドキュメントとしてテストが必要なことを残しておいたとしても、
すでに動いていたコードだから大丈夫だろうと判断されてしまったらと思うと。
そしてそれがたまたまbsearch()がNULLや末尾を返す環境で、実運用時に問題が出てきたらと思うと。
それに、いちいちテストが必要なのはやっぱり面倒ですし。



この投稿にコメントする

削除パスワード

No.4598

Re:NULLと末尾を返さないbsearch()
投稿者---REE(2005/08/31 10:49:32)


>> このassertにひっかかったとき、改めて考えればいいんじゃないかと。
>
>それだと、別の環境へ使いまわす度に、前回の投稿のようなコードによって
>全ての値でアサートが出ないことをテストすることになります。
>気にしているのは、そのテストを強制できないことです。

違う環境に移植する時に、テストをしない方が問題だと思います。

>ドキュメントとしてテストが必要なことを残しておいたとしても、
>すでに動いていたコードだから大丈夫だろうと判断されてしまったらと思うと。

そういう判断がされたら、その判断した人の責任でしょう。



この投稿にコメントする

削除パスワード

No.4599

Re:NULLと末尾を返さないbsearch()
投稿者---かずま(2005/08/31 10:55:13)


> そしてそれがたまたまbsearch()がNULLや末尾を返す環境で、
> 実運用時に問題が出てきたらと思うと。
> それに、いちいちテストが必要なのはやっぱり面倒ですし。

conv_table 専用の bsearch を自分で書けば安心です。
conv_compare をちょっと修正すれば書けますよ。



この投稿にコメントする

削除パスワード

No.4601

Re:NULLと末尾を返さないbsearch()
投稿者---chu-(2005/08/31 14:31:19)


返信ありがとうございます。

規格書を閲覧できることを知り、JIS-X3010のbsearch()の項目を見てみましたが、
今回の疑問を解消する記述は見当たりませんでした
なので、環境によってはあのコードでもNULLや末尾が返ることがあると考えることにしました。
できれば、十分テストされていて信頼性の高いであろう標準関数を使いたかったのですが、
bsearch()を使うのはやめて自分で2分探索を実装することにしました。

> 違う環境に移植する時に、テストをしない方が問題だと思います。

テストをしないで済むのであれば、テスト漏れ等のミスも発生しませんからそれが一番です。

> そういう判断がされたら、その判断した人の責任でしょう。

その判断した人からのなぜ?という問い合わせに答える等のフォローをする羽目に合います。

> conv_table 専用の bsearch を自分で書けば安心です。

範囲を表す2点を返す2分探索関数にしようと考えているため、
プロトタイプに悩んでまだ関数化はしていませんが、
下記のように2分探索は実装し、理想通り動作することを確認しました。

[test.c]
#include    <stdio.h>
#include    <stdlib.h>
#include    <limits.h>
#include    <assert.h>

#define     ARRAYSIZE(array)    (sizeof(array)/sizeof(array[0]))

typedef     short   conv_t[2];

const   conv_t  conv_table[/*記述不可*/] = {
    /*  電圧            温度            */
    /*  (0.001V単位)    (0.01℃単位)    */
    {   SHRT_MIN,       15000,          },  /* 0    */
    {   143,            15000,          },  /* 1    */
    {   146,            14900,          },  /* 2    */
    {   149,            14800,          },  /* 3    */
    /*投稿用省略*/
    {   4338,           -1800,          },  /* 169  */
    {   4366,           -1900,          },  /* 170  */
    {   4393,           -2000,          },  /* 171  */
    {   SHRT_MAX,       -2000,          },  /* 172  */
};
const   void    *const  convtable_check = ARRAYSIZE(conv_table) - 8/*投稿用変更*//*173*/;
const   short   convtable_size = ARRAYSIZE(conv_table);

short   volt;       /* 電圧(0.001V単位) */
short   temp;       /* 温度(0.01℃単位) */

int     main(void)
{
    conv_t  key;
    conv_t  *item;
    conv_t  *next;
    int     left, right, mid;
    long    i;

    printf("電圧(V),温度(℃)\n");

    for ( i = SHRT_MIN; i <= SHRT_MAX; i++ ) {
        volt = (short)i;

        /* テーブル探索 */
        assert( convtable_size >= 2 );          /* テーブルサイズは2以上必須    */
        key[0] = volt;
        left = 0;
        right = convtable_size - 1;
        while ( left != right - 1 ) {
            mid = (left + right) / 2;
            if ( key[0] >= conv_table[mid][0] ) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        assert( left >= 0 );                    /* 範囲チェック */
        assert( right <= convtable_size - 1 );  /* 範囲チェック */
        item = &conv_table[left];
        next = &conv_table[right];

        /* 直線補間 */
        temp = (short)( (long)((*next)[1] - (*item)[1]) * (volt - (*item)[0])
                                        / ((*next)[0] - (*item)[0]) + (*item)[1] );

        printf("%.3f,%.2f\n", volt*0.001, temp*0.01);
    }

    return 0;
}



この投稿にコメントする

削除パスワード

No.4602

Re:NULLと末尾を返さないbsearch()
投稿者---nop(2005/08/31 14:58:28)


> テストをしないで済むのであれば、テスト漏れ等のミスも発生しませんからそれが一番です。

移植である以上、テストは必要です。
例え標準準拠と銘打っていても、
実際には準拠していない箇所があるかもしれません。
移植であるにも関わらず、
テストを行わないのは問題ありかと思います。

テスト漏れ等の問題は、
テストケースを作っておく事で防止すべきでは?


この投稿にコメントする

削除パスワード

No.4603

Re:NULLと末尾を返さないbsearch()
投稿者---もぐりん(2005/08/31 19:36:09)


> テストをしないで済むのであれば、テスト漏れ等のミスも発生しませんからそれが一番です。

テストをやらないで、バグが発見された場合にクレームが付きませんか?
その場合、信用問題になりますよ。
特にお客に納品するアプリなら。

あなたはそれでもテストをやらないつもりですか?
顧客やあなたの上司に納得できる理由が説明できないなら、テストはやるべきです。



この投稿にコメントする

削除パスワード

No.4604

Re:NULLと末尾を返さないbsearch()
投稿者---chu-(2005/09/01 15:11:37)


返信ありがとうございます。

テストケース、最近耳にして興味はあったのですがまだ詳細には調べていません。
これを機に調べてみようと思います。

「keyの前後2点を返す汎用2分探索関数」となると作った後の確認が大変そうでした。
なので、今回はかずまさんの「conv_table 専用の bsearch を自分で書けば安心です。」の方法で行くことにしました。

それとは別に、興味があったので「keyの前後2点を返す汎用2分探索関数」も書いてみました。
私は下記のように組んだのですが、他の方はどう組まれるのか興味があります。
よろしければ見せていただけないでしょうか。
下記コードの、仕様やバグや環境依存コード等への指摘も嬉しいです。

[test.c]
#include    <stdio.h>

#define  ARRAYSIZE(array) (sizeof(array)/sizeof(array[0]))

typedef  struct { void *begin; void *end; }   range_t;

range_t bsearch_range(const void *key, const void *base, size_t nelem, size_t width,
                                                int (*fcmp)(const void *, const range_t *))
{
    range_t range = { NULL, NULL };
    void    *mid;
    void    *bak;
    int  res;

    if ( key != NULL && base != NULL && nelem > 0 && width > 0 && fcmp != NULL ) {
        range.begin = (void *)base;
        range.end = (char *)base + width * (nelem - 1);
        res = fcmp(key, &range);
        if ( res < 0 ) {
            range.end = range.begin;
            range.begin = NULL;
        }
        else if ( res > 0 || range.begin == range.end ) {
            range.begin = range.end;
            range.end = NULL;
        }
        else {
            while ( (char *)range.begin + width != range.end ) {
                mid = ((char *)range.end - (char *)range.begin) / (2 * width) * width
                                                                    + (char *)range.begin;
                bak = range.end;
                range.end = mid;
                if ( fcmp(key, &range) != 0 ) {
                    range.begin = mid;
                    range.end = bak;
                }
            }
        }
    }
    return range;
}

const   int    table1[] = { 1000 };
const   int    table2[] = { 1000, 2000 };
const   int    table3[] = { 1000, 2000, 3000 };
const   int    table4[] = { 1000, 2000, 3000, 4000 };

const   struct { const int *table; int size; } array[] = {
    {   NULL,      0                   },
    {   table1,    ARRAYSIZE(table1)   },
    {   table2,    ARRAYSIZE(table2)   },
    {   table3,    ARRAYSIZE(table3)   },
    {   table4,    ARRAYSIZE(table4)   },
};
const   int    arraysize = ARRAYSIZE(array);

int compare(const void *vp_key, const range_t *range)
{
    int key = *(int *)vp_key;
    int begin = *(int *)range->begin;
    int end = *(int *)range->end;

    if ( key < begin ) return -1;
    if ( key > end ) return 1;
    return 0;
}

int main(void)
{
    int  sel;
    int  key;
    int  *begin;
    int  *end;
    const   int    *table;
    size_t  size;
    range_t range;
    int  i;

    /* テーブル決定 */
    printf("array:");
    for ( i = 0; i < arraysize; i++ ) {
        printf(" %d=size%d", i, array[i].size);
    }
    printf("\n");
    printf("sel>");
    scanf("%d", &sel);
    if ( sel < 0 || arraysize <= sel )
        return 1;
    table = array[sel].table;
    size = array[sel].size;
    printf("table:");
    for ( i = 0; i < size; i++ ) {
        printf(" %d", table[i]);
    }
    printf("\n");

    while ( 1 ) {
        /* キー決定 */
        printf("key>");
        scanf("%d", &key);

        /* テーブル探索 */
        range = bsearch_range(&key, table, size, sizeof(table[0]), compare);
        begin = (int *)range.begin;
        end = (int *)range.end;

        /* 探索結果表示 */
        if ( begin != NULL ) {
            printf("%d,", *begin);
        } else {
            printf("NULL,");
        }
        if ( end != NULL ) {
            printf("%d\n", *end);
        } else {
            printf("NULL\n");
        }
    }

    return 0;
}

[実行]
プロンプト>lcc test

プロンプト>test
array: 0=size0 1=size1 2=size2 3=size3 4=size4
sel>2
table: 1000 2000
key>-32767
NULL,1000
key>999
NULL,1000
key>1000
1000,2000
key>1001
1000,2000
key>1999
1000,2000
key>2000
1000,2000
key>2001
2000,NULL
key>32767
2000,NULL
key>^C

プロンプト>



この投稿にコメントする

削除パスワード

No.4605

Re:NULLと末尾を返さないbsearch()
投稿者---REE(2005/09/01 16:15:22)


>それとは別に、興味があったので「keyの前後2点を返す汎用2分探索関数」も書いてみました。
>私は下記のように組んだのですが、他の方はどう組まれるのか興味があります。
>よろしければ見せていただけないでしょうか。

実際にコーディングはしませんが、
とりあえず、与える比較関数は、範囲との比較ではなく、直接の比較のものにします。
範囲の始点と終点は片方ずつしか変化しないので、必要な片側だけ比較すれば済みます。
それだけで、比較回数を半分程度に減らせそうです。



この投稿にコメントする

削除パスワード

No.4606

Re:NULLと末尾を返さないbsearch()
投稿者---chu-(2005/09/02 11:27:05)


返信ありがとうございます。

よく考えてみると、確かに範囲との比較と2点の返り値の価値は薄いですね。
テーブルサイズが1や、テーブルの先頭データ未満のキー、末尾データを超えるキー、
という例外的なデータを除けば返り値のbeginとendは必ずbegin+1==endなんですから。
つまり、仕様はbsearch()そのままで実装詳細を明らかにする。
それだけでキーの前後2点探索など様々な応用が利くようになりますね。

bsearch_range()はほぼ無意味でしたが、いい勉強になりました。
void *を引数とするような汎用アルゴリズム関数を組むのはなかなか楽しいですね。
良い遊び道具を見つけました。



この投稿にコメントする

削除パスワード

No.4611

Re:NULLと末尾を返さないbsearch()
投稿者---かずま(2005/09/04 14:34:54)


> 規格書を閲覧できることを知り、JIS-X3010のbsearch()の項目を見てみましたが、
> 今回の疑問を解消する記述は見当たりませんでした
> なので、環境によってはあのコードでもNULLや末尾が返ることがあると考えることにしました。
> できれば、十分テストされていて信頼性の高いであろう標準関数を使いたかったのですが、
> bsearch()を使うのはやめて自分で2分探索を実装することにしました。

どうしても bsearch() を使いたいのなら、bsearch に渡す配列のサイズを一つ
小さく指定すれば大丈夫でしょう。conv_compare が最後の要素を参照します。
key が SHRT_MAX の場合、bsearch は { 4366, -1900 } の項目を返しますが、
直線補間で、SHRT_MAX に対する正しい値が得られます。

配列の要素を構造体にしてみました。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>

#define  ARRAYSIZE(array)    (sizeof(array)/sizeof(array[0]))

typedef struct {
    short   volt;       /* 電圧(0.001V単位) */
    short   temp;       /* 温度(0.01℃単位) */
} conv_t;

const conv_t conv_table[/*記述不可*/] = {
    /*  電圧            温度            */
    /*  (0.001V単位)    (0.01℃単位)    */
    {   SHRT_MIN,       15000,          },  /* 0    */
    {   143,            15000,          },  /* 1    */
    {   146,            14900,          },  /* 2    */
    {   149,            14800,          },  /* 3    */
    /*投稿用省略*/
    {   4338,           -1800,          },  /* 169  */
    {   4366,           -1900,          },  /* 170  */
    {   4393,           -2000,          },  /* 171  */
    {   SHRT_MAX,       -2000,          },  /* 172  */
};

const short convtable_size = ARRAYSIZE(conv_table);

int conv_compare(const void *pkey, const void *pitem)
{
    short key = *(short *)pkey;
    const conv_t *item = pitem;

    if (key < item[0].volt) return -1;
    if (key > item[1].volt) return 1;
    return 0;
}

int main(void)
{
    short volt, temp;

    printf("電圧(V),温度(℃)\n");
    for (volt = SHRT_MIN; ; volt++) {
        conv_t *item = bsearch(&volt, conv_table, convtable_size - 1,
            sizeof(conv_table[0]), conv_compare);
        assert(item != NULL);                           /* NULLはダメ */
        assert(item != &conv_table[convtable_size-1] ); /* 末尾はダメ */
        temp = (long)(item[1].temp - item[0].temp) * (volt - item[0].volt)
            / (item[1].volt - item[0].volt) + item[0].temp;
        printf("%.3f,%.2f\n", volt * 0.001, temp * 0.01);
        if (volt == SHRT_MAX) break;
    }
    return 0;
}



この投稿にコメントする

削除パスワード

No.4612

Re:NULLと末尾を返さないbsearch()
投稿者---chu-(2005/09/04 22:18:44)


返信ありがとうございます。

>どうしても bsearch() を使いたいのなら、bsearch に渡す配列のサイズを一つ
>小さく指定すれば大丈夫でしょう。

なるほど!そのアイデアいただきます。
目から鱗でした。
その柔軟な発想、私も身に付けたいものです。


この投稿にコメントする

削除パスワード

No.4613

Re:NULLと末尾を返さないbsearch()
投稿者---かずま(2005/09/05 10:05:01)


> key が SHRT_MAX の場合、bsearch は { 4366, -1900 } の項目を返しますが、
> 直線補間で、SHRT_MAX に対する正しい値が得られます。

訂正します。

key が SHRT_MAX の場合、bsearch が返すのは、{ 4366, -1900 } ではなく、
{ 4393, -2000 } です。

{ 4393, -2000 } と { SHRT_MAX, -2000 } との間の直線補間で、
SHRT_MAX に対する値 -2000 が得られます。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧




掲示板提供:Real Integrity