アヤチノオト

覚書のこと

里々がなんで遅いのかやっぱりよくわからんという記事

このまえ記事で無料のプロファイラ使って調べたんだけどよくわかんなかったのでVisual Studio Ultimate 2013買いました。
嘘です。試用期間あるみたいだからインストールして分析機能を使ってみたよ。

実験方法~

ミニゲームてんこもりな某ゴーストの辞書をloadしてからOnBootを呼び出してみた。

辞書の読み込み

大体10秒位かかっててそのうちの約9割がsatori_load_dict.cppってファイルにあるLoadDictionaryって関数だったよ。LoadDictionaryの中身は pre_processとselect_dict_and_load_to_vectorがそれぞれ30%程度。
たとえばpre_processが倍の速さになれば起動時間が1.5秒ほど縮まる計算に……?
f:id:ayachigin:20140729210425p:plain

OnBoot

satori_tool.cppのSatori::calculateが実行時間の54%を占めてて、この関数自体はほとんど何もしてないんだけどこの関数から呼び出してるcalcとUnKakkoがそれぞれ約27%。
calcの時間かかってるのはほとんど全部vectorの操作(push_backとかな)でした。UnKakkoはたくさん関数呼び出しててよくわからんでした。
f:id:ayachigin:20140729202755p:plain

感想

これvectorがおそいんじゃねって気がほんのりする。ほんのりな。
もっともっと括弧を多用するとまた違う結果になるかもだけど。
というか括弧使いまくると遅くなるというのがよくわからなくて。具体的に遅いコードがどこかに載っていたら教えて欲しいです。

里々はなんで重いのかわかったような気がしなくもなくも

注意書き

僕なりに頑張って調べたつもりですがこの記事の内容は全くもって間違っている可能性があります。
やっぱり間違ってました。新しい記事をこっちに書きました

概要

整備班でダウンロードできる里々Mc151-8のパフォーマンスを解析してみた。

解析方法

satoriteをビルドして適当なスクリプトを入力して送信する。
具体的にはこんなの。

(set、ほげ、ふが)
(loop、ほげ、10000)

結果

平均経過時間(子を含まない)が長い関数を調べました。
するとsatoritranslate.cppのSatori::Translateがぶっちぎりのトップ。
これは高速化できるのかわからない。まだソースあんまし読んでないという意味で。(別のところが問題だろうと思っていたので)

それ以外で遅い関数というとsatori_sentence.cppにあるSatori::SentenceToSakuraScriptInternalと他のいくつかの関数がおそらく同じ理由で処理に時間がかかってる。(これが本命と思ってた)
これ以下はSatori::SentenceToSakuraScriptInternalとかがなんで遅いのかについて書く。

ちなみにここから下はあんま自信ないです。

SentenceToSakuraScriptInternalがなんで遅いのか

トークをただの文字列として持っていることが原因。
里々が次に何かすべきことはあるかな?って一文字ずつ調べながら処理を分岐してるので遅い。たぶんおそらくきっと。

どうすれば一文字ずつ調べなくてよくなるか

ここでは簡単のため、里々のトークには普通の文字列と()を使った変数の展開しか無いということにする。
トークを”普通の文字列か、変数の名前のどちらかである値(直和型という)”のリストで表現する。

具体的にはこんなん。Haskellでごめん。

-- 里々の値は普通の文字列、または変数の名前ということを表すデータ型
data SaotoriValue = String String
                  | Variable String
                    deriving (Eq, Show, Read)

-- トークというのは里々の値のリストだよという宣言
type Talk = [SaotoriValue]

-- トークを文字列に変換する再帰関数
eval :: Talk -> String
-- リストが空なら空のリストを返す
eval [] = []
-- リストの先頭がただの文字列なら、中身の文字列とリストの残りをevalしたものとくっつける
eval (String x: xs) = x ++ eval xs
-- リストの先頭が変数の名前なら、変数を展開した文字列とリストの残りをevalしたものとくっつける
eval (Variable x: xs) = getValue x ++ eval xs

-- 変数名を受け取って変数の中身を返す関数
-- ここでは簡単のため引数を無視して常に"Hello world!"を返す
getValue :: String -> String
getValue _ = "Hello world!"

こんなプログラムで、「こんにちは(変数)」というトークを変換するとこうなる。

eval [String "こんにちは", Variable "変数"] -- "こんにちは Hello world!"

ほかの機能も使えるようにするには変数の定義とか選択肢を表現するデータ型とその評価関数(うえのevalってやつ)を定義していけばよい。

んでこの直和型とその評価関数みたいなパターンはBoostってライブラリのVariantを使うと出来るっぽいけどこれで速くなるかはわからない。辞書を読み込んだときに変換するコストもかかるしね。

こんだけ書いておいてあれだけどもSatori::SentenceToSakuraScriptInternalを書き換えて高速化を目論むのは現実的でない気がする。大規模工事すぎるし。
てことでSatori::Translateが高速化出来ないか調べるのがいいんでないかな。
(もう疲れたのでなげやり

里々をビルドしてみたのことのメモ

ソースを取ってくる

里々のリポジトリ整備班 -The Maintenance Shop-
svnのインストールはChocolateyがあるとコマンド一発でいけて便利。

Visual Studioをインストールする

最新のVisual Studio Express 2013 for Windows Desktopを使う。
里々のプロジェクトをビルドするにはVisual Studio 2008とVisual Studio 2010もインストールしないとできない。
Visual Studio 2008はVisual C++ 2008 Express Editionて書いてあるとこのリンクからインストーラをダウンロードできる。
Visual Studio 2010はこっちのページ中段。

Visual Studio 2013でsatori.slnを開く

プロジェクトとソリューションの変更をレビューって画面出たらそもままOK押す
f:id:ayachigin:20140720183500p:plain
ソリューションエクスプローラからcnってプロジェクトを右クリックしてプロパティを開く
左上の構成をすべての構成にして画像のとおりにプラットフォームツールセットをVisual Studio 2008 (v90)に変える
f:id:ayachigin:20140720190603p:plain
全部のプロジェクトのプラットフォームツールセットを変える(これまとめて出来ないのかなダレか教えてえろいひと)
これでsatoriとssuとcnはそのままビルド通るようになる

satoriteのビルドが通らないの何とかする

satoriteをビルドしようとすると「error RC1015: cannot open include file 'afxres.h'.」
ってえらーでる。
ここ見ながら直す
error RC1015:cannot open include file 'afxres.h' - 大人になったら肺呼吸

あと

satori_testはむりだれかたのんだ

チケットゴブル問題に挑戦したけど評価3だった

ダブリのいちばん多いチケットを取り除き、ダブリがなくなるまで繰り返す。

module Main where


import Control.Applicative ((<$>), (<*>))
import Data.List ((\\))
import System.Environment (getArgs)
import Debug.Trace


type Date = Integer
type Ticket = (String, Date, Date)


-- |
-- main
-- >>> :main
-- 4 Austria Canada Denmark Egypt
main :: IO ()
main = do
  args <- getArgs
  if null args then
      readFile "five.txt" >>= putStrLn . solve
  else
      readFile (head args) >>= putStrLn . solve
  where
    solve = (++) <$> (++" ") . show . length <*> unwords  <$> unconflictedCountries
    unconflictedCountries = map getCountry . resolveConflict . toTickets . nonEnptyLines
    nonEnptyLines = filter (/="") . lines
    toTickets = map readTicket
    getCountry (c, _, _)= c

-- |
-- readTicket
-- >>> readTicket "Afghanistan 4/17-4/18"
-- ("Afghanistan",417,418)
readTicket :: String -> Ticket
readTicket s = (country, start, end)
    where
      (country, ds) = break (==' ') s
      (start', end') = break (=='-') ds
      start = readDate start'
      end = readDate (tail end')

-- |
-- readDate
-- Converts String to Date that indicated with Int that less than 1231 more than 101.
-- Two lower digits indicates day, and two upper digits indicates month.
-- >>> readDate "1/13"
-- 113
-- >>> readDate "12/1"
-- 1201
readDate :: String -> Date
readDate dateString = a' * 100 + b'
    where
      a' = read a
      b' = read (tail b)
      (a, b) = break (=='/') dateString

-- |
-- conclictedTo
-- Whether the two tickets are conflicted.
-- >>> conflicted ("America", 113, 115) ("India", 110, 113)
-- True
-- >>> conflicted ("India", 110, 113) ("America", 113, 115)
-- True
-- >>> conflicted ("America", 113, 122) ("India", 115, 120)
-- True
-- >>> conflicted ("America", 113, 115) ("India", 116, 120)
-- False
-- >>> conflicted ("America", 121, 135) ("India", 116, 120)
-- False
isConflictedTo :: Ticket -> Ticket -> Bool
isConflictedTo (_, s1, e1) (_, s2, e2) = s1 == s2 ||
                                     (s1 < s2 && e1 >= s2) ||
                                     (s1 > s2 && s1 <= e2)

-- |
-- countConflicted
-- Conts the number of conflicted tickets.
-- >>> let tickets = [("America", 113, 115), ("India", 110, 112), ("Germany", 112, 113)]
-- >>> countConflicted tickets ("America", 113, 115)
-- 2
-- >>> countConflicted tickets ("Germany", 112, 113)
-- 3
countConflicted :: [Ticket] -> Ticket -> Int
countConflicted [] _ = error "There is no tickets"
countConflicted tickets t = length . filter (isConflictedTo t) $ tickets

-- |
-- resolveConflict
-- Removes all tickets that conflicted to other.
-- >>> let tickets1 = [("America", 100, 105), ("India", 106, 112), ("Germany", 113, 114)]
-- >>> resolveConflict tickets1
-- [("America",100,105),("India",106,112),("Germany",113,114)]
-- >>> let tickets2 = ("Japan", 103, 116):tickets1
-- >>> resolveConflict tickets2
-- [("America",100,105),("India",106,112),("Germany",113,114)]
resolveConflict :: [Ticket] -> [Ticket]
resolveConflict tickets
    | all ((==1) . countConflicted tickets) tickets = tickets
    | otherwise = resolveConflict (tickets \\ [snd mostConflictedTicket])
    where
      mostConflictedTicket =
          let t = foldr1 (\t1 t2-> if fst t1 >= fst t2 then t1 else t2) ticketC
          in trace (show t) t
      ticketC = map (\t -> (countConflicted tickets t, t)) tickets

D言語でモナドインタフェースとMaybeモナド

maybe.d

module maybe;

import std.conv;
import std.stdio;

void main()
{
  // モナド則を満たしているかのチェック

  Maybe!int m = Just(10);

  // Left identity
  // return a >>= f == f a
  write("Monad laws 1: ");
  writeln(Maybe!int.Return(10).Bind(x => Just (x^2)) ==
	  (x => Just (x^2))(10));

  // Rithg identity
  // m >>= return == m
  write("Monad laws 2: ");
  writeln(m.Bind(&Maybe!int.Return) ==
	  m);

  // Associativity
  // (m >>= f) >>= g == m >>= (\x -> f x >>= g)
  // f = \y -> Just (y^2)
  // g = \z -> Just (z/3.0)
  write("Monad laws 3: ");
  writeln(m.Bind(y => Just (y^2)).Bind(z => Just(z/3.0)) ==
	  m.Bind(x => (y => Just (y^2))(x).Bind(z => Just (z/3.0))));
}

// Just :: a -> Maybe a
Maybe!T Just(T)(T v)
{
  return Maybe!T.Just(v);
}

// Nothing :: Maybe a
Maybe!T Nothing(T)()
{
  return Maybe!T.Nothing();
}

interface Monad(M) {
  // Bind :: m a -> (a -> m b) -> m b
  M!U Bind(T, U)(T);

  // Return :: a -> m a
  static M!T Return(T)(T);
}

class Maybe(T): Monad!(Maybe!T)
{
  const T value;
  const bool has_value;

  // Type constructor Just T
  this(T v) {
    value = v;
    has_value = true;
  }

  // Type constructor Nothing
  this() {
    value = cast(T)null;
    has_value = false;
  }

  override string toString()
  {
    if (this.isJust()) {
      return "Just " ~ to!string(value) ~
	     " :: Maybe " ~ typeid(T).toString();
    } else {
      return "Nothing" ~ " :: Maybe" ~ typeid(T).toString();
    }
  }

  override bool opEquals(Object a)
  {
    auto other = to!(Maybe!T)(a);
    if (this.isJust() && other.isJust()) {
      return this.value == other.value;
    } else if (this.isNothing() && other.isNothing()) {
      return true;
    } else {
      return false;
    }
  }

  bool isNothing()
  {
    return !has_value;
  }

  bool isJust()
  {
    return has_value;
  }

  static Maybe!T Just(T v)
  {
    return new Maybe!T(v);
  }

  static Maybe!T Nothing()
  {
    return new Maybe!T();
  }

  public Maybe!U Bind(U)(Maybe!U function(T) f)
  {
    if (this.isJust()) {
      // (Just x) >>= f = Just (f x)
      return f(value);
    } else {
      // Nothing >>= f = Nothing
      return Maybe!U.Nothing();
    } 
  }

  static public Maybe!T Return(T v) {
    return Maybe!T.Just(v);
  }
}

こんなかんじで、モナド則も満たしています。たぶん

$ dmd -run maybe.d
Monad laws 1: true
Monad laws 2: true
Monad laws 3: true

D言語でMaybeモナドのようなもの

インターフェイスを使ってMonadを作りたかったんだけどそれはやり方がよく分からなかった。

import std.conv;
import std.stdio;

void main()
{
  auto a0 = Maybe!(int).just(8);       // Maybe Int
  writeln(a0);                         // Just 8
  auto a1 = a0.bind(&plus);            // Maybe Int
  writeln(a1);                         // Just 9
  writeln(a1.bind(&plus).bind(&plus)); // Nothing
}

// 整数iを受け取って10より小さいならJust (i+1)を返す、
// 10以上ならNothingを返す関数plus
Maybe!(int) plus(int i) {
  if (i < 10) {
    return Maybe!(int).just(i + 1);
  } else {
    return Maybe!(int).nothing();
  }
};

// 何か値を一つ持ってるかもしれないし持ってないかもしれない物のクラス
class Maybe(T)
{
  private T value;
  private bool has_value = false;

  // 何か値があるとき用コンストラクタ
  private this(T a)
  {
    value = a;
    has_value = true;
  }

  // なにも値がないとき用コンストラクタ
  private this()
  {
    has_value = false;
  }

  static Maybe!(T) just(T a)
  {
    return new Maybe!(T)(a);
  }

  static Maybe!(T) nothing()
  {
    return new Maybe!(T)();
  }

  override public string toString()
  {
    if (has_value) {
      return "Just " ~ to!(string)(value);
    } else {
      return "Nothing";
    }
      
  }

  // bind :: Maybe!(T) m => (a -> m a) -> m a
  public Maybe!(T) bind(Maybe!(T) function(T) f)
  {
    if (this.has_value) {
      return f(value);
    } else {
      return this; // Nothing なら何もしない
    }
  }
}

CodeIQのナムドット問題解きました

評価1(最低評価)だったよ!
解説見ながらHaskellで書いてみました。

module Main where

import Data.List

partitionOfSet :: Eq a => [a] -> [[[a]]]
partitionOfSet [] = []
partitionOfSet xs = partSet xs [] []
    where
      partSet [] ys zs     = ys:zs
      partSet (x:xs) ys zs = partSet xs ([x]:ys) zs'
          where
            zs' = foldr (\y a -> partSet xs ((x:y):delete y ys) a) zs ys

numdot :: String -> String
numdot = unlines . map (intercalate ".") . nums
    where nums = map (sort . (map reverse)) . reverse . partitionOfSet

main :: IO ()
main = writeFile "answer.txt" $ numdot "12345"

なかなか簡潔でいいんじゃないかと思うんだけど並び順が答えと一緒にならない……orz