- 投稿日:2020-08-30T23:27:21+09:00
ISUCON10に向けて、isucon9を行う
講評などを見ながら理解したものを備忘録的に残していきます。
(都度更新します)
参考:
http://isucon.net/archives/53916974.html新着・カテゴリ新着・ユーザごと新着商品
私の担当がSQL/アプリですので、こちらのインデックス問題、N+1問題に対して残して行きます
インデックス不足
こちらはSQLでよく検索する場所に対して、インデックスを追加することで高速化にできます。
インデックス名の指定が必要ですが、インデックス名で実際に検索するわけではなく、SQLのカラム名で検索するときに有効です。INDEX "index名" (`"カラム名"`)で追加できます。
isucon9では、
webapp/sql/01_schema.sqlの場所にwebapp/sql/01_schema.sqlCREATE TABLE `items` ( `id` bigint NOT NULL AUTO_INCREMENT PRIMARY KEY, `seller_id` bigint NOT NULL, `buyer_id` bigint NOT NULL DEFAULT 0, `status` enum('on_sale', 'trading', 'sold_out', 'stop', 'cancel') NOT NULL, `name` varchar(191) NOT NULL, `price` int unsigned NOT NULL, `description` text NOT NULL, `image_name` varchar(191) NOT NULL, `category_id` int unsigned NOT NULL, `created_at` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP, `updated_at` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP, INDEX idx_category_id (`category_id`), INDEX idx_created_at (`created_at`), INDEX idx_name (`name`), INDEX idx_seller_id (`seller_id`), INDEX idx_buyer_id (`buyer_id`), INDEX idx_status (`status`), INDEX idx_price (`price`) ) ENGINE=InnoDB DEFAULT CHARACTER SET utf8mb4;と既存に追加されていたidx_category_idのように、INDEXを追加することでスコアがローカル実行時、
3110 から4500ほどまで平均してのびました。N+1問題
参考記事:
https://qiita.com/muroya2355/items/d4eecbe722a8ddb2568b
https://qiita.com/rihofujino/items/b69e6a23e7cef1d692c4こちらは、例えばisucon9予選問題、getNewItems内で、itemのsellerIDによって、
userテーブルから、N+1の検索が毎回実行され、
O(item数 * N+1)の計算時間が実行されてしまう問題だと思います。
方針としてはjoin句などでくっつけるか、itemのsellerIDによってO(1)で持ってくるかしなければいけません。mapを使った解法
webapp/go/main.gofunc getUserSimpleByID(q sqlx.Queryer, userID int64) (userSimple UserSimple, err error) { user := User{} err = sqlx.Get(q, &user, "SELECT * FROM `users` WHERE `id` = ?", userID) if err != nil { return userSimple, err } userSimple.ID = user.ID userSimple.AccountName = user.AccountName userSimple.NumSellItems = user.NumSellItems return userSimple, err } for _, item := range items { seller, err := getUserSimpleByID(dbx, item.SellerID) . . . }isucon9のgetNewItemsのgetUserSimpleByIDに注目します。
元々items(以下n)回*users(以下m)回を探してuserを返しています。
計算量はざっとO(nm)とします
ここでO(N+M)を目指します
私が書いたコードをまず載せますwebapp/go/main.gousers := map[int64]UserSimple{} rows,_ := dbx.Queryx("SELECT * FROM users") for rows.Next() { var user User var userSimple UserSimple rows.StructScan(&user) userSimple.ID = user.ID userSimple.AccountName = user.AccountName userSimple.NumSellItems = user.NumSellItems users[user.ID] = userSimple } // fmt.Println(users,"users") // sqlx.Get(q, &user, "SELECT * FROM `users` WHERE `id` = ?", userID) itemSimples := []ItemSimple{} for _, item := range items { seller, ok := users[item.SellerID] . . }このようにして、userを前処理として、全て持ってきて、userIDで格納し、
それを、O(1)アクセスでfor item時に読み込ませる...
という処理でO(N+M)としたのですが、スコア的にはほぼ変化なしとなりました。
原因として考えられるのは、・元々のsqlx.getの時点とやってる計算量がほんとは変わらない
・N+1問題の適用箇所が少なく、もっと増やせばスコア的に伸びる
・この前処理のどこかでエラーを吐いてて早くなってる反面エラーが発生しスコア的に変化がない
・ボトルネックがこれ以前にたくさんあり、そこを解消しなければここのスコアの変化は見れないだと考えています
- 投稿日:2020-08-30T14:38:23+09:00
「語尾に自動でやんすをつけてくれるアプリ」を作ってみた
こちらで色々面白いアイディア並んでて何かできるかな・・と眺めてたけど
Webアプリが多くて出来そうにもない・・と、そこに光明の光が!wつくってみたわ
v0.2 途中まで入力したものを、訂正して違う語尾ルールへ変換できるようにしました (追記)
途中から"ました"→"です"のルールに変えて変換しています。
v0.3 実行した時のオプションをコンフィグファイルとして保存するようにしました (追記)
デフォルトで".goBi"に実行した時のオプションを保存します。起動時にコンフィグがあれば読み込みます。
これで再実行時に毎回同じ語尾が使える!やったね!!つかいかた:
バイナリに変換前と、変換したい単語を"@"(デフォ)で区切って渡してください
>goBi.exe desu@deyannsu masita@tadeyannsu 190@yannsuこう指定すれば”です”、”ました”、”。”が入力されると”やんす系”に変換します。
数字一個の指定は対応しているASCIIコードが一個来たら変換するモードです※v0.3 からコンフィグファイルに対応していますので、オプション無しでもコンフィグから
前回の設定を読み込んで動くようになりました!よって毎回オプション指定しなくてOKうごくOS (追記)
動作環境は今のところWindows系OSのみです。
キー入力しているウィンドゥが変わったら、それまで入力してたカウンターをリセットする処理にWindowsのAPIを使用しているためです。
途中まで入力したのが、他の窓で暴発しないようにしたためで、それでも良いなら簡単に他OSへ移植できます。あとがき
アプリじゃねー!ww
でもTwitterでキャラ作ってるとか、うっかり設定崩さない時に使えます。つか、これrm -rfとか入力したら無効化してくれるみたいな実用的な使い方も無くもないな。
以外と使い道あるかもしれん。ひとまず、今はここまで。でも一日もかからず、ここまでパッと書ける言語ガチで凄くね?
サンキューGo言語!!