F#で Priority Queueを使う

概要

競技プログラミング的なものを解いているときに, 優先度付きキューを使いたくなることがあるのでそのメモ

コード

.NETの標準ライブラリには存在しないので F#向けのコレクションライブラリを nugetから取ってくる. fsxで書いている場合は以下のような行を足す. projectがある場合は dotnet add で依存関係を追加する

#r "nuget: FSharpx.Collections"

定義を見るとわかるが, キューの要素は comparison制約を満たす必要があり, System.IComparableを実装している必要がある. IComparableを実装する際は Equals, GetHashCodeも overrideする必要があるのでそれを行う.

以下に例を示す. 年齢順, 年齢が同じなら名前で並べるというもの. F#で独自の比較, 等価性のチェックを行う場合は該当の methodを override, 実装するだけでなく属性も指定する必要があるようである.

open FSharpx.Collections

[<CustomEquality; CustomComparison>]
type PersonData =
    { Name: string
      Age: int }

    override this.GetHashCode() = hash this

    override this.Equals other =
        match other with
        | :? PersonData as o -> this.Name = o.Name && this.Age = o.Age
        | _ -> false

    interface System.IComparable with
        member this.CompareTo other =
            match other with
            | :? PersonData as o ->
                if this.Age <> o.Age then
                    compare this.Age o.Age
                else
                    compare this.Name o.Name
            | _ -> failwith "cannot compare with different object"

全体の例は以下の通り.

#r "nuget: FSharpx.Collections"

open FSharpx.Collections

[<CustomEquality; CustomComparison>]
type PersonData =
    { Name: string
      Age: int }

    override this.GetHashCode() = hash this

    override this.Equals other =
        match other with
        | :? PersonData as o -> this.Name = o.Name && this.Age = o.Age
        | _ -> false

    interface System.IComparable with
        member this.CompareTo other =
            match other with
            | :? PersonData as o ->
                if this.Age <> o.Age then
                    compare this.Age o.Age
                else
                    compare this.Name o.Name
            | _ -> failwith "cannot compare with different object"

let q =
    PriorityQueue.empty true
    |> PriorityQueue.insert { Name = "Alice"; Age = 42 }
    |> PriorityQueue.insert { Name = "Bob"; Age = 50 }
    |> PriorityQueue.insert { Name = "Chris"; Age = 18 }
    |> PriorityQueue.insert { Name = "David"; Age = 73 }
    |> PriorityQueue.insert { Name = "Elly"; Age = 33 }
    |> PriorityQueue.insert { Name = "Yoshida"; Age = 73 }

let (a, q1) = PriorityQueue.pop q
printfn "poped=%A" a // Yoshida

let (b, q2) = PriorityQueue.pop q1
printfn "poped=%A" b // David

let (c, q3) = PriorityQueue.pop q2
printfn "poped=%A" c // Bob

let (d, q4) = PriorityQueue.pop q3
printfn "poped=%A" d // Alice

let (e, q5) = PriorityQueue.pop q4
printfn "poped=%A" e // Elly

let (f, _) = PriorityQueue.pop q5
printfn "poped=%A" f // Chris

quadmath Perlでハマったところ備忘録

細々とメンテナンスしている Perlモジュールで quadmathが有効な Perlで失敗しているケースがいくつか見られたので対応していた. その対応に関する記録.

usequadmathとは

https://perldoc.perl.org/Config#usequadmath

数値の保持に可能であれば 4倍精度浮動小数点型である __float128を利用するコンフィグオプション. 設定を有効にしてビルドするためには libquadmathがインストールしておく必要がある.

名前だけ聞くと浮動小数点だけ影響があるのかと思うのだけど Perlような言語では整数とか浮動小数点はあいまいなので整数にも影響が出ておりテストがこけていた.

ハマった点

整数の精度が変わる

https://github.com/msgpack/msgpack-perl/blob/10544440a0a47f9d4a1ab78f75d6fccfe17bdeab/t/05_preferred_int.t

大きい整数リテラルを文字列化したときの精度が異なっており予期せぬテスト結果となっていた

#!/usr/bin/env perl

print "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFF=", 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, "\n";
print "0x800000000000000000000000000000=", 0x800000000000000000000000000000, "\n";

上記のスクリプトを quadmathが有効な Perlとそうでない Perlで実行した結果は以下の通り異なるものとなる.

quadmathが有効

0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFF=8.30767497365572420564879412675215e+34
0x800000000000000000000000000000=6.64613997892457936451903530140172e+35

quadmathが無効

0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFF=8.30767497365572e+34
0x800000000000000000000000000000=6.64613997892458e+35

github.com

対応は管理の保守の問題などから quadmath Perlではテストを行わないことにした.

数値から文字列への変換が適切に行えない

https://github.com/gfx/Perl-Data-Util/blob/f8db84cf6fe5c526adfa76d047bfd715296477bf/t/18_is_value.t

の is_integerの浮動小数点数の場合は数値を文字列化してそれを解析して判定を行っているが, 変換に使われていた関数が snprintfだったため正しく変換ができていなかった. snprintf等の標準ライブラリの変換関数は __float128には対応しておらず, quadmath_snprintfを使わなくてはならない.

https://perldoc.perl.org/perlapi#my_snprintf

ifdefで分けることを考えたが Perlソースコードを眺めていたところ, my_snprintfが quadmathを有効にしてビルドした場合内部で quadmath_snprintfを呼び出すような実装になっていたのでそちらを呼ぶように切り替えた。

github.com

modifierと specifierはべた書きしてしまうとポータビリティがなくなるので, Perlで定義されているマクロを使っています.

おわりに

Perlみたいな動的型言語で標準で使われる浮動小数点数の精度を変えるというのは影響は多すぎると思った. あとドキュメントがロクに書かれていないのも辛かった.

unzip file which contains symbolic link by zip-rs

zip-rs does not support symbolic link yet(https://github.com/zip-rs/zip/issues/77). However it is possible by using public APIs as below.

use std::fs;
use std::io;

fn main() {
    std::process::exit(real_main());
}

fn real_main() -> i32 {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 2 {
        println!("Usage: {} <filename>", args[0]);
        return 1;
    }
    let fname = std::path::Path::new(&*args[1]);
    let file = fs::File::open(&fname).unwrap();

    let mut archive = zip::ZipArchive::new(file).unwrap();

    for i in 0..archive.len() {
        let mut file = archive.by_index(i).unwrap();
        let outpath = match file.enclosed_name() {
            Some(path) => path.to_owned(),
            None => continue,
        };

        {
            let comment = file.comment();
            if !comment.is_empty() {
                println!("File {} comment: {}", i, comment);
            }
        }

        if (&*file.name()).ends_with('/') {
            println!("File {} extracted to \"{}\"", i, outpath.display());
            fs::create_dir_all(&outpath).unwrap();
        } else {
            println!(
                "File {} extracted to \"{}\" ({} bytes)",
                i,
                outpath.display(),
                file.size()
            );
            if let Some(p) = outpath.parent() {
                if !p.exists() {
                    fs::create_dir_all(&p).unwrap();
                }
            }

            let is_symlink = if cfg!(unix) {
                const S_IFLINK: u32 = 0o120000;
                file.unix_mode().unwrap() & S_IFLINK == S_IFLINK
            } else {
                false
            };

            if is_symlink {
                #[cfg(unix)]
                {
                    use std::io::Read;
                    use std::os::unix::fs;

                    let mut data = Vec::new();
                    file.read_to_end(&mut data).unwrap();
                    let original = String::from_utf8(data).unwrap();
                    fs::symlink(original, outpath).unwrap();
                }
            } else {
                let mut outfile = fs::File::create(&outpath).unwrap();
                io::copy(&mut file, &mut outfile).unwrap();
                // Get and Set permissions
                #[cfg(unix)]
                {
                    use std::os::unix::fs::PermissionsExt;

                    if let Some(mode) = file.unix_mode() {
                        fs::set_permissions(&outpath, fs::Permissions::from_mode(mode)).unwrap();
                    }
                }
            }
        }
    }

    return 0;
}

Advent Of Code 2020を終えて

memo.sugyan.com

yosuke-furukawa.hatenablog.com

今年始めて参加した Advent of Code 2020年版を終えました

f:id:syohex:20201228212254p:plain

結果は上記のような感じ. 各問題 100位以内に解ければポイントがもらえるのですが, 100位なんて程遠すぎて結果は 0点. これは早くできたなと感じてもそんな問題はみんな早く解けているわけで自分が早く解けたときの方がむしろ順位は低かった印象. ポイントを取るにはまだまだ実力不足であることを感じました

Advent of Codeの特徴

  • コードの提出はない, 答えだけ提出
    • どんなに非効率なアルゴリズムでも答えが出ればいい. 微妙な問題サイズの場合はしばらく待てば解けてしまうこともあった
    • 超早いマシンを持っていれば幾分有利かも
  • 問題の入力が人によって違う
  • 世界中の人が多く解いているので解説が多数ある

感想

  • 初期の方は 1時間もかからず解けていたのであまり手応えがないって思っていたけど, 中盤からどんどん難しくなり休みをほとんど潰した日もあった
  • 問題が(無駄に)ストーリーがあり読んで理解するのに時間がかかる
    • 英語力が低いのが原因
    • 最速の人の解答時間に私の問題理解速度が追いついていないレベル. 10分ぐらい読んでやっとわかってことが多々あった
  • 入力のパースが面倒くさい
    • 去年はそんなことなかったらしいけど..
    • 構造と呼べるものも微妙だし, 問題によっては末尾に改行があったりなかったりと面倒くさかった
    • C++でずっと解いていたけど, 面倒くさくて Pythonで一問やってしまった. しかしC++で突き通そうということで全部 C++でやりましたが, 面倒くさかった
  • 例があるのは助かる
    • 例を見て問題をちゃんと理解できたということが多々あった
    • テストケースとして使える
    • しかし例があることで逆によくわからなくなることもあった(day 17の三次元, 四次元ライフゲーム)

問題の振り返り

全く解答が思いつかなかったという問題はありませんでしたが, 現実時間で解答を求められない問題がいくつかありそれらは解説を見た上で解答を作成しました. わからなかったのは以下の問題.

  • day 10 part2
    • 電源アダプタの並べ方が何通りあるかという問題. 愚直に求める方法しか思いつかず.
  • day 23 part2
    • ボール並び替えゲームを 1000万回やった後の並び方を求める問題. 愚直に求める方法しか思いつかず
    • 問題的に時間がかかることは予見できていたのだけど, 見当はずれの効率化を探していていつまで経っても効率的な方法が思い浮かばなかった

私の解答がいまいちだった問題として * day 15 part02 * 非効率的な実装だったけど, 3分ぐらい動かしていたら答えが出たのでそれで提出. 考え直したい

このあたりは単純に力不足だなと感じた. 来年はできれば解説を一つも見ずに完走したい. あとやっぱり自分で考えに考えて解くってのはやっぱり快感が伴うのでそういう意味でも自分で解けたらと思いました

最後に

楽しい経験ができたのと, まだまだ自分が力不足だということが認識できました. 来年も参加して 1ポイントでも取れるように実力をつけていければと思います

この半年でやったこと, 継続していること

studio3104.hatenablog.com

を見て, leetcodeがキリがいいところだったので, 私も真似して書いてみる. そもそも私は 40年近く生きてきて何かを継続してできたということがほとんどない. あったとしても若かりし頃のゲーセン通いぐらいで勉強に関してはおそらく皆無である. 今年の何ヶ月か過ぎたあたりでふと自分のキャリアについて考えたとき, 何もできることなくてこのままでいいのかとなって, (遅すぎるけど)いい加減真面目に考えないとまずいとなった. そこで雑ではあるが自分の幅を広げるために根本的なプログラミングスキルと英語をなんとかしようと思い, いろいろ試している. 初めて危機感を持った影響なのか今のところは毎日少しずつではあるが継続できていることもある. それらについてまとめておこうと思う.

leetcode

leetcode.com

@sugyanさんが Twitterで継続しているというのを見て自分もやってみようと思って始めた.

f:id:syohex:20201216221800p:plain

現状は上記の通りで今日で 500問分解いた. 基本的には C++で解いている. 他の人に比べると easyが圧倒的に多いので質的にどうなのかというのがあるが.. アルゴリズム系はまるっきりダメだったのでとりあえず easyからひたすらやっていった. 初期の頃は mediumでもものすごい難しく感じてこれで mediumなのかと自分のレベルの低さに驚いた.

現状

  • mediumぐらいならなんとかなるかなってことは増えた. ただ mediumでもまだまだすんなりとはいかない問題は多い.
  • アルゴリズムを考えるときは計算量をなるべく意識できるようにはなった.
  • 苦手な分野(=勉強しなくてはいけない分野)が何なのか見えてきた.

取り組み方

  • できれば一日 1問は解く. dailyの課題は見て, なんとかなりそうなら解く. 全く無理そうなら諦める
  • 同じ問題を何度も解く
    • 1月前とかにやった問題を改めて解こうとするとすんなり解けないことが案外多かったりするので, しっかり理解していることを確認するために過去に解いた問題でも定期的にやっている.
    • それで過去の結果と比べてより早かったり, コードがスマートに書けていると成長を感じる. 同じところでハマったりすると改めてちゃんと確認する

leetcodeのいいところ

  • 問題がテストを書きやすい
    • 基本的には関数の引数と戻り値で考えられるのでテストしやすい. AtCoderだと入力・出力が標準入出力だからそもそも面倒くさい.
  • 世界中でやっている人がいるので参考にできるものが多い. コードしかり解説然り

leetcodeのあまり良くないと感じたところ

  • 問題のレベル判定が雑. easy, medium, hardが当てにならないこともある
  • 条件が雑, 問題分が不親切なものが少なからずある
  • SQLの問題がクイズみたいなのばっかりで実際の現場で書く SQLではないことがほとんど

iknow

iknow.jp

初めは英会話スクールを考えていたのだけど, コロナだし, そもそも私 TOEIC 300点ぐらいの論外レベルなのでまずは基礎だろうということで英単語から始めるということで iknowを始めてみました.

f:id:syohex:20201216223444p:plain

現状は上記のような感じで毎日 40-50分程度 200日ぐらい継続できている.

現状

  • 単語力は少し上がったような気はするが, まだまだわからない単語が多い.
  • 元が低すぎてあれだけど, 英語力が伸びたという感じはまだまだしないがすぐ伸びるものでもないので継続したいとは考える.

取り組み方

  • ひたすら単語 + 文章問題をやる

LingoChamp

www.lingochamp.com

先月ぐらいから始めており, 現在 45日間ぐらい継続している. iknowだけだと知識だけだし話す練習もした方がいいかと思って始めた. LingoChampでは何か喋ったあと自分の声を流されるのですが, 本当に自分の発音がダメダメなと気付かされる. 某米国在住の日本人の方のプレゼンなどを見たときに英語の発音がネイティブっぽくないなぁとか生意気にも思っていたことがあったけど, 自分の発音はもっと論外ということに気付かされた.

現状

  • 自分の発音のひどさを実感した
  • 単純な単語でも全然正しく発音できないものが多々あることに気付かされる
  • 大学のときなど発音がひどいとよく怒られていてそのとき何も理解できなかったけど, ここが変だったのかというのに 20年ぐらいして気付かされた.
  • 発音するとき意識をするようになった(本当は無意識で適切な発音がいいのだろうけど, その域にはまだまだ到達できない)

取り組み方

  • 毎日 20-30分課題をやる

その他

AtCoder

atcoder.jp

  • たまに解いている. A, Bと Cをたまにって感じ. leetcodeよりも難しい印象. leetcodeと違い, 数値の範囲を意識しないといけないことが多い.
  • 前述の通り標準入出力を使うのは若干手間だと感じている.

ELLLO

elllo.org

  • 学習サイトって感じではあまりないけど, リスニングのためにたまに聞いている
  • 日常会話と言われるとやや違う気もするけど, ありそうな会話ではあるので面白い. いざしゃべるとなるとこんな感じでスラスラ言えないといけないんだろうなぁと感じる

Advent of Code

adventofcode.com

  • これも sugyanさん経由で知って始めてみた.
  • 今のところ 1問だけ常識的な時間で解く方法がわからなくて解説を見た以外は自力で解けている. できれば完走したい.

最後に

ここまで自分が何かを継続できていることが信じられないが, 現状なんとかやれている. ただ正直なところ継続できている一番大きな理由はこの一年仕事が全くうまくいっておらず何の成果も上げられていない反動によるところが大きいと思う. 今後仕事がどうなるかはわからないけどこれらのことを継続していって自分の能力を上げることにつなげていればと思う.

年取ったからって遅いってことはないと思いますが, 若い内からやるに越したことないので若い人はなるべく早くやるといいと思います.

vscodevimで Ctrl- keyは VScodeのものを使うようにする

IdeaVimとか VSVim(Visual Studio)は IDEのキーを優先するのをデフォルトにできるのだけど, vscodevimはデフォルトだとめちゃ VimVScode本来のショートカットキーがほとんど使えない. macOSだと Command keyベースで Ctrlキーのものと衝突しないというのはあるが, Windows, Linuxではコンフリクトする. Vim好きならそれでいいんだろうけど, 個人的には Ctrl-wの画面分割ぐらいしか使わないので, VScode本来のキーを使う方法をようやく調べてみた.

結論としては vim.handleKeys を調整すればよかった. File -> Preferences -> Settingsから handlekeysで検索するとヒットするので以下のように設定した.

    "vim.handleKeys": {
        "<C-a>": false,
        "<C-f>": false,
        "<C-n>": false,
        "<C-c>": false,
        "<C-x>": false,
        "<C-v>": false,
        "<C-b>": false,
        "<C-j>": false,
        "<C-k>": false
    }

しばらくこれで試してみる.

C#で簡素な Scheme処理系を書いてみた

github.com

peter.michaux.ca

C#でやった. C#で書いたのは最近 Unityにふれることがあるのでその影響. C#らしい部分はほとんどない. むしろ書きづらかったさえある. あとこの前に Common Lisp風の処理系を書いていたのでシンボルと値の扱いに 若干混乱した. 処理も無駄に複雑になってしまったと思う. あと C#力が低すぎるというのもあり, クオリティは低い. まだまだ勉強する必要がある.

Linux環境で JetBrains Riderで書いたけど, Visual Studioの出来がいいから(特に C#開発ではすごい), 競合する C#IDEの出来はいいんだなと感心した(言語の性質的なところもあるんだろうけど, CLionもそれぐらい便利だったらなぁと思った)