牧場生まれの牛乳

いろんなことしてる牛乳です。

2022年の振り返り

去年も振り返りブログを書いていたみたいなので、今年も振り返りブログを書いていきます。

本業関係

高専に居た頃からバイトしていたが、今年度からちゃんと社員としてLINE株式会社の社員として働きはじめることになりました。研修でSPY×FAMILYのアーニャをモチーフとしたチャットアプリを作成したり、FRRにコントリビューションしたりとアルバイトの頃と似たようなことを継続して続けています。アルバイトの時にやっていることはJANOG49でも発表しているので、より詳しく知りたかったらそっちを確認してもらえればです。

www.janog.gr.jp

フルタイムで仕事に時間を割けるようになった分、本業にコミットできるようになりました。やっていることは社外に殆ど出ていないですが、社外で出ているものとしては、FRRへのコントリビューションがあります（ほとんど細かい修正ばっかりですが...）。

github.com

ちょっと本業から逸れることとして、JANOG50からJANOGでNETCONスタッフをやっています。JANOG51からは本格的に参加して、NETCONと呼ばれるネットワークコンテストのバックエンドの実装をしたりしています。JANOG51のNETCON Wrap-upで発表する予定です。

www.janog.gr.jp

github.com

後述しますが、9月から北海道からリモートワークで仕事をしています。弊社のLINE Hybrid Wroking Styleという制度を利用してリモートワークしています。どうなるかなと思いながら4ヶ月働いてみましたが、今のところはあんまり支障なく仕事をすることができていると思います。

linecorp.com

あと今年度から業務で英語を使うことになり、少しだけ英語で話せるようになったぽいです。まだ全然満足して話すことはできないですが、ちょっとだけスキルアップしていたらしいので、継続して頑張っていきたいです。

プライベート

今年度の最も大きな変化は、9月から北海道に移住したことです。まだ4ヶ月程度しか暮らしてないですが、稚内や函館に行ったりしました。僕にしてはかなり旅行に行く機会があったので、どんな経路を通ったのかを地図に記録していますが、北海道を縦に行ったり横に行ったりしています。

それに合わせて念願の一眼レフも買ってしまいました。Sony α7 Ⅳです。普段あんまり高い買い物しないので、会計時にちょっと手が震えてました。初年にしてはいい写真を撮れたかなと思いますが、今後もいい感じの写真を撮っていきたいです。

支笏湖

金森赤レンガ倉庫

道の駅 名水の郷きょうごく

来年やりたいこと

仕事面では粛々とやるべきことをこなしていきますが、来年はもっと対外活動やブログで発信とかしていきたいですね...。今年もFRRの記事を書こうとして、やるやる詐欺を続けてきましたが...。

プライベート面ではいろんなことをやりたいなと思っています。まずは北海道に移住したので、来年こそは車の免許を取ろうと思っています。今は徒歩で移動しているのでかなり大変な時もあり、早く文明の利器の力を借りたいです。他にも、「キャンプに行きたい」「ビール検定を取りたい」などの細々としたやりたいことがあります。

まとめ

他の人のブログとかを見ると、一年かけてなんにもしていないような気持ちになってきますが、来年も少しずつ頑張っていけたらいいなと思ってます。来年も何卒よろしくお願いします。

exabgpでSRv6 L3VPN経路を流すときにハマったことのメモ

よくハマるので走り書きのようなメモ。

exabgpを用いてSRv6 L3VPN経路を広報する際には次のようなconfigを書く。この中で、exabgpから広報するAFI/SAFIのリストにipv4 mpls-vpn, ipv6 mpls-vpnの両方を指定している。だが、実際に広報しているのはIPv4のVPN経路のみである。

neighbor fd00::1 {
    router-id 10.0.0.2;
    local-address fd00::2;
    local-as 65182;
    peer-as 65182;

    capability {
        nexthop true;
    }

    family {
        ipv4 mpls-vpn;
        ipv6 mpls-vpn;
    }

    nexthop {
        ipv4 mpls-vpn ipv6;
    }

    static {
        route 172.31.1.0/24 {
            rd 4:100;
            next-hop 2001:db8:1::;
            extended-community [ target:4:100 ];
            label 1024;
            attribute [0x28 0xc0 0x0500220001001e0020010db800010000000000000000000000001300010006281810001040];
        }
    }
}

これは、exabgpがextended nexthopの設定をパースする際に、AFI/SAFIのペアだけでなく、NHAFI/SAFIのペアも広報する設定になっているかどうかをチェックしているためである。

        if neighbor.nexthop:
            nexthops = []
            for family in nexthop:
                nexthops.extend(nexthop[family])
            if nexthops:
                for afi, safi, nhafi in nexthops:
                    if (afi, safi) not in neighbor.families():
                        self.logger.debug(
                            'skipping nexthop afi,safi ' + str(afi) + '/' + str(safi) + ' as it is not negotiated',
                            'configuration',
                        )
                        continue
                    if (nhafi, safi) not in neighbor.families():
                        self.logger.debug(
                            'skipping nexthop afi ' + str(nhafi) + '/' + str(safi) + ' as it is not negotiated',
                            'configuration',
                        )
                        continue
                    neighbor.add_nexthop(afi, safi, nhafi)

github.com

2021年の振り返り

来年以降の僕のために、今年の振り返りを書き残しておく。来年はもっとちゃんと書きたいが、今年のも書きたい部分については書けたしおっけーなはず。

エンジニア的なこと

トラコン関係では、ICTSC2020, ICTSC2021 夏の陣を開催することができた。やっぱり参加者に出会うことのない大会ってのは寂しいもので、競技中も障害が起きない限りは雑談しまくっていた。ICTSC2020自体からは運営が変わってしまったので、これからオフラインで開催できるのか怪しい面が大きい（これは僕の努力も足りていない部分ではあるんだけど、他のタスクやら精神状態やらでそこまでいろいろ時間を割ききることができなかった）けど、やっぱりオフラインでサーバをマウントしたり、参加者にラックを見せたりするトラコンを復活させたいなって気持ちは少しある。

f:id:proelbtn:20211231110546j:plain
廃棄されるえると

他の大きな出来事としては、STM（ShowNet Team Member）に選ばれたことと、セキュリティ・キャンプの講師をしたことがある。STMでは、普通にネットワークを学んでいるとあまり意識しないL1の知識だったり、新しい技術を知ることができたり、同じネットワークを学んでいる同志に出会えたりとめちゃくちゃ良いことがたくさんあった。また、セキュリティ・キャンプの講師も同様に、いろいろな人にBGPについて教えることで交友関係だったりが広がったなというように感じた。また、自分ももっと頑張っていくぞという気持ちにもなった。

他にも、Linuxカーネルにパッチを投げてマージされたり、FRRにコントリビューションしたりというような活動も行うようになった。この点においては、今年かなり成長をした部分かなというように思う。ここらへんの話については来年のJANOGでも発表する予定です。

patchwork.ozlabs.org

github.com

www.janog.gr.jp

プライベートなこと

3月くらいまでは学校もめちゃくちゃ忙しかったけど、今年に入ってからはかなり余裕のある生活を送れていたと思う。電通大に編入すると単位変換によっては一年間地獄を見るので、きつかった。

人間関係周りで紆余曲折大きすぎていろいろ大変な一年だった。本当にまぁひどかった。辛いことも多かったけど、深夜よく麻雀したり相談に乗ってくれた人たちがいたのがなんやかんや心の支えになっていてとても助かっていた。自分だけでどうにか対処できるような強い気持ちを持っていきたいなって思い続けているけど、あと何年経つのやらって感じがある。

今年は、山梨, 高尾山, 京都, 大阪に行った。山梨はゆるキャンの聖地巡礼を兼ねて行った気がする。高尾山, 京都, 大阪については、現実逃避の旅をしていた。11月から割とメンタルが弱っている時に、卒研とJANOGの資料作りのダブルパンチにあってしまったので、ある程度余暇が出来た冬休みに入った途端、突発的な京都旅行に行くことにした。行きの夜行を乗り忘れ、帰りの新幹線も雪で運転見合わせまくるような無計画を極めた旅行だったけど、行って色々してきたら生きる活力が5回復したので良かった。この旅の最中で、生まれてはじめてたばこを吸ったり、御朱印帳を買っちゃったり、いろいろ自分らしくないことも多くした感じがした。来年はもっと自分らしくないことをして生きていきたいですね。楽しいので。

ちなみにこの現実逃避行は、ふたりエスケープっていう漫画による影響なので全人類は早く読んで現実逃避をした方がいいと思います。

f:id:proelbtn:20211231111035j:plain
富士山

f:id:proelbtn:20211231115859j:plain
高尾山の紅葉

f:id:proelbtn:20211231115654j:plain
清水寺

comic.pixiv.net

まとめ

なんやかんやあって、過去を振り返ると辛い部分だらけだった一年だったけど、総じてみんないい思い出で途中でゲームオーバーしないで生きてこられたのでヨシッと感じている。「来年度は就職するので、そちらの会社でバリバリ成果を出しつつ、プライベートを充実させていきたい」という月並みな来年の目標を持っていますが、もうちょっとちゃんと具体的な目標は後々考えていこうかなと思う。

netfilterについて

netfilterは、Linuxカーネルのデータプレーン中のいくつかの地点に任意の関数をattachすることができるようにしてくれるフレームワークである。netfilterはLinuxのネットワーク機能を実装する際の基礎になるフレームワークで、iptablesやconntrackで利用されている。ここでは、netfilterがどのようなものなのか、どのように実装されているのかという点についてまとめた。

概要

先述の通りnetfilterは、Linuxカーネルのデータプレーン中のいくつかの地点に任意の関数をattachすることができるようにしてくれるフレームワークである。以下に、netfilterの概要図を示す。netfilterは、PREROUTING, INPUT, FORWARD, OUTPUT, POSTROUTINGの5つのフックポイントを提供してくれる。netfilterの利用者はこのフックポイントの好きな地点に任意の関数をattachすることができ、パケットがそのフローを通ったらその関数が実行される。

f:id:proelbtn:20211206221744p:plain

www.semanticscholar.org

netfilterは、多くのLinuxの機能を実装するのに利用されている。代表的なのはiptablesなどのファイアウォール機能だろう。iptablesでは、それぞれのフックポイントで対応するチェインに含まれているルールを逐次評価し、パケットのフィルタリングやロードバランシング、NATなどの機能を提供している。また、conntrackでは、データプレーンを流れるコネクションを追跡するためにnetfilterを利用している。パケットがカーネルに入ってくるPREROUTING, OUTPUTでそのパケットがどのコネクションの通信なのかを判別し、後段に存在するiptablesなどがそのコネクションの情報を利用してステートフルにパケットをフィルタリングしたり、NATのセッションを発見して適切にアドレス変換を行うなどをしている。

また、ネットワークの機能だけではなく、AppArmorやSELinuxなどのMandatory Access Control機能でもnetfilterは利用される。あるプロセスから出る通信が認可されている地点への通信なのかどうかを判別し、もし認可されていなければその通信を遮断するといった目的でnetfilterが利用されている。

このように、netfilterはLinuxの多くの機能を実現するための基盤として利用されている。

フックポイントの定義

では、これらのフックポイントはLinux内でどのように定義されているのだろうか？netfilterのフックポイントの多くは、NF_HOOKを利用して定義されている。一部については、NF_HOOKの内部で呼んでいるnf_hookを直接呼び出している。このどちらかを利用している地点がフックポイントになる。NF_HOOKを参照している地点を検索すると、それなりに多くの地点から参照されていることが分かる。

NF_HOOK identifier - Linux source code (v5.15) - Bootlin

nf_hook identifier - Linux source code (v5.15) - Bootlin

実際にフックポイントが定義されている場所を見てみよう。以下に、ip_local_deliverを示す。この関数は、IPルーティングが行われた後に、ホスト宛のパケットが通る関数である。この関数の最後で、NF_HOOKが呼び出されている。このようにしてフックポイントを定義している。ip_local_deliverでは、INPUTチェインのフックポイントが定義されている。

int ip_local_deliver(struct sk_buff *skb)
{
    /*
    *  Reassemble IP fragments.
    */
    struct net *net = dev_net(skb->dev);

    if (ip_is_fragment(ip_hdr(skb))) {
        if (ip_defrag(net, skb, IP_DEFRAG_LOCAL_DELIVER))
            return 0;
    }

    return NF_HOOK(NFPROTO_IPV4, NF_INET_LOCAL_IN,
               net, NULL, skb, skb->dev, NULL,
               ip_local_deliver_finish);
}

NF_HOOKの定義を見てみよう。NF_HOOKはnf_hookの非常に薄いラッパー関数なので、retに応じてokfnを呼び出すか否かという点が異なる。

static inline int
NF_HOOK(uint8_t pf, unsigned int hook, struct net *net, struct sock *sk, struct sk_buff *skb,
    struct net_device *in, struct net_device *out,
    int (*okfn)(struct net *, struct sock *, struct sk_buff *))
{
    int ret = nf_hook(pf, hook, net, sk, skb, in, out, okfn);
    if (ret == 1)
        ret = okfn(net, sk, skb);
    return ret;
}

netfilter.h - include/linux/netfilter.h - Linux source code (v5.15) - Bootlin

第一引数のpfはプロトコルファミリーを表している。netfilterでは、IPレベルのデータパスだけではなく、ブリッジレベルのデータパスだったり、ARPのデータパスにも同じように関数をアタッチする仕組みが存在する。この中では、NFPROTO_IPV4, NFPROTO_IPV6に限定してまとめているが、他のプロトコルファミリーでも同様な処理が行われている。以下にプロトコルファミリーの一覧を示す。

enum {
    NFPROTO_UNSPEC =  0,
    NFPROTO_INET   =  1,
    NFPROTO_IPV4   =  2,
    NFPROTO_ARP    =  3,
    NFPROTO_NETDEV =  5,
    NFPROTO_BRIDGE =  7,
    NFPROTO_IPV6   = 10,
    NFPROTO_DECNET = 12,
    NFPROTO_NUMPROTO,
};

netfilter.h - include/uapi/linux/netfilter.h - Linux source code (v5.15) - Bootlin

第二引数のhookはフックポイントを表している。この部分はプロトコルファミリー毎に定義されている。ここでは、IPv4, IPv6で利用されるフックポイントについて見ていく。IPv4, IPv6では、以下のようなフックポイントが存在する。これは、それぞれ先に述べたPREROUTING, INPUT, FORWARD, OUTPUT, POSTROUTINGに対応している。他にも、NFPROTO_ARPでは、NF_ARP_IN, NF_ARP_OUT, NF_ARP_FORWARDなどのフックポイントが定義されている。

enum nf_inet_hooks {
    NF_INET_PRE_ROUTING,
    NF_INET_LOCAL_IN,
    NF_INET_FORWARD,
    NF_INET_LOCAL_OUT,
    NF_INET_POST_ROUTING,
    NF_INET_NUMHOOKS,
    NF_INET_INGRESS = NF_INET_NUMHOOKS,
};

最後の引数は、nf_hookの結果としてACCEPTが返された時に呼び出される関数である。それ以外の引数については以下の通りである。net, skbは常に存在しているが、sk, in, outはフックポイントによってはNULLが代入される。例えば、NF_INET_LOCAL_INの呼び出しにおけるsk, outやNF_INET_LOCAL_OUTの呼び出しにおけるinは定義不能である。

  • struct net *net: 現在のnetwork namespaceを表す構造体（常に存在する）
  • struct sock *sk: ソケットを表す構造体
  • struct sk_buff *skb: パケット本体を表す構造体
  • struct net_device *in: 入力デバイスを表す構造体
  • struct net_device *out: 出力デバイスを表す構造体

nf_hook

それでは次に、NF_HOOKの内部で呼び出されていたnf_hookについて見ていく。とはいっても、非常に構造はシンプルである。まずはじめに、第一引数, 第二引数に与えられたプロトコルファミリーとフックポイントの情報から、フック関数のリストを取得し、hook_headに代入する。

static inline int nf_hook(u_int8_t pf, unsigned int hook, struct net *net,
              struct sock *sk, struct sk_buff *skb,
              struct net_device *indev, struct net_device *outdev,
              int (*okfn)(struct net *, struct sock *, struct sk_buff *))
{
    struct nf_hook_entries *hook_head = NULL;
    int ret = 1;

  // snipped

    rcu_read_lock();
    switch (pf) {
    case NFPROTO_IPV4:
        hook_head = rcu_dereference(net->nf.hooks_ipv4[hook]);
        break;
    case NFPROTO_IPV6:
        hook_head = rcu_dereference(net->nf.hooks_ipv6[hook]);
        break;
    // snipped
    }

nf_hook_entriesは、フック関数の個数を保持するnum_hook_entriesと、フック関数自体を保持するhooksから成る構造である。nf_hook_entryは、フック関数へのポインタとプライベートなデータ保存領域の対から成る。

struct nf_hook_entries {
    u16             num_hook_entries;
    struct nf_hook_entry       hooks[];
};

netfilter.h - include/linux/netfilter.h - Linux source code (v5.15) - Bootlin

struct nf_hook_entry {
    nf_hookfn           *hook;
    void               *priv;
};

netfilter.h - include/linux/netfilter.h - Linux source code (v5.15) - Bootlin

フック関数のリストが取得できた場合、nf_hook_slowを呼び出してフック関数を逐次呼び出していく。

 if (hook_head) {
        struct nf_hook_state state;

        nf_hook_state_init(&state, hook, pf, indev, outdev,
                   sk, net, okfn);

        ret = nf_hook_slow(skb, &state, hook_head, 0);
    }
    rcu_read_unlock();

    return ret;
}

nf_hook_slowでは、第三引数で与えられたnf_hook_entriesに格納されているフック関数を順番に呼び出し、フック関数から返されたverdictに対応する処理を行う。実際のフック関数の呼び出しはnf_hook_entry_hookfnで行っている。

int nf_hook_slow(struct sk_buff *skb, struct nf_hook_state *state,
         const struct nf_hook_entries *e, unsigned int s)
{
    unsigned int verdict;
    int ret;

    for (; s < e->num_hook_entries; s++) {
        verdict = nf_hook_entry_hookfn(&e->hooks[s], skb, state);

後半部分では、フック関数から返されたverdictに応じて必要があればパケット処理を行っている。

     switch (verdict & NF_VERDICT_MASK) {
        case NF_ACCEPT:
            break;
        case NF_DROP:
            kfree_skb(skb);
            ret = NF_DROP_GETERR(verdict);
            if (ret == 0)
                ret = -EPERM;
            return ret;
        case NF_QUEUE:
            ret = nf_queue(skb, state, s, verdict);
            if (ret == 1)
                continue;
            return ret;
        default:
            /* Implicit handling for NF_STOLEN, as well as any other
            * non conventional verdicts.
            */
            return 0;
        }
    }

    return 1;
}

このようにしてフックポイントから事前に登録された関数を呼び出している。

フック関数の登録

これまでのところで、フックポイントがどのように定義されて、どのようにしてフック関数が呼び出されるのかについて見てきた。今度は逆にフック関数を登録する側について見ていく。フック関数を登録するには、nf_register_net_hooksを利用して登録を行う。第一引数はnetwork namespaceを、第二引数は登録する関数を、第三引数では何個登録するのかを指定する。

int nf_register_net_hooks(struct net *net, const struct nf_hook_ops *reg,
              unsigned int n);

core.c - net/netfilter/core.c - Linux source code (v5.15) - Bootlin

では次に、実際にiptablesで利用されるフック関数の登録について見ていく。ここでは、AppArmorで利用されるフック関数の登録例について見ていく。iptables等でもwrapper関数を経由しているが、同様に登録が行われているので興味がある場合は適宜参照してもらいたい。AppArmorでは、apparmor_nf_registerでnetfilterのフック関数の登録を行っている。第二引数のapparmor_nf_opsで、実際のフック関数の定義が行われている。

static int __net_init apparmor_nf_register(struct net *net)
{
    int ret;

    ret = nf_register_net_hooks(net, apparmor_nf_ops,
                    ARRAY_SIZE(apparmor_nf_ops));
    return ret;
}

フック関数の定義には、関数ポインタが代入されるhook, NF_HOOKで指定されていたpf, hooknum（hookと同義）以外にもpriorityという項目がある。これは名前の通りで、登録するフック関数の優先度を示しており、プロトコルファミリー毎に定義されている。細かい順番は実装するのでなければ覚えておく必要はないと思うが、この優先度を見ると、iptablesのテーブル毎の優先度（raw → mangle → filter → securityの順序で実行される）だったり、Destination NATがSource NATよりも先に実行されることなどが分かる。

static const struct nf_hook_ops apparmor_nf_ops[] = {
    {
        .hook =         apparmor_ipv4_postroute,
        .pf =           NFPROTO_IPV4,
        .hooknum =      NF_INET_POST_ROUTING,
        .priority =     NF_IP_PRI_SELINUX_FIRST,
    },
#if IS_ENABLED(CONFIG_IPV6)
    {
        .hook =         apparmor_ipv6_postroute,
        .pf =           NFPROTO_IPV6,
        .hooknum =      NF_INET_POST_ROUTING,
        .priority =     NF_IP6_PRI_SELINUX_FIRST,
    },
#endif
};

enum nf_ip_hook_priorities {
    NF_IP_PRI_FIRST = INT_MIN,
    NF_IP_PRI_RAW_BEFORE_DEFRAG = -450,
    NF_IP_PRI_CONNTRACK_DEFRAG = -400,
    NF_IP_PRI_RAW = -300,
    NF_IP_PRI_SELINUX_FIRST = -225,
    NF_IP_PRI_CONNTRACK = -200,
    NF_IP_PRI_MANGLE = -150,
    NF_IP_PRI_NAT_DST = -100,
    NF_IP_PRI_FILTER = 0,
    NF_IP_PRI_SECURITY = 50,
    NF_IP_PRI_NAT_SRC = 100,
    NF_IP_PRI_SELINUX_LAST = 225,
    NF_IP_PRI_CONNTRACK_HELPER = 300,
    NF_IP_PRI_CONNTRACK_CONFIRM = INT_MAX,
    NF_IP_PRI_LAST = INT_MAX,
};

次に登録される関数側について見ていく。第一引数のprivには処理に必要なステートを指すポインタが渡される。第二引数はパケット自体、第三引数はnf_hook_slowを呼ぶ際に用意していたステートが渡される。第三引数のステートを経由して、NF_HOOKを呼ぶ時に渡された、ソケットの情報や入出力デバイスの情報を参照することができる。フック関数では、その後のパケットの処遇を返す必要があり、ここではNF_ACCEPTなどの値が返されている。

static unsigned int apparmor_ip_postroute(void *priv,
                      struct sk_buff *skb,
                      const struct nf_hook_state *state)
{
    struct aa_sk_ctx *ctx;
    struct sock *sk;

    if (!skb->secmark)
        return NF_ACCEPT;

    sk = skb_to_full_sk(skb);
    if (sk == NULL)
        return NF_ACCEPT;

    ctx = SK_CTX(sk);
    if (!apparmor_secmark_check(ctx->label, OP_SENDMSG, AA_MAY_SEND,
                    skb->secmark, sk))
        return NF_ACCEPT;

    return NF_DROP_ERR(-ECONNREFUSED);

}

static unsigned int apparmor_ipv4_postroute(void *priv,
                        struct sk_buff *skb,
                        const struct nf_hook_state *state)
{
    return apparmor_ip_postroute(priv, skb, state);
}

この関数の中でパケットの処理を行うことで、iptablesやconntrackなどの処理が実現されている。

まとめ

iptablesやconntrackなどの基盤になるnetfilterについて、概要やその実装についてまとめた。もっと細かい部分についてはおいおい追記していくかもしれない。

Pythonにおける再帰回数の上限について

研究室でプログラムを書いていたら遭遇したのでメモ。

シミュレーション用の環境を生成して、それをpickleモジュールを使ってシリアライズし保存しようとしていたところ、iPythonでは保存できるが、Pythonでは保存できないという問題に遭遇した。

関数の呼び出しを行う際には、スタック上にリターンアドレスや引数などが保存される。そのため、基本的にはただ大量に関数呼び出しを行っていくだけでもスタックを消費し、メモリを枯渇させることになる（末尾再帰最適化を行っている場合にはこの限りではない）。

この問題を引き起こさないようにするために、Pythonではスタックフレームの深さに上限を設けている。この上限は、 sys.getrecursionlimit() で取得することができる。

以下の例は、スタックフレームの上限に引っかかる程度に再帰関数を実行する例である。この例を実行すると、設定されているrecursion limitの値と、実際にスタックフレームの上限に引っかかった時の様子が確認できる。Python 3.9.7では、デフォルトで1000に設定されている。1000回以上関数呼び出しをしたい場合は、 sys.setrecursionlimit() を用いて明示的に上限を引き上げる必要がある。

import sys

def f(x):
    return f(x - 1) if x != 0 else None

d = sys.getrecursionlimit()
print(d)
f(d)
1000
Traceback (most recent call last):
  File "/private/var/folders/s7/wxfjx1rj59ld0trt0wfqn3d40000gn/T/tmp.dXOnmfMy/main.py", line 8, in <module>
    f(d)
  File "/private/var/folders/s7/wxfjx1rj59ld0trt0wfqn3d40000gn/T/tmp.dXOnmfMy/main.py", line 4, in f
    return f(x - 1) if x != 0 else None
  File "/private/var/folders/s7/wxfjx1rj59ld0trt0wfqn3d40000gn/T/tmp.dXOnmfMy/main.py", line 4, in f
    return f(x - 1) if x != 0 else None
  File "/private/var/folders/s7/wxfjx1rj59ld0trt0wfqn3d40000gn/T/tmp.dXOnmfMy/main.py", line 4, in f
    return f(x - 1) if x != 0 else None
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded in comparison

先のプログラムを、iPython 7.27.0で実行してみると、recursion limitが3000になっていることが分かる。デフォルトで設定されているこの値が異なることによって、pickleモジュールでオブジェクトをシリアライズしようとした際に、iPythonではシリアライズできたが、Pythonではシリアライズできないという問題が発生した。

簡易書留とChange-Making Problem

この前、知り合いと一緒に、入学願書の返信用封筒に貼る切手を買いに行った。返信は簡易書留で郵送されるので、414円分の切手を買う必要があった。普通は、94円（通常の配達料金）+ 320円（簡易書留用の追加料金）で切手を買うのだが、コンビニには、1円, 10円, 63円, 84円, 140円の5種類の切手のみが販売されていた。

知り合いはちょうど414円になる切手の組み合わせを考えた。貪欲法で計算を行うと、140円切手2枚 + 84円切手1枚 + 10円切手5枚, 合計8枚の切手を買えばちょうど414円になるので、8枚切手を購入することにした。コンビニからの帰り道、僕らは「この問題、AtCoderでたまに見る『支払う枚数を最小にする問題』じゃん」という話をしながら帰っていた。

実際、今年の7月に行われたABC208でも同様の問題が出ている。

atcoder.jp

さて、今回は8枚切手を購入したが、果たしてこれは最良の購入方法なのだろうか？

今回の場合、それぞれの切手が十分にある場合、ちょうど414円になるような切手の組み合わせは538通りあり、枚数最小の組み合わせは140円切手1枚 + 84円切手1枚 + 63円切手3枚 + 1円切手1枚, 合計6枚になる。

この例からも分かる通り、一般に、貪欲法で得られた切手の組み合わせは枚数最小の組み合わせにはならない。

では、枚数が最小になるような組み合わせを求めるにはどのようにしたら良いだろうか？

動的計画法を用いれば、枚数最小の組み合わせを求めることができることが知られている。この問題は、コイン問題やChange-Making Problemとして知られている。そのため、詳しい実装方法については、もっと詳しく解説している記事を参照していただきたい。

o-treetree.hatenablog.com

だが、動的計画法は貪欲法に比べて計算量もメモリ使用量が大きく、できるならば貪欲法で計算したいだろう。特に、人間の場合、頭にDPテーブルを構築できるくらい容量がある人間を除いて、基本的には貪欲法でなければ計算ができないだろう。

今回の切手の例では、貪欲法で求めた解が枚数最小の組み合わせにならない例が存在していたが、日本の通貨体系は貪欲法で求めた解は必ず枚数最小の組み合わせになる。では、どのような場合に、貪欲法で求めた解が枚数最小の組み合わせになるのだろうか？ここからは、この条件について考えていく。

貪欲法と枚数最小の組み合わせの関係

貪欲法が枚数最小の組み合わせを生む条件は知られており、この証明*1に沿って説明をしていく。まずはじめに、これ以降の証明で利用する用語を定義する。

用語

通貨体系

C = (c_1, c_2, \cdots, c_n) \in \mathbb{N}^n \ (c_1 > c_2 > \cdots > c_n = 1)を通貨体系と呼ぶ。これは、コインの種類に相当する。日本の通貨体系であれば、 C = (10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)となる。

通貨体系上での表現

V = (v_1, v_2, \cdots, v_n) \in \mathbb{N}^nが、 C \cdot V = xとなるとき、通貨体系 Cでの xの表現と呼ぶ。文脈から明らかな場合は「通貨体系 Cでの」という部分は省略する。これは、 x円を支払う時のコインの組み合わせに相当する。

表現 Vの大きさを |V| = \sum_{i=1}^n v_iで定義する。これは、コインの枚数に相当する。

また、表現は、ベクトルの辞書順を用いて順序付けすることができる。つまり、ある i\ (1 \le i \le n)について、 u_i \le v_i \land \forall_{j: 1 \le j \lt i}\ u_j = v_jを満たすとき、 U \le Vと定義する。

greedy

表現 Vが貪欲法を用いて得られる表現である時、表現 Vはgreedyであるという。また、ある自然数 xのgreedyな表現を G(x)と表す。貪欲法では、大きい金額の硬貨から順番に使用していくため、 xの表現のうち最大の表現がgreedyな表現になる。

また、自然数 x, yについて、 x \lt yと G(x) \lt G(y)は同値である。

minimal

xの表現 Vが、大きさが最小な表現の中で最大な表現である時、表現 Vはminimalであるという。また、ある自然数 xのminimalな表現を M(x)と表す。定義より、 M(x) \le G(x)である。

canonical

任意の自然数 xについて、 M(x) = G(x)となるとき、この通貨体系はcanonicalであるという。つまり、今回求めたいことは「ある通貨体系がcanonicalであるかを判定する条件」と言い換えられる。

補題1

通貨体系 C上の表現 U, Vを考える。非負整数からなる n次元のベクトル Dが V = U + Dを満たしているとき、以下が成り立つ。

  1. Vがgreedyならば、Uはgreedy
  2. Vがminimalならば、Uはminimal

証明

（略*2）

補題2

通貨体系 Cを考える。また、 wを M(w) \lt G(w)を満たす最小の自然数とする。この時、 M(w) \perp G(w)が成り立つ。

証明

背理法で証明する。 M(w) \lt G(w)かつ M(w) \perp G(w)でないとする。この時、 M(w)の i番目の要素と G(w)の i番目の要素が共に0でないような自然数 iが存在する。すると、補題1より、 M(w)の i番目の要素から1引いて得られる表現は、 w - c_iのminimalで、 G(w)の i番目の要素から1引いて得られる表現はgreedyである。また、ベクトルに定数を足しても順序関係は変化しないので、 M(w - c_i) \lt G(w - c_i)となる。だが、これは wの最小性に反する。

定理

通貨体系 Cがcanonicalでないとする。また、 wを M(w) \lt G(w)を満たす最小の自然数とする。また、 i, jを M(w)の中の0でない最初と最後の要素のインデックスとする。この時、 M(w)は G(c_{i-1} - 1)の j番目の要素に1足した表現である。

証明

補題2より、 M(w) \perp G(w)となる。また、 M(w) \lt G(w)なので、 G(w)は i番目の要素よりも前の要素が1になっている必要がある。よって、 w \gt c_{i-1}となる。また、補題1より、 M(w)がminimalなので、 M(w)の j番目の要素を1引いた表現はminimalである。また、 wの最小性より、greedyでもある。よって、 M(w - c_j) = G(w - c_j)である。 G(w - c_j)は、 M(w)と iの定義より、 i番目より前の要素は全て0である。よって、 G(w - c_j) \lt G(c_{i-1})、つまり、 w - c_j \lt c_{i-1}となる。よって、以下の式が得られる。

w - c_j \lt c_{i-1} \le w

次に、 V = (v_1, v_2, \cdots, v_n) = G(c_{i-1} - 1)を考える。 c_i \le c_{i-1} - 1 \lt c_{i-1}より、 v_i \neq 0である。補題1より、 G(c_{i-1} - 1)の i番目の要素から1引いた表現はgreedyである。よって、この表現は G(c_{i-1} - 1 - c_i)である。また、 M(w)の i番目の要素から1引いた表現はminimalであり、 wの最小性からgreedyでもある。よって、 G(w - c_i)である。先ほど得られた関係式より、 c_{i-1} - 1 - c_i \lt w - c_iなので、 G(c_{i-1} - 1 - c_i) \lt G(w - c_i)となる。この両辺の i番目の要素に1を加えても辞書順は変化しないので、 V = G(c_{i-1} - 1) \lt M(w)となる。

また、 M(w)の j番目の要素を1引いた表現はminimalであり、 wの最小性からgreedyである。よって、 G(w - c_j)である。 w - c_j \le c_{i-1} - 1より、 G(w - c_j) \le G(c_{i-1} - 1) = Vである。よって、以下の式が得られる。

G(w - c_j) \le V \lt M(w)

G(w - c_j)と M(w)は j番目の要素が1異なるだけであり、 j番目以降の要素は0であるため、 V = G(w - c_j)となる。よって、定理が成立する。

canonicalであることを判定するアルゴリズム

定理の対偶を取ることで、通貨体系がcanonicalであるかを調べるアルゴリズムが実装できる。これを利用してコンビニで販売されている切手がcanonicalかどうかを調べると、canonicalでなく、最小の反例 wは93であることが分かる。貪欲法を用いた表現だと「84円切手1枚 + 1円切手9枚」となるが、minimalな表現は「63円切手1枚 + 10円切手3枚」である。

import numpy as np


def greedy_algorithm(C, x):
    G = np.array([0] * len(C))
    for i, ci in enumerate(C):
        G[i] = x // ci
        x = x % ci
    return G


def check_canonical(C):
    samples = []
    for i, _ in enumerate(C):
        if i == 0:
            continue

        V = greedy_algorithm(C, C[i-1] - 1)

        jmin = max([i for i, vi in enumerate(V) if vi != 0])
        for j in range(jmin, len(C)):
            M = V.copy()
            M[j] += 1
            w = C @ M
            G = greedy_algorithm(C, w)

            if M.sum() < G.sum():
                return (False, w, M)

    return (True, None, None)


C = np.array([140, 84, 63, 10, 1])

is_canonical, w, M = check_canonical(C)

if is_canonical:
    print(f"{C} is canonical")
else:
    print(f"{C} is not canonical (counterexample: {w})")
    print(f"M(w): {M}")
    print(f"G(w): {greedy_algorithm(C, w)}")

感想

適当な会話から発生した話題だったけど、調べてみると結構面白い話題だった。生活の役に立つかは分からないですが、皆さんも身近な通貨体系がcanonicalかどうかが気になって夜も眠れない時があったら計算して求めてみてください。

*1:https://ecommons.cornell.edu/handle/1813/6219

*2:書くのが面倒くさくなってきた

2020年度 電気通信大学 情報理工学域 Ⅱ類 特別編入学 推薦試験 編入体験記

どうも。5月ごろに「受験を控えて精神が死んでいるえるとです。」と名乗っていたえるとです。

Visual Studio CodeのRemote Developmentを試したお話。 - Don't cry over spilt milk

それから一月が過ぎ、あっという間に進路が決定してしまいました。

遅くなりましたが、進学勢らしく編入体験記を書いていきたいと思います。

続きを読む