KMC活動ブログ

京大マイコンクラブの活動の様子を紹介します!!

3DCG勉強会2022 第5回~第8回

こんにちはこんにちは! 3DCG勉強会2022 担当の crashRT です。
だんだん暑くなってきている中レンダリングを回しているので室温が大変なことになっています。今回は 3DCG勉強会2022 第5回~第8回の活動を報告します。

過去のレポートはこちらから

3DCG勉強会とは?

参加者に 3DCG制作を布教する 3DCG制作の雰囲気を知ってもらうことを目指して、毎週火曜日の20:30から開催している新入生向け 1 の勉強会です。

初めて3DCGに触れる参加者が多いので基礎を中心にゆっくり進めながら、3DCG を制作していく上で必要な知識や技術などについて話していきます。現在は無料の Blender を扱っていますが、今後 CINEMA 4D も扱う予定です。

現在は、昨今の情勢もあり Discord というサービスを用いて遠隔で開催しています。

勉強会の内容

第4回までで Blender の基本的な使い方は一通り紹介できたと思うので、 作品の作り方や知識的なものを扱い始めました。

第5回:トンネルを作る

第5回ではトンネルを扱いました。 トンネルとはある一定の区画が繰り返されて通路のようになってるもののことで、正式な名前ではないですが慣例的にそう呼ばれています。 使える機能があまり多くなくても、それなりのものが作れることを感じてもらえたらと思います。

また、作品を制作する上で重要なリファレンスについて説明し、良い作品が集まっているサイトである PinterestBehanceArtStation と、リファレンスの管理に便利な PureRef を紹介しました。

3DCGのトンネル
第5回の作成

第6回:ビルのモデリング

第6回ではビルのモデリングを扱いました。 インスタンス機能や Array モディファイアなどを用いて、繰り返しのあるものを効率的にモデリングする方法を解説しました。

3Dモデリングされたビルの画像
第6回の作例

第7回:カメラとライティング基礎

第7回ではカメラとライティングの基本的な部分を扱いました。 ライティングとは ライトを設定し、3DCG の世界を照らす工程のことです。

カメラについては被写界深度と画角について、ライティングについては影の扱い方と、伝統的なライティングの手法である三点照明について解説しました。

被写界深度の例

三点照明された猿の3Dモデル
三点照明の例

第8回:ボリュームで遊ぶ

第8回ではボリュームについて解説しました。 ボリュームレンダリングとは光の通り道でのふるまいを計算するもので、光の通り道を可視化したり雲や煙などを表現したりするときなどに使われます。

Blender でのボリュームの使い方と、その応用例をいくつか紹介しました。

ボリュームレンダリングの例

参加してみたい方へ

講座はすべて録画しているので、今からの参加でも全く問題ありません。質問もいつでも受け付けているので、気軽に参加してください!

まずは、KMCの Twitterメール にご連絡ください。

KMC の宣伝

KMCではパソコンで何かしたい人々を大募集しています。入部資格に制限はありません。興味のある人は下のリンクからどうぞ!!

www.kmc.gr.jp


  1. ここでの新入生はKMCの新入部員のことで、大学での回生・年齢は無関係です。

Webサービス勉強会2022 第2回〜第4回

こんにちは!Webサービス勉強会2022を担当している ryokohbato (KMC ID: rhato, ID: ryokohbato) です。今回は、Webサービス勉強会2022の第2回〜第4回のレポートをお届けします。

過去のレポートはこちらから

Webサービス勉強会2022とは?

Webサービスについて1年かけて学ぶ勉強会です。以下リポジトリで環境および資料を公開しています。

github.com

第2回 書いて覚えるCSS

第1回「書いて覚えるHTML」 同様、手を動かしながらCSSに慣れてもらいました。資料は 第2回 書いて覚えるCSS です。

第2回裏講座 そもそもなんでこんなことをやらされているのか

第1回 イチからWebpackのconfigを書いてTypeScriptをコンパイルする では、TypeScriptをコンパイルするために、npmなどを使ってパッケージを入れたり webpack.config.js を書いたりする必要がありました。今回は、なぜこのような複雑な方法でTypeScriptの開発環境を整えたのか、歴史的な経緯も踏まえつつ扱いました。資料は 第2回 そもそもなんでこんなことをやらされているのか です。

第3回 デザインパターン1

第3回では、カード風のスタイルを作りながらHTMLとCSSを組み合わせた基本的な開発の方法を扱いました。また、スクロールバーの表示方法やmarginの相殺についても扱いました。資料は 第3回 デザインパターン1 です。

第3回裏講座 新しいCSSの機能を試してみる

最近使えるようになったセレクタである :is():where()、そしてカスケードレイヤー (@layer) について、実際に書いて動かしてみつつ、書き方や動作を確認しました。資料は 第3回 新しいCSSの機能を試してみる です。

第4回 Webアクセシビリティの基礎

スクリーンリーダーやキーボードによるコントロールを使って閲覧されることを念頭に置いたWebページの開発について扱いました。今回はWebアクセシビリティについて学ぶ上で最も基礎になる部分について扱うにとどめましたが、今後より発展的な内容も扱っていきたいと思います。資料は 第4回 Webアクセシビリティの基礎 です。

コンテナ、Docker、Kubernetes って何が嬉しいの?という例会講座をしました

はむはー!最近は私たち人間に優しい気温になってきました。ずっとこれくらいの気温になっててほしいです。

今日、KMC の例会講座で「コンテナ、Docker、Kubernetes って何が嬉しいの?」というタイトルで例会講座を行いました。

docs.google.com

コンテナや Docker、Kubernetes はアプリケーションを書いたりサーバーを触ったりしていると目にすることがあると思いますが、「なんか難しそう」「今の運用でうまくいってるしな」と敬遠する人も多いと思います。また、アプリケーションを使うときに README の通りに Docker コマンドを打って、よくわからないけど動いている、でもなんか普通に立ち上げた時と違ってよく分からん、といったこともあるでしょう。

そんな人達がコンテナ技術に触れるきっかけとなるよう、「コンテナとはなんなのか?Docker や Kubernetes は何をしてくれて、使うと何が嬉しいのか?」ということに焦点を置いて講座をしてみました。

コンテナ、Docker、 Kubernetes を使うとっかかりが欲しい人に、ぜひこの資料を読んでいただければと思います!

Webサービス勉強会2022 第0回〜第1回

こんにちは!Webサービス勉強会2022を担当している ryokohbato (KMC ID: rhato, ID: ryokohbato) です。今回は、Webサービス勉強会2022の第0回、および第1回のレポートをお届けします。

Webサービス勉強会2022とは?

Webサービスについて1年かけて学ぶ勉強会です。以下リポジトリで環境および資料を公開しています。

github.com

第0回 (5/8)

第0回は環境構築回でした。Node.jsなど必要なツールをインストールした上で、開発用サーバーを立てました。

また、Webサービス勉強会2022では、Dockerを使用した開発環境も提供しています。こちらを使用して環境を構築してくれた部員もいたようですね。

第1回 (5/15)

さて、いよいよ勉強会の本格始動です。Webサービス勉強会は、大きく3つのパートに分けられています。

  1. メインパート (私が資料をもとに説明をしていく)
  2. 演習パート (扱った内容に関する演習を行う)
  3. 裏講座 (演習パートと並行して開催)

1. メインパート

今回のメインパートでは、「書いて覚えるHTML」と題して手を動かしながらHTMLに慣れてもらいました。第1回の資料は こちら です。手軽にリッチなUIを作れる楽しさが感じてもらえたと思います。

2. 演習

今回の勉強会では進捗管理シートを用意しています。みなさん演習もかなり解き進めてもらえたようで何よりです。

3. 裏講座

さて、演習の時間を利用して、Webサービス勉強会2022ではより発展的な内容を扱う講座、裏講座を開催しています。第1回の今回は「イチからWebpackのconfigを書いてTypeScriptをコンパイルする」と題し、TypeScriptをコンパイルするために必要な webpack.config.jstsconfig.json の書き方を学びました。次回は、コンパイルのためになぜこんな複雑なことをしているのか、について扱う予定です。

裏講座の様子
裏講座の様子

宣伝

Webサービス勉強会2022では、Botの開発やWebサービスの開発を学びます。興味のある方は、以下の入部案内を参考にメールやTwitterのDMなどでいつでもご連絡ください。お待ちしております!

www.kmc.gr.jp

3DCG勉強会2022 第1回~第4回

こんにちはこんにちは! 3DCG勉強会2022 担当の crashRT です。
普段は Motion Graphics と呼ばれる CG を用いた映像を制作しています。最近ではKMCの新勧用のビラを作ったり Webサービスの勉強を始めたりしました。

3DCG勉強会とは?

参加者に 3DCG制作を布教する 3DCG制作の雰囲気を知ってもらうことを目指して、毎週火曜日の20:30から開催している新入生向け 1 のイベントです。

初めて3DCGに触れる参加者が多いので基礎を中心にゆっくり進めながら、3DCG を制作していく上で必要な知識や技術などについて話していきます。現在は無料の Blender を扱っていますが、後半では CINEMA 4D も扱う予定です。

現在は、昨今の情勢もあり Discord というサービスを用いて遠隔で開催しています。

勉強会の内容

これまでに開催した回では以下のような内容を扱いました。

  • 第1回:Blender の導入、使い方の基本(Object Mode での操作など)
  • 第2回:ポリゴンの編集(ランプのモデリング
  • 第3回:SDS 2 の使い方(腕時計のモデリング
  • 第4回:マテリアルの基礎(テクスチャ、UV展開など)

3Dモデリングしたランプ
第2回の作例
3Dモデリングした腕時計
第3回の作例

沼にハマってくれた新入生もいるようで、色々作ってくれています。また、5/7 (土) には1日で上回生が支援をかましつつ新入生にとりあえずモデリングしてもらう、「ラピッドモデリング祭り」と呼ばれるイベントを開催し、無事参加してくれた新入生に作り上げてもらうことができました。(気がついたら完成していた新入生もいてビビっています)

これまでの4回で基礎の部分はある程度カバーできたと思うので、次回からは少しずつレベルを上げていこうと考えています。

参加してみたい方へ

講座はすべて録画しているので、今からの参加でも全く問題ありません。質問もいつでも受け付けているので、気軽に参加してください!

まずは、KMCの Twitterメール にご連絡ください。

KMC の宣伝

KMCではパソコンで何かしたい人々を大募集しています。入部資格に制限はありません。興味のある人は下のリンクからどうぞ!!

www.kmc.gr.jp


  1. ここでの新入生はKMCの新入部員のことで、大学での回生・年齢は無関係です。

  2. subdivision surfaces

独自のSlack転送システムを作った話

こんにちは!現会長のryokohbato (KMC ID: rhato, ID: ryokohbato) です。普段はたまに雑用業務をしつつKMCライフを満喫しています。今回はKMCの新歓で使うために開発した、独自のSlackメッセージ転送システムについて紹介するよ!

概要

現在のKMCではSlackが主な活動の場になっており、KMC Slackには部員のいろいろなことが書き込まれているわけですが、体験入部時にはアカウントがMCG (マルチチャンネルゲスト) に設定されているため、それらを見ることはできません。しかし今年の新歓では新たな試みとして、体験入部時にもその一部を見えるようにすることで、KMCの空気感を知ってもらおうという話になりました。

Slackにはreacji (リアク字)と呼ばれる機能があり、特定のリアクションが付けられた投稿を自動で別のチャンネルに転送することができます。これを使って、外部に見せても良い投稿をゲストアカウントからも見えるチャンネルに転送するようにすれば良さそうです。

Reacji Channeler
reacji (Reacji Channeler) によりメッセージが転送された様子

ところが、この機能はSlackのゲストアカウントとの相性が悪いです。(当然といえば当然ですが、) ゲストアカウントからは見えないチャンネルからゲスト用チャンネルにreacjiで転送されたメッセージは、ゲストアカウントからは見えません。

それぞれのアカウント種別から見ることができるメッセージの範囲
それぞれのアカウント種別から見ることができるメッセージの範囲

そこで、reacji相当の機能を独自に開発することにしました。

そうしてできたのが、kmc-reacjiです!宗教上の理由によりオープンソースとなっております。

登録された部員が、自分の投稿に特定のリアクションを付けた場合に、全く同じ内容をゲスト用チャンネルに投稿します。テキストだけなく画像も転送されますが、画像はそのまま投稿するのではなく、Gyazo APIを使ってアップロードされた画像のリンクを投稿します。

kmc-reacjiによりメッセージが転送されている様子
kmc-reacjiによりメッセージが転送されている様子

詳しい実装の話

転送が発生する条件は以下の通りとしました。

  • kmc-reacjiのシステムに登録されていること
  • :transfer: のリアクションが 本人により 押されること
  • リアクションが押された投稿が その本人の投稿 であること

kmc-reacjiでは、「誰の投稿をどのチャンネルに転送するか」を src/transfer-rule.ts で管理しており、「システムへの登録」というのはこのファイルに自分のユーザーIDを記入することを指しています。

ここからは詳しい実装についてささっと書いていきたいと思います。ちなみに私は axiosAPIを叩くのが好きなので、有名な node-slack-sdk などは使わず、express でサーバーを立てて axios で Slack APIGyazo APIを叩いています。

プログラムの全体的な動作は以下のような感じです。

  1. reaction_added イベントを受け取る (KMC Slackのチャンネルで押された絵文字リアクションの全てを受け取っている)
  2. イベントを発生させたユーザー、すなわち絵文字リアクションを付けたユーザーを特定して、そのユーザーがシステムに登録されているかどうかを確認する
  3. 自分の投稿に自分で押したリアクションであることを確認する
  4. リアクションが :transfer: であることを確認する

プログラムの本体は src/kmc-reacji.ts で全てです。簡単に紹介します。

まずは express でサーバーを立てます。先頭で response.end(); していますが、これはSlack APIあるあるで、独自のUIを作ってユーザーに選択させる、みたいなものを作るときには3秒以内に応答する必要がある 1 のでそのクセでこう書いています。今回は応答が遅くなっても大丈夫なはずですが、わざわざ遅らせる意味もないので先頭で応答しておきます。

const express = require("express");
const app = express();

app.use(express.json());
app.use(express.urlencoded({ extended: true }));

app.post("/", async (request: any, response: any) => {
  response.end();

  // ここから先にプログラムが続く
}

次に、転送するメッセージを取得します。絵文字リアクションが押されたメッセージのテキストを取得したいですね、絵文字リアクションイベントにはこの情報は含まれていないので、ts (タイムスタンプ) を使って頑張って取得する必要があります。それをしているのが下の部分です。

絵文字リアクションが押されたメッセージの投稿時間はイベントに含まれているので、この時間の1ms前から1ms後までの間に投稿されたメッセージを検索しています。 正直ここはもうちょっとなんとかしたい。。。

const requestBody = request.body;
// 略
const target_channel: string = requestBody.event.item.channel;
const target_ts: string = requestBody.event.item.ts;
const latestTs = `${target_ts.split(".")[0]}.${Number.parseInt(target_ts.split(".")[1]) + 1}`;
const oldestTs = `${target_ts.split(".")[0]}.${Number.parseInt(target_ts.split(".")[1]) - 1}`;

const target_message = await axios.get("https://slack.com/api/conversations.history", {
  headers: {
    Authorization: `Bearer ${token.slack.user}`,
    "Content-Type": "application/json",
  },
  params: {
    channel: target_channel,
    latest: latestTs,
    oldest: oldestTs,
  },
});

さて、次に必要なのは投稿時のアイコンとユーザー名の設定です。Nullish coalescing operator (??・Null合体演算子)、便利ですねー

const profile = target_user_info.data.user.profile;
const icon_url: string =
  profile.image_original ??
  profile.image_512 ??
  profile.image_192 ??
  profile.image_72 ??
  profile.image_48 ??
  profile.image_32 ??
  profile.image_24 ??
  "";
const user_name = target_user_info.data.user.name;

ちなみに、ユーザー名やアイコンを個別に設定してメッセージを投稿する場合、chat:write.customize permission を与えた上でBot User OAuth Tokenを使う必要があります。

さて、最後に画像をGyazo APIを使ってアップロードしていきます。ハマりポイントがたくさんあって大変でした。

まず、メッセージに添付された画像のデータを取得するには、url_private に書かれたURLにBot User OAuth Tokenを記載したAuthorizationヘッダを付けてGETリクエストを投げる必要があります。

以下のようにして、添付された全ての画像のデータをArrayBufferで受け取ることができます。(MIME typeがimage/から始まるものを画像と判断しています。)

const images_data: { data: any; mimetype: string }[] = await Promise.all(
  target_message.data.messages[0].files
    .filter((x: any) => /image\/.*/.test(x.mimetype))
    .map(async (x: any) => {
      return {
        data: (
          await axios.get(x.url_private, {
            headers: {
              Authorization: `Bearer ${token.slack.user}`,
            },
            responseType: "arraybuffer",
          })
        ).data,
        mimetype: x.mimetype,
      };
    })
);

また、Gyazo APIのUploadを叩く際は、filenameを指定しないと動きません。

かなり適当にfilenameを決めてしまっていますが、とりあえず動くのでヨシ!

const gyazo_urls = await Promise.all(
  images_data.map((x) => {
    const form = new FormData();
    form.append("access_token", token.gyazo);
    form.append("imagedata", x.data, {
      filename: `${target_ts}__kmc-reacji`,
      contentType: x.mimetype,
    });
    return axios.post("https://upload.gyazo.com/api/upload", form);
  })
);

そんなこんなで完成です!メッセージに添付された画像データを取得するところでかなりハマってしまい、画像の転送が実装されるまでに1ヶ月以上かかってしまいました。。。

App Manifestも置いておきます。(event_subscriptionsrequest_url は隠しています)

display_information:
  name: kmc-reacji
  description: お試し用memoチャンネルにメッセージを転送
  background_color: "#008000"
features:
  bot_user:
    display_name: kmc-reacji
    always_online: true
oauth_config:
  scopes:
    user:
      - channels:history
      - reactions:read
    bot:
      - channels:read
      - chat:write
      - chat:write.customize
      - chat:write.public
      - users:read
settings:
  event_subscriptions:
    request_url: https://example.com/
    user_events:
      - reaction_added
  org_deploy_enabled: false
  socket_mode_enabled: false
  token_rotation_enabled: false

あとがき

継ぎ足しのソースコードで型定義も最悪なので、このあたりはなんとかしたいですね。今度Twitterへの転送機能も付けたいなー。

宣伝

今年もKMCでは 新入生プロジェクト を開催します。また、今年の Webサービス勉強会 は私が担当します。今回紹介したようなBotの開発やWebサービスの開発に興味のある方は、以下の入部案内を参考にメールやTwitterのDMなどでいつでもご連絡ください。お待ちしております!

www.kmc.gr.jp

補足

実際には、間違って転送してしまった際に転送されたメッセージを消去するための :cancel-transfer: という絵文字リアクションも実装していますが、chat.delete しているだけで大したことは何もないので省略します。


  1. 気になる方は 公式ドキュメントのこのあたり を読むと書いてあります。

Pietを高速化するデータ構造

ジェルばんは! KMC-id: prime, id:PrimeNumber のそすうぽよだよ〜。 みなさん、Pietプログラミングを楽しんでいますか? 知らない人のために解説すると、Pietはドット絵がソースコードプログラミング言語で、いわゆる「難解プログラミング言語」の一つです。 以下のような「ドット絵」がソースコードになっています!

devide_by_2.10cs.11x4.png, Created by Hideaki Nagamine(https://github.com/1995hnagamin) Creative Commons BY-SA 4.0

Pietの仕様

Pietについてより詳しく知りたい人は以下のスライドを読むのがおすすめです。

www.slideshare.net

Pietの本家サイト(英語): DM's Esoteric Programming Languages - Piet

Pietの仕様について、この記事を読むのに必要な部分だけ説明します。

Pietの画像は、内部的に17種の命令から構成された命令列として解釈されます。 Pietでは、実行時にただ一つのスタックを持ち、17種の命令はスタックを操作しつつ入出力や条件分岐を行います*1

Pietのスタック操作

17種の命令はスタックに対する操作の違いにより、以下の通りに分類することができます。

  • スタックに値を1つ積む: push, in(char), in(number)
  • スタックから値を1つ取り除く: pop, switch, pointer, out(char), out(number)
  • スタックから値を1つ取り除き、それに応じて新たな値を1つ積む: not
  • スタックから値を2つ取り除き、それに応じて新たな値を1つ積む: add, subtract, multiply, divide, mod, greater
  • スタックから値を1つ取り除き、それに応じて新たな値を2つ積む: duplicate
  • 特殊な操作(後述): roll

rollは特殊な操作で、

  • まず、スタックから2回pop操作を行う。このときの値を1回めから順にcount, depthとする。
  • countが非負のときは、count回以下の操作を繰り返す(以後これをroll-stepと呼ぶことにします)
    • スタックの1番上の要素を、depth番目まで移動する(その分、2番目からdepth番目までの要素は1個分スタックのトップに近づく)
  • countが負の場合は、逆操作(depth番目の要素を1番上に持ってくる)をabs(count)回繰り返す。

例えば、スタックのサイズが9で、depth=8, count=3のときは次のような操作になります。

Pietにはヒープメモリに相当する概念はありませんが、このroll操作によって自由にスタックを操ることで、チューリング完全な計算能力を得ることができます。

rollの実装

さて、このroll操作を普通の配列上に実装したスタックで実装するとどうなるでしょうか? 当然、配列上のdepth個の要素すべてを移動しなければならないため、少なくともdepthに比例した計算量が必要です。実のところ、rollは配列上で  O(depth) で実現可能です。

簡潔な実装として、列のreverseを3回行って実現する方法があります。先ほどと同じ、depth=8, count=3のときは次のようにして実現できます。

実用上高速な方法はRustの標準ライブラリ実装のコメントを読むとわかりやすいです。 rust/rotate.rs at e1b71feb592ba64805689e2b15b9fa570182c442 · rust-lang/rust · GitHub

rollにふさわしいデータ構造とは

さて、スタックを保持するデータ構造を工夫することで、もっと高速にrollを行う方法はないでしょうか? 一つの方法として、平衡二分木を使う方法があります。平衡二分木を順序を持った列を管理するデータ構造だと思うと、以下の操作を行うことができます( Nはスタックのサイズ)。

  • insert: 新たな要素を任意の場所に挿入する  O( \log N)
  • erase: 列の任意の位置の要素を削除する  O( \log N)
  • split: 列を任意の位置で2つに分割する  O( \log N)
  • concatenate: 2つの列を連結する  O( \log N)
  • build: 配列から対応する平衡二分木を構築する  O(N)
  • dump: 平衡二分木から対応する配列を構築する  O(N)

スタックに対するpush, popはそれぞれinsert, eraseで実現できます。rollはsplit, concatenateを用いて次のように書くことができます(Rust風疑似コード、 0 \leq count \lt depthとする)

fn roll(tree: Tree, depth: usize, count: usize) {
    let (left, remain) = tree.split(depth);
    let (middle, right) = remain.split(count);
    left.concatenate(right.concatenate(middle))
}

したがって、平衡二分木を用いるとすべての命令を O( \log N) で処理することができます。めでたしめでたし。

ではなく、配列で実装したときと比べて、roll以外の操作が O(1)から O( \log N)に悪化してしまっています。roll以外の命令を頻繁に実行する場合(実際、多くの場合はそうなります)、これはあまり嬉しくありません。 高速なPietの処理系には、さらに効率的なデータ構造が必要です。

これが一番速いと思います

今回紹介するデータ構造は id:joisino (KMC-ID: joisino) さんの考案したものです。この記事はjoisinoさんの許諾を得て執筆しています。

性能

  • roll以外: 償却 O(1)
  • roll: (償却ではなく、厳密に) O( \log N)

roll以外が償却定数時間になっているのが大きなポイントです。また、実用上も高速な実装が可能です。

データ構造

スタックのtopからt個( t \leq 2 \log N)を(配列等で実装した)通常のスタックで、残りをsplit/concatenateのできる平衡二分木で管理します。

操作

roll

  1. スタックから全部取り出して要素数 t の平衡二分木を作る  O(t) = O(\log N)
  2. 本体の平衡二分木と concatenate する  O(\log N)
  3. roll する  O(\log N)
  4. 平衡二分木の最後の  \log N 要素を split する  O(\log N)
  5. split した要素をスタックに詰める  O(\log N)

push

  1. 通常のスタックに push する  O(1)
  2. 通常のスタックの要素が  2 * \log N に達した時 ★
    1. スタックの最初の  \log N 個の要素を取り出して平衡二分木を作る  O(\log N)
    2. 本体の平衡二分木と merge する  O(\log N)

pop

  1. 通常のスタックから pop する  O(1)
  2. ただし、スタックが空の場合、以下の操作を行ってから pop する ★
    1. 平衡二分木の最後の  \log N 要素を split する  O(\log N)
    2. split した要素をスタックに詰める  O(\log N)

push, pop 操作で ★ が起こるのは最悪でも  \log N 回 push, pop 操作を連続して行うごとなので、これで償却  O(1) になります

さらなる最適化

roll操作において、depthが通常のスタックに収まるほど小さい場合は、配列に対するroll操作のみで完結させることができ実用上高速です。 headに収まるという条件から、 O(\log N)であることにも変わりはありません。

実装

あらかじめ実装したものがこちらになります

github.com

平衡二分木の実装は赤黒木です。頻繁に木に対する変更を行うこと、rollを厳密(償却ではなく) O(\log N)に保つためには平衡二分木の操作が厳密 O(\log N)である必要があることから選択しました。

赤黒木の実装はlibrary/red-black-tree.cpp at master · ei1333/library · GitHubをもとに、いくらかの変更を施して利用しています。

ベンチマーク

漸近的計算量の改善だけでなく、実際にも速くなるか確かめたいところです。

  • スタックに対するpush, pop, rollクエリを6 : 3 : 1の比率でランダムに選択し実行
    • Pietにおけるroll命令を一回実行するたびに、スタック対して2回popが呼ばれること、popするにはpushする必要があること、pushの方が多くないとスタックが成長しないこと、等を考慮しこの比率に設定
  • rollのdepthは、depthの対数が一様分布になるようにランダムに選択
    • これは、参照の局所性のあるプログラムの動作を模倣したもの
  • rollのcountは32bit整数の範囲から一様ランダムに選択
    • 内部でdepthでmodを取ることから、おおよそ0以上depth未満の一様ランダム

比較対象には、配列(のみ)による実装と赤黒木(のみ)による実装を用意しました。

結果

クエリ数Qを10万、30万、100万、300万、1000万と変えて実行時間を計測しました。

縦軸: 実行時間(ms), 横軸: クエリ数

考察

Q=1,000,000では他の実装よりも高速になりました! しかし、Q=100,000では配列実装より遅く、Q=10,000,000では赤黒木実装より遅くなってしまいました。なぜでしょうか?

一般に、平衡二分木は間接参照を多用するため、現代のコンピュータではかなりオーバーヘッドが大きいことが知られています。 一方、配列実装ではメモリに対してシーケンシャルにアクセスするパターンが多いため、性能を出しやすいです。 そのため、漸近的計算量が悪くても、スタックの大きさが小さいうちは配列実装の方が高速になります。 スタックの大きさに応じて赤黒木を併用するかどうかを切り替えると、実用上良いかもしれません*2

また、そもそも今回導入したデータ構造では全クエリを通しての漸近的計算量を改善するものではないため、赤黒木だけの実装と比べると定数倍勝負になってしまいます。 赤黒木のみの実装と比較すると、push/popの計算コストをrollに押し付けることでpush/popの償却計算量を改善しているため、rollの計算量は定数倍悪化しています。 赤黒木のみとどちらが速いかは、クエリ中のrollの比率によって変わってきます。 実際、rollの比率をベンチマークに用いた1/10から1/20にすると、Q=10,000,000でも赤黒木+配列のハイブリッドの方が赤黒木のみの実装より3割程度高速になりました。

今後の課題

赤黒木の代わりにB+木等を使うと、間接参照のオーバーヘッドを緩和できる可能性があるので、暇があれば試してみたいです(あるいは誰か実装してくれ頼む!)。 あるいは別のデータ構造(フィンガーツリーの亜種とか…?)で、よりよい性能を示すものがあるかもしれないので、それについても調べて(できれば実装もして)みたいです。

ではみなさん、よいPietライフを~!

*1:いわゆるスタックマシンに近いですが、後述のroll操作はイレギュラーな操作です

*2:スタックの大きさがある閾値を超えたら切り替え、だと閾値をまたぐたびに切り替えコストがかかってしまうので、1000個を超えたら赤黒木を併用、500個を下回ったら配列のみ、のような実装にすると良さそうです