  |
はてなキーワード: stdとは
この記事は Competitive Programming （その2） Advent Calendar 2015の12月20日の分です．12月19日はhadroriさんの競技プログラマー入門者用単語集，12月21日はroiti46さんです．
皆さんこんばんは．Mです．Advent Calendarを書くのは初めてなのでドキドキしていますが，どうぞよろしくおねがいします．普段あまり記事を書かないので anond を使わせてもらっています．
ここでは，ちょっと役立つ小ネタとして，今年書いたコードを１つ紹介します．「ビット行列を高速に乗算するコード」です．ごく簡単なコードですが定数倍効率化効果が大きいので嘘解法に使えます．
要素がブール値（True/False）であるような行列をビット行列と呼ぶことにします．このような行列に対する演算（特に乗算）はアルゴリズム理論ではよく出てきます．最も有名な例はグラフの推移包閉（各点から行ける点を全部求める）です；行列 A をグラフの隣接行列とし，和をbit-or, 積をbit-and で定義すると，行列のべき乗和「A^0 + A^1 + ... + A^{n-1}」の (i,j) 要素が True であることと，j から i に到達可能であることが同値になります．なお，このべき乗和は (I + A)^{n-1} と等しいので，高速べき乗で一発で求めることが可能です．グラフの推移包閉を求める現在（理論的に）最速の手法はこのアプローチに基づいており，計算量 O(n^\omega / log n) を達成します．O(n^\omega) は行列乗算の計算量で，現時点では \omega = 2.3728639... が最良です（Francois 2014）．また，log n は Method of Four Russians と呼ばれるビット演算を高速化する一般的なテクニックで，サイズ log n までの演算結果を全部ハッシュに突っ込んでおくものです．
さて，この Method of Four Russian というテクニックは，実際に実装してもあまり早くないことが知られています（テーブル引きが遅い・単純なループが早い）．ただし「いくつかのビットをブロック単位で計算する」というアイデアは実用的にも有用です．ブロック単位の演算をビット演算で実装できるとき，そのアルゴリズムは「ビットパラレルアルゴリズム」と呼ばれています．編集距離などの例が有名です．
ここでは，ビット行列に対するビットパラレル行列乗算を実装してみました．
A^n を計算するプログラムを書きました．実測結果を以下に示します．MacBook Pro; 2.8GHz Intel Core i7; 16GB 1600 MHz DDR3; g++ -std=c++11 -O3．実装は http://ideone.com/8AsuI2 にあります．
| n | 提案手法[s] | 通常手法[s] |
|---|---|---|
| 16 | 0.000014 | 0.000082 |
| 32 | 0.000025 | 0.000602 |
| 64 | 0.000074 | 0.004485 |
| 128 | 0.000440 | 0.036760 |
| 256 | 0.002757 | 0.311192 |
| 512 | 0.020163 | 2.847787 |
| 1024 | 0.200556 | 24.648609 |
| 2048 | 1.567657 | 205.503351 |
| 4096 | 13.894987 | --- |
| 8196 | 124.414617 | --- |
それなりに大きな n について 120倍くらい高速化しました．これだけ差があると嘘解法が通るようになります．
ビット行列を 8×8 のブロックに分割し，それぞれを unsigned long long (64bit) 1つで保存します．64が平方数というのが美しいですね．全体の乗算は8×8ブロックの乗算を普通に行えばよいので，結局 unsigned long longで表現された２つの8×8行列の積を考えれば十分です．
ここでは8×8行列の積を外積形式で実装します．外積形式というのは C = A B という積を C = (Aの1列目×Bの1行目) + ... + (Aのn列目×Bのn行目) という外積の和の形で表現するものです．各外積は，すべての列がAのk列目と等しい8×8行列とすべての行がBのk行目と等しい8×8行列の bit andに等しいので，Aからすべての列がAのk列目と等しい行列を作る方法とBからすべての行がBのk行目に等しい行列を作る方法を考えれば十分ですが，これはビットマスクして定数乗算すれば実装できます．
このコードはとある問題に対する嘘解法用に作成したものですが，結局普通のほうでも通るようになってしまったので，オフィシャルにお披露目する機会がありませんでした．
問題を他人に押し付けられる感じが嫌なんだよね。
まったりと、自分の好きな課題だけに取り組んでいきたい。そういう風にして生きている。
プログラミングも同じで、自分の作りたいものだけを作って生きている。
それともう一つ不満なのは（或いは『自分に合ってない』と表現した方が適切なのかも知れない）、洗練されたデータ構造や設計の必要性が問題中に殆ど出現しない所。
これは多くの言語に対して同じ問題を提供するには仕方のない事かも知れない。でも個人的にはそれが不自由で仕方がなかった。
例えばC++における純粋仮想関数（インターフェイス）と継承を使った下記の様な「木」を表現した構造、まず出てこないでしょ？C++ではなくCならswitchテーブルを使った再帰関数で実現する必要があるし、これが言語間で共通な問題を隔てる原因にもなっている。
struct interface_tree{ virtual double eval() const = 0; virtual std::size_t subtree_num() const = 0; virtual interface_tree *subtree(std::size_t) = 0; virtual ~interface_tree(){} }; // expression tree, add struct tree_add : public interface_tree{ tree_add(std::size_t n, interface_tree **t){ subtree_[0] = t[0], subtree[1] = t[1]; } virtual double eval(){ return subtree(0)->eval() + subtree(1)->eval(); } virtual std::size_t subtree_num() const{ return 2; } virtual interface_tree *subtree(std::size_t i){ return subtree_[i]; } virtual ~tree_add(){ delete subtree_[0]; delete subtree_[1]; } interface_tree *subtree_[2]; }; // expression tree, sub struct tree_sub : public interface_tree{ tree_add(std::size_t n, interface_tree **t){ subtree_[0] = t[0], subtree[1] = t[1]; } virtual double eval(){ return subtree(0)->eval() - subtree(1)->eval(); } virtual std::size_t subtree_num() const{ return 2; } virtual interface_tree *subtree(std::size_t i){ return subtree_[i]; } virtual ~tree_add(){ delete subtree_[0]; delete subtree_[1]; } interface_tree *subtree_[2]; }; // expression tree, value struct tree_val : public interface_tree{ tree_val(double n_) : n(n_){} virtual double eval(){ return n; } virtual std::size_t subtree_num() const{ return 0; } virtual interface_tree *subtree(std::size_t i){ assert(0); } virtual ~tree_add(){} double n; }; // ...
スマートポインタは、ここで言われている アドレスの参照指定としてのポインタじゃないよ。単なるコンテナ。名前にポインタってついてるからといって、いわゆるポインタじゃない。分類的にはコンテナ。
std::tr1::smart_ptr＜std::vector＜char＞ ＞ hako(new std::vector＜char＞);
の３種類があった時に string型も ポインタを代入しているが、 ポインタとは呼ばないだろ。コンテナと呼ぶ。
記法上 new を呼び出すが、 それが嫌なら、そういうコンストラクタ書いてもいいしな。
str++ とか str-- str+n という記法＝アドレス参照 ができるが
スマートポインタは そういう使い方はしない。 あくまでも指定されたオブジェクトを管理するだけ。
たいていの使い方をする場合に、参照カウンタの増減なんて手動ではしないから。（というか、ポインタがわからない奴がするな コピコン使え という設計方針でいいとおもう）
風俗を使うことをここで開き直っている男の悪しき所は、
後ろめたくないんだったら彼女に言えばいい。
プロのテクで心地よく射精させてもらうのが、美容院へ行くのと同じ「正当なサービスの消費」なんだったら、彼女に言えばいいよね？
なぜ隠れて行くのかわからない。もし後ろめたいなら、それは正当じゃないってことだ。
正直に言ってくれれば、風俗漬けの男とは別れようとか、検査に行こうとか、この人と粘膜接触は控えようとか、
ヤったあとは石鹸で洗おうとか、はたまた私も出張ホストと寝ようとか、色々行動のしようがある。
でも隠されたらどうしようもない。
「元彼の元カノの元彼の元カノの・・」っていうSTD注意喚起のCMがあったが、それと同じ。
感染率について、仮にキャリアだったとしてもまず0.01%以下です。傷がある場合は一桁以上あがりますが。
全部あがってきているとは限りませんが異性間の接触での感染者は年間200件にも満たないのです。
ましてオーラル程度では感染率はさらに低いです。おちつきましょう。
http://oshiete.goo.ne.jp/qa/6034345.html?check_ok=1
また、日本でAIDS自体のキャリアである確率は高いとはいえません、これは一般論にすぎませんが。
ただしほかのSTDのキャリアである確率はかなり高いと思います。クラミジアで30%という報告もありますし、風俗の半分近くは何らかの感染症をもっていると考えても過言ではないでしょう。
特に素股を拒まれたというのであればなおさらです。いずれにしてもゴムは最初からつけましょう。
3週間、ひどくても一ケ月程度もすれば自然治癒するものは治るはずで、治療しないとひどくなるSTDも多くありますので、内科で性感染症全般の検査をお願いすることをお勧めします。
たぶん円光歴もかれこれ10年くらい？
今まではそんなに頻繁にやっていたわけではないが、相手に支払った額やホテル代、出会い系サイトの利用料含めればざっと100万はくだらないのではないか。
その金があったらもっと有意義なことに使えただろう。
でも、性欲が高まってるときは冷静な判断できない。
「支出が収入を超えてるわけじゃないし」「貯金が○○円切るまではパーッと使っちゃおう」みたいな思考に囚われてしまう。
ちなみに風俗には数えるほどしか行ったことがない。価格と時間制限のバランスがちょっと割高に感じるのが主な理由だ。
最初は会うだけでかなり緊張してた。美人局の可能性も考え恐怖もあった。会えたら普通に飯食ったりするだけで、飲食代・カラオケ代＋ちょっとしたお小遣い代だけ払ってた。
性的なのも、最初は5000円～1万くらいで、おっぱいやお尻触らせてもらったり、手や口でしてもらったりというソフトな注文ばかりだった。いわゆるプチ。本番に対しては何か恐れを抱いていた。そもそもの女性経験がほとんどなかったし、稼ぎも少なかったことも理由だ。
それでも最初はかなり背徳感があった。しかし、それだけに興奮度も高かった。プチの場所がカラオケやネカフェだったこともスリルを加速した。
初めて円光で本番したのは誰が相手だっただろうか？思い出せない。ジェームス三木みたいに日記つけとくんだったな。しかし、本番やったときに一線越えたな、という感じはあった。
この頃から（たぶん2005、6年ごろ？）、売り手の方でもどうせ円光するなら単価が高い方がいいからか、プチ希望はぐっと減って本番のみ希望者が圧倒的になったようだ。本気で金が必要な人も増えたせいか、売り手の年齢層が上がった気もする。サイト運営者の工夫もあるのか業者や冷やかしはほとんどいなくなった。純粋に相手の条件とこちらの条件が合うかどうかだけがポイントになったようだ。
相手の容姿は、意外と美人の方がプロフに写メを出してたり、リクエストしたら送ってくれる傾向があるような気がする。見られたい願望があるタイプもいるんだろう。あと金欠で切羽詰りすぎてる人もわりと写メくれる。しかし、一般的に警戒して写メを出さないのが多数派か。だから当たり外れは現地に行って初めてわかる。あまりにも好みとかけ離れてたら（ありていにいえばブス）ブッチすることもあったが、そうでなければ据え膳食わぬは何とやらで…。確率的にはかなりの美人にあたることもある（メイクした上での話しだが）。おおむね好みと言えるのは会った中の２割くらいか。
JK16、JC14と本番したことがあり、JC15とプチしたことがある。それまではやりたく仕方なかったJK・JCだが、ある時、円光で逮捕の記事を読んでから急に怖くなり、警察に逮捕される可能性を考えると眠れないこともあった。朝、自宅のインターフォンが鳴らされた時は心臓が縮みあがる思いだった。家族・職場に逮捕が知られたら…と思うと自殺も考えたこともある。おかげさまで（？）無事時効を迎えました。しかし、そもそも出会い系サイトではJK・JCなんてまずいないような気がする。一部報道ではグリーやモバゲーに流れてるらしいが、それは男が声かけてるんじゃなくて、JK・JCの方から募集してるんだろうか？何にしても俺はもう追いかけたりしない。
生や中出しもやったことがある。中出しOKの子はもちろんピルを飲んでるんだが、生外の子はわからない。外に出せば大丈夫だと思ってるのだろうか。そして、当の自分は性病が怖くなってやった3ヶ月後に保健所にHIV・STD検査に行くのであった。今のところはセーフ。いい加減学習しろよと自分でも思うが、やはり性欲の衝動に勝てないのだ。
ちなみに今日は生でアナルに入れてみた。相手も了承済みの上でお互い初アナルだったが、少し痛がったのでピストンはしなかった。そして来年1月にはまた保健所に行くんだろうな、俺。
これまでは数ヶ月に一度の性欲の高まりに応じて、サイトで相手を探すという感じだったのだが、今年に入ってからはペースが上がってきた。月に二度、三度という時もある。貯金が目に見えて減って行ってる。
ひょっとすればセックス依存症か何かの病気なのかもしれない。いくらなんでも性衝動に太刀打ちできなさすぎる。円光以外にも様々な悪さをしているし。このまま人生が破滅するまで続くのだろうか。
fooのintへのキャストがtrue/falseを返すというように、fooのクラス仕様が決められてるんなら、
そしてboolへのキャストが未定義だったり、また違う意味なのなら
if (foo) {
ではなく
if (foo == true) {
って書かざるをえないだろう。嫌いとか好きとかの問題ではないと思う。
class { public: operator bool() { std::cout << "xxx\n"; return true; } //*1 operator int() { std::cout << "yyy\n"; return true; } //*2 } foo;
があったときに、「if (!foo)」だったら*1が、「if (foo == false)」だったら*2が実行されるような処理系がある。
最新のVC++だと後者は曖昧だってエラー出るね(たぶんC++だと「trueは1でfalseは0」なんかではなくあくまでもtrueとfalseなんだ)。
なんにせよ演算子や条件式などに関連する暗黙のキャストはわかりづらく、そしてそんなのを利用したコードはきっとバグる。
だから
というのが本当なら、==trueがどうこうなんて些細な問題はおいておいて、fooを暗黙のうちにintにキャストしたりboolにキャストしたりして使っているという危険な部分をまずなんとかすべきだろう。
古いC言語風に書けばこんな感じ。
#define FALSE 0 #define TRUE (!FALSE)確かに、実際に値を表示させてみると、昔のVC6だと「1」という結果が出てくるし、VB6だと「-1」という結果が出てくる。これ、当時混乱の元だったんだよね。
VC6とか関係なくてC言語の仕様でそうなんだが、それをわかってないとすればやばい。
個人的には
if( foo != FALSE ){
も十分きもちわるいので
if (foo) { ... }
if (!foo) { ... }
にしてほしい。
もちろん
if(!i%15){
std::cout << "fizzbuzz" << std::endl;
}else if(!i%5){
std::cout << "buzz" << std::endl;
}else if(!i%3){
std::cout << "fizz" << std::endl;
}else{
std::cout << i << std::endl;
}
とか書くことはできますが、見やすさとかそういう話はいいかと思って短くしてみました。
あと3項演算子の:の左右で違う型を受け付けてくれないので、intを文字列に変換する必要がありました。
sprintfを使わないで変換する方法がわからなかったもので。
「ヤバい」と書かれた方でしょうか？
最近は、２４インチ ３０インチディスプレイなんて安いんだから、横８０ではなく横１２０ぐらいは平気で使える。
classname::enumname という毎回指定でも エディタがインテリジェントに保管してくれるから問題ない。
基本的に 外部ツールがチェックしてくれるんだから
enum{
{
};
で問題ないと思われ
言い方を変えれば、class内部以外でenumを定義することなんて最近はあるのか？グローバルなenumなんて余り無いと思うが・・・
クラス内部では、省略できるし、外部から、クラス内部の値を呼ぶときは、どのクラスのこのenumって外部だよって意味で毎回書いたほうが安全だろ？
using namespace std
ですら、書かないほうが安全 毎回std::って書かないと、うっかり、stringクラスを定義する人がいないとは限らんからね・・・
一斉に変更したい？ エディタに正規表現で置換すればよろしい・・・
原則、外部のツールで解決できる問題は、外部のツールで解決すればいい。
言語仕様を拡張されると、初心者に、その理屈を説明するという問題が出てきて、そういうのは初心者には無理。
他方、ツールを使えない初心者でも、毎回コピペや手で置換は出来る。
指摘ありがとう。以前に見かけた資料を再確認したらHIVに限った話じゃなくてSTD全体の話だった。
元にした資料はこれ。
http://www.acc.go.jp/kenkyu/ekigaku/2000ekigaku/eki_016/016.htm
| 女性 | 男性 | |
| 決まった相手のみ | 59.4 | 17.3 |
| 不定期の相手のみ | 3.1 | 13 |
| 定期・不定期両方 | 25.0 | 43.5 |
| 不明 | 12.5 | 26.1 |
感染の危険があってもなんで生でやるのかっていう話に対するツッコミのつもりだったので、趣旨としては多分あんまずれないと思うけど、表記として正確じゃないので撤回します。
横だけど。
コンドームを配って使い方教えてやっても生でやるんだ
救い難いね
日本も先進国の中では新規感染率が増えているやばい国なんだよね。
でも、子供ができたら結婚するつもりのカップルとかだったら、生でやるのは珍しくないんじゃないのかな。
日本では、HIVの新規感染率STDの感染率は男女差あまりないけれど、感染者の性行動の内訳としては男性は不特定多数と１年以内に性交渉を持っている人がメインだけど女性の場合は１年以内に特定の１人としか性交渉を持っていない人がメインらしい。
そういうわけで、少なくとも女性に対しては、特定の相手とだけ性交渉をしていれば感染のリスクは少ないという啓蒙は意味がないということが分かって、啓蒙内容を検討しなければならないという見解になっているそうだ。
日本は男性の風俗利用について寛容であることが比較的求められてるけど、風俗に行くような男性と生でやることが一番リスクが高いことなんだっていう啓蒙がもっとなされないとやばいよね。
C++において多倍長整数，多倍長浮動小数点を扱うライブラリとしてGMPが有名だ．
Visual C++を使っているのなら，GMPと互換のあるMPIRが導入しやすくて良い．
以下，VC10 (Visual Studio 2010)環境での話．
このMPIRはどうもC++の複素数クラスstd::complexと相性が悪いようだ．
#include <complex> #include <iostream> #include <iomanip> #include <mpirxx.h> int main() { std::complex<mpf_class> a(1.0, 2.0); std::complex<mpf_class> b(0.0, 1.0); std::complex<mpf_class> c1 = a + b; std::complex<mpf_class> c2 = a - b; std::complex<mpf_class> c3 = a * b; // std::complex<mpf_class> c4 = a / b; // error std::cout << "a =" << a << std::endl << "b =" << b << std::endl << "c1 =" << c1 << std::endl << "c2 =" << c2 << std::endl << "c3 =" << c3 << std::endl; // std::cout << "c4 =" << c4 << std::endl; return 0; }
「operator/=」から呼び出される「_Div」内部でエラーが出る．
そこでテンプレートの特殊化をする．
#pragma once #include <mpirxx.h> #if defined(_MSC_VER) &amp;&amp; (_MSC_VER == 1500) /* VC9 (Visual Studio 2008) */ #pragma comment(lib, "C:\\lib\\MPIR\\vc9\\mpirxx.lib") #pragma comment(lib, "C:\\lib\\MPIR\\vc9\\mpir.lib") #else if defined(_MSC_VER) &amp;&amp; (_MSC_VER == 1600) /* VC10 (Visual Studio 2010) */ #pragma comment(lib, "C:\\lib\\MPIR\\vc10\\mpirxx.lib") #pragma comment(lib, "C:\\lib\\MPIR\\vc10\\mpir.lib") #endif #include<complex> namespace std { template<> complex<mpf_class>&amp; complex<mpf_class>::operator/=(const complex<mpf_class>&amp; _Right) { // divide by other complex //this->_Div(_Right); mpf_class _Rightreal = (mpf_class)_Right.real(); mpf_class _Rightimag = (mpf_class)_Right.imag(); mpf_class bunbo = _Rightreal * _Rightreal + _Rightimag * _Rightimag; mpf_class re = ( this->real() * _Rightreal + this->imag() * _Rightimag ) / bunbo; mpf_class im = ( this->imag() * _Rightreal - this->real() * _Rightimag ) / bunbo; this->real(re); this->imag(im); return (*this); } }
これでとりあえずは割り算もできるようになった．
計算精度については何も考えていない．
＃突っ込みお待ちしてます．