C++相談室 part139
■ このスレッドは過去ログ倉庫に格納されています
次スレを立てる時は本文の1行目に以下を追加して下さい。
!extend:on:vvvvv:1000:512
C++に関する質問やら話題やらはこちらへどうぞ。
ただし質問の前にはFAQに一通り目を通してください。
IDE (VC++など)などの使い方の質問はその開発環境のスレにお願いします。
前スレ
C++相談室 part137 (正しくはpart138)
http://mevius.5ch.net/test/read.cgi/tech/1535353320/
このスレもよろしくね。
【初心者歓迎】C/C++室 Ver.103【環境依存OK】
https://mevius.5ch.net/test/read.cgi/tech/1530384293/
■長いソースを貼るときはここへ。■
http://codepad.org/
https://ideone.com/
[C++ FAQ]
https://isocpp.org/wiki/faq/
http://www.bohyoh.com/CandCPP/FAQ/ (日本語)
----- テンプレ ここまで -----
VIPQ2_EXTDAT: default:vvvvv:1000:512:----: EXT was configured >>287
近くなったがまだちょっと違う
結果用の配列は要素数nしか確保しない。閾値以上が100個あってもn=2なら要素数2
で、元データを順に見ていって、3個目以降が見つかったら結果用の配列に入り切らないので
後から見つけたのが結果用の配列の中の最小よりも大きければ、最小のを捨てた上で二分探索した位置に挿入する
……というつもりだった
元データに後から追加があったら、みたいなことを考えて書いたわけではないです std::upper_bounds とかで挿入位置を決めて挿入、
n個を超えたら小さい方を1つ切り捨てるって感じだよね
たかだか数件ならループで位置を決めてもいい >>288
なるほど。
今全部分かった。
うーん。
それは任意の個数nと閾値以上の個数が近くないと、n個目以降が見つかる度に比較、探索、挿入を繰り返す事に。。。
データによりけりではあるけど、微妙。
>>282 は、イメージとしてはクイックソートの最初のピボットを閾値にして、閾値以下はソートしない様に変形させた感じ。
どっちがどうとかは、実測しないとなんとも言えなさそう。 >>291
そっちのが凄い。
任意のnーmまでの範囲だけクイックソートっぽくソートするのか。
最上位(m)からn位までのソートでおkじゃないか。 標準にstd::partial_sortってのがあってな ほとんど中身を知られていないalgorithmさん それは >>282,>>290,>>292 書いた私の事だろうか。
そんな呼び名がつくのは光栄だけど、高卒で基本アルゴリズムしか知らないんだ。
その割には悪く無い処理を考えられたと自画自賛してたんだけど、やっぱ頭のいい人の考えるアルゴリズムは凄いね。 partial_sortなんてあったのか……orz
でもquickselectは元データを並び替えてしまうから
それができないならこのスレに書かれた方法でもいいけどな(負け惜しみ)
負け惜しみついでに>>290の議論だが、mは元データの個数、nは欲しい個数として
>>282の閾値以上を抽出してから一括してソートは
最速のソートが使えるのでオーダーはO(m log m)、空間使用量は元データと同じ作業領域がいるのでmに比例
>>288(俺)のソート済み配列に追加していくのは
挿入ソートを小分けにしてるわけだからオーダーはO(m*n)、空間使用量はnに比例
nとmが近いかそもそものデータ量が小さければ>>282が、そうでなければ>>288有利かな
……で良いと思う >>297
大丈夫、私も同じく沈んだw
純粋に貴方と私のロジックでは、貴方の方が有利という試算なのね。
おk。了解した。 いやまああくまで最悪計算量なんで、結局実際のところは実測しないとだけどもね
オーダー上は挿入でnに比例するから二分探索に意味はない、と書きながら気付いたりもしてる(苦笑) >>294
地味に標準指定のアルゴリズムも改善されてて追いきれないよぉ そして誰からも忘れられているstd::nth_element ていうか4位同順が10万画素ぐらいあったらどうするんじゃスレ主、 ttps://www.magezinepublishing.com/equipment/images/equipment/H6D50c-6100/highres/Hasselblad_SHOT_01_F1_RGB_1460032379.jpg
一枚一億画素
jpg一枚で25MB
FFでは開けた 専ブラのプレビューでも相当時間掛かった
リンクを踏む気は無い できたので貼る
Insertion sortで上位5件の相関値と座標(x, y)を表示するやつ：
ttps://ideone.com/L0fXH2
これは、同着があっても上位5位に入れば全部出力する。
get_top_N_pixels()がご本尊の関数
get_top_N_pixels_exp()が比較用に作ったバージョンで、std::sortで全画素並べ替えて上位5件を出力する。
上位5位以内に同着があまりに多いとget_top_N_pixels_exp()の方のが早いが
適当に作ったランダムな値の条件でQVGAぐらいの画像サイズだったらget_top_N_pixels()の方が8倍ぐらい早いっぽ 訂正 s/同着/同順/g
で、同順がそれなりにある前提でパホーマンスをちゃんと計ったら8倍どころではなかったわ3000倍以上早かったわ；
条件は以下の通り
■ 画像サイズ:
W=320 - 10, H=240 - 10
(Number of pixels=71300)
■ データ
値域[-5000.0F, 5000.0F]の一様分布。データ重複無し。
■ Basic design の結果（get_top_N_pixels_exp(): 全画素std::sort()）
387 sec @ 反復回数ntimes=100, TOP_N=256 --> ntimesを10倍にすると3870 secの見込み
■ Practical designの結果（get_top_N_pixels(): TOP_N画素のInsertion sort
1 sec @ 反復回数ntimes=1000, TOP_N=256
14 sec @ 反復回数ntimes=10000, TOP_N=256
とゆーわけで、今回は一様分布かつデータ重複無しでこうだったので、TOP_N=256は一般条件における128と解釈するとして、
上位5位に入るデータの個数が128個以下なら>>305のpractical designで上記のパホーマンスが出る見込み ごめwwwwwデータ訂正および結論は480倍早かった、に訂正、
■ Practical designの結果（get_top_N_pixels(): TOP_N画素のInsertion sort
1 sec @ 反復回数ntimes=1000, TOP_N=256
8 sec @ 反復回数ntimes=10000, TOP_N=256 -- 3870 / 8 = 483.75
14 sec @ 反復回数ntimes=10000, TOP_N=65536 ごめｗｗｗｗｗｗ結論は3000倍以上早かった、で訂正の必要はなかったorz
Basic designの結果
387 sec @ 反復回数ntimes=100, TOP_N=256
に対して、Practical designの結果
8 sec @ 反復回数ntimes=10000, TOP_N=256
は、(387/100) / (8/10000) = 4837.5倍早い
今日日のCPUアーキテクチャーとinsertion sort様様じゃ STLってもはやスクリプト言語などと変わらない使用感でプログラム書けるな
最高過ぎる c標準ライブラリの関数ってstd名前空間にあるのに必ずしもstd::をつける必要ないよね
なぜか分かる人いない？ C言語との互換性のため。
using使っているから。 cstdio → stdで囲まれる
stdio.h → 囲まれない 横から納得w
古いC++(C互換重視)と新しいC++(新世界の王に俺はなるモード)の互換のためか。
ナル。 directory_recursive_iteratorで各ディレクトリを読み込むと読み込み順がおかしくなりますが、これvectorに突っ込んでソートしないと辞書順に戻せないのですか？ >>322
戻すっていうか、普通のファイルシステムでは辞書順に並ばないことの方が多いんじゃないの。 知らんけど。
言語仕様的には recursive_directory_iterator が辿る順序は未規定。 二次記憶装置のデータをいちいちソート済みに保とうとするとオーバーヘッドが無茶苦茶だからな
読み込み順がおかしくなるんじゃなく、いつもOSがソートして見せてくれてたのが元のまま出てきただけだ
DOSの時代はdirに/oスイッチが追加されたとき便利になったものだと思ったよ 毎日毎日ソートして表示してくれてる ls や dir.exe や exproler.exe には頭が上がりません 総統も相当ソートがお好きですなあ
ｶﾞﾊﾊﾊﾊﾊﾊ、 また低学歴知恵遅れたちは頭わるいこといってるわ。。。
ｄｉｒ．ｅｘｅ？
ｄｉｒはｃｍｄ．ｅｘｅの内部ｺﾏﾝﾄﾞだからな
ｄｉｒ．ｅｘｅなんかあるﾜｹがない
ｿｰﾄするのはｃｍｄ．ｅｘｅがｄｉｒｺﾏﾝﾄﾞを受けつけたときの機能で
OS自体の機能じゃないからな
ﾎﾝﾄな低学歴知恵遅れたちは基本的なことが分かってない >>330
最近飽きられてきたから(構ってもらえなくなったから)、芸風を変えてきたんだろ。触らないのがよろしいかと。 全角の部分を半角で書き込むと403ではじかれる
わかった？
低学歴知恵遅れの書き込みはいつも浅はか ｃｍｄ．ｅｘｅ を半角で書いたら、
コマンドが実行されて、サーバーをハッキングされるとか、
5ch・サーバーの運営は、頭おかしい
素人がシステム・サーバーの運営構築してる
漏れは、何十冊も本を読んでいるけど、
ｃｍｄ．ｅｘｅ を送ったら、ハッキングできるという記事を見たことがない dir .exe
dir
cmd. exe
OS
ﾎﾝﾏや！弾かれた！！ サニタイズの最先端・ユーザーに入力させない←いまここ
いや知らんけど多分、 5chのNGワードチェックには文字参照という抜け穴が空いてる。 間違えた cmd.exe か
>>339
実体参照は書き込めない短縮url貼ったりするときにも使えるよね 文字実体参照・数値文字参照なら、コマンドが実行されて、5ch サーバーをハッキングされる事もない
cmd.exe
dot, period は、ascii コード、46 (0x2E) 戻り値がオブジェクトの関数書きました。
すると上司が、変更があったとき不具合の原因になるからポインタで返せと。
これ本当でしょうか。stackoverflowとか覗いてるんですがオブジェクトで返すかスマポで返すかみたいな論調ばかりです。
少なくとも生ポインタ使えという意見は見当たりません。
（生）ポインタ使ったほうがいいケースというのは実際にあるんでしょうか。 >>346
malloc してるやつなら
FILE * とかな >>346
参照返しでもポインタ返しでもプログラムの堅牢性は大差ない気がする。
ちなみに俺は、NULLを返すケースがある関数はポインタ返し、
NULLを返すケースがない関数は参照返しにしてる。 c++ の標準のスマートポインタでは循環参照を持つもの、
例えば get_child() と get_parent() を持つような木構造やリスト構造は扱えない
で、大抵の場合これらは単に生ポインタで実装される。 >>346
C++ のミスりやすい箇所ってのはメモリ管理が多くを占めるので、
生ポインタは面倒くさいわってのが普通の感覚だと思うし、
不具合の原因になるってのはよくわからん言い分なので、
もっと掘り下げて聞かないとなんとも言えん。
共有オブジェクト (DLL) のインターフェイスにする場合なんかだと
ABI の都合とかでおかしなことになったりすることもあるかもしれんなぁ
みたいな可能性を想像することは出来るが、
書いてるプログラムや開発環境の性質に固有の事情はわからん。
一般的には、生ポインタにせざるを得ないことは有っても生ポインタの方が良いってことはあんまりなさそう。 ファクトリー関数は生ポインタ返すように作るのが良いと思う たしかにどこも指してない参照を返したいときは
NULLポ使えるポインタ返しにする
ダミーの空オブジェクト作れるように
C++が最初からルートオブジェクト基底してくれてればよかったのにと思うことはある struct Point{int x; int y;};
みたいな単純なPOD構造体をstructだからって教条的にいちいちnewとポインタで取り回してるプログラムは時々見かけるけど
そういうのは危ないし遅いしウザいからやめてほしい そんなの参照と値渡しでいいということには同意するが
point 型を new / delete してるコード見た経験はないな >>346の上司が言ってるのは、コピーコンストラクトや代入が正しく機能するということを
保証しなくちゃならなくなるから、ってことだろ
そこまで気にかけてる暇はないし、生ポで書くのが一般的な職場だというならそれに倣うしかない そういえば俺コピー不可のクラス書いてもちゃんと private だ何だで実際に代入できないようにしてないな… コピー不可で思い出したけど、コピーコンストラクタと代入演算子をprivateにしたクラスを
vectorにpush_back()する記述がコンパイルエラーになるよね。
vector<Hoge> hogeVec;
hogeVec.push_back(Hoge()); // コンパイルエラー
これってどうすればいいの？ >>358
std::vector の要素は CopyAssignable と CopyConstructible の要件を満たす必要がある。
実際、 std::vector は内部で要素をコピーしたり代入したりすることがあるんだから、
それが出来ない要素を入れられないのは当たり前の話で、
コンテナに入れるならポインタ (上記要件を満たすスマートポインタでもよい) を入れるようにするくらいしか方法はないと思う。 >>358
ムーブしてもいいならムーブコンストラクタと代入演算子を定義すれば行けないかな どうせ所有権意識して std::move を使うなら個々のクラスには
手を加えず unique_ptr かますのが楽じゃないかな >>362-363
ムーブ可能なだけでは必要な要件を満たしてない。
コピー可能であることが要求されている。 >>364
vectorの型Tの満たすべき要件は操作による
push_backとかresrveとかはコピーかムーブのどちらかが可能ならば問題ない リストのイテレータ使って周期的な処理をしたいんだが、そういう使い方合ってる？
N 要素のリストのイテレータ it = s.begin() を N 回インクリメントしたら、it はルート(？)を指すわけだが、そうじゃなくて s.begin() と同じところを指してほしい
こういう場合、どうしたら良いだろうか ｽｱﾎﾎﾟｲﾝﾀみたいな頭ﾜﾙｲの使うぐらなら
C++なんかつかわなければいいのに
低学歴知恵遅れは新しいもんができると
使わないといけないという使命感があるらしい
低学歴知恵遅れは自分で要否が判断できない そうだね痴呆おじいちゃんには7年前に標準化された最新機能は難しすぎるから仕方ないね
半角に限らず今でもウヨウヨいるからあんまり笑い事じゃないんだけど あんのが難しい？
知恵遅れは頭ﾜﾙｲｼﾛﾓﾉを使ってる自覚がないからな
低学歴知恵遅れはｱﾚで難しいもん使ってるつもりでいんのか
へー >>367
それ参考にして自力で実装してみます
ありがとうございます >>365
あ、ほんまや。 ワイの記憶は C++03 時代のやつやった。
ムーブないからしゃーなしでコピー必要やったんやな。 うろ覚えで>>364みたいなこと断言してたのかよ
自分の記憶を疑う癖つけた方がいいよマジで >>373
いや、このサイトを見て確認はしたんだよ。
https://ja.cppreference.com/w/cpp/container/vector
ただ、 「C++11 以前」という書き方になってたから、前後を見ずに C++11 は含むのだと思ったし、
(現在の最新ではないとはいえ) C++11 くらいには配慮すべきだろうなっていう前提で言ってたの。
でも、ちゃんと仕様を確認したら「C++11 以前」は C++11 を含まないことに気づいたって次第。 あー、確かにあれは紛らわしいかもね・・
でもすぐ近くに「C++11およびそれ以降」ってあるしな Cとhaskellはどちらがどれくらい速いですか？ STLのリストは要素を挿入するごとにメモリーの割り当てが起こるのか一度に割り当てられている場所に
なのかどちらですか？ 規格は要素ごとに割り当てるのを想定してるだろうけど
例えば10個分まとめて、みたいな実装もOKじゃないかな……
挿入削除やイテレータの++がO(1)みたいな各種要件さえ満たしてれば vectorならともかく、そんな実装するってメリットがあまり無い気が メモリのローカリティを維持できれば性能がよくなる可能性もあるんじゃね？ >>380
メモリのアロケーションは意外にコスト高いからまとめてアロケートしておいて
node を用意するときにそこから placement new とかして使ってゆくと高速になる
リストのノードに限らず、プロファイル取って new が時間
食ってるときにオブジェクトについてはこれで簡易に改善できる
最近はデフォルトのアロケータが高性能で意味がないこともあるけど 続き
解放も一気にしないと面倒なので基本追加一方で不要になったら全部消すみたいな場合に使う
巨大 xml の dom を作って、不要になったら全解放みたいなとき。 大きいデータだと何十万回、何百万回もnewしなくちゃいけないようなクラスは
１メガくらいまとめてnew [] したほうが絶対いい。
実行時間比較すればわかるけど、かなり高速になる。 １メガくらいという根拠の薄いマジックナンバーに依存する糞コード >>385
当然、実装するときは、まとめて確保するメモリ量は指定できるように作るのが当たり前。
いちいちそんなこと言わなくてもみんなわかると思って、例えば１メガという意図で「１メガくらい」
と書いたが、バカには伝わなかったみたいだな で、１メガという定量的な根拠は？ いくら罵倒しても自動的には出てこないぞ ■ このスレッドは過去ログ倉庫に格納されています
