template parameter packのN番目の型を取り出すアプローチ

これはメタプロする事自体を目的にした遊びで，実用という意味で考えればO(N)で線形再帰するべき． 線形再帰ならば誰でも読めるし，数十個ぐらいなら最も速い．もし真面目にテンプレート引数を1000個も渡すケースに陥っているならばそれは多分そこに至る時点で相当設計が悪いはず．

下2つの実装方針のうちN番目の型を取り出すだけなら前者の方が有意に早いです(手元のclangだとN = 10000で3倍くらい速い)

melpon.org

前者はidentity<Ts>*...をvoid*..., T*, ...で受ける方針，後者は多重継承しておいてオーバーロード解決に持ち込む方針． どちらも再帰深度が対数オーダーになるのでNが大きくなってもスケールはする．

そもそも言語仕様のレベルでランダムアクセス出来るようになってないことがイケてないというのはある．

#include <utility>

template <typename T>
struct identity {
    using type = T;
};

template <std::size_t>
using void_p = void*;

template <typename Indices>
struct at_impl;
template <std::size_t... Indices>
struct at_impl<std::index_sequence<Indices...>> {
  template <std::size_t>
  using void_ptr = void*;

  template <typename T>
  static T eval(void_ptr<Indices>..., T*, ...);
};


// split parameter pack 
template <std::size_t N, typename... Ts>
using at = typename decltype(
  at_impl<std::make_index_sequence<N>>::eval(static_cast<identity<Ts>*>(nullptr)...))::type;

template <std::size_t I, typename T>
struct indexed_identity {
  using type = T;
};

template <typename Indices, typename... Ts>
struct at2_impl;
template <std::size_t... Indices, typename... Ts>
struct at2_impl<std::index_sequence<Indices...>, Ts...> : indexed_identity<Indices, Ts>... {
  template <std::size_t N, typename T>
  static identity<T> eval(indexed_identity<N, T>);
};


// overload resolution
template <std::size_t N, typename... Ts>
using at2 = typename decltype(at2_impl<std::make_index_sequence<sizeof...(Ts)>, Ts...>::template eval<N>(
  std::declval<at2_impl<std::make_index_sequence<sizeof...(Ts)>, Ts...>>()))::type;

int main() {
    static_assert(std::is_same<int, at<9, int, int, int, int, int, int, int, int, int, int>>::value, "");
    static_assert(std::is_same<int, at2<9, int, int, int, int, int, int, int, int, int, int>>::value, "");
}

時間を浪費するのやめたい

限界AtoZタイピング

#include <iostream>

int main() {
    // Generate applescript
    std::cout << "on run {input, parameters}\n\tactivate application \"Google Chrome\"" << std::endl;
    for (char i = 'a'; i <= 'z'; ++i) {
        std::cout << "\ttell application \"System Events\" to keystroke " << '"' << i << '"' << std::endl;
    }
    std::cout << "end run" << std::endl;
}

on run {input, parameters}
    activate application "Google Chrome"
    tell application "System Events" to keystroke "a"
    tell application "System Events" to keystroke "b"
    tell application "System Events" to keystroke "c"
    tell application "System Events" to keystroke "d"
    tell application "System Events" to keystroke "e"
    tell application "System Events" to keystroke "f"
    tell application "System Events" to keystroke "g"
    tell application "System Events" to keystroke "h"
    tell application "System Events" to keystroke "i"
    tell application "System Events" to keystroke "j"
    tell application "System Events" to keystroke "k"
    tell application "System Events" to keystroke "l"
    tell application "System Events" to keystroke "m"
    tell application "System Events" to keystroke "n"
    tell application "System Events" to keystroke "o"
    tell application "System Events" to keystroke "p"
    tell application "System Events" to keystroke "q"
    tell application "System Events" to keystroke "r"
    tell application "System Events" to keystroke "s"
    tell application "System Events" to keystroke "t"
    tell application "System Events" to keystroke "u"
    tell application "System Events" to keystroke "v"
    tell application "System Events" to keystroke "w"
    tell application "System Events" to keystroke "x"
    tell application "System Events" to keystroke "y"
    tell application "System Events" to keystroke "z"
end run

dlopenやdlsym辺りの実装を読んでそのうちまとめたい

#include <dlfcn.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
  FILE *fp;
  if ((fp = fopen("hello.c", "w")) == NULL) {
    fprintf(stderr, "file cannot open");
    exit(EXIT_FAILURE);
  }
  fprintf(fp,
    "#include <stdio.h>\n"
    "void hello(void) { printf(\"hello dl world!\\n\"); }\n"
  );
  fclose(fp);

  system("gcc -shared hello.c -o hello.so");
  
  void *dl = dlopen("./hello.so", RTLD_LAZY);
  if (dl == NULL) {
    fprintf(stderr, "dl cannot open");
    exit(EXIT_FAILURE);
  }

  void (*f)(void) = dlsym(dl, "hello");
  if (f == NULL) {
    fprintf(stderr, "dl cannot open");
    exit(EXIT_FAILURE);
  }

  f();  // hello dl world!
  dlclose(dl);

  return 0;
}

大量のメモリを使用するプログラムからコマンドを実行する方法というのを読んだ

メモリを多く使用したプロセスから繰り返しfork()する場合，performance issuesになりうるという話．

StackOverflow linux - 大量のメモリを使用するプログラムからコマンドを実行する方法 - スタック・オーバーフロー

実際困ることあるらしく

昨日今日ちょっと話題になったお話。fork()はあまり速くはないシステムコールですが、では1回あたり何ミリ秒かかるでしょう。個人的な感覚値としては0.3ミリ秒ぐらいという感覚で、実際測ってみると「動かしたて」のプロセスなら現代のCPUならこんなものです。しかし……

— mayah (@mayahjp) 2016, 1月 27

@mayahjp メモリを使ったりファイルを開いたりした状態だと、fork()がコピーするものが増えるのでfork()に時間がかかるようになります。malloc(4)を1M回呼んだ状態では、fork()が突然1ミリから2ミリ秒かかるようになります。

— mayah (@mayahjp) 2016, 1月 27

...

@mayahjp 改善案としては、fork()のときにいろいろコピーするのをやめればよいので、fork()/exec()の代わりにposix_spawn()を使うとちょっとだけましになります。こっちは共有するものが少ないので。あとはfork()専用の軽いプロセスを作って……

— mayah (@mayahjp) 2016, 1月 27

@mayahjp そのプロセスをfork()するようにコードを直すという感じでしょうか。すごく軽いプロセスからのposix_spawn()は、秒間1万回ぐらいは呼べます。

— mayah (@mayahjp) 2016, 1月 27

結論としてはposix_spawn()使えというのが良いそうだ．

リンクされているvforkの話も面白かった． http://www.a-k-r.org/d/2014-09.html#a2014_09_06

vfork速いけどメモリ空間をコピーしない特性上クセはある．子プロセスがデッドロックするのでマルチスレッドでforkしたら直後にexecしろというのと同様，vforkしたら直後にexecするべきなのだろう．(しない有用な例はあまり思いつかないけれど)

UNIX上でのC++ソフトウェア設計の定石 (3) - memologue

マルチプロセス難しいなー．

github.io

htmlを生成するテンプレートエンジンJade Jade - Template Engine と，cssを生成するStylus Expressive, dynamic, robust CSS — expressive, robust, feature-rich CSS preprocessor の使い方について少し勉強したので，かねてより手を付けたいと思っていたgithub.ioにとりあえずindexページを置いた．置いてみて思ったけれど，こことの使い分けのビジョンがイマイチ沸かないし不要そうだ．

http://fimbul.github.io/

Jadeはpythonライクなindentでタグのスコープが決まり，閉じタグを書く必要が無いとか，- var title = "page title"などと変数に値を入れておいて，#{title}で後から参照出来るとか便利なところは結構ある． templateなのでもっと色々使いまわしたり，includeでそのままファイルを埋め込むとか出来るようだけれど読んだだけでそこまで試してない．

Stylusは，sassやlessに似たものだけれど新しいもの好きなので試してみた．変数や条件分岐，ループなど一通り揃っている．

簡単にnpmで全部入るしgulp, gulp-stylus, gulp-jadeも入れて全部gulpを叩けばページが生成されるようにしてみたらよさ気だった．

fimbul.github.io/index.jade at master · fimbul/fimbul.github.io · GitHub

しかし，jadeにコードを埋め込もうと思うと普通にpreタグの中に#include と書くと#がJadeのdirectiveに認識されたりするし， かといって | を使うと</iostream>のような望まぬ閉じタグが生成されたりして結構困った．=を使うとエスケープしてくれるんだけど，今度は= "#include "とダブルクォートで囲ってやる必要があり コードが複数行になるとヒアドキュメントが無いためにいちいち各行を囲い，更に末尾に\nを追加し，途中にダブルクォートがあればバックスラッシュでエスケープしてやらないと上手くいかない．

とりあえずはコードをそのように変換してくれるスクリプトで対処すれば良いけれど，どうすれば幸せになれるんだろう．理解が足りない．

巷で流行りの活動日記

木構造系のデータ構造の実装のベストプラクティスが知りたいと思いつつ，適当に非常に簡単なものを試作するなど．
競プロ用途などで，自分用に簡単なprint機能などを備えた木構造のライブラリなどを作っておきたいという気持ちはある．
TSから標準に入るoptionalを使えば不正値を表現出来るので親が居ないだとか，子が居ないという状態を持つのは楽になる筈．

とりあえず二分木にしたけれど，葉の数nを渡せるような形にしてi番目の子にインデックスアクセス出来る方が良いのかも．

http://melpon.org/wandbox/permlink/FDIoIYYovywpE6ym

#include <functional>
#include <iostream>
#include <memory>
#include <queue>

namespace tree {

struct pre_order_tag {};
static constexpr pre_order_tag pre_order{};

struct in_order_tag {};
static constexpr in_order_tag in_order{};

struct post_order_tag {};
static constexpr post_order_tag post_order{};

struct dfs_order_tag {};
static constexpr dfs_order_tag dfs_order{};

template <typename T>
struct binary_tree : std::enable_shared_from_this<binary_tree<T>> {
  binary_tree(T v,
              std::weak_ptr<binary_tree> p = {},
              std::shared_ptr<binary_tree> l = nullptr,
              std::shared_ptr<binary_tree> r = nullptr)
    : value(v), parent(p), left(l), right(r) {}
  binary_tree(const binary_tree&) = default;
  binary_tree(binary_tree&&) = default;

  std::shared_ptr<binary_tree> append_left(std::shared_ptr<binary_tree> c) {
    left = c;
    c->parent = this->shared_from_this();
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> append_right(std::shared_ptr<binary_tree> c) {
    right = c;
    c->parent = this->shared_from_this();
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> remove_left() {
    left = nullptr;
    return this->shared_from_this();
  }

  std::shared_ptr<binary_tree> remove_right() {
    right = nullptr;
    return this->shared_from_this();
  }

  T value;
  std::weak_ptr<binary_tree> parent;
  std::shared_ptr<binary_tree> left;
  std::shared_ptr<binary_tree> right;
};

namespace detail {

  template <typename Tag>
  struct print;

  template <>
  struct print<pre_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       printer(t);
       eval(t->left, printer);
       eval(t->right, printer);
    }
  };

  template <>
  struct print<in_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       eval(t->left, printer);
       printer(t);
       eval(t->right, printer);
    }
  };

  template <>
  struct print<post_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
       if (t == nullptr) return;
       eval(t->left, printer);
       eval(t->right, printer);
       printer(t);
    }
  };

  template <>
  struct print<dfs_order_tag> {
    template <typename T, typename P>
    static void eval(const T& t, const P& printer) {
      if (t == nullptr) return;
      std::queue<T> q;
      q.push(t);
      while (!q.empty()) {
        const auto& tmp = q.front();
        q.pop();
        printer(tmp);
        if (tmp->left != nullptr) q.push(tmp->left);
        if (tmp->right != nullptr) q.push(tmp->right);
      }
    }
  };

}  // namespace detail

struct default_printer_t {
  template <typename T>
  void operator()(const T& t) const { std::cout << t->value << std::endl; }
};

static constexpr default_printer_t default_printer{};

template <typename T, typename Tag = pre_order_tag>
inline void print(const T& t,
           Tag = {}, const std::function<void(const T&)>& printer = default_printer) {
  if (t != nullptr) detail::print<Tag>::eval(t, printer);
}

}  // namespace tree

int main() {
  using tree_type = tree::binary_tree<int>;

  auto t = std::make_shared<tree_type>(0);
  t->append_left(std::make_shared<tree_type>(1));
  t->append_right(std::make_shared<tree_type>(2));
  t->left->append_left(std::make_shared<tree_type>(3));
  t->left->append_right(std::make_shared<tree_type>(4));
  t->right->append_left(std::make_shared<tree_type>(5));
  t->right->append_right(std::make_shared<tree_type>(6));

  std::cout << "pre_order:" << std::endl;
  tree::print(t);
 
  std::cout << "in_order:" << std::endl;
  tree::print(t, tree::in_order);
  
  std::cout << "post_order:" << std::endl;
  tree::print(t, tree::post_order);

  std::cout << "dfs_order:" << std::endl;
  tree::print(t, tree::dfs_order);
}

Tower of Hanoi

#include <iostream>
#include <stack>

int main() {
  int n;
  std::cin >> n;
  std::stack<int> s[3];
  for (int i = n; i > 0; --i) {
    s[0].push(i);
  }

  int mpos = 0;
  while (!s[0].empty() || !s[1].empty()) {
    s[(mpos + 1 + (n % 2)) % 3].push(s[mpos].top());
    s[mpos].pop();
    mpos = (mpos + 1 + (n % 2)) % 3;

    if (s[0].empty() && s[1].empty())
      break;

    if (s[(mpos + 1) % 3].empty()) {
      s[(mpos + 1) % 3].push(s[(mpos + 2) % 3].top());
      s[(mpos + 2) % 3].pop();
    } else if (s[(mpos + 2) % 3].empty()) {
      s[(mpos + 2) % 3].push(s[(mpos + 1) % 3].top());
      s[(mpos + 1) % 3].pop();
    } else if (s[(mpos + 1) % 3].top() < s[(mpos + 2) % 3].top()) {
      s[(mpos + 2) % 3].push(s[(mpos + 1) % 3].top());
      s[(mpos + 1) % 3].pop();
    } else {
      s[(mpos + 1) % 3].push(s[(mpos + 2) % 3].top());
      s[(mpos + 2) % 3].pop();
    }
  }

  std::cout << "----" << std::endl;

  for (int i = 0; i < 3; ++i) {
    while (!s[i].empty()) {
      std::cout << s[i].top() << ' ';
      s[i].pop();
    }
    std::cout << std::endl;
  }
}