オフラインリアルタイムどう書く E22 の実装例(腕力)

問題 : http://nabetani.sakura.ne.jp/hena/orde22numord/
解答リンク集 : https://qiita.com/Nabetani/items/99e38a39165e1905b415

非OpenMP版

まずは、並列実行しないバージョン。

//g++-7 -std=c++14 -O3 slow.cpp && time ./a.out -> real  3m16.642s
//clang++ -std=c++14 -O3 slow.cpp && time ./a.out -> real  2m27.300s
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

array<char,32> tostr( int n, int b )
{
  array<char,32> s;
  array<char,32> m;
  int i=0;
  while( 0<n ){
    m[i]=(n%b)+'0';
    n/=b;
    ++i;
  }
  for( int j=0 ; j<i ; ++j ){
    s[j] = m[i-j-1];
  }
  s[i]=0;
  return s;
}

int tonum(array<char,32> const & c, int b )
{
  int r=0;
  for( int pos=0 ; c[pos] ; ++pos ){
    r*=b;
    r+=c[pos]-'0';
  }
  return r;
}

int solve( int m, int n, int b, int x )
{
  int size = n-m+1;
  vector<array<char,32>> c(size);
  for( int i=0; i<size ; ++i ){
    c[i] = tostr( i+m, b );
  }
  std::sort(c.begin(), c.end(), [](array<char,32> const & a, array<char,32> const & b )->bool {
    return strcmp(a.data(), b.data())<0;
  });
  return tonum(c.at(x-1), b);
}

void test( char const * src, char const * expected )
{
  char * p;
  int m=strtol( (char*)src, &p, 10 );
  int n = strtol(p+1, &p, 10 );
  int b = strtol(p+1, &p, 10 );
  int x = strtol(p+1, &p, 10 );
  int actual = solve( m, n, b, x );
  int exp = atoi( expected );
  cout << ( actual==exp ? "ok" : "**NG**" ) << " " << src << " / " << actual << " / " << exp <<"\n";
}

int main()
{
  /*0*/ test( "2,15,3,8", "14" );
  /*1*/ test( "6,8,8,1", "8" );

  // 中略

  /*35*/ test( "26065964,66252692,18,29196596", "63208819" );
  /*36*/ test( "66097362,104618756,16,32740764", "98838125" );
}

clang の方が速かった。

OpenMP版

これを、 ciel さんの記事 を参考にして OpenMP を使ってみると、こんな感じ：

//g++-7 -std=c++14 -O3 -fopenmp slow_omp.cpp && time ./a.out -> real 0m50.694s
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <omp.h>
#include <parallel/algorithm>

using namespace std;

array<char,32> tostr( int n, int b )
{
  array<char,32> s;
  array<char,32> m;
  int i=0;
  while( 0<n ){
    m[i]=(n%b)+'0';
    n/=b;
    ++i;
  }
  for( int j=0 ; j<i ; ++j ){
    s[j] = m[i-j-1];
  }
  s[i]=0;
  return s;
}

int tonum(array<char,32> const & c, int b )
{
  int r=0;
  for( int pos=0 ; c[pos] ; ++pos ){
    r*=b;
    r+=c[pos]-'0';
  }
  return r;
}

int solve( int m, int n, int b, int x )
{
  int size = n-m+1;
  vector<array<char,32>> c(size);
#pragma omp parallel for
  for( int i=0; i<size ; ++i ){
    c[i] = tostr( i+m, b );
  }
  __gnu_parallel::sort(c.begin(), c.end(), [](array<char,32> const & a, array<char,32> const & b )->bool {
    return strcmp(a.data(), b.data())<0;
  });
  return tonum(c.at(x-1), b);
}

void test( char const * src, char const * expected )
{
  char * p;
  int m=strtol( (char*)src, &p, 10 );
  int n = strtol(p+1, &p, 10 );
  int b = strtol(p+1, &p, 10 );
  int x = strtol(p+1, &p, 10 );
  int actual = solve( m, n, b, x );
  int exp = atoi( expected );
  {
    cout << ( actual==exp ? "ok" : "**NG**" ) << " " << src << " / " << actual << " / " << exp <<"\n";
  }
}

int main()
{
  /*0*/ test( "2,15,3,8", "14" );
  /*1*/ test( "6,8,8,1", "8" );

  // 中略

  /*35*/ test( "26065964,66252692,18,29196596", "63208819" );
  /*36*/ test( "66097362,104618756,16,32740764", "98838125" );
}

OpenMP と __gnu_parallel::sort のパワーで4倍近く速くなった。すごい。

tostr がもうちょっと速くなる気もするんだけど、今日のところはこれぐらいで。