【C++】配列とVectorとArrayで比較
きっかけ
以前、C++で実装した際に、コードを読まれた方からなんでVectorにしないの?と聞かれたことがありました。
機能面での違いはたしかにありますが、固定サイズならば別に配列でもOKではと思っていたのですが、ふと気になったので調べてみました。
比較対象
比較した方法は次の4通りです。
Vector同士で比較しているのは、配列っぽく使うパターンと、push_backで代入させた場合のものの2種類です。
push_backは遅いと書いていらっしゃる方もいたので、比較として入れてみようと思い、含めました。
コード
ダメダメながらも書いたコードは次に続きます。
やったことはすごく単純で、10万のデータを作って、そのデータから総和を求めるという操作です。
もっと良いベンチマークがあるかもしれませんが…。
配列(一番最初に習うであろうもの)
#include <iostream> #include <cstdio> #include <vector> #include <array> #include <chrono> int main(int argc, char const *argv[]) { std::chrono::system_clock::time_point start, end; double elapsed; const long int MAX = 100000; long int a[MAX+1]; // Array start = std::chrono::system_clock::now(); for (long int i = 0; i <= MAX; i++) { a[i] = i; } long int sum1 = 0; for (long int i = 0; i <= MAX; i++) { sum1 += a[i]; } end = std::chrono::system_clock::now(); elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count(); std::cout << elapsed << "μs" << std::endl; return 0; }
↑の修正版
#include <iostream> #include <cstdio> #include <vector> #include <array> #include <chrono> int main(int argc, char const *argv[]) { std::chrono::system_clock::time_point start, end; double elapsed; const long int MAX = 100000; long int a[MAX+1] ={}; // Array start = std::chrono::system_clock::now(); for (long int i = 0; i <= MAX; i++) { a[i] = i; } long int sum1 = 0; for (long int i = 0; i <= MAX; i++) { sum1 += a[i]; } end = std::chrono::system_clock::now(); elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count(); std::cout << elapsed << "μs" << std::endl; return 0; }
Vector(配列っぽく)
#include <iostream> #include <cstdio> #include <vector> #include <array> #include <chrono> int main(int argc, char const *argv[]) { std::chrono::system_clock::time_point start, end; double elapsed; const long int MAX = 100000; std::vector<long int> b1(MAX); // vector(like Array) start = std::chrono::system_clock::now(); for (long int i = 0; i <= MAX; i++) { b1[i] = i; } long int sum2 = 0; for (long int i = 0; i <= MAX; i++) { sum2 += b1[i]; } end = std::chrono::system_clock::now(); elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count(); std::cout << elapsed << "μs" << std::endl; return 0; }
Vector(push_back)
#include <iostream> #include <cstdio> #include <vector> #include <array> #include <chrono> int main(int argc, char const *argv[]) { std::chrono::system_clock::time_point start, end; double elapsed; const long int MAX = 100000; std::vector<long int> b2; // vector(push_back) start = std::chrono::system_clock::now(); for (long int i = 0; i <= MAX; i++) { b2.push_back(i); } long int sum3 = 0; for (long int i = 0; i <= MAX; i++) { sum3 += b2[i]; } end = std::chrono::system_clock::now(); elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count(); std::cout << elapsed << "μs" << std::endl; return 0; }
Array(C++11から追加されたもの)
#include <iostream> #include <cstdio> #include <vector> #include <array> #include <chrono> int main(int argc, char const *argv[]) { std::chrono::system_clock::time_point start, end; double elapsed; const long int MAX = 100000; std::array<long int, MAX> c; // C++11's Array start = std::chrono::system_clock::now(); for (long int i = 0; i <= MAX; i++) { c[i] = i; } long int sum4 = 0; for (long int i = 0; i <= MAX; i++) { sum4 += c[i]; } end = std::chrono::system_clock::now(); elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count(); std::cout << elapsed << "μs" << std::endl; return 0; }
↑の修正版
#include <iostream> #include <cstdio> #include <vector> #include <array> #include <chrono> int main(int argc, char const *argv[]) { std::chrono::system_clock::time_point start, end; double elapsed; const long int MAX = 100000; std::array<long int, MAX> c = {}; // C++11's Array start = std::chrono::system_clock::now(); for (long int i = 0; i <= MAX; i++) { c[i] = i; } long int sum4 = 0; for (long int i = 0; i <= MAX; i++) { sum4 += c[i]; } end = std::chrono::system_clock::now(); elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count(); std::cout << elapsed << "μs" << std::endl; return 0; }
結果
単位はすべて、μsことマイクロ秒(100万分の1秒)。
rev2とついてるものは修正版です。
Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./array.out 792μs Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./array_rev2.out 489μs Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./vector_like_array.out 603μs Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./vector_push_back.out 2962μs Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./array_cpp11.out 827μs Ruby@Kotori-no-MacBook-Pro ~/Desktop $ ./array_cpp11_rev2.out 528μs
やっぱりpush_backは遅いですね。
Vectorを配列っぽく使うと配列と変わらない速度みたいです。
あと意外にもC++11から追加されたArrayはわずかながら配列より遅いみたいです。なぜでしょうか。
と思っていましたが、初期化を行ったうえで再実験行ってみたら配列が一番高速でした。次に、Array(C++11以降)が速いという結果となりました。
まとめ
今後はVectorを配列っぽく使います。
いや、修正した結果、配列が速かったのでやっぱり配列が一番ですね。
追記1(2016.07.09 0:27 UTC+9)
一部のコードを修正前のものを記載していました。修正しました。
なお、結果は修正後のものを記載しているため、変化ありません。
追記2(2016.07.09 0:52 UTC+9)
研究室の先輩(id:togatogah)から、「配列とArray(C++11以降)の初期化されていない可能性があるのに対し、Vectorは構築時に必ず初期化を行うので、配列とArrayを初期化してみてはどうか」という提案がありました。
そこで試してみたところ、大きく結果が変わりました。
id:togatogahさんありがとうございました。
ファニーナイツ ご注文はうさぎですか?? シャロ 1/7スケール PVC製 塗装済み 完成品 フィギュア
- 出版社/メーカー: 青島文化教材社
- 発売日: 2016/05/19
- メディア: おもちゃ&ホビー
- この商品を含むブログ (4件) を見る
猫でもわかるC++プログラミング 第2版 (猫でもわかるプログラミング)
- 作者: 粂井康孝
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2013/07/27
- メディア: 単行本
- この商品を含むブログ (2件) を見る
- 作者: ビャーネ・ストラウストラップ,Bjarne Stroustrup,柴田望洋
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2015/02/28
- メディア: 大型本
- この商品を含むブログ (11件) を見る
手帳型スマホケース?iPhone6/6S専用?ご注文はうさぎですか???05 シャロ
- 出版社/メーカー: A3
- 発売日: 2016/07/09
- メディア: おもちゃ&ホビー
- この商品を含むブログを見る
【ネットワーク分析】 #1 グラフってなんぞや
最近真面目な投稿をしていないので、ネットワーク分析とかグラフ理論とかその周辺のアルゴリズムとかについてシリーズっぽくゆるゆると記述していこうと思います。
本シリーズでは、「ネットワークだぁ?グラフだぁ?全く知らないよ!」って方を対象に書いていくつもりです。
ネットワーク分析とは
ネットワーク分析とは、グラフ理論におけるグラフで表現したものに対する分析方法です。
対象となるデータは幅広く、SNSの繋がりとか感染症の伝搬だとか色々あります。
そもそもグラフとは
グラフ理論のグラフとかドヤ顔で言われてもわかんないですよね。いやそれが普通だと思います。
グラフとは、頂点(またはノード、V: Vertex)と辺(または枝、E: Edge)で表されるものと定義されています。
それらの集合を数学っぽく記述すると、
となります。これは、頂点N個と、枝M本の集合を表すという具合です。
頂点は、何か物(?)を示し、枝はその物々の繋がりを示します。
身近な例で言うと、高速道路の出入り口が頂点、高速道路そのものが枝だと考えたらわかりやすいかと思います。
図1: 簡単な例・首都高のサイトより
引用元: http://search.shutoko.jp/
有向グラフと無向グラフと次数
グラフと言っても2種類あります。有向グラフと無向グラフです。
何が違うのかといいますと、有向グラフは向き(方向)が指定されており、無向グラフは向きが指定されていません。
また、頂点に接続している枝の数のことを次数といいます。
有向グラフにおいては、出次数(でじすう)と入次数(いりじすう)の2つが存在します。
無向グラフ
無向グラフとは、簡単に言うと、頂点間を結ぶ枝向きが指定されていないグラフです。
データセットとかのサイトに行くと、undirectedと記述されているものがそれです。
簡単な図で示しますと、以下の図2です。
図2: 私が描いた無向グラフ
この図1では、
という枝があることが分かります。
次数ですが、から順に
3, 4, 3, 4, 2
となっており、最大次数は頂点とにおける4となります。
てか、図汚いですね。はてなフォトライフめ・・・。
有向グラフ
有向グラフとは、簡単に言うと、頂点間を結ぶ枝向きが指定されているグラフです。つまり、どこからどこに向かって、枝があるのか…というのが表現できます。
データセットとかのサイトに行くと、directedと記述されているものがそれです。
簡単な図で示しますと、以下の図3です。
図3: 私が頑張って描いた有向グラフ
このグラフですと、がモテモテですね。
出次数ですが、から順に
0, 4, 2, 2, 0
となります。
これは、点から出て行く枝の数を表します。わかりやすく言うと、何人に向けてラブレターを書いたかみたいな感じですね。
一方、入次数はから順に
3, 0, 1, 2, 2
となります。
これは、店に入ってくる枝の数を表します。わかりやすく言うと、何人からラブレターをもらったかという感じですね。
隣接行列
グラフには、その隣接関係を示す隣接行列というものがあります。
簡単に言うと、どことどこがつながっとんねんって話です。
行、列ともに頂点集合に対応しています。
ちなみに、蛇足ながら書くと領域計算量はです(頂点の数をnとした場合)。
無向グラフにおける隣接行列
図2の例を元に隣接行列を書くと、
となります。
無向グラフの場合、双方の向きを考慮しないため、行列は対称となります。
有向グラフにおける隣接行列
図3の例を元に隣接行列を書くと、
となります。
有向グラフの場合、向きを考慮し、それを隣接行列でも表現するため、行列は非対称となります。
行方向に攻め、列方向に受け、と考えると簡単だと思います。
今回のまとめ
簡単な事項について取り扱いました。
ループとか、重みとか、接続行列とか色々すっとばしていますが、今回はここまで…。
RかPythonで業界地図を作る(作りたい)
世間では就職活動というものが行われています。
かくいう私も就活生。来月から説明会ラッシュになりそうで、今からスタミナが切れそうな予感しかしてません。
就活生必須アイテム(?)とやらの1つに業界地図という本があります。
それぞれの業界について、資金の流れだったり、株の保持の数値だったりで、相関図を描いてるという本です。
自分自身で買いたいとは思わないのですが、本屋で立ち読みして「へえ〜」と思うことも多いです。
ここで、ふと、私の研究分野について思い出してみました。
私の研究分野はいわゆるネットワーク分析(グラフ理論)です。
そう、こんなことを思いつきました。
「まてよ?株の保持数とかをデータとして落としこめば、グラフ理論におけるグラフでそれって表現できるのでは?」
早速データ探しの旅へ。
・・・見つからない・・・・・・
一応、ページをスクレイピングすればできそうですが、できればスクレイピングは避けたいところ。
いやでも避けられないか。
ということで今後の構想としては、
という感じです。
「次回、なにかやる。」お楽しみに。
- 作者: 東洋経済新報社
- 出版社/メーカー: 東洋経済新報社
- 発売日: 2015/08/28
- メディア: 大型本
- この商品を含むブログ (1件) を見る
- 作者: 日本経済新聞社
- 出版社/メーカー: 日本経済新聞出版社
- 発売日: 2015/08/28
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
- 作者: 帝国書院編集部
- 出版社/メーカー: 帝国書院
- 発売日: 2015/10/22
- メディア: 単行本
- この商品を含むブログを見る
音楽から見たこの1年 改め 音楽から見た去年の1年
あけましておめでとうございます。
去年せっかく書き起こしていたのに公開するのを忘れていましたので一部修正した上で公開します。
去年1年間で再生した回数が多かったもの、単純に衝撃をうけたものなどを振り返るだけの記事です。
修羅場 by 東京事変
東京事変はもともと椎名林檎が好きなので聞いていたのですが、何故かこの修羅場という曲はずっとスルーしてたのに急に惹かれたという感じです。
水星(instrumental) by tofubeats
本来ならば歌詞ありの方を推すんですが、僕自身はトラックの良さに惹かれたのであえてinstを。
tofubeats - 水星 (suisei) instrumental
Luv(Sic) pt.3 by Nujabes Feat. Shing02
ほぼ毎年上位に入ってる曲です。たぶん高校2年からずっと聴き続けてる気がします。
シリーズ物なんですが、僕としてはpart3の方がJazzyな感じがして好きです。
Nujabes - luv (sic.) pt 3 [ft.shing02]
キラーボール by ゲスの極み乙女。
Amazon Musicでたまたまみつけてきいてみたら、イントロで即ヤラれました。
そういえば紅白に出るんですね --> 出てました。
トレンチコートマフィア by DJ 松永 Feat. R-指定
たぶん2015年で唯一iTunes Music Storeで購入した曲です。
曲としては、高校生とかの頃にある、おもろいやつとか目立つ奴がパッとしててそうじゃない人間側はパッとしないということへの不満と生き残りをテーマにした曲です。
ちょうどこの曲を知ったのは、自分があることですごく不満を持っていて、どうしてって思うことが常にあった時期でした。
分かる人には共感が得られる・・・といった具合でしょうか。
そう、2015年にリリースされた曲がない…。いや聞いてたんですけどなんか何も来なかったというか。
来年はたぶん書かないだろうなあ --> 今年はたぶん書かないだろうなあ。
- アーティスト: くのいち☆Girls 彩美唯~あみゅ~,林宏次,三浦誠司,シノビ塾音楽部
- 出版社/メーカー: South to North Records
- 発売日: 2007/08/15
- メディア: CD
- クリック: 4回
- この商品を含むブログ (4件) を見る
- 作者: 大蔵康義
- 出版社/メーカー: 国書刊行会
- 発売日: 2010/04/27
- メディア: 単行本
- この商品を含むブログを見る
2015年を振り返ってみる
2015年も残り僅か。
今年もツイートと共に振り返っていきたいと思います。
昨年は簡単に振り返りましたが、今年はイベントが多かったのでもっと細かく書きたいと思います。
can.hatenadiary.com
1月
卒論の提出と、卒研の発表練習で追われてた毎日でした。
プライベートでのトラブルが立て続けに起きたこともあって結構疲れてました。
あと、初めてTokyo.Rで発表したのもこの時でしたね。
2月
現在所属している大学院の冬入試があり、翌週に合格しました。
そこから、進学予定だった大学院の辞退届提出とか色々手続きでバタバタしていました。
3月
ハッカソンとかサークルの春合宿とか追いコンとかありましたが、やはり卒業式が印象深かったです。
学部の4年間、本当に色々やってきたので楽しかったですね。
4月
入院しました(大学院に入学しました)。
5月
Mac買ったり、プロ生でLTしたり五月祭に行ったり。
6月
インターンのESを書き始めたり、面接に行ったりしました。
7月
77円のUSBメモリを買いました。 https://twitter.com/wonder_zone/status/618295861496295424
8月
インターンシップに行ってました。
9月
インターンシップに行ってました。
あとTokyo.RでLTをしたりしました。また、某合宿に行きました。
10月
このくらいの時期からJapan.Rを宣伝するようになりました。
11月
サークルOBとして学祭に行ったりしました。
12月
Japan.Rをしました。
ブシロードライブに行きました(今年行ったイベントはこれだけ)。
実家に帰省して、高校の同窓会行きました。
今年は、色々充実した1年間でした。
生活基盤が変わったこともあり、色々大変でしたがその分楽しめました。
それではみなさん良いお年を。
【引越し・ご挨拶】信州戸隠そば 車屋印生そば(大) (半生そば110g×5、濃縮つゆ15ml×5) 約5人前)[商品番号ク-大]
- 出版社/メーカー: 信州戸隠そば株式会社
- メディア: その他
- クリック: 2回
- この商品を含むブログを見る
信州戸隠そば 本十割生そば(大) (十割 生そば110g×6 ストレートつゆ50ml×6) 約6人前 [商品番号ホ-大]
- 出版社/メーカー: 信州戸隠そば株式会社
- メディア: その他
- 購入: 1人 クリック: 3回
- この商品を含むブログを見る
北海道 北のシェフ 和風&海鮮 おせち料理 三段重 盛り付け済み 冷凍おせち お届け日:1月1日?1月2日
- 出版社/メーカー: 美食サークル
- メディア: その他
- この商品を含むブログ (2件) を見る
小正月おせち! 神楽坂「ここさち」監修 寿ぎ和風おせち 【夢殿】 八角一段重 1~2人前 特典:天然真昆布プレゼント
- 出版社/メーカー: ここさち
- メディア: その他
- この商品を含むブログを見る
【R Advent Calendar 2015】Japan.Rのお話(副主催目線) #JapanR
「R Advent Calendar 2015」12月7日の記事です。
昨年のAdvent Calendarはスクフェス解析でしたが、今年は12月5日にJapan.R 2015を開催しましたので、ここに書き残しておきます。
きっかけ
昨年のJapan.Rのお手伝いをしたご縁もあり、主催のgepuroさんから今回の運営のお誘いをいただきました。
厳密には、「あ、Japan.R運営に入ってるからよろしくねー」と言われたのがきっかけです。
あと、副主催になったきっかけはJapan.R運営メンバーとのキックオフの飲み会でgepuroさんに「副主催な副主催」と言われたことです。
結構ゆるふわです。
実際のお仕事(当日まで)
今回のJapan.Rは主催・副主催に加えて、多数のサポートメンバーがいました。
メンバー内のコミュニケーションツールとして、TwitterのグループDM(今年くらいに実装された?)を使用していました。
僕自身は、おもに宣伝と、宣伝と、宣伝と、時々講演の依頼(結局おじゃんになってしまいましたが…)と、宣伝と、宣伝と、gepuroさんのサポートと、他のメンバーのサポートとかしていました。
仕事はそんなに多くなかったなと後から反省しています。
当日の出来事
1時間半前に集合し、色々セッティングとか行いました。
ここで発覚したのは、電源の数が少ないことと、Wi-Fiの環境がなかったこと。この時は結構びっくりしました。
また、USTREAM配信向けにiPadを設置したのですが、家にあったいらないハンガーを曲げて台代わりにしました。結構、便利でしたのでおすすめです。
USTREAMをiPadで配信する際は、どうもWi-Fiが途切れたらそのまま配信が終了になるみたいなので、注意が必要です。
会が始まってからの話ですが、途中から司会が僕に変わりまして、前に立つ機会が多かったです。
幸いにして(?)、学部時代に人の前に立つことが多かったのもあってそこまで緊張しませんでした。むしろ楽しかったぐらいですね。
懇親会の二次会の場所で色々ゴタゴタしてたので、今後はビシっと意思決定できる男になりたいです。
それと懇親会のあとなんですが、山手線を寝過ごして、品川から家までタクシーで帰りました。辛い。
https://twitter.com/wonder_zone/status/673172108302753792
来年とか他の勉強会を運営するとき向けのお話
- 場所の確保(200人規模だったので大変でした)
- 電源は基本ないものだと思ってタップとかを用意する
- Wi-Fiルーターは持参しておく
- 喫煙所の位置確認
- 入り口の写真撮影&Twitter等で共有
- USTREAMはつながってるか適宜確認
- キャンセルは割と多いと想定すること
- ドミノは半額クーポンが多いので活用
- 懇親会で酒を飲み過ぎない(笑)
最後に
来てくださった皆さん、発表してくださった皆さん、本当にありがとうございました。
【情報理工+工学系+学際情報 Advent Calendar 2015】実は便利かもしれないトラベルセンターのお話
- 12/3の分ダ
- 今日は箇条書きスタイルでいク
- トラベルセンターは割と使える子だということを知ってるカ?
- マルス端末設置なんだゾ
- わざわざJRの駅までいかなくても特急券とか切符とか買えるゾ
- たぶんムーンライトながらも買えるゾ
この辺りの話はtozaiuserくんが詳しいので書いてくれることを期待してるゾ
国際学生証も発行できるゾ
- Officeの・・・なんでもないをやりたいときに使えるゾ
- クレカが使えるかどうかは知らないゾ
- 筆者はまだ国際学生証の発行にしか行ったことがないゾ
偉大なるOB様からトラブルセンターといわれたゾ
@wonder_zone トラブルセンター
— TJO (@TJO_datasci) 2015, 12月 3
【追記】 スポンサーから助言を頂いたゾ
@wonder_zone クレカは使えます
— 天井 (@willelbn) 2015, 12月 3
(おわり)
TOMIX Nゲージ 92985 限定 373系特急電車 (東海・ムーンライトながら) セット
- 出版社/メーカー: トミーテック
- メディア: おもちゃ&ホビー
- クリック: 3回
- この商品を含むブログを見る
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/02/14
- メディア: Kindle版
- この商品を含むブログを見る