蟻本を読んで動的計画法を学んだのでGo言語で復習してみます。 ナップサック問題 重さと価値がそれぞれw_i, v_iであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。 入力 n = 4 (w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)} W = 5 出力 7 全探索 まずは全探索で解いてみます。 package main import "fmt" var ( n, W int w, v []int ) func main() { // 入力は省略 fmt.Println(rec(0, W)) } func rec(i, j int) (res int) { if i == n { // 品物なし res = 0 } else if j < w[i] { // 重量オーバー res = rec(i+1, j) } else { // 品物を入れるか入れないか試す if rec(i+1, j) < rec(i+1, j-w[i])+v[i] { res = rec(i+1, j-w[i]) + v[i] } else { res = rec(i+1, j) } } return } 2回の分岐が全ての深さで行われるので計算量はO(n^2)です。これでは大きなnに対しては解けません。

はじめに Hasuraを使っていて認証をするときにどうすればいいんだろうってなったので自分なりに記事にしておきます。 Hasuraとは HasuraはPostgres上でGraphQLを簡単に扱うことのできるGraphQL Engineです。 コンソール上でスキーマの定義などが全て行えてすごい楽。 https://hasura.io/ Hasuraを準備する Hasuraをデプロイ Hasura Docを開き、Deploy to Herokuをクリックします 次にHerokuの画面が出てくるので適当なアプリ名を決めてデプロイ テーブルを定義 デプロイが完了したらManage appからアプリの管理画面に飛ぶので右上のOpen appからHasuraのコンソールを開きます。 コンソールを開いたらヘッダーにあるDATAをクリックしてスキーマ定義のページに飛びます。 次にCreate Tableをクリックしてテーブルを定義をします。今回はUserがArticleを作成するときのことを想定します。Userはidとnameを文字列で持っていて、主キーはidです。 次にArticleはidとtitleとbody、そして作成したuserのidを持ち、主キーはidです。 また、ArticleとUserには親子関係が発生するので Foreign Keyを設定します。 Roleの作成 先ほど設定したTablesに対してRoleを作成し権限を付与します。 ここではすでにadminというRoleが作成されているのでuserとanonymousというRoleを追加で作成します。 anonymousの作成 anonymousは記事を見ることしかできないのでarticleのデータを一部を見ることに対してのみ権限を与えます。 左のTablesにあるarticleを開き、Permissionsタブを選択します。 そしてRoleのところにanonymousと入力し、selectのところのペンマークをクリックして下の画像のような設定を行います。 下の設定では、全ての列に対して中身を見ることを許すのでAllow role anonymous to select rows:の部分はWithout any checksを選択します。 また、articleの中身は公開してもよいのでToggle Allを選択します。 最後のaggregationに関しても今回は公開しても大丈夫なのでチェックをつけています。 userの作成 anonymousと同じようにuserのRoleも作成していきます。 userは自分の書いた記事は編集をすることができるのでarticleのinsertとupdate、deleteに対しては以下の設定をします。 { "user_id":{ "_eq": "X-Hasura-User-Id" } } この設定はarticleのuser_idがX-Hasura-User-Idと同一のときにpermissionを与えるというものです。selectに関してはanonymousのときと同じ設定で大丈夫です。 次にuserというRoleは自分自身の情報も編集できるので同じような設定をuserテーブルにも行います。 環境変数の設定 HasuraをデプロイしているHerokuのコンソールに移動し、Settingsを開きます. 次にConfig VarsのReveal Config Varsを押し、環境変数の設定を行います。 ここでは、HASURA_GRAPHQL_ADMIN_SECRETとHASURA_GRAPHQL_UNAUTHORIZED_ROLEという2つの環境変数を設定します. HASURA_GRAPHQL_ADMIN_SECRET あとで出てくるJWTモードを有効するために必要となります。 またこれを設定するとHasuraのコンソールにログインするときに入力が求められるようになります。 HASURA_GRAPHQL_UNAUTHORIZED_ROLE エンドポイントにクエリを投げるときに、認証が行われていない場合はここに設定されたRoleの権限で許されていることが実行することができます。 今回は先ほど作ったanonymousというRoleをHASURA_GRAPHQL_UNAUTHORIZED_ROLEに設定しました。 また、HASURA_GRAPHQL_ADMIN_SECRETは今回xxxxxxxxにしていますがこれが漏れたら終わりなので出来る限りセキュアなものにしてください。

この記事は 東京理科大学 Advent Calendar 2018 ６日目の記事です。 はじめに 今回Goのnetパッケージを使ってTCPソケット通信を扱う機会があったので、同じnetパッケージで扱うことのできるUDPソケット通信と比較してみました。 比較方法 クライアント側からサーバ側にhelloとたくさん送り、そのまま出力した時の両者の違いをみます。 TCPソケット通信 TCPによる通信ではデータをバイトストリームと呼ばれるbyte型のひと続きのデータとして扱います。 ・クライアント クライアントのコードは以下です。 package main import ( "log" "net" ) func main() { conn, err := net.Dial("tcp", "localhost:8088") if err != nil { log.Fatal(err) } defer conn.Close() // メッセージを送信する for { msg := "hello" conn.Write([]byte(msg)) } } ・サーバ サーバのコードは以下です。 package main import ( "fmt" "log" "net" ) func main() { listener, err := net.Listen("tcp", "localhost:8088") if err != nil { log.