Stories of Your Life and Others » Blog Archive » C++で文字列のsplit
つい最近、C++の文字列splitが必要な場面がありました。 いい加減C++のsplitを毎回書くのが面倒になってきましたので、忘れないようにメモっておきたいと思います。 C++でsplitを書く方法はいくらでも方法があると思いますが、代表的な実装例をあげてみます。 boostが使える環境であれば一番最初の選択肢としてboostのstring algorithmを利用した方が車輪の再発明をしなくて済むかと思います。 ただ、競技プログラミングなどでは残念ながら利用できません。 find_first_ofを利用する方法 vector<string> split(const string &str, char delim){ vector<string> res; size_t current = 0, found; while((found = str.find_first_of
Efficient substring searching
There are many times when programmers need to search for a substring, for example when parsing text. This is commonly referred to as searching for a needle (substring) in a haystack (the string to search in). The most straightforward way to do this is by using search functions that your language provides: C: strchr()/memchr(), strstr()/memmem() C++: string::find() Ruby: String#index or regular exp
平方根のアルゴリズム
平方根である。sqrtである。私の数学知識は非常に乏しく、かろうじて平方根の何たるかを解するばかりであるが、ふと、平方根を計算するアルゴリズムが知りたくなった。理由は、constexprなsqrtを実装してみたくなったからだ。 日本語では、いい情報がWeb上に存在しないので、ここに書いておく次第。この説明は、私のように数学の知識を持たない人間にも理解できるはずである。 ここで使うのは、バビロニア人の方法（Babylonian method）と呼ばれている、歴史あるアルゴリズムである。この方法は、手動でも、プログラミングでも、非常に簡単に計算できる、大変便利で汎用的なアルゴリズムである。しかも、速度もそれほど遅くない。 √Sに対して、 任意の正の整数を初期値X0と定める（できるだけ平方根に近い値が望ましい） Xn+1を、Xnと S / Xnの平均値とする（平均値は相加平均で求める） 必要な精
開発メモ: トップNソートの検討
上位N件をソートした状態で取り出すという、いわゆる「トップNソート」の効率的な実装について検討してみた。 背景 データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと "ORDER BY xxx LIMIT yyy" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。 全体をソートして上位を取り出せば目的は満たせるのだが、それだと無駄な計算が多い。100万件の中から上位10件だけ欲しい場合に、残りの99万9990件まで律儀にソートする必要はない。ということで、上位N件をソートして取り出すという「トップNソー
本当に1.5倍のほうがメモリ効率がよいのか - inamori’s diary
C++のstd::vectorにpush_backしていくと、ある領域を確保して、それを超えそうになったらまたある程度ゆとりのある領域を確保するという機構になっています。 ２倍だけじゃない - d.y.d. にまとめてありますが、std::vectorや類似するコンテナは2倍ずつ領域を大きくしていくのかと思いきや、1.5倍というのも多いんですね。実際にVC10 beta2で動かしてみると、 #include <iostream> #include <vector> int main() { std::vector<int> v; for(int i = 0; i < 100; i++) { const std::vector<int>::size_type old_cap = v.capacity(); v.push_back(i); const std::vector<int>::siz
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
SACHICA(類似文字列列挙アルゴリズム) - Yasuo Tabeiの日記
SACHICA(類似文字列列挙アルゴリズム)のC++による実装を公開しました。 http://sites.google.com/site/yasuotabei/sachica sachicaは、同じ長さの文字列集合を入力として、ハミング距離がある閾値以下のすべてのペアーを超高速に出力します。 アルゴリズムは、マルチソーティングという手法に基づきます。 詳しくは、ハミング距離がd以内で長さがmの文字列集合があったとします。初めに、各文字列をk (> d)の部分文字列のブロックに分割します。 今、ハミング距離がd以内の文字列のペアーを求めたいので、もし、ハミング距離がd以内の文字列のペアーが存在すれば、鳩の巣原理により、それらにはk - d個の完全一致するブロックが存在します。この原理に基づき、sachicaはcombination(k, k-d)のすべての組み合わせのブロックをラディックスソ
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ
GT Nitro: Car Game Drag Raceは、典型的なカーゲームではありません。これはスピード、パワー、スキル全開のカーレースゲームです。ブレーキは忘れて、これはドラッグレース、ベイビー！古典的なクラシックから未来的なビーストまで、最もクールで速い車とカーレースできます。スティックシフトをマスターし、ニトロを賢く使って競争を打ち破る必要があります。このカーレースゲームはそのリアルな物理学と素晴らしいグラフィックスであなたの心を爆発させます。これまでプレイしたことのないようなものです。 GT Nitroは、リフレックスとタイミングを試すカーレースゲームです。正しい瞬間にギアをシフトし、ガスを思い切り踏む必要があります。また、大物たちと競いつつ、車のチューニングとアップグレードも行わなければなりません。世界中で最高のドライバーと車とカーレースに挑むことになり、ドラッグレースの王冠
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
SubversionのDiffをC++に移植
何ですかこれは？ 二つのシーケンスのLongest Common Subsequence, Longest Common Subsequence Distance及びShortest Edit Scriptを求めるクラス。 Subversionのコードを、C++に移植したものです。 アルゴリズムは、"An O(NP) Sequence Comparison Algorithm" (Sun Wu et al.)に述べられているものと同一で、計算量は最悪でO(NP)、平均的にはO(N+PD)です。ただし、N=二つのシーケンスの長さの和、P=D/2-Δ/2、D=LCS距離、Δ=二つのシーケンスの長さの差です。 ここでいうLCS距離(longest common subsequence distance)は、あるシーケンスを別のシーケンスに変化させるために必要な、シンボルの挿入及び削除操作の最小
お手軽パーザー
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://kikairoya.hatenablog.com/entry/20100718/1279465696