2018-11-22

Kahan summation algorithmを試してみました。

Algorithm

発端

0.01f を 10000 回足すと 100.003f になる話に関連して、カハンの加算アルゴリズムを使うと、浮動小数点数の合計を求めるときの誤差を減らせることも知っておきたい https://t.co/Ctrz6V3QQ6 pic.twitter.com/FPPrUG2v8W
— Ryo Suzuki (@Reputeless) 2018年11月19日

発端はこの@Reputelessさんのツイートからです。

コンピューターが発明された以後、そして２進数が発明してメモリ領域のあらゆる値を表現するにとって採用されてから浮動小数点は大きな数まで表現できるようになりました。

しかし浮動小数点は整数とは表現が違って浮動小数点は単なる２進数の羅列じゃなくIEEE754という表現の規定にそってメモリの領域の２進数を操ります。そしてその表現による重大な問題があります。

すべての素数を完全に表現することができないという事です。何故ならIEEE754の表現によると、0.01みたいな素数てんは２進数でぴったりと表現できることができません。0.5 0.25のように２で割れられる小数点は誤差なしに表現できますが、0.01の場合には実際には0.001000001みたいになってしまいます。

勿論浮動小数点一つ一つの誤差は大きくないですが、問題はこの浮動小数点を何千回も演算すると誤差が大きくなって、望ましい値とはだいぶ違ってしまいます。その誤差による演算が違ってしまうのを防ぐために開発されたのがPairwise summationかKahan Summation Algoritihmです。今回はPairwiseの代わりにKahanを取り上げてみたいと思います。

説明

Kahan summation algorithm - Wikipedia

Kahan summation algorithmは浮動小数点の演算の際に正確度の欠如による誤差を減らす為のアルゴリズムである。Pairwise summation algorithmとは違いリストの形で一連の浮動小数点を渡さなくても、実時間で補正を行うことができる。

浮動小数点をN個演算するときに、最悪の場合Nに比例して誤差（Error）が大きくなる傾向がある。しかし演算するときに補正を行うと最悪の場合にもエラーバウンドはNに独立となり、ただ今使っている浮動小数点の正確度だけに依存するようになる。

実装コード

void KahanProcess(std::vector<float>& input)
{
  auto com = 0.0f;

  for (const auto& value : input)
  {
    const auto y  = value - com;
    const auto t  = kahanSum + y;
    com           = (t - kahanSum) - y; 
    (void)com;
    kahanSum      = t;
  }
}

このアルゴリズムで注目すべきのところはcomに補正を入れて、浮動小数点の正確度の欠如によるアンダフローを防ぐことだと思います。そして浮動小数点ごとの補正を演算するために、今までの合計を引き算してcomを求めます。

Neumaier-Summationという、Kahanからより正確に補正を行うアルゴリズムも存在します。

結果

私がテストしたコードではstd::vector<>に1,000,000個の0.01fを入れてこれらを和して10,000.0からいくらの誤差が出るかを検証します。そしてコード演算の結果、このように出ました。

PS C:\Users\jmyun\Documents\Dev\SH-Algorithm\Algorithm\KahanCompensation> .\a.exe
Test "Plain-Sum" took 1415200ns.
Test "Kahan-Sum" took 5268500ns.
Expected : 10000.000000
Given(Plain-Sum) : 9865.223633
Given(Kahan-Sum) : 10000.000000

普通（Plain）に小数点を和したのは9865.224の10000から随分離れた数値が出たのが分かりますが、Kahanを使用すると補正により10,000.0が求められるのを確認できます。勿論補正のための追加演算が行われますので普通の和よりはだいぶ遅いです。

そのためのPairwise-Summationというまた別の和演算補正アルゴリズムがありますが、そちらは誤差がO(lgN)に比例している短所や浮動小数点をまとめたリストの形で渡さなければならない短所があります。（だとしてもPlainよりは誤差がほぼないです。）

参照

Kahan summation algorithm - Wikipedia

Pairwise summation - Wikipedia

2018-11-21

Chapter 3 Typelists メモ (1)

C++

Typelists

Typelistというのは支援する値に関した一連の型をリスト化して提供する道具である。３章ではこのTypelistを実装する。
Typelistが有用に使用されるところは、Abstract Factoryか、Visitorパターンでよく使われる。

3.2 Defining Tyeplists ~ 3.6 Indexed Access

Typelistは２つのタイプを持つことができる。この２つのタイプの別称をHead、Tailと呼ぶ。そしてTypelistのTailにまた別のTypelistをつけて複数のタイプを持つように調整することもできる。
しかし、タイプが複数存在する場合には、最後の型をもう以上締めるということでNullTypeという別のタイプを使って閉まる。これによってHalf-opened rangeが構成できる。
Typelistに複数の型を用意するには一つ一つ書く方法もあるけど、本にはMacroを使って個数ごとにマクロを使用して簡単にTypelistリストを作成できるようにした。しかし、僕はマクロを使わずにTypelistPackage::typeを実装して、可変長型引数を入れてリストを作るようにした。
length変数テンプレートはTypelistリストに対していくつかの型を貯めているかを示す。NullTypeの場合には０を返す。

#include <type_traits>

struct NullType final {};

template <class T, class U>
struct Typelist final {
    using Head = T;
    using Tail = U;
};

template <class... TArgs>
struct TypelistPackage final {
private:
    template <class... TTypeArgs>
    struct Constructor;

    template <class TType>
    struct Constructor<TType> final { using type = Typelist<TType, NullType>; };

    template <class TType, class... TTypeArgs>
    struct Constructor<TType, TTypeArgs...> final { 
        using type = Typelist<TType, typename Constructor<TTypeArgs...>::type>; 
    };

public:
    using type = typename TypelistPackage::Constructor<TArgs...>::type;
};

template <class TList> 
constexpr unsigned int length = 0;
template <> 
constexpr unsigned int length<NullType>  = 0;
template <class TT, class TU> 
constexpr unsigned int length<Typelist<TT, TU>> = 1 + length<TU>;

using Charlist = TypelistPackage<char, signed char, unsigned char>::type;
using SingedInts = TypelistPackage<signed char, short int, int, long int>::type;

static_assert(length<SingedInts> == 4, "");

TypeAtはTypelistのリストからインデックス番地にある型を取り出すために作られたものである。
本で主要に扱われているライブラリーのLokiでは、このTypeAtのデフォルト値を返すバージョンであるTypeAtNonStrictも実装されている。
Typelistを使用し番地を探索することはリストや番地の数が多いばあい、ビルドタイムの低下を招きやすい。

template <class TList, unsigned int TIndex>
struct TypeAt;
template <class THead, class TTail>
struct TypeAt<Typelist<THead, TTail>, 0> final { 
    using type = THead; 
};
template <class THead, class TTail, unsigned int TIndex>
struct TypeAt<Typelist<THead, TTail>, TIndex> final { 
    using type = typename TypeAt<TTail, TIndex - 1>::type; 
};

static_assert(std::is_same_v<TypeAt<SingedInts, 1>::type, short int>, "");

3.7 Searching Typelists ~ 3.9 Erasing a Type from a Typelist

IndexOfは任意のTypelistに任意の型Tを入れると、Typelistにある型リストから当てはまる型のインデックスを返すようにする。
もしNullTypeか型を探せなかったら, -1を返す。

template<class TList, class TTarget> struct IndexOf;
template <class TTarget>
struct IndexOf<NullType, TTarget> { enum { value = -1 }; };
template <class TTarget, class TTail>
struct IndexOf<Typelist<TTarget, TTail>, TTarget> final {
    enum { value = 0 };
};
template <class THead, class TTail, class TTarget> 
struct IndexOf<Typelist<THead, TTail>, TTarget> final {
private:
    enum { temp = IndexOf<TTail, TTarget>::value };
public:
    enum { value = temp == -1 ? -1 : temp + 1 };
};

using SignedIntegrals = SingedInts;
static_assert(IndexOf<SingedIntegrals, int>::value == 2, "");

Appendを使用してTypelistを既存のTypelistに入れたり、単一タイプをTypelistに入れるようにする。再起を用いて既存のTypelistのNullType部分を入れ替えるようにした。

template <class TList, class TType> struct Append;
template <>
struct Append<NullType, NullType> { using type = NullType; };
template <class TTarget>
struct Append<NullType, TTarget> { using type = Typelist<TTarget, NullType>; };
template <class THead, class TTail>
struct Append<NullType, Typelist<THead, TTail>> {
    using type = Typelist<THead, TTail>;
};
template <class THead, class TTail, class TTarget>
struct Append<Typelist<THead, TTail>, TTarget> {
    using type = Typelist<THead, typename Append<TTail, TTarget>::type>;
};
template <class TList, class TType>
using Append_T = typename Append<TList, TType>::type;

using Charlist          = TypelistPackage_T<char, signed char, unsigned char>;
using OneTypeOnly       = TypelistPackage_T<int>;
using SingedIntegrals   = TypelistPackage_T<signed char, short int, int, long int>;

using SignedIntegralsAdded = Append_T<SingedIntegrals, char>;
static_assert(IndexOf_V<SignedIntegralsAdded, char> == 4, "");
static_assert(IndexOf_V<SignedIntegralsAdded, int> == 2, "");

using Integrals = Append_T<
    SingedIntegrals, 
    TypelistPackage_T<unsigned char, unsigned short, unsigned, unsigned long>
>;
static_assert(IndexOf_V<Integrals, unsigned> == 6, "");
static_assert(IndexOf_V<Integrals, int> == 2, "");

EraseはTypelistから特定のタイプを取り外す役割をする。本ではEraseと再帰を行うEraseAllが実装しているが私の場合にはbool定数を使ってEraseだけで処理を行うようにした。

template <class TList, class TType, bool TIsAll> struct Erase;
template <class TType, bool TIsAll>
struct Erase<NullType, TType, TIsAll> { using type = NullType; };
template <class TTail, class TType>
struct Erase<Typelist<TType, TTail>, TType, false> { using type = TTail; };
template <class TTail, class TType>
struct Erase<Typelist<TType, TTail>, TType, true> { 
    using type = typename Erase<TTail, TType, true>::type; 
};
template <class THead, class TTail, class TType, bool TIsAll>
struct Erase<Typelist<THead, TTail>, TType, TIsAll> { 
    using type = Typelist<THead, typename Erase<TTail, TType, TIsAll>::type>; 
};
template <class TList, class TType, bool TIsAll = false>
using Erase_T = typename Erase<TList, TType, TIsAll>::type;

using IntegralsExceptChar = Erase_T<SingedIntegrals, char>;
static_assert(IndexOf_V<IntegralsExceptChar, char> == -1, "");
using CharChunk = TypelistPackage_T<char, char, int, int, char, char>;
static_assert(length<Erase_T<CharChunk, char, true>> == 2, "");

3.10 Erasing Duplicates ~ 3.11 Replacing an Element in a Typelist

Typelistに存在する重複する型を一つに締め付けるために、AlignTypelistを実装する。実装するに以前に実装ｓしたEraseを活用する。
しかしEraseを活用するときに注意するところはTIsAllがfalseというところである。なぜなら、__type1を型引数として使用してEraseを行う。そして__type1は再帰的にAlignTypelistを既に行ってから結果として出すTypelist型を使用する。そのため、再帰的にEraseする必要が無くなる。

template <class TList> struct AlignTypelist;
template <>
struct AlignTypelist<NullType> { using type = NullType; };
template <class THead, class TTail>
struct AlignTypelist<Typelist<THead, TTail>> {
private:
    using __type1 = typename AlignTypelist<TTail>::type;
    using __type2 = Erase_T<__type1, THead>;
public:
    using type = Typelist<THead, __type2>;
};
template <class TList>
using AlignTypelist_T = typename AlignTypelist<TList>::type;

using CharChunk = TypelistPackage_T<char, char, int, int, char, char>;
using AlignedCharChunk = AlignTypelist_T<CharChunk>;
static_assert(1
    && length<AlignedCharChunk> == 2
    && std::is_same_v<TypeAt_T<AlignedCharChunk, 0>, char>
    && std::is_same_v<TypeAt_T<AlignedCharChunk, 1>, int>, "MUST BE SUCCEEDED."
);

Replaceは特定の型を探して別の型に入れ替えることを受け取っている。そしてEraseの再帰バージョンのようにReplaceもIsApplyAll<false> IsApplyAll<true>を使用して再帰かないかを定められる。

template <class TList, class TTarget, class TReplace, class TIsApplyAll>
struct Replace;
template <class TList, class TTarget, class TReplace, class TIsApplyAll>
using  Replace_T = typename Replace<TList, TTarget, TReplace, TIsApplyAll>::type;
template <class TTarget, class TReplace, class TIsApplyAll>
struct Replace<NullType, TTarget, TReplace, TIsApplyAll> { 
    using type = NullType; 
};
template <class TTail, class TTarget, class TReplace>
struct Replace<Typelist<TTarget, TTail>, TTarget, TReplace, IsApplyAll<false>> {
    using type = Typelist<TReplace, TTail>;
};
template <class TTail, class TTarget, class TReplace>
struct Replace<Typelist<TTarget, TTail>, TTarget, TReplace, IsApplyAll<true>> {
    using type = Typelist<
        TReplace, 
        Replace_T<TTail, TTarget, TReplace, IsApplyAll<true>>
    >;
};
template <class THead, class TTail, class TTarget, class TReplace, class TIsApplyAll>
struct Replace<Typelist<THead, TTail>, TTarget, TReplace, TIsApplyAll> {
    using type = Typelist<
        THead, 
        Replace_T<TTail, TTarget, TReplace, TIsApplyAll>
    >;
};

using CharChunk = TypelistPackage_T<char, char, int, int, char, char>;
static_assert(
    std::is_same_v<
        TypeAt_T<
            AlignTypelist_T<Replace_T<CharChunk, char, short, IsApplyAll<true>>
        >, 0>
    , short>, 
    "MUST BE SUCCEEDED."
);

2018-11-18

C++で大きな整数の掛け算を実装してみよう。

C++

実装した理由。

アルゴリズムの本を呼んで勉強していたところ、物凄く気になってやって見たかったものがあったからです。

「からツバ法」

カラツバ法 - Wikipedia

これによって大きな整数たちの掛け算の計算コストを f:id:neuliliilli:20181025112041p:plain にすることが出来ます。以前の力任せで f:id:neuliliilli:20181025112126p:plain にした方法より単位が大きい場合にはものすごく速くなります。しかし整数たちの単位が少ない場合には「からつば法」によるコストが悪い為、ただの力任せでやるほうが速くなります。

コード全文

/// Karatsuba equation (カラツバ法) (N^lg3) using divide and conquer
/// a  = a1|a0
/// b  = b1|b0
///
/// z0 = a1 * b1
/// z2 = a0 * b0
/// z1 = (a1 + a0) * (b1 + b0) - z0 - z2;
///
/// a * b = z0 * 10^(half<<1) + z1 * 10^(half) + z2
///

#include <vector>
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <string>
#include <algorithm>
#include <stdexcept>

#define _MIN_
#define _MOUT_
#define _MINOUT_
#define M_BEGIN_END(__MA__) __MA__.begin(), __MA__.end()
#define M_RBEGIN_REND(__MA__) __MA__.rbegin(), __MA__.rend()

class BigInteger final
{
public:
  BigInteger(_MIN_ const int64_t value) noexcept
  {
    this->mIsNegative = ((value >> 63) & 0b1) == true;
    int64_t _val = this->mIsNegative ? (value * -1) : value;
    while (_val != 0)
    {
      mValue.emplace_back(_val % 10);
      _val /= 10;
    }
  };

  BigInteger(_MIN_ const std::string &value) : mIsNegative{false}
  {
    if (value.empty() == false)
    {
      int32_t startId = 0;
      const int32_t len = static_cast<int32_t>(value.size());
      if (value[0] == '-')
      {
        this->mIsNegative = true;
        startId = 1;
      }
      for (int32_t i = len - 1; i >= startId; --i)
      {
        if (value[i] < '0' || value[i] > '9')
        {
          throw std::runtime_error("value is not numeric character.");
        }
        this->mValue.emplace_back(value[i] - '0');
      }
    }
  }

  [[nodiscard]] std::string ToString() const noexcept
  {
    auto it = std::find_if(M_RBEGIN_REND(this->mValue), [](const uint8_t &val) { return val != 0; });
    if (it == this->mValue.rend()) { return "0"; }
    else
    {
      std::string result = {};
      if (this->mIsNegative == true) { result += '-'; }

      for (; it != this->mValue.rend(); ++it) { result += *it + '0'; }
      return result;
    }
  }

  [[nodiscard]] friend BigInteger operator*(_MIN_ const BigInteger &a, _MIN_ const BigInteger &b) noexcept
  { // Use karatsuba equation! O(N^(lg3))
    // * N is maximum unit
    return BigInteger::__KaratsubaMultiplyEntry(a, b);
  }

private:
  using TContainer = std::vector<int16_t>;
  BigInteger(_MIN_ const BigInteger::TContainer &valueContainer, _MIN_ const bool isNegative) noexcept
  {
    this->mValue = valueContainer;
    this->mIsNegative = isNegative;
  }

  [[nodiscard]] static BigInteger
  __KaratsubaMultiplyEntry(_MIN_ const BigInteger &a, _MIN_ const BigInteger &b) noexcept
  {
    const TContainer unsignedResult = BigInteger::__ProcessKaratsuba(a.mValue, b.mValue);
    const bool isNegative = (a.mIsNegative ^ b.mIsNegative) == true;

    const BigInteger result{unsignedResult, isNegative};
    return result;
  }

  [[nodiscard]] static TContainer
  __ProcessKaratsuba(_MIN_ const TContainer &a, _MIN_ const TContainer &b) noexcept
  {
    const int32_t aUnitSize = static_cast<int32_t>(a.size());
    const int32_t bUnitSize = static_cast<int32_t>(b.size());
    // Integrity  : If aUnitSize is smaller than bUnitSize, swap each other and execute.
    if (aUnitSize < bUnitSize) { return __ProcessKaratsuba(b, a); }
    // Base  : If aUnitSize or bUnitSize is 0 (no value), just return 0.
    if (aUnitSize == 0 || bUnitSize == 0) { return TContainer(0); }
    // Base : If aUnitSize or bUnitSize is 2, just multiply each other O(N^2) but might be fast.
    if (aUnitSize <= 2) { return BigInteger::__Multiply(a, b); }

    // Normal case...
    const int32_t halfUnit = aUnitSize / 2;
    TContainer a0(a.begin(), a.begin() + halfUnit);
    TContainer a1(a.begin() + halfUnit, a.end());
    TContainer b0(b.begin(), b.begin() + std::min(halfUnit, bUnitSize));
    TContainer b1(b.begin() + std::min(halfUnit, bUnitSize), b.end());

    // z0 = a1 * b1, z2 = a0 * b0
    const TContainer z0 = __ProcessKaratsuba(a1, b1);
    const TContainer z2 = __ProcessKaratsuba(a0, b0);

    // a1 + a0, b1 + b0
    const TContainer ar = __KaratsubaAddContainer(a1, 0, a0);
    const TContainer br = __KaratsubaAddContainer(b1, 0, b0);
    // calculate z1
    TContainer z1 = __ProcessKaratsuba(ar, br);
    __KaratsubaSubFrom(z1, z0);
    __KaratsubaSubFrom(z1, z2);

    // calculate a * b finally!
    TContainer result = {};
    result = __KaratsubaAddContainer(z2, 0, result);
    result = __KaratsubaAddContainer(z1, halfUnit, result);
    result = __KaratsubaAddContainer(z0, halfUnit * 2, result);
    __Normalize(result);
    return result;
  }

  ///
  /// @brief a * 10^k + b
  ///
  [[nodiscard]] static TContainer
  __KaratsubaAddContainer(_MIN_ const TContainer &a, _MIN_ const uint32_t k, _MIN_ const TContainer &b) noexcept
  {
    const int32_t len = static_cast<int32_t>(a.size());

    TContainer result = b;
    result.resize(std::max(b.size(), a.size() + k) + 1);

    for (int32_t i = 0; i < len; ++i)
    {
      result[i + k] += a[i];
      if (result[i + k] > 10)
      {
        result[i + k] -= 10;
        result[i + k + 1] += 1;
      }
    }

    while (result.size() > 1 && result.back() == 0) { result.pop_back(); }
    return result;
  }

  [[nodiscard]] static TContainer
  __Multiply(_MIN_ const TContainer &a, _MIN_ const TContainer &b) noexcept
  {
    const int32_t aUnitSize = static_cast<int32_t>(a.size());
    const int32_t bUnitSize = static_cast<int32_t>(b.size());
    // Integrity Check : If aUnitSize is smaller than bUnitSize, swap each other and execute.
    if (aUnitSize < bUnitSize) { return __Multiply(b, a); }

    TContainer result(aUnitSize + bUnitSize + 1, 0);
    for (int32_t i = 0; i < bUnitSize; ++i)
    {
      for (int32_t j = 0; j < aUnitSize; ++j)
      {
        result[i + j] += a[j] * b[i];
      }
    }

    __Normalize(result);
    return result;
  }
  static void __KaratsubaSubFrom(_MOUT_ TContainer &a, _MIN_ const TContainer &b) noexcept
  { // Assertion
    assert(a.size() >= b.size());
    // Body
    int len = b.size();
    a.resize(std::max(a.size(), b.size()) + 1);

    for (int i = 0; i < len; i++)
    {
      a[i] -= b[i];

      if (a[i] < 0)
      {
        a[i] += 10;
        a[i + 1] -= 1;
      }
    }
  }

  ///
  /// @brief Normalize value container and reflect carry or borrow flag to container.
  /// @param value Value container to be updated.
  ///
  static void __Normalize(_MINOUT_ TContainer &value) noexcept
  {
    value.push_back(0);
    //
    const int32_t len = static_cast<int32_t>(value.size());
    for (int i = 0; i < len; ++i)
    {
      if (value[i] < 0)
      {
        int32_t borrow = (std::abs(value[i]) + 9) / 10;
        value[i + 1] -= borrow;
        value[i] += borrow * 10;
      }
      else
      {
        value[i + 1] += value[i] / 10;
        value[i] %= 10;
      }
    }
    //
    while (value.size() > 1 && value.back() == 0) { value.pop_back(); }
  }

  /// Example) integer value 1258
  /// [0][1][2][3]
  ///  8  5  2  1
  TContainer mValue = {};
  bool mIsNegative : 1;
};

//!
//! Example
//!

int main()
{
  std::printf("Result is %s\n", (BigInteger("-12345678901234567890") * BigInteger("9876543210987654321")).ToString().c_str());
  std::printf("Result is %s\n", (BigInteger("3427350981709347230968723049827105342342") * BigInteger("98427038974902731329876543210987654321")).ToString().c_str());
}

Result is -121932631137021795223746380111126352690
Result is 337344008657377058152329638352568707324009767133475478830316644492106260559782

2018-11-18

취업 분석 (ATLUS, SPI 잡다...)

Memo

ATLUS 2019년도 채용 요강

2018년 3월 1일부터 응모 접수를 시작함.
응모 직종은 시스템 플래너, 시나리오 플래너, 디자이너, 프로그래머, 사운드 크리에이터, 종합직이 있음.
프로그래머는 게임의 제작에 있어서 각종 소프트웨어의 코딩과 각종 개발 툴의 작성, 메인테넌스를 하는 직종.

ATLUS 선고 플로우

3월에서 5월까지 마이나비로 엔트리
3월에서 5월까지, 각 직종의 응모 서류와 우편 배송으로... 1차는 4월 10일, 2차 는 5월 10일 까지. 엔트리 만으로는 정식 응모가 안되고, 서류를 제출을 해야 됨.
4월에서 6월까지 서류 심사, 선고.
4월에서 6월까지 일차 면접.
4월에서 7월까지 이차 면접.
5월에서 7월까지 SPI 테스트, 최종 면접.
5월에서 7월까지 내내정 발표.

7월까지 다 끝나는 것을 알 수 있음.

2019년도 신졸 채용 각종별 응모 서류 (프로그래머)

사진을 첨부한 이력서
앙케이트를 프린트해서 적은 것.
게임과 툴 프로그램 (실행파일과 소스) 및 그 설명문. 여기서 중요한 것은 자기가 담당한 부분과, 어필 포인트, 사용 방법, 고생한 부분, 토리쿤다 부분, 개발 기간, 사용 툴 등 을 상세히 설명문으로 적을 것. 또한 ATLUS 는 C/C++ 로 만든 프로그램을 필수로 함. 제출 모체에도 분실 방지를 위해 씨명을 적어서 우편 배송할 것.

ATLUS 대우 및 조건

게임 업계 미경험자 가능
모국어를 일본어로 하지 않는 한, JLPT 1급을 따는 것을 전제로 할 것.
ATLUS 당사에서 입사할 때는 계약사원으로, 평가에 따라서 입사 후 1~3년 후에 정사원 등용의 기회가 있음.
계약 기간은 3 ~ 6 개월
시용 기간은 6 개월
月給23.0万円～44.0万円
심야 잔업 수당, 휴일 출근 수당, 통근 수당 제공.
승급은 연 1월 4월달에 실시
토, 일, 축일, 연말연시 및 연차유급휴가 제공. 경조사 휴가 제공.
시간 외 노동(잔업)으로는 평균 월당 약 30시간.
면접 시에는 외국 사람은 직접 일본 본사로 방문할 필요가 있음.
연수는 新卒入社の場合、入社後約一ヶ月間は、セガグループ全体の新人研修を受講します。

ATLUS 에서 만든 게임들

진여신전생 시리즈
페르소나 시리즈
캐서린 시리즈
세계수의 미궁 시리즈
등등...

`SPI 테스트` 라고 하는 것은?

saisokuspi.com

https://goo.gl/Nk6FSF

Synthetic Personality Inventory 의 약자로 능력 검사와 성격 검사를 합친 개인의 자질을 종합적으로 파악하는 검사. 이다. 인적성 검사와 비슷하다.
일본의 기업 중 70% 이상이 이 SPI 을 채택하고 있기 때문에 기술 면접과 더불어 반드시 준비 해야함.
SPI 는 비언어, 언어파트 두 파트로 구분이 되며, 수리, 추론, 방정식, 시사, 독해 등의 다양한 분야의 문제가 출제됨.
인적성 검사와 비슷하기 때문에 시간이 촉박함.
시중에 나와있는 SPI 문제집을 구매하거나, 무료 학습 사이트를 이용해서 감을 익힐 것.

도움이 될 만한 사이트 링크

dreaminsite.tistory.com

2018-11-17

Chapter 1 Memo (1)

C++

1.5 Policies & Policy Classes

Policy Classes : Determine arbitary but specific small behavior, but different from dynamic run-time interface. Each Policy classes are bound to compound user-custom type as template on compile time. This class type have more importance to syntactic construct that should be valid, rather than which exact functions that class must implement.
Host Classes : That classes that use one or more policies. Host are responsible for assembling the structures and behaviors of their policies in a single complex unit.

1.5.1 Implementing Policy Classes with Template Template Parameters

テンプレートテンプレートパラメータを使用して、各Policyクラスの継承での特殊化を行うことも出来る。
Template Template Parameterを使う時には、見た目に騙されずに型パラメータが一致するテンプレートクラスの基本型だけを入れること。

template <template <typename> class CreationPolicy>
class WidgetManager : public CreationPolicy<Widget> {};

using MyWidgetMgr = WidgetManager<OpNewCreator>;

これを使って、同じPolicyを使用して別の型を特殊化したクラスで提供することもできるようになる。

// Library code
template <template <typename> class CreationPolicy>
class WidgetManager : public CreationPolicy<Widget> {
  // ...
  void DoSomething() {
    auto pW = CreationPolicy<Gadget>().Create();
    // ...
  }
};

Virtual Functionを使用することに似ているが、Policyは静的バインディングを使うので全てがコンパイルに処理される。そしてVtableなどの追加費用も費やさなくても済む。

1.5.2 Implementing Policy Classes with Template Member Functions

struct OpNewCreator {
  template <class TType>
  static T* Create() { return new TType(); }
};

Policyを作成するときに、Policyクラスに型引数をつけることではなくて指定したメンバー関数に型引数をつける方法もある。
しかしメンバー関数に型をつけるようとしたら、コード作成の維持補修が難しくなる。C++03以前のコンパイラーも支援するようにする長所もあるが、今どきとなってはこういうやり方をすすめるのは推薦できなさそう。

1.7 Destructors of Policy Classes

もしHostからPolicyへ型変換をするつもりであるなら、Policyで変換したものは絶対にPolicyのままで削除したりすることは出来ないようにしなければならない。そのため、こういうコードは禁じられている。

MyWidgetManager wm;
PrototypeCreator<Widget>* pCreator = &wm;
delete pCreator;

最後の行の実行によるUBを防止する為にはPolicyクラスのDestructorをVirtualにする方法もあるが、そうするとVtableが生じてしまう。
この本ですすめる方法は、DestructorをProtected以下の権限を持つようにしてPolicy型のインスタンスを削除できないようにコンパイルに任せることである。

template <class T>
struct OpNewCreator {
  static T* Create() { return new T; }
protected:
  ~OpNewCreator() {}
};

1.8 Optional Functionality Through Incomplete Instantiation

クラスTemplateのメンバー関数がコードで使わなかったら、そのメンバー関数はそのコードが特殊化した型によって結果的に正しいコードになるかを確認しない。

例えて、以下のようなコードがあるとする。

template <template <class> class CreationPolicy>
class WidgetManager : public CreationPolicy<Widget> {
  // ...
  void SwitchPrototype(Widget* pNewPrototype) {
    CreationPolicy<Widget>& myPolicy = *this;
    delete myPolicy.GetPrototype();
    myPolicy.SetPrototype(pNewPrototype);
  }
};

上記のコードは使い方によって３つの分析結果に分かれる。

もしCreatorが型をPrototypeを支援する型として特殊化したら、Specializedした型はSwitchPrototype関数を使える。
もしCreatorが型をPrototypeを支援すない型として特殊化してSwitchPrototype関数を使うとそのSwitchPrototype関数はコンパイラに分析され、そいてコンパイルエラーを吐き出す。
もしCreatorが型をPrototypeを支援すない型として特殊化してSwitchPrototype関数を使わなかったら、プログラムはコンパイルが通せる。

1.9 Combining Policy Classes

template<
  class TType, 
  template <class> class CheckingPolicy, 
  template <class> class ThreadingModel>
class SmartPtr;

using SafeWidgetPtr = SmartPtr<Widget, EnforceNotNull, SingleThreaded>;

上のコードのようにPolicyを適切に組み合わせして、モジュール化した効率が良いコードが書けることができる。

1.10 Customizing Structure with Policy Classes

データを貯蔵するものさえPolicyで変換できる。たとえば、SmartPtrはPointerをセーブするためにあるが、他の実装体ではHandleで処理することもある。

template <class T> class DefaultSmartPtrStorage {
public:
  using PointerType = T*;
  using ReferenceType = T&;
protected:
  PointerType GetPointer() { return ptr_; }
  void SetPointer(PointerType ptr) { ptr_ = ptr; }
private:
  PointerType ptr_ = nullptr;
};

そしてSmartPtrはこの様に実装する。

template <
  typename TType,
  template <class> class CheckingPolicy,
  template <class> class ThreadingModel,
  template <class> class Storage = DefaultSmartPtrStorage>
class SmartPtr;

1.11 Compatible and Incompatible Policies

一つのPolicyで派生した様々のPolicy Classの間にも適切に変換関数を用意しなければいけない。
Policyのクラス間の変換を効率よくする方法とは、Policyごとに変換ができるように実装することである。
Policyのクラス間の変換をよりよくする為には変換するクラスを元としたConstructorか、Conversionオペレーターを実装する方が望ましい。
だとしても、Policyクラス間の変換には適切な政策を考えて実装すべき。

1.12 Decomposing a Class into Policies

とあるクラスで複数の行動があるとしたら、その行動が複数で処理できるようになればこの行動はPolicyの適用が出来るデザインを持つ。
typedefまたはusingを積極的に使うべき。
Policyを実装するときには、他のPolicyまたはサイドエフェクトを起こさないように、即ちお互いに垂直的の実装政策を持つこと。
垂直的ではないPolicy政策を実装しようとしたら、そのお互いでの連絡手段を実装しなければいけない。だとしてもそうすることによって複雑度が増しになる。

例を挙げて、ArrayというPolicyがあるとする。このポリシーはSmartPtrが配列を持っているか否かを確かめる為にある。

template <class TType>
struct IsArray {
  TType& ElementAt(TType* ptr, unsigned int index) noexcept {
    return ptr[index];
  }
  const TType& ElementAt(TType* ptr, unsigned int index) const noexcept {
    return ptr[index];
  }
};

template <class TType> struct IsNotArray {};

しかしこのポリシーには問題が潜在する。ポリシーによってdelete[]をするかdeleteをするかがサイドエフェクトとして存在してしまう。この削除を行うポリシーをDestructionだとしたら、このArrayとDestructionはお互いに垂直的でなくなってしまう。

結論を言うと、垂直的でPolicyを作って、そうでなくなければならない場合にはお互いの通信の為にBoolean整数を利用して伝送しかねない。

Overall

#include <cstdlib>
#include <type_traits>
#include <memory>

struct OPNewCreator {
    template <class TType>
    static std::unique_ptr<TType> Create() { return std::unique_ptr<TType>(new TType); }
};

struct MallocCreator {
    template <class TType>
    static std::unique_ptr<TType> Create() {
        void* buf = std::malloc(sizeof(TType));
        if (buf == nullptr) { return nullptr; }
        else                { return std::unique_ptr<TType>(new(buf) TType); }
    }
};

struct SmartNewCreator {
    template <typename TType>
    static std::unique_ptr<TType> Create() { return std::make_unique<TType>(); }
};

struct CompileValidityCheck final {
    template <typename...> struct DetachedParam {};
    template <template <typename TParam1> class TPolicy, typename TParam1>
    struct DetachedParam<TPolicy<TParam1>> {
        using TParamType1 = TParam1;
    };

    template <typename CompoundCreationPolicy>
    static constexpr bool IsSatisfiedCreationPolicy() {
        using TParamType1 = typename DetachedParam<CompoundCreationPolicy>::TParamType1;

        return false 
        || std::is_same_v<OPNewCreator<TParamType1>,CompoundCreationPolicy> 
        || std::is_same_v<MallocCreator<TParamType1>, CompoundCreationPolicy> 
        || std::is_same_v<SmartNewCreator<TParamType1>, CompoundCreationPolicy>;
    }
};

struct Widget {
    Widget() = default;
    int operator()() { return 997; }
};

template <class CreationPolicy>
class Manager : public CreationPolicy {
    CompileValidityCheck::DetachedParam<CreationPolicy> TPolicyParam;
    static_assert(
        CompileValidityCheck::IsSatisfiedCreationPolicy<CreationPolicy>, 
        R"(Can not create class that not satisfied "creation policy")");
};

int main() {
    Manager<OPNewCreator<Widget>> widgetManager;
    
    auto widget = widgetManager.Create();
    const auto returnValue = (*widget)();

    return returnValue;
}

NEUROMANTIC

自分でC/C++/UE4/Graphics/ゲームなどをやったことをメモするブログ

Kahan summation algorithmを試してみました。

発端

説明

実装コード

結果

参照

Chapter 3 Typelists メモ (1)

Typelists

3.2 Defining Tyeplists ~ 3.6 Indexed Access

3.7 Searching Typelists ~ 3.9 Erasing a Type from a Typelist

3.10 Erasing Duplicates ~ 3.11 Replacing an Element in a Typelist

C++で大きな整数の掛け算を実装してみよう。

実装した理由。

「からツバ法」

コード全文

취업 분석 (ATLUS, SPI 잡다...)

ATLUS 2019년도 채용 요강

ATLUS 선고 플로우

2019년도 신졸 채용 각종별 응모 서류 (프로그래머)

ATLUS 대우 및 조건

ATLUS 에서 만든 게임들

`SPI 테스트` 라고 하는 것은?

도움이 될 만한 사이트 링크

Chapter 1 Memo (1)

1.5 Policies & Policy Classes

1.5.1 Implementing Policy Classes with Template Template Parameters

1.5.2 Implementing Policy Classes with Template Member Functions

1.7 Destructors of Policy Classes

1.8 Optional Functionality Through Incomplete Instantiation

1.9 Combining Policy Classes

1.10 Customizing Structure with Policy Classes

1.11 Compatible and Incompatible Policies

1.12 Decomposing a Class into Policies

Overall

発端

説明

実装コード

結果

参照

Typelists

3.2 Defining Tyeplists ~ 3.6 Indexed Access

3.7 Searching Typelists ~ 3.9 Erasing a Type from a Typelist

3.10 Erasing Duplicates ~ 3.11 Replacing an Element in a Typelist

実装した理由。

「からツバ法」

コード全文

ATLUS 2019년도 채용 요강

ATLUS 선고 플로우

2019년도 신졸 채용 각종별 응모 서류 (프로그래머)

ATLUS 대우 및 조건

ATLUS 에서 만든 게임들

SPI 테스트 라고 하는 것은?

도움이 될 만한 사이트 링크

1.5 Policies & Policy Classes

1.5.1 Implementing Policy Classes with Template Template Parameters

1.5.2 Implementing Policy Classes with Template Member Functions

1.7 Destructors of Policy Classes

1.8 Optional Functionality Through Incomplete Instantiation

1.9 Combining Policy Classes

1.10 Customizing Structure with Policy Classes

1.11 Compatible and Incompatible Policies

1.12 Decomposing a Class into Policies

Overall

`SPI 테스트` 라고 하는 것은?