大学生活＋αの振り返り
こんにちは。最近書くネタがなくてどうしようかと思い、でも月一更新はなんとか続けないと今後も続かないと思い、 「そういえば最近１年生や２年生の子にいつからプログラミングやってたかよく聞かれるなー」ってなって自分でもいつからこっち方面に進もうと思ったか曖昧だったので改めて思い返してみました。書くことが大事（戒め）
小学３年生
今思えばこの時に初めてパソコンに触った。目的は「ドラクエ５のブオーンの攻略方法を知るため」。父親が買ったMacBook（相当古いですが今でも家にあります）と「これみてひらがな打ちなさい」と言われ渡されたローマ字表片手にずっとGoogle先生と遊んでました。
小学４年生
確かこの頃近所に住む友達に面白フラッシュ倉庫を勧められてめちゃくちゃハマった気がします。Flash全盛期ってやつだったかと・・・ まだプログラミングとかには手を出してません。あと夏休みにポケモン大好きクラブにも登録して友達と一緒にミニゲームやってたりもしました。
小学５年生
特に進歩せずひたすらGoogle先生にゲームの攻略方法聞いてました。確かこの年はテイルズオブジアビスとドラクエ８あたりだった気がする・・・
小学６年生
引っ越して環境が変わってなんかすごく辛かった年だった思い出です。確かここら辺でなんの映画か忘れましたがハッカーがターミナル画面をカタカタしてるシーンがあってそういうのにすぐ影響される僕は「あれ、どうやってやるの！？」って父に聞いた覚えがあるようなないような。この頃Windowsでコマンドプロンプトを覚えてひたすら意味のない文字をガタガタ打ち込んでました。それでハッカーになった気でいたのです。
中１
なんか部活と塾で手一杯であんまりパソコンに触れた覚えがありません。この頃から受験という言葉に悩まされるようにになってた気がします。
中２
多感な時期です。この年か前の年かわかりませんがBloodyMondayというドラマが放映されました。ある意味これが僕の今後の人生を決定づけたといっても過言ではないぐらい大きい作品でした。
あらすじとしては天才ハッカーがテロリストから国を守るために戦うというもの、もうその主人公がかっこよすぎて一時期壁紙とかも真似したりしてました。 そして、そのドラマに使われている技術についてついにネットで調べるようになりました。主人公が使っていたのはUbuntuというOSだった。使用言語はPython（この頃プログラミング言語の種類なんて一つも知りません）という情報を頼りに、Ubuntuとは？Pythonとは？と必死に調べました。
その後ついにUbuntuをOSだと理解し、ディスクにイメージを焼いて起動し、Pythonをインストールして使うことができました。この時はかなり感動しました。
ただ、もっとかっこよくUbuntuを起動したいと思ってUSBからイメージを起動しようとしてPC(父の)のBIOS設定をいじっていたら元のOSが立ち上がらなくなってめちゃくちゃ怒られたのは少しトラウマです。
はてさて、この男はプログラミングを初めて経験したのですがなんとそこで満足、というか挫折しました。BloodyMondayの主人公がしていたようなプログラミングはどうやってするのだ！と一人途方に暮れていました。当然ですね。この頃はTCP/IPやサーバーという単語すら知らなかったのですからそもそも調べようがない。ですが、もうごく自然に僕の頭の中では将来こういう方面の仕事をしよう。他の仕事はありえないという考えになっていました。
中３
受験です。もうこの年はひたすら受験勉強です。といっても塾に通って勉強した気になっていただけなので学力は大したことなかったです。 まぁそれでも身の程を知らずに東工大の附属に推薦と一般受験どちらも受けて玉砕という哀れな結果になりました。それでも理工学系に強い学校に行くつもりはあって芝浦工大柏に受かりそちらに通うことになりました。ちなみに僕が一番得意なのは国語でした。 プログラミングの勉強はあれから「VisualStudio2005 で学ぶC++」みたいな本を買って貰ったのですがクラスの概念が理解できず挫折。早いですねー2回目の挫折w
高１
中学と同様に部活には入ったのですが大学受験する気は１ミリもありませんでした。「だって推薦で芝浦工大の情報工いければいいやん」という発想のもとテスト勉強もせず部活とゲーセン通いの日々でした。うーん思い返すと清々しいほどのクズですね。 この頃から今は廃刊になってしまいましたが白夜書房から発売されていた「ハッカージャパン」という本を買うようになりました。これ結構すごい雑誌でサンプルアプリをクラックしてみよう！とかゲームのバイナリを解析してチートコードを書こう！みたいなことが書いてあったんですよ。この頃CTFの存在を知りました(知っただけで参加するのは数年後)
高２
一番楽しい時期だと言われていますね。部活とゲーセンしか記憶がありません。楽しかったのでいいんですが。 プログラミングの方はこの頃すっかり頭から抜け落ちてました。ひたすら音楽ゲームの譜面を脳内でリピートしてた気がします。
高３
みんなが受験勉強してる中一人でのほほんとゲーセン通いを続けてのほほんと推薦に必要な最低限の勉強をしてました。 そんで推薦が決まってよーし大学に入った時のために勉強しておくかーと思ってネットで色々調べてもどれから手をつけていいかわからずすぐやめてゲームしてました。うーんクry
ここまで見るとろくに勉強してませんね。ぼんやりとした将来像しかなかった気がします。結局本格的にプログラミングを始めたのは大学からですし。逆にこんなのでも割となんとかなるってことですかね。
大学に入ってからは特に言うこともなく真面目に勉強するようになりました。自分がやりたいことだったし、自分でどうやって学べばいいかわからないところを「ああ！こういうキーワードで調べてこういうので勉強すればいいのか！」ってモヤモヤが晴れてすごく楽しかったですね。あとは知り合いの影響も大きかったと思います。大学１年の時は適当なサークルに入ってたんですけどその中で同じ学科の人から「こういうプログラミングしてるサークルあるんだけど入らない？」と誘われてそこに居た人たちに凄く良い刺激を貰いました。
ITの世界はすぐに新しいものが出てきて隆盛が特に激しい分野だと思っています。それでも僕はパソコンを触るのが好きだしプログラミングするのも好き。ロジックを考えて実装できた時なんかは一人で小躍りしますし、人にレビューを貰って一喜一憂することもあります。
このPCから繋がる全ての世界が僕は好きなのだと最近改めて実感するようになりました。と、いい感じに締めておきます。
途中からなんの話かわからなくなりましたがまあ良しとしておきます。文字数も稼げましたし。 にしても、改めて振り返ると初めて触れた言語Pythonだったんですね・・・（他人事）なんか今でもそれをガッツリ書いていると思うと多少は進歩が見られて嬉しいです。
では今回はこのあたりで筆を置かせていただきます。次の更新は6月中になんとか・・・
とりあえず機械学習を実践してみる方法
どうも、おばんです。
あ〜そろそろなんか記事書いてまとめておくか〜って思うと大体綺麗に１ヶ月経ってます。
突然なんですが最近一身上の都合（特に深い意味はないです）でpythonで機械学習を使う機会が増えました。
自分ではやろうやろうと思いつつも理論がワケワカメすぎたので敬遠していたのですが改めてやってみると機械学習の概念自体はそこまで難しくない（数学的な理論は置いといて）。むしろ難しさはもっと別の場所にある。
んでもって機械学習を理論はさっくりでいいからとりあえず手っ取り早く実践してソースからイメージを掴みたい。そういう時どうすればいいのか、意外としっかりまとめてるサイトがなかったので書いてみようと思います。 一応私の環境としてはMac,Pythonを用いています。
機械学習の定義
理論の話はさっくりとと言いましたが機械学習とはなんぞやぐらいはまとめておかないといけないのでそこはご容赦ください。 あと今回はDeepLeaningの話は今回はしません。ちょいと方針が違うので・・・ wikipedia先生によると、
センサやデータベースなどから、ある程度の数のサンプルデータ集合を入力して解析を行い、そのデータから有用な規則、ルール、知識表現、判断基準などを抽出し、アルゴリズムを発展させる。なお、データ集合を解析するので、統計学との関連が深い。 そのアルゴリズムは、第一にそのデータが生成した潜在的機構の特徴を捉え、複雑な関係を識別（すなわち定量化）する。第二にその識別したパターンを用いて、新たなデータについて予測を行う。データは、観測された変数群のとりうる関係の具体例と見ることができる。一方、アルゴリズムは、機械学習者として観測されたデータの部分（訓練例などと呼ぶ）を学習することで、データに潜在する確率分布の特徴を捉え、学習によって得た知識を用いて、新たな入力データについて知的な決定を行う[1]。
まぁ、つまりは沢山のサンプルデータから傾向とかを見つけ出して次のデータはこうなるはずだ！とか、
こういうデータはやばいデータなんだな！とかをコンピュータが判断できるようになるアルゴリズムを作ること って感じですかね
機械学習の分類
そんなすごそうな機械学習ですがいくつか種類があります。
- 教師あり学習 入力（データ）とラベル（答え）がある学習方法 （売上、株価の予測とかは大体これ）
- 教師なし学習 ラベルのない入力のみの学習 （データの分類分けとかに使われてるイメージ）
- 強化学習 よくわからんけど動的計画法（最大の報酬を得るための選択）みたいな感じ？
超アバウトです。でも詳しく書こうとするとどうしても専門的な手法とか数学の話が絡むので今回は省略。
主に使われる手法とかのキーワードは「線形回帰（未来予測）、K近傍法（分類）、ナイーブベイズ分類器（分類）、サポートベクターマシン（忘れた）」とか色々あります。
一番情報が多いのは教師あり学習です。なぜならデータさえあればあとはライブラリ使ってデータを突っ込むだけです。
必要な材料
pythonで機械学習を始めるのに必要なものはすぐ揃えられます。仮に揃わなかったらStackOverflowにでも投稿すればいいんじゃないかな？（適当）
まずはPython 2.7でも3.5x系でもどっちでもいいですができれば3.5x系の方がいいかもしれません。インストールしましょう
さて、インストールが完了すればターミナルからpythonと叩けばインタプリタが起動するでしょう。
そこでprint('Hello world')と打って見事出力されればもう機械学習の世界はあなたを受け入れているでしょう。
ですが罠がもう一つあります。パッケージの管理です。どんなプログラミング言語でもパッケージ、ライブラリの管理は面倒臭いもの。
pythonではそれはpipというものが管理しています。それぞれのOSに合わせてpipをインストールしましょう。Macならbrew,Unixならapt-getかな。Windowsにそんなコマンドはない？bash_on_windowsでunixコマンドが叩けるようになったらしいからそれを使えばいいんじゃないかな？
pipが入ったら pip install ~~~~コマンドでscikit-learn,numpy,pandasをインストールしましょう。scikit-learnは基本的な機械学習のアルゴリズムが詰まった素晴らしいライブラリです。他にも沢山の機械学習ライブラリがあります。Tensorflowとかchainerとかね。numpyとpandasは言わずと知れた行列計算ライブラリと柔軟なデータ構造を実現するこれまた最高のライブラリです。
失礼、もう一つライブラリを忘れていました。それはmatplotlibです。これはグラフの描画ライブラリですがデータを可視化できるのでとても便利です。
さて、それらのインストールが済んだら実際に簡単なソースを動かしてみましょう
実践
import pandas as pd import numpy as np// データの読み込み wine = pd.read_csv("winequality-red.csv", sep=";") wine.head
// sklearn.linear_model.LinearRegression クラスを読み込み from sklearn import linear_model clf = linear_model.LinearRegression()
// 説明変数に "density (濃度)" を利用 X = wine.loc[:, ['density']].as_matrix() print(X) // 目的変数に "alcohol (アルコール度数)" を利用 Y = wine['alcohol'].as_matrix()
// 予測モデルを作成 clf.fit(X, Y)
// 回帰係数 print(clf.coef_)
// 切片 (誤差) print(clf.intercept_)
// 決定係数 print(clf.score(X, Y))
// 実際の値を与えてみての予測 result = clf.predict(0.9978) print("%s : %s" % (result,Y[0]))
// matplotlib パッケージを読み込み import matplotlib.pyplot as plt
// 散布図 plt.scatter(X, Y)
// 回帰直線 plt.plot(X, clf.predict(X)) plt.show()
scikit-learn で線形回帰 (単回帰分析・重回帰分析) – Python でデータサイエンス
上記のソースをお借りしたサイトです。少しだけ改変しています。 上をコピって実行すればライブラリさえあれば動くはずです。 これは何をしているソースかというとリンク先を読むとわかると思いますがワインの諸々のデータを読み込んで、試しに濃度からアルコールを予測してみよう的なことをしてます。
この予測に用いてる手法は線形回帰です。これは機械学習の数ある手法の中でもダントツでわかりやすい手法だと思います。 これを応用すれば売り上げの予測、アクセス数の予測、株価の予測とかもできるはずです。やってないのでわかりませんが。
処理に関してはコメント文そのまんまです。
機械学習の難しさ
さて、ソースを動かすだけならライブラリを使えば難しくはないことがお分かりいただけたでしょうか？
勿論、手法の方から自分でコーディングしてもいいと思います。それにはかなりの数学的知識とそれをコードに落とし込むプログラミング能力が必要にはなりますが・・・
そして実際に最近機械学習をやるようになって私が一番難しいと思っているのは何か。
それは データの調達、整形です。
今回のソースはあらかじめ用意されたデータを使っているのでとても綺麗で無駄がありません。 何か新しい分野に機械学習を利用したい！そういう人はいると思います。私も例外ではありません。しかし、新しい分野、たとえば日本の農業のこれからの総生産量を海外からの輸入量と比較しつつ予測するのに機械学習を用いるとなった場合はまず当然ですが日本の農業のデータが莫大に必要です。海外からの輸入データも必要でしょう。それはどこから入手しますか？農林水産省？財務省？。まだ当てがある場合はいいです。そもそもまとめられていないデータを分析したいならまとめるところから始めなければなりません。
まとめたデータにノイズとなるようなデータが混じっていることもあります。それだけで学習器の精度は狂ってしまいます。コンピュータは人間より繊細ですからね優しく扱ってあげないといけません。
更に今まさに私が直面している問題ですが、データの定量化、評価です。機械学習で学習器に学習させるデータは全てを数値化する必要があります。 例えば学生のデータとして「170,50,男,性格に難あり」といった４次元の特徴ベクトルの集合の場合、男というベクトルは男女、しかないのであれば0,1に変換する必要があります。最後の備考的な項目はもっと評価するのが難しいです。定量化するのか、それとも独自のアルゴリズムで評価すべきなのか。
そこも考えるのがとても難しい。
ついでにデータの性質、傾向を学習させる前に自分でそれらを理解する必要もあります。なので統計や確率などの知識多少はあった方がいいのではないでしょうか。 データを理解すれば必要ではない項目、ノイズのようなデータもすぐにわかるようになるので学習器の精度向上にも繋がるでしょう
ですがとりあえず機械学習に触れるのであればライブラリに付属しているデータセット（csv） とかを使えばどういうものなのかはつかめると思います。
Pythonがわからない？ 今すぐAmazonでOreillyの本を買うべきです。
今回の記事で機械学習の入り口が広がって（主に大学の関係者の方々へ）ついでに私に色々教えてくれるようになるのを願っています。
では今日はこのあたりで筆を置かせていただきます。次もなるべく早めに更新したいです
2週間ほどのベトナム滞在記
お久しぶりです。学校の留学プログラム、みたいなもので2週間ほどベトナムのハノイに行っていました。
今回はそこでの経験を書き起こしておこうと思います。
そもそもなんで行ったのか
そもそもなんで留学なんか行ったの？というお話ですがそれは研究室配属の時に教授に「君プログラミングそれなりにできるみたいだし院行くから春休み暇だよね！まさにベストスウィートだよ！」と激押しされ、さらに渡航費用も成績のおかげで2万～4万で済むということでホイホイ釣られたというわけですね。実際に大した予定もなく、英語でコミュニケーション取ってアプリ開発というのも良い経験になりそうだなと思い、今回の滞在に繋がるという次第です。
滞在先での目的
では現地で一体何をするかというと「BLEを使ったAndroidアプリケーション開発」です。BLEはBluetooth Law Energyの略だったはず。 事前の勉強会ではBLEにおける、サーバーのような役割をもつPeripheral(今回はAndroid側です)とクライアント的な役割のCentral(今回はRaspberry PiのNode.jsプログラム)の解説を受けました。スマホアプリ開発に関してはiOSを少し触った程度ではありましたが大体一緒だったので仕様の把握にはそこまで手惑いませんでした。問題はNode.jsの理解です。 正直javascriptがなんとなく苦手で今まで避けてはいたのですが今回いい機会だったので片っ端からソースを読んで使用するライブラリのGitHubのソースもしっかり理解しました。おかげでコールバックを少し理解できました。
と、まぁここまでが事前準備です。実際に何を作るかは現地で他の外国人の方と話し合って決めます。
着いたはいいけど…
さて、6時間のフライトの末に着いたそこはまさに発展途上国。溢れるバイク、雲から太陽が顔を覗かせることはほぼ皆無。青空？なにそれ美味しいの？状態の街でした。歩道は普通にバイクが走るし道の舗装もがたがたです。日本の電車に乗ってる人たちがそのままバイクに乗っていると思ってもらえばその交通量の多さが想像できるでしょうか？
泊まるところも泊まるところで控えめに言って牢屋のようだなと。初日にはお湯も使えず冷水しか出ない。なので他の部屋にシャワーを借りにいくという事態になっていました。
ベッドも寝返りをうつたびにギシギシと結構大きな音を立て、掛布団はなく、どう見てもシーツだろこれっていう感じの薄い布で初日の夜を明かしました。 正直初日にしてもう日本に帰りたいと思っていました。
気を取り直してプロジェクトスタートです
文句を言おうが朝はやってくるもので泊まっている寮からはタクシーを使って学校にいきます。「タクシーとか贅沢してんじゃねえよ」と憤慨する方もいるかもしれませんがベトナムのタクシーは2キロ走ってもらっても150円ぐらいで済みます。超安いです。 そんなこんなで学校に着き、軽く他の現地学生の方や留学生の方たちと自己紹介を済ませてプロジェクトメンバーが決められます。
今回の僕たちの班は3人でした。内訳としては僕、同じ日本人（Rさん）、ナイジェリアからの留学生(Eさん)でした。 他にも3つほどチームがあり日本人とベトナム人の混成チームです。
メンバーも決まったとこで何を作るかという話になりました。僕はあらかじめ考えていた「脱出ゲームとかで使えそうなスマホアプリケーション」を提案しました。詳細は後述します。
まぁぶっちゃけ拒否られるかなーなんて思ったりもしてましたけど意外とすんなり受け入れてくれたので決定しました。
プロジェクトの概要
ではプロジェクトの概要をざっくばらんに書いてみます。 まず、何をするシステムかというと「raspberry piに近づいてアプリを起動するとクイズが配られるのでそれを解いて得点ゲット！」という非常にチープなものです。構想自体はCTF4bで誰かが問題を解くたびにブザーが鳴っていてそれがラズパイで管理してるというものから着想しました。ただそれを実装してみると意外とめんどくさい。
上の写真はシステムのアーキテクチャを図で表現してみたものです。 大きく分けて3つのコンポーネントがあります。
ラズパイ node.jsのプログラムが走ってます。nobleというライブラリを用いて片っ端からAndroid端末をサーチして条件が合致しているようであればJSON形式のクイズをバッファーに変換してandroidに送信します。JSONデータは別ファイルに保存してます。
Android javaで書いてます。まずこいつが「今ここにいますよー」的な宣伝をして、そいつをラズパイが検知して、問題拾って、ユーザー作るorログインして、問題解いて正解か否かを判断してユーザー情報更新のリクを別サーバーに送信するって感じです
JsonAPIServer 自作したAPIサーバーです。ユーザー情報（ユーザー名、ID、スコア）を保持しています。一般的なGET,POST,PUTリクエストを受け付けます。Node.jsで書いていてmongoDBでコレクションを保存しています。
すごく大雑把でこんな感じです。実は最初はAPIサーバーを使わずに普通にMySQLとかで済ませるつもりでした。しかし、Androidアプリから外部DBサーバーにアクセスするのがすごく面倒くさくて（まる1日格闘してコネクションエラーとかで無理でした）Httpリクとか使うAPIサーバーだったらそこまで面倒くさくないだろうということでこの形に収まりました。
役割分担としてはラズパイ側はEさんに、画面UIと効果音とかをRさんに、APIサーバーの作成とAndroidとAPIサーバーのコネクション、その他JSONデータのパースやその処理は自分が担当しました。
作業日数は実質的には7日ほどでしたが無事完成させることはできました。
思わぬ伏兵
開発の方自体はそこまで問題ではなかったのですがしかし全てがうまくいくことなんて当然ないわけで…
7日目ぐらいに高熱を出しました。その3日前から休日だったのですが休日という名の観光だったので体力的に全く休むことができず恐らく疲労によるものだと思いました。日本から持ってきた解熱剤をがぶ飲みしてなんとか1日で復帰しましたが頭痛や腹痛は帰るまで続いていました。観光自体は楽しかったですがやはりどこかでストレスは溜まっていたのかもしれません。自己管理不足です。
そして最終発表へ…
ぶっ倒れそうになりながらもなんとかプログラムを完成させ動作確認もしっかりでき、あとは最後のプレゼンだけでした。
しかし、英語でのプレゼンなんて当然したこともなかったので台本しっかり作って５，６時間練習してようやくそれっぽく仕上げられました。日本語だったら…なんて考えもありましたがそれはそれ。しっかり他の皆さんと同じ土俵でいい発表をしようと思いました。
本番は多少つまりながらも伝えたいことは伝えられたと思います。しかし、問題はそのあとの質問タイム。ベトナム人の先生の英語での質問が全くと言っていいほど何を言っているのかわかりませんでした。見かねたEさんが返答してくれましたがとても悔しかったです。 英語は引き続き自分の重要課題ですね。
と、そんなこんなで発表は終わり自分は「燃え尽きちまったぜ。真っ白にな…」状態でした。
発表は午前だけだったので午後からは自由時間で他のみんなは桜祭りとやらに行っていたのですが自分は寮の部屋で一人発表の反省とプログラムの確認をしていました。もうなんか何も動きたくなかったですね。
ベトナムに来る前からプログラムの開発と発表のことしか頭になかったのでそれが終わったら本当に抜け殻になってました。もしかして自分は仕事人間の才能があるのではないかと自覚した瞬間でした。 畢竟、ここまでガチでやったのは僕だけなんじゃないかと思います。自惚れだとは思いますが。
帰国へ
色々ありましたが二週間ほどをなんとか生きて過ごし、ついに帰国となりました。 今帰国してから3日ほど経ちますが日本は素晴らしい国ですね。帰ってきてから次の日に親子丼を食べに行ったのですが美味しすぎて心が慈愛に満ち、すべてを穏やかな心で見ることができるくらいでした。
と、まぁ冗談はここまでにしておいて今回のベトナム滞在で得たものは非常に大きかったです。英語でコミュニケーションを取るということ。違う環境下での体調の管理。プレゼンの仕方。まだまだ学ぶことは沢山あります。自分は韜晦するような振る舞いが苦手なのでいつも全力でやりますがそれ故に自分に足りないものが痛いほどわかるのはある意味利点だと思います。 4月にはTOEICの試験があるのでとりあえずそこに向けてしっかり勉強しておきたいと思います。
柄にもなく長文をしたためてしまいましたがここまでお付き合いしていただきありがとうございました。 今回はこのあたりで筆をおかせていただきます。
アナグラム判定メソッドの実行速度を比較してみた
今回は前回の続きといいますか、似たような問題に対する実装を複数パターンあったのでその速度を比較してみました。
問題
二つの文字列が与えられた時、片方がもう片方の並び替えになっているかどうかを決定するメソッドを書いてください。
前提条件：空白や大文字小文字も区別する。文字コードはASCIIコードだけで構わない。
というわけで書いてみました。
実装コード
static boolean MyisAnagram(String word1,String word2){ int sumCode_1=0; int sumCode_2=0; if(word1.length()!=word2.length()) return false; for(int i=0;i<word1.length();i++){ sumCode_1 += word1.charAt(i); } for(int i=0;i<word2.length();i++){ sumCode_2 += word2.charAt(i); } if(sumCode_1 == sumCode_2){ return true; } else{ return false; } }
あ、今回はjavaです。Eclipseで書いているので書いてる途中に間違えがすぐわかるので便利です。
上記のコードは自分が完全に０から考えたメソッドです。
文字列の文字コードを全て足し合わせて一致しているならアナグラムであると言えます。
中々スマートに書けたかなとは思います。
次に解答例としてあった二つの実装パターンをご紹介します。
static String sort(String s){ char[] content = s.toCharArray(); java.util.Arrays.sort(content); return new String(content); } static boolean permutation(String s,String t){ if(s.length() != t.length()){ return false; } return sort(s).equals(sort(t)); }
static boolean permutation_2(String s,String t){ if(s.length() != t.length()){ return false; } int[] letters = new int[256]; //文字コードの仮定; char[] s_array = s.toCharArray(); for(char c:s_array){ letters[c]++; } for(int i=0;i<t.length();i++){ int c = (int)t.charAt(i); if(--letters[c] < 0){ return false; } } return true; }
１個目はsortメソッドを作成し、二つの文字列を整列してから比較しています
２個目のメソッドは文字コードのリストをboolで作って出現したら1に、二個目の文字列を判定して、存在したら-1して0より小さくなったらその時点でfalseというのは面白いですね。
比較結果
メインメソッドを以下のように実装し実行時間を計ってみました。
public static void main(String[] args){ long start = System.nanoTime(); MyisAnagram("word","wo rd"); MyisAnagram("word","fugafuga"); MyisAnagram("word","rdow"); long end = System.nanoTime(); System.out.println("Processing time:" + (end - start) + "ns"); start = System.nanoTime(); permutation("word","wo rd"); permutation("word","fugafuga"); permutation("word","rdow"); end = System.nanoTime(); System.out.println("Processing time:" + (end - start) + "ns"); start = System.nanoTime(); permutation_2("word","wo rd"); permutation_2("word","fugafuga"); permutation_2("word","rdow"); end = System.nanoTime(); System.out.println("Processing time:" + (end - start) + "ns"); }
結果は以下のとおりになりました
| MyisAnagram(自分の実装) | permutation(解答例１) | permutation_2(解答例２) |
|---|---|---|
| 13927ns | 226304ns | 5590ns |
自分のは２位でしたね。悔しい。やはり全て足し合わせてから比較して結果を返すのと、比較しつつ結果を返すので差がついてしまったのでしょうか。 解答例１の方はコードもスマートでしたがやはり関数呼び出しが入る分遅くなってしまったのでしょうか。
文字列操作を弄るのは楽しいですね。 次回もまた何かプログラムを載せると思います。なにか御指摘ありましたら是非お願いします。
今月はまさかの２回更新できました。すごい
C言語のポインタインクリメントの話
新年あけましておめでとうございます。 今年は特に勉学への時間を費やしたいと思います。
さて、最近は競技プログラミングというか一からプログラミングとコンピュータの仕組みについて改めて勉強しているので今回は そこでふと疑問に思った点について書いてみました。
それはC言語のポインタの仕様です。
仕様というよりはコンパイラの解釈の方なのですが・・・ なにはともあれまずは次のCで書いたソースをご覧ください
#include <stdio.h> #include <string.h> #include <stdlib.h> void A_reverse(char *str); int main(void){ char str[] = "abcdef"; A_reverse(str); return 0; } void A_reverse(char *str){ char* first=str; char* end=str; char tmp; int i,count=0; if(str){ while(*end){ ++end; } --end; while(str<end){ tmp = *str; *str++ = *end; *end-- = tmp; count++; } printf("%s\n",first); } }
このソースコード、まぁ読めばわかると思いますが文字列を逆に置換するものです。
str[]に文字を設定し、A_reverseメソッドでポインタを張り替え置換します。
ここで何が引っかかったかというと
while(str<end){
tmp = *str;
*str++ = *end;
*end-- = tmp;
count++;
}
このループ部分の
*str++ = *end; *end-- = tmp;
この辺りです。 まず、strには文字列の先頭のアドレスが、endには文字列の終端が格納されています。 endは上の処理でヌル文字の一個手前のアドレスを指すようにしています。(今回の文字列をわかりやすくすると'[a][b][c][d][e][f][¥0]'でendは'[f]'を指します)
そしてもう一つ説明としてこの処理が属するwhileループは先頭と終端からお互いのアドレスを張り替えていき、中央で張り替えを中止します。
a b c d e f str→a end→f
↓
f b c d e a str→b end→e
↓
f e c d b a str→c end→d
↓
f e d c b a
↓
strのアドレスがendより大きくなったのでここで終わり！
となっています。この張り替えの処理が
tmp = *str;
*str++ = *end;
*end-- = tmp;
です。
その時重要なのがポインタ演算子の評価順です。
上記のソースの *str++ = *end の部分ですがこれだけパッと見ると、strをインクリメントしたアドレスにendのアドレスを代入する って僕は思ってました。
ですが、実際には
strの指すアドレスの内容をendのアドレスの内容に変更 → strインクリメント という流れらしいです。ややこしい
しかも最初のstr書き換えた後にstrをインクリメントしたらそれってendのアドレスから一個進むってことじゃねえの？って思ったら、なんと*str++と書くことでインクリメント前の値を取り出して参照変更して複写、そしてアドレスをインクリメントするそうです
なんというかスマートなコードではありますが少しわかりづらいので結構議論のタネになったりするそうです。
こういう記法は後置記法というそうで、*++strというような前置記法もできます。
この場合はインクリメントしてから値を取り出すという処理のようです。
これはコーディング問題の一つだったのですが思わぬ落とし穴があったので取り上げてみました。
ちなみにこれ以外にも落とし穴はあってメイン関数で宣言している str[] を *strで宣言したりするとプログラムがBus error 10という忌まわしい文字を吐いて落ちます。
というわけでC言語を書き始めて３年以上が経っても未だに嵌る時は嵌るといったものでした。１時間ぐらい調べました。恐るべしポインタ。
大学の授業ではそこまで詰まった記憶はないのですがやっぱりまだまだ詰めが甘いですね。 常に精進しろというお達しだと思ってがんばります。
それでは今回はこの辺りで筆を置かせていただきます。
SECCON2016に少しだけ参加
土日に開催されたSECCON2016に素人ながら参加したので少しだけ解けた問題について
writeupなんて言うほどでもないのでタイトルにはつけてないです
Vigenere
Vigenere
k: ????????????
p: SECCON{???????????????????????????????????}
c: LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ
k=key, p=plain, c=cipher, md5(p)=f528a6ab914c1ecf856a1d93103948fe
|ABCDEFGHIJKLMNOPQRSTUVWXYZ{}
-+----------------------------
A|ABCDEFGHIJKLMNOPQRSTUVWXYZ{}
B|BCDEFGHIJKLMNOPQRSTUVWXYZ{}A
C|CDEFGHIJKLMNOPQRSTUVWXYZ{}AB
D|DEFGHIJKLMNOPQRSTUVWXYZ{}ABC
E|EFGHIJKLMNOPQRSTUVWXYZ{}ABCD
F|FGHIJKLMNOPQRSTUVWXYZ{}ABCDE
G|GHIJKLMNOPQRSTUVWXYZ{}ABCDEF
H|HIJKLMNOPQRSTUVWXYZ{}ABCDEFG
I|IJKLMNOPQRSTUVWXYZ{}ABCDEFGH
J|JKLMNOPQRSTUVWXYZ{}ABCDEFGHI
K|KLMNOPQRSTUVWXYZ{}ABCDEFGHIJ
L|LMNOPQRSTUVWXYZ{}ABCDEFGHIJK
M|MNOPQRSTUVWXYZ{}ABCDEFGHIJKL
N|NOPQRSTUVWXYZ{}ABCDEFGHIJKLM
O|OPQRSTUVWXYZ{}ABCDEFGHIJKLMN
P|PQRSTUVWXYZ{}ABCDEFGHIJKLMNO
Q|QRSTUVWXYZ{}ABCDEFGHIJKLMNOP
R|RSTUVWXYZ{}ABCDEFGHIJKLMNOPQ
S|STUVWXYZ{}ABCDEFGHIJKLMNOPQR
T|TUVWXYZ{}ABCDEFGHIJKLMNOPQRS
U|UVWXYZ{}ABCDEFGHIJKLMNOPQRST
V|VWXYZ{}ABCDEFGHIJKLMNOPQRSTU
W|WXYZ{}ABCDEFGHIJKLMNOPQRSTUV
X|XYZ{}ABCDEFGHIJKLMNOPQRSTUVW
Y|YZ{}ABCDEFGHIJKLMNOPQRSTUVWX
Z|Z{}ABCDEFGHIJKLMNOPQRSTUVWXY
{|{}ABCDEFGHIJKLMNOPQRSTUVWXYZ
}|}ABCDEFGHIJKLMNOPQRSTUVWXYZ{
最初に解いたのはヴィジュネル暗号。なんだけどこれ普通にpをmd5でハッシュ化してるので演算ツールにハッシュ値を入力して逆演算させればFLAGが出てきた 本当はキーをプログラム書いて特定して復号するのが正解なのかな？
VoIP
２問目はVoIP
VoIP
Extract a voice.
The flag format is SECCON{[A-Z0-9]}.
voip.pcap
パケットのキャプチャファイルが手に入るのでwiresharkで開くとRTPパケットが沢山。シーケンスから音声データに戻すと英語でフラッグを喋っているので聞き取ってFLAGを獲得、のはずがフラッグ部分の SECCON{9001I??}となって最後の２文字が何回聞いてもZAにしか聞こえなかった。orz
正解はSECCON{9001IVR}だったらしい…
basiq
basiq What is admin's password?☺ http://basiq.pwn.seccon.jp
adminの本当のパスワードは何かという問題。パスにadminと追加して入力するとbasic認証が出てくる。SQLインジェクションの問題かな？って思ったのでpasswordに ' or 'A'='A'と入力したら入れたけど多分違う。結局FLAGまでたどり着けず時間切れ。この問題１００点なのに解けてるチームかなり少なくてビックリ。他の参加者の方のwriteupに期待
pwnとかexploitとかも解いてみたかったけど全然わからなかった！ もっと色々勉強しようと思います><
最近
お久しぶりです。いつ更新しようかなー、明日かなーなんて考えてるうちにいつの間にか前回から２ヶ月近く経ってました。
なんというかネタがなかったわけじゃないんですがいざ書くとなると急にめんどくさくなってきたしまったんです…
というわけで今回は（逃げの）近況報告会に致します。
今まで何回かブログは作ったんですけどそのたんびにすぐ飽きて忘れてそのまんまっていうことが多かったので今回はなるべく継続いきたいです＞＜
さて、最近なにやってるかというと勉強してます。
学校の授業なんかではjavaのサーブレットjspとpostgresql使ってシステム一つ作ってみようっていうのをやったりしたんですがフルスタックのWebフレームワークの強さを実感させられました。
あとはひたすらに自学自習といった感じです。と言っても根詰めするのが苦手なのでのんびりです。空いた時間にはゲームしてます。FF15面白かったです。
で、何を勉強してるかというとまずは英語。できるといろいろ便利なので洋書読んだり、プログラミング言語の英語のドキュメント読んだりしてます。
わからない単語や熟語は随時google先生や単語帳へ！！って感じです。
次にOSの勉強ですね。こちらはLinuxのカーネル部分のソースを少しずつ紐解いて全体像をより詳しく把握するようにしています。
なんでそんなことやってるんだって言われると何ででしょうね… 面白そうだったから？でしょうか…
まぁ低いレイヤのことを理解すれば自ずと上の部分も理解しやすくなるだろうという浅ましい考えが透けて見えますがそこはノータッチで
次にPythonです。pythonはCTF等のセキュリティ関連でよく使われるので是非言語仕様を把握しておきたかったので勉強してます。
この言語面白いですね。機械学習とか興味なかったのですが色々調べ始めてしまっています。Web関連の方でもDjangoに触れてみたら便利だなーなんて思ってました。
pythonはCTFの問題において文字列の扱いや２、８、１６進数に対しての各エンコードなどが他の言語に比べても柔軟に扱えるイメージがつきました。
という感じで色々勉強している「つもり」ではあるのですが学び調べていけばいくほど新しく知らないことが沢山でてきたてんやわんやな日々です。
学校の方で研究室の配属も決まり、研究テーマも決めなくてはいけない時期が近づいてきましたが、興味のある分野が多すぎて最終的に一つに絞るというのが非常に苦しいです。
時間があれば色々できますがそうも言ってられませんね。なるべく寝る前とかにベッドでどんな研究がいいかなーなんて考えてます。そしていつの間にか寝ています。
というわけで最近の報告でした。
今回はこのあたりで筆をおかせていただきます。
次の更新を年明けまでにできるかな…
