Home > C++ Archive

C++ Archive

ツンデレソート

「最初の方はぐちゃぐちゃだけど徐々に整列されていく」というツンデレソートってのがあるそうです。
私も作ってみたのですが、なかなか難しいです。


#include <stdlib.h>
#include <math.h>

template< typename T >
class Tundere {
private:
    T tmin;
    double average;        // 平均
    double average2;    // 2乗平均
    double count;        // カウント
    static const int width = 4;       // 分散の幅

public:
    Tundere():tmin(0),average(0),average2(0),count(-1){}

    bool operator()(T a, T b) {
        if (count < 0) {
            average = ((double)(a+b))/2.0;
            average2 = ((double)(a*a+b*b))/2.0;
            count = 0;
        } else {
            average = average*(count/(count+2.0)) + ((double)(a+b))/(count+2.0);
            average2 = average2*(count/(count+2.0)) + ((double)(a*a+b*b))/(count+2.0);
        }
        count += 2;
        tmin = std::min(tmin, std::min(a,b));   // 最小値を保存
        double variance = average2 - average*average;    // 分散
        double x = std::max(a,b);
        if (average + sqrt(variance)/((double)width) - (double)tmin + 1.0 < 1.0) return false;        // エラー?
        int prob = (double)(100.0*log(x + 1.0 - (double)tmin)/log(average + sqrt(variance)/((double)width) - (double)tmin + 1.0));
        int dummyrand = 0;
        T c = a + b;
        for (int i = 0; i < sizeof(T); i++) {
            dummyrand = 31 * dummyrand + ((char*)&c)[i];
        }
        dummyrand %= 100;
        if (dummyrand < prob) {
            return (a < b);
        } else {
            return false;
        }
    }
};

以下のように使います。


int main(int argc, char* argv[])
{
	std::vector< int > target;

	for (int i = 0; i < 3000; i++) {
		target.push_back(rand()%3000);
	}


	std::sort(target.begin(), target.end(), Tundere<int>());
	for (int i = 0; i < target.size(); i++) {
		std::cout << target[i] << std::endl;
	}

	return 0;
}

平均値(のようなもの)と分散(のようなもの)を逐次更新していき、平均値+分散/4より大きいところでは正しい比較結果を返し、そうでないときは適当な結果を返すようになっています。確率を決定する乱数にrandを使いたくなかったのでJava流ハッシュ計算方法を用い、閾値には怪しく適当なLog関数を用いています。
結果は下記みたいになりますが、分散が大きいデータではうまくいかないらしいです。
うまくいった(?)例
適当な確率なんて使わない方がいいかもしれません。というかツンデレソート意外と難しいです。

以上

C++トリビアルメモ6 STLのsort

  • 2008-07-01 (火)
  • C++

そろそろSTLのsortについてまじめに語ろうと思う。
でもごめん。余白が足りないのであんまり書けない。

まず、簡単な使い方。
サンプル1:


#include <vector>
#include <algorithm>
using namespace std;

vector< int > target;

target.push_back(3);
target.push_back(1);
target.push_back(4);
target.push_back(0);
target.push_back(2);

sort(target.begin(), target.end());

結果は0,1,2,3,4になる。sortの引数はランダムアクセスイテレータなら何でもよく、vectorじゃなくてもdaqueでもいいし、配列のポインタでもいい。ただし、ソートの範囲は第2引数の終端を含まないので注意が必要。vectorとかのend()は最終要素の一つ先を指しているから上記で問題ない。(配列でやるときは無理矢理一歩先を入れればいいのかな??)
サンプル2:


#include <algorithm>   // for "sort"
using namespace std;

int target[5];

target[0] = 3;
target[1] = 1;
target[2] = 4;
target[3] = 0;
target[4] = 2;

sort(&(target[0]), &(target[4]));

0,1,3,4,2になる。&(target[4])を&(target[5])にすれば、VC2008ではサンプル1と同じ結果になった。

で、前置きはこれくらいにして、書きたかったのは自前の比較関数について。その前にまず、サンプル1は以下のサンプル3と全く同じであることを押さえておく。
サンプル3:


#include <vector>
#include <algorithm>   // for "sort"
#include <functional>   // for "less"

std::vector< int > target;

target.push_back(3);
target.push_back(1);
target.push_back(4);
target.push_back(0);
target.push_back(2);

std::sort(target.begin(), target.end(), std::less< int >());

namespaceのstdを復活させてみたのはlessのnamespaceを明示するため。ようするにサンプル1のsortはデフォルトで比較関数にlessを使っているということ。したがって自前の比較関数を使いたい場合はこのlessの代わりになるような物を作ればいい。lessっていうのはつまり<。小なりで比較する。なので、比較関数というとちょっと語弊がある。一般に(C言語とかPHPで)比較関数というと、


int cmp(int a, int b) {
   if (a < b) {
      return -1;
   } else if (a == b) {
      return 0;
   } else {
      return 1;
   }
}

というように第1引数が第2引数より小さいときに-1、等しいときに0、大きいときに1を返すのが普通(昇順ソートの場合)。たいてい、


int cmp(int a, int b) {
   return a - b;
}

でも間に合う。a、bがint型じゃないときは型にあわせてa-bを定義するようなイメージがある。しかし、stlのsortに対して同じようなイメージで比較関数を作るとハマル。なぜならless< int >(a, b)はa < bの時にtrueを返すから。そもそもlessの戻り値はboolであり、昇順ソートにするためにはa - bが負になるときにtrueを返さないといけなく、a - bが正になるときおよび0になるときにfalseを返さないといけない。降順ソートしたい場合は逆の真偽値にすればよいので、降順ソートにする場合は次のようなtestcmpを定義すればよい。
サンプル4:


bool testcmp(int a, int b) {
	if (a > b) {
		return true;
	} else {
		return false;
	}
}

std::sort(target.begin(), target.end(), testcmp);

もっとも、本当に降順ソートしたいだけなら自分で定義しなくてもstd::greater< int >()を使った方がいい。

サンプル4だとC言語のqsort使ってるのと同じような感じであるが、せっかくC++、STLなので関数オブジェクトを利用した方がいい。
サンプル5:


struct testcmp {
	bool operator()(int a, int b) const {
		if (a > b) {
			return true;
		} else {
			return false;
		}
	}
};

std::sort(target.begin(), target.end(), testcmp());

関数オブジェクトはoperator()をオーバーロードした物で、ソートのための比較オブジェクトを作るためには引数を二つ取るoperator()を作ればいい。関数オブジェクトはオブジェクトでありながらoperator()が定義されているが故に関数みたいに使える物である。関数オブジェクトにすることで比較部分がinline化されるため、より高速にソートできるようになる。上記はstructで作成したが当然classでもいい。ただし、publicをつける(structだと勝手にpublicになる)。
サンプル6:


class testcmp {
public:
	bool operator()(int a, int b) const {
		if (a > b) {
			return true;
		} else {
			return false;
		}
	}
};

testcmp mycmp;
bool result1 = mycmp(3, 1);   // true
bool result2 = mycmp(1, 2);   // false

std::sort(target.begin(), target.end(), mycmp);

サンプル6のようにインスタンス化してからsortの第3引数に渡すこともできるが、これだとたぶんinline化されないんじゃないかと思う(よく知らない)。

たぶん、すぐ忘れるので今のうちにメモっておいた。

以上

C++トリビアルメモ5 テンプレートとオブジェクトと

  • 2008-06-26 (木)
  • C++

いろんな言語に手を出していると頭がごっちゃごちゃになってきます。
例えばstd::mapにstd::vectorを入れる場合。
中にポインタを入れておく場合は下記のような使い方かと思います。最初に使うときに初期化するという。JavaでHashMapにArrayListを突っ込むときとかはこんな感じじゃなかったかと思ってます(2年前の知識では)。


#include <vector>
#include <map>
#include <iostream>

using namespace std;

int main(int argc, char *argv[]) {
	map< int, vector< int >* > vectorMap;
	
	if (vectorMap.find(4) == vectorMap.end()) {
		vectorMap[4] = new vector< int >();
	}
	vectorMap[4].push_back(1);
	vectorMap[4].push_back(2);
	
	if (vectorMap.find(20) == vectorMap.end()) {
		vectorMap[20] = new vector< int >();
	}
	vectorMap[20].push_back(3);
	
	for (map< int, vector< int >* >::iterator it = vectorMap.begin(); it != vectorMap.end(); it++) {
		for (vector< int >::iterator ptr = it->second->begin(); ptr != it->second->end(); ptr++) {
			cout << "map[" << it->first << "] = " << *ptr << endl;
		}
	}
	
	return 0;
}

PHPとかだと配列なら$hoge[]=$fooってやれば勝手に初期化されるので気にしないかもしれません。で、C++でもポインタを入れない場合は気にしなくていいわけです。


#include <vector>
#include <map>
#include <iostream>

using namespace std;

int main(int argc, char *argv[]) {
	map< int, vector< int > > vectorMap;
	
	vectorMap[4].push_back(1);
	vectorMap[4].push_back(2);
	vectorMap[20].push_back(3);
	
	for (map< int, vector< int > >::iterator it = vectorMap.begin(); it != vectorMap.end(); it++) {
		for (vector< int >::iterator ptr = it->second.begin(); ptr != it->second.end(); ptr++) {
			cout << "map[" << it->first << "] = " << *ptr << endl;
		}
	}
	
	return 0;
}

これ下のやつでいいのかなあ。上のやつは実はメモリリークしてるしなあ。下の方法はvectorのコンストラクタがmapの内部で2回呼ばれる(正確にはデフォルトコンストラクタとコピーコンストラクタが1回づつかな?)ため若干効率が悪いのかもしれない。vectorならまだしもコンストラクタが重いクラスだとだめなのかも。上のやつはスマートポインタとかを使えばいいのかもしれないけれども、あんまり信用してないというか使ったことないぜ!今度使ってみよう。

以上

C++トリビアルメモ4 テンプレートと可変長と

  • 2008-06-17 (火)
  • C++

例えばC99だとマクロで可変長引数を使えて、…ではなくて
__VA_ARGS__
を使う。

あんまり関係ないけど、テンプレートクラスでもstdargが使えるのかと思ってやってみたら使えた。in vc2008。
PrintfClass.h:


#pragma once

#include <stdarg.h>

template<typename T>
class PrintfClass
{
public:

	PrintfClass(void)
	{
	}

	~PrintfClass(void)
	{
	}

	T printfTest(int n, ...) {
		va_list args;
		T sum = 0;

		va_start(args, n);
		for (int i = 0; i < n; i++) {
			sum += va_arg(args, T);
		}
		va_end(args);

		return sum;
	}
};

main.cpp:


#include "PrintfClass.h"
#include <iostream>

int _tmain(int argc, _TCHAR* argv[])
{
	PrintfClass<double> a;

	double b = a.printfTest(3, 1.0, 2.0, 3.0);
	std::cout << b << std::endl;

	return 0;
}

結果:


6

さらに関係ないけど、std::coutのフォーマットは「マニピュレータ」を使う。名前さえ分かってれば調べられる。
例えば。
http://www-nh.scphys.kyoto-u.ac.jp/~shoji/Tips/Cpp_Stream.html

以上

CppUnitの使い方 4~登録マクロ生成(おまけ)

CppUnitの使い方のおまけ。
テストコードを書いたはいいものの、テストスイートに登録するためのマクロを書くのが結構めんどくさい。
そういうわけで
test_関数名_連番()
みたいな名前にしてるときにマクロを生成してくれるちょんスクリプトをメモ。
ソースコードをコマンドライン引数で渡す。


<?php

if (empty($argv[1])) exit(1);

$file = file($argv[1]);

$result = array();
foreach ($file as $line) {
    if (preg_match('/.*void\s+(test.+?)\(.*/i', $line, $matches)) {
        $result[] = "CPPUNIT_TEST(" . $matches[1] . ");";
    }
}

foreach ($result as $line) {
    echo $line . "\n";
}

?> 

phpだけど。

以上

CppUnitの使い方 3~ソースの書き方

CppUnitの使い方ラスト。

目次
1.準備
2.プロジェクトの構成
3.ソースの書き方

まずはメイン。コンソールでテキストベースに使う場合はHogeTest.cppを次のように書く。HogeTest.cppやらファイルの構成やらについては前回を参照のこと。


#include <cppunit/ui/text/TestRunner.h>
#include <cppunit/TextOutputter.h>
#include <cppunit/extensions/TestFactoryRegistry.h>

int _tmain(int argc, _TCHAR* argv[])
{
    CppUnit::TextUi::TestRunner runner;
    runner.addTest(CppUnit::TestFactoryRegistry::getRegistry().makeTest());
    CppUnit::Outputter* outputter = new CppUnit::TextOutputter(&runner.result(),std::cout);
    runner.setOutputter(outputter);
    int ret = runner.run() ? 0 : 1;
    return ret;
}

Hogeクラスのテストコードは以下のようにする。


// 必要なヘッダの #include
#include "Hoge.h"
#include <stdio.h>
#include <stdlib.h>
#include <string>

#include <cppunit/extensions/HelperMacros.h>
#include <cppunit/TestAssert.h>


class Hoge_Test : public CppUnit::TestFixture {
    // テストスイート作成
    CPPUNIT_TEST_SUITE(Hoge_Test);  // クラス名を指定してテストスイート(テストの集合)を作成する。
    CPPUNIT_TEST(test_foo_001);  // 下で定義したテストコードを登録する。これを書かないとそのテストはテストされない。
    CPPUNIT_TEST_SUITE_END();
private:
    // 必要な メンバ変数/関数

    // テスト用ツール関数はこの辺に定義しとく。以下はサンプル。
    
    /**
     * 整数を文字列に変換する。
     */
    std::string itos(int i) {
        char buff[50];
        sprintf(buff, "%d", i);
        return std::string(buff);
    }

    /**
     * 乱数を発生させる。0以上N未満。
     */
    int my_rand(int N) {
        return (int)((double)rand() / ((double)RAND_MAX + 1) * N);
    }





public:

    /*
     * コンストラクタ/デストラクタ
     */
    Hoge_Test() {
    }

    ~Hoge_Test() {
    }

    /*
     * 初期化。
     * 各テストコードを実行する前に呼ばれる。
     * 内部変数を初期化したいとか、そういうのを書く。
     */
    virtual void setUp() {
    }

    /*
     * 後始末。
     * 各テストコード終了後に実行される。
     * たぶん、テストに失敗しても呼ばれるんじゃないかな。
     */
    virtual void tearDown() {
    }


    /**
     * 実際のテストコードを書く。
     * 名前はたぶんなんでもいいが、分かりやすさのため
     * test_関数名_番号()
     * としておく。引数・戻り値はvoid。
     */
    void test_foo_001() {
        Hoge instance;
        
        CPPUNIT_ASSERT(true == instance.foo());  // foo()がtrueを返すかどうかをテスト。
        CPPUNIT_ASSERT("foo test", true == instance.foo());  // 上と同じ。エラーのとき「foo test」って出る。
        CPPUNIT_ASSERT_EQUAL(true, instance.foo());  // instance.foo()がtrueと同じかのテスト。これ使わなくても上でいいんじゃね?
        CPPUNIT_ASSERT_DOUBLES_EQUAL(0.1, instance.foo(), 0.001);  // instance.foo()が0.1を返すかどうか。浮動小数点なので。誤差0.001。
        CPPUNIT_FAIL("error");  // 失敗する。エラーパスに仕込むのかな。あるいはまだ中身作ってないテストとか?
    }

};

/*
 * テストスイート(このクラスの冒頭で登録した奴)をテストとして登録。
 * これをしないとこのスイートはテストされない。
 * 逆に言うと、これさえ書いておく、あるいは消しておけばメインを変更しなくてもテストするクラスを指定できる。
 */
CPPUNIT_TEST_SUITE_REGISTRATION(Hoge_Test);

そういうわけで、privateなメソッドをテストするためにHogeクラスは以下のようにしておく。(参考:前方宣言


class HogeTester;   // 前方宣言

class Hoge {
   friend HogeTester;

private:
   bool foo;
   void bar();
};

C言語のソースでも同じように適当にテストクラス作ってテストコード作ってやればいい。ファイルスコープ関数(staticなやつ)をテストするには*.cファイルをインクルードするとかいう荒業もありか。(なしかも)

以上

CppUnitの使い方 2~プロジェクトの構成

そういうわけでCppUnitの使い方、個人的な使い方の続きを。

目次
1.準備
2.プロジェクトの構成
3.ソースの書き方

みたいな感じで今回は「2.プロジェクトの構成」

VCだとソリューションがあって、その下にいくつかプロジェクトをぶら下げられるので、メインプロジェクトとテストプロジェクトを同じソリューション下におく。また、前回で作成したlibやcppunitのヘッダをインクルードするため、それらをテストプロジェクト下におく。
例えばディレクトリ構成は下記のようにする。

プロジェクト名:Hoge(=ソリューション名)
Hoge/
  -source/                # この下はメインプロジェクトのソース
      -Fuga.cpp
  -header/                # この下はメインプロジェクトのヘッダ
      -Fuga.hpp
  -HogeTester/
      -HogeTest.cpp             # テストプロジェクトのmainソース
      -Fuga_Tester.cpp         # Fuga.cppのテスト用ソース
      -cppunit-1.12.0/          # cppunitのいるとこ抜粋してコピーする
          -include/                   # cppunit/ とか msvc6/ とかを丸々置いておく
          -lib/                  # 作成したlibファイル群(cppunit.lib, cppunitd.libなど)

HogeTesterプロジェクトのプロパティでリリースモード、デバッグモードそれぞれでパスを設定する。

・追加のインクルードディレクトリ (C/C++)
  ../header               # メインプロジェクトのヘッダ
  cppunit-1.12.0/include         # cppunitのヘッダ
・追加のライブラリディレクトリ (リンカ)
  cppunit-1.12.0/lib
・追加の依存ファイル (リンカ)
[リリースモードの場合]
cppunit.lib TestRunner.lib
[デバッグモードの場合]
cppunitd.lib TestRunnerd.lib

C/C++のコード生成でランタイムライブラリは前回の通り

[リリースモードの場合]
マルチスレッドDLL
[デバッグモードの場合]
マルチスレッドデバッグDLL

としておく。
あと経験上、プリコンパイル済みヘッダーは使用しないほうがトラブルに巻き込まれずにすむ。プロジェクトが固まってきたら使用してもいいかも知れんけど。でっかいプロジェクトだとコンパイル遅いしな。

次回は実際のコードのテンプレートを示す。

以上

CppUnitの使い方 1~準備編

そういうわけで、CppUnitの私なりの使い方を3回くらいに分けてメモっておく。
VCでコマンドプロンプトでテキストベースで使うという、限定的な使い方だけども!

目次
1.準備
2.プロジェクトの構成
3.ソースの書き方

見たいな感じで今回は「1.準備」

CppUnitは要するにC++のユニットテストをするためのフレームワーク。
いろんな組み込み方はあるだろうけども、私はlibファイルを作って静的リンクにより利用するのが簡単で好きだ。
そういうわけで、まずはここからダウンロード
解凍したらsrcフォルダのVCプロジェクトを開く。
そんでもってビルド!リリースビルドとデバッグビルドをやっておく。
ここでなんかしらんけども、プロジェクトのランタイムライブラリはマルチスレッドDLL(リリースの場合)、マルチスレッドデバッグDLL(デバッグの場合)じゃないとうまくできなかった。そういうわけで、テスト対象もこのどっちかになってしまう。うーん、どうにかなるのかね?
ビルドしたらlibファイルができる。dllとかGUIっぽいexeもできるがそんな軟弱なものはとりあえず使わない。そんなのはすげぇなれてから、ひまでしかたなかったらやってみればいい(と思って3年くらい使ってない)。

というわけで、実際のプロジェクトからlibファイルをリンクして使うわけだが、そのときのディレクトリ構成とかは次回メモる。

以上

Doxygenでヘルプファイルを作りたいんだけど

CPPUNITは最初の導入がめんどいな。今度書く。

で、Doxygenなんですけど1.5.4あたりからヘルプファイル(.chm)を作ったときに日本語が文字化けする。
1.5.5が出てたんですけど、やっぱり文字化けする。
というわけでとりあえずの対処法。

1.普通にヘルプファイルを作ろうとする。文字コードはインプットとアウトプットと両方指定しておいたほうがいいかも。指定できる文字コードはたぶんこれ。アウトプットはUTF-8がいい気がする。
2.できたヘルプファイルを開いて左側のメニューが文字化けしていることを確認する。あと経験ではプロジェクト名に日本語を使っていると本文のプロジェクト名の部分も?????になる。(これはもう英語にするしか?)
3.index.hhcファイルをテキストエディタで開き、SHIFT_JISで保存する。メモ帳ではだめかもわからん。とにかくUTF-8⇒SHIFT_JISへの変換を行う。
4.コマンドプロンプトで”C:\適当なパス\hhc.exe index.hhp”を実行する。

以上

(2010/04/21 追記)
いつの間にか「CHM_INDEX_ENCODING」という設定項目ができていた。
OUTPUTもCHM_INDEX_ENCODINGも文字コードに「CP932」を指定しておけば、めんどくさいことをしなくても文字化けしないchmが作れる。

以上

C++トリビアルメモ(ポインタの参照)

平成20年ってほんと?ありえなくない?

VC++でポインタの参照を使ってみました。どういうことなのかよく分からないけど動いたから正しいに違いない。
コンパイラが神様です。
C言語の場合、引数で渡された変数に関数内で領域を割り当てる場合は普通(?)二重ポインタにする。私の場合。


void foo(char **bar) {
   *bar = (char *)malloc(sizeof(char)*10);
}

int main(int argc, char **argv) {
   char *bar;

   foo(&bar);

   return 0;
}

そもそもこれがあってるのかという話もありますが、


void foo(char *bar) {
   bar = (char *)malloc(sizeof(char)*10);
}

ってやるとコンパイラに怒られるんだもん。
C++だとこんな感じ?


class Hoge {
public:
   Hoge(){}
   ~Hoge(){}

   int a;
};

void hogeUser(Hoge **hoge) {
   *hoge = new Hoge();
}

int main(int argc, char **argv) {
   Hoge *hoge;

   hogeUser(&hoge);

   return 0;
}

しかしこれ、以下のように書けた。


void hogeUser(Hoge *(&hoge)) {
   hoge = new Hoge();
}

int main(int argc, char **argv) {
   Hoge *hoge;

   hogeUser(hoge);

   return 0;
}

でもひょっとしたら動いてないかもしれない。デバッグ中に奇妙に勝手に終了することがあった(アクセス違反)。
関係ないところだったけど、これが影響しているのかもしれない。

「あほやん」と言う人は教えてください。

以上

Home > C++ Archive

Return to page top