wrongwrongな開発日記

しんまいさんの忘備録

【プログラミング】末尾再帰を使って累乗(バイナリ法)を実装する【Kotlin】

wrongwrong163377.hatenablog.com
続きです。
ネット上のループや通常の再帰を使った実装に比べ、末尾再帰で書いた方がシンプルにバイナリ法を実装できました。

バイナリ法とは

 a^n a^{2^x}を掛け合わせた形に変形することで乗算回数を抑えるアルゴリズムです。
例えば \displaystyle n = 4 = 100{\rm b}*1とした場合、 a^nは以下のように変形できます。
 \displaystyle \begin{align}
a^4 &= a^{2^2 \times {\rm flag}_3} \times a^{2^1 \times {\rm flag}_2} \times a^{2^0 \times {\rm flag}_1} \\
&= a^{4 \times {\rm flag}_3} \times a^{2 \times {\rm flag}_2} \times a^{{\rm flag}_1}
\end{align}
ここで、 \displaystyle {\rm flag} \displaystyle nのビットを示しており、 \displaystyle {\rm flag}_3 = 1, {\rm flag}_2 = 0, {\rm flag}_1 = 0です。
つまり上式は以下のようになります。
 \displaystyle \begin{align}
a^4 &= a^{4 \times {\rm flag}_3} \times a^{2 \times {\rm flag}_2} \times a^{{\rm flag}_1} \\
&= a^4 \times a^0 \times a^0
\end{align}

実装

このアルゴリズムをKotlinで実装したものが以下です。
コメントを書きたかったので改行を挟んでいますが、実質4行で関数全体が実装できています。

tailrec fun pow(a: BigInteger, n: Int, ans: BigInteger = BigInteger.ONE): BigInteger{
    if(n == 0) return ans
    return pow(
        a * a, //a^2^xを作っておく
        n.ushr(1), //nを右ビットシフトして一番下の桁をずらしていく、符号は無視
        if(n.and(1) == 1) ans * a else ans //nの最終ビットが1なら掛け、それ以外は無視する
    )
}

おまけ

通常ループをpow_nとして実装し、以下の状態で動かしてみました。

import java.math.BigInteger
import kotlin.system.measureTimeMillis

//累乗(バイナリ法)
tailrec fun pow(a: BigInteger, n: Int, ans: BigInteger = BigInteger.ONE): BigInteger{
    if(n == 0) return ans
    return pow(a * a,  n.ushr(1),  if(n.and(1) == 1) ans * a else ans)
}

//通常ループ
fun pow_n(a: BigInteger, n: Int): BigInteger{
    var ans = BigInteger.ONE
    for(i in 1..n){ ans *= a }
    return ans
}

fun main(args: Array<String>) {
    for(i in 0..100000 step 10000){
        val time1 = measureTimeMillis{
            pow(BigInteger("17"), i)
        }
        val time2 =  measureTimeMillis{
            pow_n(BigInteger("17"), i)
        }
        println("$i,$time1,$time2")
    }
}
実行結果

 17^{100000}とかまでいくとすごい差が付きますね。
f:id:wrongwrongwrongwrong163377:20181210064747p:plain

*1:100bは2進数表記

【プログラミング】末尾再帰を使う【Kotlin】

末尾再帰とは

この記事ではtailrec funで宣言すると末尾再帰最適化がかかる関数全てを末尾再帰であるとします。

なぜ末尾再帰が必要なのか

再帰的な書き方ではコードが美しくなる反面、実行時間が遅い、スタックオーバーフローを引き起こすなど、実用上の問題があります。
一方末尾再帰最適化を行えば、コンパイル結果はforやwhileを使うのと同じになるので、実用性を保ちながら再帰で書くことが可能になります。
また、単純な再帰で書くよりもシンプルに書くことができる場合もあります。
今回はKotlinを用いて説明をしていますが、言語やコンパイラによっては末尾最適化を行なってくれるものがあります。

もう少し詳しく

個人的理解

末尾の条件に引っかからなかった時に、再帰呼び出しの結果のみを返すのが末尾再帰再帰呼び出しの結果に何か処理を行なって返すのが通常の再帰と理解しています。

実装による解説

※雑実装なので1以下を入れると結果がおかしくなります。後結果が大きくなるのでBigIntegerで計算しています。
通常の再帰関数で階乗を実装すると以下のようになると思います。

val TWO = BigInteger("2")

fun fact(n: BigInteger): BigInteger{
    if(n.compareTo(TWO) < 1) return TWO
    return n * fact(n.dec())
}

一方、末尾再帰最適化が効くように書き直した結果が以下です。

val TWO = BigInteger("2")

tailrec fun fact_t(n: BigInteger, ans:BigInteger = BigInteger.ONE): BigInteger{
    if(n.compareTo(TWO) < 1) return ans * TWO
    return fact_t(n.dec(), ans * n)
}

前者は再帰呼び出しの結果にnを掛けており、後者は再帰呼び出しの結果のみを返しています。

使ってみる

ここまでの内容をまとめると以下のようになります。
通常の実装で10000!を計算しようとすればスタックオーバーフローで落ちますが、末尾最適化を行うことで正常に計算が行えます。

import java.math.BigInteger

val TWO = BigInteger("2")

fun fact(n: BigInteger): BigInteger{
    if(n.compareTo(TWO) < 1) return TWO
    return n * fact(n.dec())
}

tailrec fun fact_t(n: BigInteger, ans:BigInteger = BigInteger.ONE): BigInteger{
    if(n.compareTo(TWO) < 1) return ans * TWO
    return fact_t(n.dec(), ans * n)
}

fun main(args: Array<String>) {
    //println(fact(BigInteger("10000"))) java.lang.StackOverflowError
    println(fact_t(BigInteger("10000")))
}
デコンパイル結果

通常実装のfactのコメントを外した上でビルドし、Javaデコンパイルした結果です。
fact_tの呼び出しが再帰ではなくなっていることが分かります。

import java.math.BigInteger;
import kotlin.Metadata;
import kotlin.jvm.internal.Intrinsics;
import org.jetbrains.annotations.NotNull;

@Metadata(
   mv = {1, 1, 13},
   bv = {1, 0, 3},
   k = 2,
   d1 = {"\u0000\u001c\n\u0000\n\u0002\u0018\u0002\n\u0002\b\u0007\n\u0002\u0010\u0002\n\u0000\n\u0002\u0010\u0011\n\u0002\u0010\u000e\n\u0002\b\u0002\u001a\u000e\u0010\u0004\u001a\u00020\u00012\u0006\u0010\u0005\u001a\u00020\u0001\u001a\u001b\u0010\u0006\u001a\u00020\u00012\u0006\u0010\u0005\u001a\u00020\u00012\b\b\u0002\u0010\u0007\u001a\u00020\u0001H\u0086\u0010\u001a\u0019\u0010\b\u001a\u00020\t2\f\u0010\n\u001a\b\u0012\u0004\u0012\u00020\f0\u000b¢\u0006\u0002\u0010\r\"\u0011\u0010\u0000\u001a\u00020\u0001¢\u0006\b\n\u0000\u001a\u0004\b\u0002\u0010\u0003¨\u0006\u000e"},
   d2 = {"TWO", "Ljava/math/BigInteger;", "getTWO", "()Ljava/math/BigInteger;", "fact", "n", "fact_t", "ans", "main", "", "args", "", "", "([Ljava/lang/String;)V", "FactTest"}
)
public final class FactKt {
   @NotNull
   private static final BigInteger TWO = new BigInteger("2");

   @NotNull
   public static final BigInteger getTWO() {
      return TWO;
   }

   @NotNull
   public static final BigInteger fact(@NotNull BigInteger n) {
      Intrinsics.checkParameterIsNotNull(n, "n");
      if (n.compareTo(TWO) < 1) {
         return TWO;
      } else {
         BigInteger var10000 = n.subtract(BigInteger.ONE);
         Intrinsics.checkExpressionValueIsNotNull(var10000, "this.subtract(BigInteger.ONE)");
         BigInteger var2 = fact(var10000);
         var10000 = n.multiply(var2);
         Intrinsics.checkExpressionValueIsNotNull(var10000, "this.multiply(other)");
         return var10000;
      }
   }

   @NotNull
   public static final BigInteger fact_t(@NotNull BigInteger n, @NotNull BigInteger ans) {
      while(true) {
         Intrinsics.checkParameterIsNotNull(n, "n");
         Intrinsics.checkParameterIsNotNull(ans, "ans");
         BigInteger var10000;
         if (n.compareTo(TWO) < 1) {
            BigInteger var3 = TWO;
            var10000 = ans.multiply(var3);
            Intrinsics.checkExpressionValueIsNotNull(var10000, "this.multiply(other)");
            return var10000;
         }

         var10000 = n.subtract(BigInteger.ONE);
         Intrinsics.checkExpressionValueIsNotNull(var10000, "this.subtract(BigInteger.ONE)");
         BigInteger var4 = var10000;
         var10000 = ans.multiply(n);
         Intrinsics.checkExpressionValueIsNotNull(var10000, "this.multiply(other)");
         BigInteger var5 = var10000;
         ans = var5;
         n = var4;
      }
   }

   // $FF: synthetic method
   @NotNull
   public static BigInteger fact_t$default(BigInteger var0, BigInteger var1, int var2, Object var3) {
      if ((var2 & 2) != 0) {
         BigInteger var10000 = BigInteger.ONE;
         Intrinsics.checkExpressionValueIsNotNull(var10000, "BigInteger.ONE");
         var1 = var10000;
      }

      return fact_t(var0, var1);
   }

   public static final void main(@NotNull String[] args) {
      Intrinsics.checkParameterIsNotNull(args, "args");
      BigInteger var1 = fact(new BigInteger("10000"));
      System.out.println(var1);
      var1 = fact_t$default(new BigInteger("10000"), (BigInteger)null, 2, (Object)null);
      System.out.println(var1);
   }
}

【日記】ドラム式洗濯機導入メモ

乾燥機能欲しさにドラム式洗濯機を導入したので、導入時のことをメモります。

www.sharp.co.jp

お手入れ

乾燥機用フィルター

1乾燥毎に取り出してきれいにする必要が有ります。

洗濯機用フィルター

こちらは2週間~程度できれいにする必要が有ります。

引っ越す時

設置に来てくれた方曰く「付属していた金具を引っ越し屋に渡せば後はよしなにやってくれる」だそうです。

感想

手入れの手間に見合うだけの洗い上がりが有ると嬉しいな……。

【日記】アドベントカレンダーに投稿した【プログラミング】

折角の機会ということで、弊社(言ってみたかった)のアドベントカレンダーに以下2記事を投稿しました。

qiita.com

qiita.com

感想

人生初アドベントカレンダーでした。

この記事に引き続きKotlinでSpringBoot触ってましたが、そもそもSpringBootに不慣れなこともあって、かなり苦戦しています。

SpringBootは業務でも使うので、もっと学習していこうと思います。最近Ktorというものを知って心が揺らいでますが。

引き続き手を動かしていきます。

【プログラミング】JetBrains製IDEでSQLのハイライトを設定する

SQLにはDialect(方言)が多々あり、IDEに適切なDialectを設定しなければハイライトや補完がうまく機能しません。

設定方法

SQLファイルで右クリックし、Change Diarectを選びます。
f:id:wrongwrongwrongwrong163377:20181205174353p:plain
以下のようにメニューが出るので、使いたいものを選択します。
f:id:wrongwrongwrongwrong163377:20181205174559p:plain

まとめて設定する

利用するDialectをプロジェクト/IDE単位でまとめて設定することもできます。
先ほどのメニューから一番下のSQL Diarectsを選びます。
f:id:wrongwrongwrongwrong163377:20181205174739p:plain
以下の画面が出るので、Global SQL DiarectやProject SQL Diarectを設定すればOKです。
f:id:wrongwrongwrongwrong163377:20181205175433p:plain

【Kotlin】バリデーション用のアノテーションを自作する【SpringBoot】

↓の続きです。
wrongwrong163377.hatenablog.com
記事執筆時点でのプロジェクトリポジトリは以下。
github.com

やること

フィールド用に名前が半角スペースで2分割できるかをチェックするCustom Validatorを作ります。
深い理解ができていないので、作って動かす程度の内容です。
Custom Validatorを作る上で必要な作業は以下の3つです。

アノテーションクラスを用意する

アノテーションクラスは、Javaでいう@interfaceです。
早速ですが、完成したアノテーションクラスは以下の通りです。

@Target(AnnotationTarget.FIELD)
@Retention(AnnotationRetention.RUNTIME)
@MustBeDocumented
@ReportAsSingleViolation
@Constraint(validatedBy = [CanSplitBySpaceValidator::class])
annotation class CanSplitBySpace(
        val message: String = "message",
        val groups: Array<KClass<out Any>> = [],
        val payload: Array<KClass<out Payload>> = []
)
解説

付与しているアノテーション関連は大体Javaと同じです。個々の機能の説明は長くなるので省略します。
@Constraint(validatedBy = [CanSplitBySpaceValidator::class])に指定しているクラスは、次に実装するバリデーター本体です。
Javaとの相違点としては、@Target@Retention辺りがKotlin独自のクラスになっている点と、メッセージやgroups等の指定の方法が異なる点があります。
また、後述しますが、Kotlinで作成したアノテーションfield:を指定しなくても正常に動作します。

バリデーターを作る

こちらはJavaの内容とほぼ変わりません。

class CanSplitBySpaceValidator: ConstraintValidator<CanSplitBySpace, String>{
    override fun initialize(constraintAnnotation: CanSplitBySpace) {}

    override fun isValid(value: String?, context: ConstraintValidatorContext?): Boolean {
        //nullなら何もしない
        if(value == null) return true
        //スペースで2分割できなければいけない
        return value.split(" ").size == 2
    }
}

ConstraintValidatorに指定しているのは、作成したアノテーションと、アノテーションが処理する対象のクラスです。

ここまでを合わせて

作成したアノテーションとバリデーターは以下の通りです。

import javax.validation.*
import kotlin.reflect.KClass

//アノテーション
@Target(AnnotationTarget.FIELD)
@Retention(AnnotationRetention.RUNTIME)
@MustBeDocumented
@ReportAsSingleViolation
@Constraint(validatedBy = [CanSplitBySpaceValidator::class])
annotation class CanSplitBySpace(
        val message: String = "message",
        val groups: Array<KClass<out Any>> = [],
        val payload: Array<KClass<out Payload>> = []
)

//バリデーター本体
class CanSplitBySpaceValidator: ConstraintValidator<CanSplitBySpace, String>{
    override fun initialize(constraintAnnotation: CanSplitBySpace) {}

    override fun isValid(value: String?, context: ConstraintValidatorContext?): Boolean {
        //nullなら何もしない
        if(value == null) return true
        //スペースで2分割できなければいけない
        return value.split(" ").size == 2
    }
}

付与して使う

前述の通り、field:を付ける必要はありません(付けても問題なく動きます)。

//import com.wrongwrong.modeltest.annotation.CanSplitBySpace インポート
import java.util.*
import javax.validation.constraints.AssertTrue
import javax.validation.constraints.NotNull

data class MyModel(
        @field:NotNull(message = "idはnull不許可")
        val id: Long?,
        @CanSplitBySpace(message = "名前が半角スペースで2つに分割できない")
        val name: String?,
        val create: Date?,
        val update: Date?
) {
    @AssertTrue(message = "updateがcreateより過去")
    fun isLater(): Boolean {
        if(create == null || update == null) return true
        return create.before(update) || create == update
    }
}

Curlで叩くと以下のようになります。

$ curl -X POST -H "Content-Type: application/json" -d '{"id":1, "name":"wrongwrong", "create":"2018-11-01", "update":"2018-11-02"}' localhost:8080/my
[Field error in object 'myModel' on field 'name': rejected value [wrongwrong]; codes [CanSplitBySpace.myModel.name,CanSplitBySpace.name,CanSplitBySpace.java.lang.String,CanSplitBySpace]; arguments [org.springframework.context.support.DefaultMessageSourceResolvable: codes [myModel.name,name]; arguments []; default message [name]]; default message [名前が半角スペースで2つに分割できない]]
$ curl -X POST -H "Content-Type: application/json" -d '{"id":1, "name":"wrong wrong", "create":"2018-11-01", "update":"2018-11-02"}' localhost:8080/my
post:MyModel(id=1, name=wrong wrong, create=Thu Nov 01 09:00:00 JST 2018, update=Fri Nov 02 09:00:00 JST 2018)

参考にさせていただいた記事

discuss.kotlinlang.org
qiita.com
qiita.com

【Kotlin】SpringBootでControllerが受け取った内容をバリデーションするまで【SpringBoot】

↓の続きです。
wrongwrong163377.hatenablog.com
Post/Putで受け取った内容をBeanのバリデーション/相関チェックするところまでやります。
この記事の内容が完了した状態のリポジトリは以下。
github.com

やること

  • モデルを追加する
  • コントローラーを追加する

モデルを追加する

↓のような形でモデルを追加します。
f:id:wrongwrongwrongwrong163377:20181202152857p:plain
持っているのはidと名前、作成日時、更新日時のデータとします。
バリデーション内容は、idがnullチェック、updateがcreateより過去でないかの相関チェックです。

import java.util.*
import javax.validation.constraints.AssertTrue
import javax.validation.constraints.NotNull

data class MyModel(
        @field:NotNull(message = "idはnull不許可")
        val id: Long?,
        val name: String?,
        val create: Date?,
        val update: Date?
) {
    @AssertTrue(message = "updateがcreateより過去")
    fun isLater(): Boolean {
        if(create == null || update == null) return true
        return create.before(update) || create == update
    }
}

Javaのノリでアノテーションをそのまま振ってしまうと正常に動作しないので、@field:...と書く必要があります。
AssertTrue/Falseを使った相関チェックはJavaの時と大差ありません。

コントローラーにメソッドを追加する

前回から引き続いて、以下のようにPostを受け取るコントローラーを追加します。
今回は「Postされた内容を受け取り、文字列として返す」ことをやっています。
@RequestBodyは、Jsonを受け取ってマッピングするためのものです。
@Validatedを付与し、hasErrors()でバリデーション結果をチェックしています。

import com.wrongwrong.modeltest.model.MyModel
import org.springframework.ui.Model
import org.springframework.validation.BindingResult
import org.springframework.validation.annotation.Validated
import org.springframework.web.bind.annotation.*

@RestController
@RequestMapping("my")
class MyController{
    @GetMapping
    fun myGetTest(model: Model): String{
        return "hello from spring boot"
    }

    @PostMapping
    fun myPostTest(
            @RequestBody @Validated myModel: MyModel,
            bindingResult: BindingResult
    ): String {
        if(bindingResult.hasErrors()){
            return bindingResult.allErrors.toString() + "\n"
        }

        return "post:" + myModel.toString() + "\n"
    }
}

叩いてみる

Curlで叩くと以下のようになります。

エラー無し
$ curl -X POST -H "Content-Type: application/json" -d '{"id":1, "name":"My Name", "create":"2018-11-02", "update":"2018-11-02"}' localhost:8080/my
post:MyModel(id=1, name=My Name, create=Fri Nov 02 09:00:00 JST 2018, update=Fri Nov 02 09:00:00 JST 2018)
idがnull
$ curl -X POST -H "Content-Type: application/json" -d '{"name":"My Name", "create":"2018-11-02", "update":"2018-11-02"}' localhost:8080/my
[Field error in object 'myModel' on field 'id': rejected value [null]; codes [NotNull.myModel.id,NotNull.id,NotNull.java.lang.Long,NotNull]; arguments [org.springframework.context.support.DefaultMessageSourceResolvable: codes [myModel.id,id]; arguments []; default message [id]]; default message [idはnull不許可]]
updateがcreateより過去
$ curl -X POST -H "Content-Type: application/json" -d '{"id":1, "name":"My Name", "create":"2018-11-03", "update":"2018-11-02"}' localhost:8080/my
[Field error in object 'myModel' on field 'later': rejected value [false]; codes [AssertTrue.myModel.later,AssertTrue.later,AssertTrue.boolean,AssertTrue]; arguments [org.springframework.context.support.DefaultMessageSourceResolvable: codes [myModel.later,later]; arguments []; default message [later]]; default message [updateがcreateより過去]]

参考にさせていただいた記事

qiita.com
beatdjam.hatenablog.com