n人中m人が当選するくじ in Other DouKaku?

n人の中から公平にm人を選ぶ、くじ引きプログラムを作ってください。

GPU向けの言語であるCUDAで作成してみました。
誰もうれしくないと思いますが、こんなのもあるんだね、とでも思って下さい。

CUDAに乱数生成関数がないため、本家サンプルの乱数生成を利用しています。

コア部分のアルゴリズムは#54の解釈を利用したので超簡単ですが、GPU駆動のコードのため伸びまくりです。かっこ悪い。

see: MersenneTwister@NVIDIA CUDA SDK Code Samples

float *d_Rand; // GPU上で利用する変数
float *h_Rand=NULL; // CPU上で利用する変数

// GPU上で乱数を生成するための関数。中身は本家サンプルを利用しているので割愛。
// d_Rand/h_Randに乱数がぶち込まれると解釈してください。
void initMTGPU()
{
  CUDA_SAFE_CALL( cudaMalloc((void **)&d_Rand, RAND_N * sizeof(float)) );
  RandomGPU<<<32, 128>>>(d_Rand, N_PER_RNG, SEED);
  CUT_CHECK_ERROR("RandomGPU() execution failed\n");
  CUDA_SAFE_CALL(cudaMallocHost((void**)&h_Rand, sizeof(float)*RAND_N));
  CUDA_SAFE_CALL(cudaMemcpy(h_Rand, d_Rand, sizeof(float)*RAND_N, cudaMemcpyDeviceToHost));
}

// コア部分。#54の解釈を利用。乱数の種は適当に設定。
#define RAND_SEED 5
__global__ void gpu(float *d_Random, int *answer, int n, int m)
{
  int i, j=0;
  int begin = d_Random[RAND_SEED] * (float)n;
  for(i=begin; i<begin+m; i++){
    answer[j++] = i % n;
  }
}

// くじ引き関数。answerに答えの数列が格納されます。
int lot(int *answer, int n, int m)
{
  CUT_DEVICE_INIT();

  initMTGPU();
  int *d_mem;
  CUDA_SAFE_CALL(cudaMalloc((void**)&d_mem, sizeof(int)*m));
  CUDA_SAFE_CALL(cudaMemcpy(d_Rand, h_Rand, sizeof(float)*RAND_N, cudaMemcpyHostToDevice));
  dim3 threads(1, 1, 1);
  dim3 grid(1,1,1);
  gpu<<< grid, threads >>>(d_Rand, d_mem, n, m);
  CUDA_SAFE_CALL( cudaThreadSynchronize() );
  CUT_CHECK_ERROR("Kernel execution failed");
  CUDA_SAFE_CALL(cudaMemcpy(answer, d_mem, sizeof(int)*m, cudaMemcpyDeviceToHost));

  CUDA_SAFE_CALL(cudaFree(d_mem));
  CUDA_SAFE_CALL(cudaFreeHost(h_Rand));
  return 0;
}

#define N_ALLSIZE 100
#define N_HITSIZE 5

int main(int argc, char** argv)
{
  int answer[N_HITSIZE];
  lot(answer, N_ALLSIZE, N_HITSIZE);

  int i;
  for(i=0; i<N_HITSIZE; i++){
    printf(" %d", answer[i]);
  }
  printf("\n");
}

Limbo習作。
rand, daytime, stringモジュールのテスト。

すでにLimboでいっぱい書いている方がいるようなので、遠慮がちに・・・

# file: d4.b
# Lottery

implement d4;

include "sys.m";
include "draw.m";
include "string.m";
include "rand.m";
include "daytime.m";

sys: Sys;
usage: fn(prog: string);

d4: module
{
    init: fn(ctxt: ref Draw->Context, argv: list of string);
};

init (ctxt: ref Draw->Context, argv: list of string)
{
    str: String;
    rand: Rand;
    time: Daytime;
    n, m, i, val: int;
    prog: string;

    sys = load Sys Sys->PATH;
    str = load String String->PATH;
    rand = load Rand Rand->PATH;
    time = load Daytime Daytime->PATH;

    prog = hd argv;

    argv = tl argv;
    if(argv == nil){
        usage(prog);
        return ;
    }
    (n, nil) = str->toint(hd argv, 10);

    argv = tl argv;
    if(argv == nil){
        usage(prog);
        return;
    }
    (m, nil) = str->toint(hd argv, 10);

    if(m == 0 || n == 0 || n < m){
        usage(prog);
        return;
    }

    flags := array [n] of int;
    for(i = 0; i < n; i++){
        flags[i] = 0;
    }

    rand->init(time->now());
    while(m > 0){
        val = rand->rand(n);
        if(flags[val] == 0){
            flags[val] = 1;
            m --;
        }
    }

    for(i = 0; i < n; i++){
        if(flags[i]){
            sys->print("%d ", i + 1);
        }
    }
    sys->print("\n");
}

usage (prog: string)
{
    sys->print("usage: %s n m\n", prog);
}

DouKaku?

n人中m人が当選するくじ

Posted feedbacks - Other

Index

Feed

Other

Link

Pathtraq