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 コンテナ禁止なのか、<algorithm>まで禁止なのかにもよるな
前者だけなら自前コンテナでもメンバー関数揃えておけばソートや探索は後者使えるし
ただ<algorithm>の中で本当にヒープ使ってないのかというのは バカに合わせないとお前が一生メンテする羽目になるぞ >>231
その昔、バカでも読める言語ってのが一世を風靡したね
そのお陰で、バカ人口が増えて生産性に比例しない人件費がうなぎ登りして
たーまやーとばかりに弾けた
ピンサロで嬢が知り合いだったときはマジびびった >>227
>ここには「stringのようなその他のC++標準ライブラリの機能にも影響を与え」
>とあり、 string 自体は STL ではないかのようにも読める。
stringというかSTLって「標準」のくせに亜種がいっぱいあった希ガス 科研費余ってるんだが、C++ とかプログラミング関係の書籍で必読だったり面白いもの教えてくれませんか
Effective C++、ストラウストラップ、リーダブルコードくらいは持ってます
個人的には C++ Coding Standards 欲しかったが新品じゃ売ってないな そら当然、STL策定直後は当時のコンパイラにはSTLは付いてきてなかったわけで
結構な数のサードパーティが追加ライブラリとして売ってたから C++ 標準化委員の本
C++テンプレートテクニック 第2版、
επιστημη(えぴすてーめー)・高橋 晶、2014
C++11/14 コア言語、江添 亮、2015 >>238
付いて来た某MS標準のSTLが酷い代物でな >>241
上と下は結構マニアックな感じしますね
真ん中は良さそうです
>>239
今回買わなくてもいずれ読みたいです
これにしても C++ coding standards にしても、需要ないんですかね >>231
こういうこと言う奴に限って３ヶ月後には自分でも読めないクソコード書きやがるからな。。 >>224
趣味でやってる奴でも結構深いところまで使いこなしてる奴いるし
逆にプロは最新の機能とかをあえて使わなかったりするから一概にはなんとも言えん >>237
ワイも D&E を推すやで。
C++ はツールやドキュメントの発展と足並みを揃えることで上手く発展してきたという話が書かれていて、
現実的な事情を踏まえた歴史の流れがわかる。
ただ綺麗にデザインした言語とは違う現実の重みを感じる。
(まあそれが負債になってもいるんだけど。)
単純に読み物としても面白いよ。 >>212
＞神は全盛時までのCだろ
ライブラリは今でもずっと悲惨なままだと思いますです…… >>224
もちろん色々と使いこなせればそれが強みにもなるんだけど、
使ったことない言語やフレームワークを使ったプロジェクトにアサインされるなんてよくあることみたいだし、
そういうときに (使いこなせるとはとうてい言えなくても) 動くものをでっちあげる能力ってのも
それはそれで重宝されたりっていう話も聞くし、
どういう強みでやっていくかっていうのは千差万別なんじゃないかと思う。 C++17は和本だと江副氏の一択なんだけどあれは
そうなった背景とか使い道にはそんなに触れられてないのがな
逆引き辞典とか流し読みして大まかな把握するには便利だけど >>249
プロ棋士の居飛車党が振り飛車指したからといってアマに負けたら恥だと思うが
「振り飛車指せないって言っても、居飛車よりはって意味や。君ら如き一間飛車でも勝てるで？」的な
「F# 書けないって言っても、メインで業務に使ってるC++よりはって意味や。君らよりは書けるで？」的な
（F# の部分にはマイナー言語が入るものとする）
プロ名乗るなら。 普段使わない言語なんて普通に読めて普通に書けりゃ十分だろ… ドラクエ10の下請けプログラマーが精鋭揃いだということはわかりますが、こういう苦情が後をたちません！
534 名無しさん＠ｺﾞｰｺﾞｰｺﾞｰｺﾞｰ！ (ﾜｯﾁｮｲ 4910-binO [180.51.97.166 [上級国民]]) sage 2018/10/15(月) 09:26:17.41 ID:5tgKKwqc0
https://hiroba.dqx.jp/sc/forum/prethread/408523/
移動速度が遅すぎてプレイする気になれない……
ぎのぎ
[GM468-320]
テーマ：操作性・メニュー 2018/10/15 09:17
こんにちは。ドラクエ10を始めて、着飾りもストーリーもたくさん楽しませていただいています。
ストーリーは進むたびにたくさん泣けて、ゲーム内容には大満足です。
しかし、移動速度があまりにも遅すぎて、ストレスが溜まってしまい、最近はゲーム自体から足が遠退いてしまっています。
ドルボードではまだ耐えられます。
ストレスになるのは、特に町のなかです。
以前の投稿で、早くなる料理はできない、とお答えしていらっしゃいましたが、移動速度が上がる装備はありますよね。
そちらの方がよっぽどあるのとないのと変わりそうですし、やりこみ具合で差が開く部分に思います。
時間設定のあるダンジョンなどもあるそうで、考慮するのは確かに大変そうです。
なんなら、素のスピードが変わらなくても構いません。町中だけでもダッシュ機能のようなものをつけていただけませんか？
ただ方向キーを押すだけの時間が、本当に苦痛なんです。
ストレスになるなら止めちゃいなｗ誰も止めないよｗ >>255
プロは言語の機能を使えるかどうかでなんて勝負しない
書いたコードの性能、わかりやすさ、バグの少なさとかで勝負する >>258
せやな
使うべきときにスマートに使う
これがプロだわな RPGってあれだろ、IBMの作ったCOBOLもどきだろ、確かに時間の無駄だし戦車には効かんだろ OpenCVのtemplatematchingについてなのですが、
しきい値を決めて類似度がしきい値以上の物を全探索で複数探すものはあったのですが、
類似度の上位2つのみを探す方法って無いですかね？
全探索は遅いので上位複数個だけ取れたらいいなと 閾値を適用するコードを探してチャチャっと改造すればいいんじゃね？
つか、最大値を求めるアルゴリズムも知らないのにOpenCVやってんの？ 高速に判定できる軽量版データ(部分画像、低解像度、モノクロなど)がありうるなら
それで箸にも棒にもかからないものを高速にふるい落としてから
残ったものだけをちゃんと調べればいいよ >>266は、閾値以上の値を全部取ってくる関数の代わりとして
上位n個(nは定数)を取ってくる関数はないか、ってことだろ？
> 全探索は遅いので
と書いちゃうから誤読されてそう。上位n個の場合でも全部見る必要はあるんだから このゲームすぐ持ち物いっぱいになるな
http://egg.5ch.net/test/read.cgi/dqo/1539336435/
使い道のないアイテム（無駄なコード）が多すぎやしないか？ >>271
だよね。
全部閾値以下って可能性考慮しても、並べ替えて上位から閾値以上か確認しながら取り出した方が早いべ。 >>274
んじゃどうすんの？
最大値を見つけた後に、最大値省いたリストなり配列から次の最大値(2番目に大きい数)探すにしたって、最大値を省くために最大値が有った場所を覚えておいて、そこを削除するなりしないと駄目でしょ？
面倒くさいし、速いと思えないんだけど。 。。。。。え“
5番目の大きさまでさがすとなら、5個もelse if書けと？
任意の個数なら、毎回書き直しか？
アホかと。 バブルソートを知っていれば、任意個数でもいける。しかし、抽出個数を任意にすると、まあちょびっと遅くなる。 >>275
元の質問が2個取り出すだけだからそれを前提にしてたすまん
n個を取り出すならソートしないとだめだな テンプレートの再帰を知ってれば遅くならずに任意個数いける。 元データをソートしなくても、結果用にn個のソート済み配列(flat_setとして提案されてるやつ)を用意して
そこに追加していきゃいいのでは。既に閾値以上のがn個集まってたら以降は最小のと比較して交換 >>281
n個のソート済み配列って、ソート済み配列を何個も用意してどうする。。。と言う言いたいこと分かるけど、書き間違いでおかしな事言ってるっぽくなってるっていうツッコミは置いといて。。。
閾値が在るんだから、先に閾値以上の物だけ別の配列に入れてソートすれば良いってのは確かに任意個数で一番速そう。 交換が発生する度にn個中の最小を検索する必要がある
閾値以上のを1回ソートとあまり変わらないような・・・データ次第か
全ソートして上から閾値見ながら、で充分じゃね？
選択部を工夫してもたいして効果なさそう >>283
ソート「済み」配列なので最小は必ず端にあるから検索の必要はないよ
代わりに追加の度に二分探索をする
それをイメージしてもらうためにflat_mapって書いたんだが未策定のものは伝わらないな、うん
>>282
すまん、要素数n個のソート済み配列を1個、で すみませんありがとうございます
ここに出てたの試してみます >>283
正直、追加の話見るまで最小と交換って私も「？」になった。
要するに1回目はソート済み配列が無いので >>282 をする。
要素を追加する度に、閾値以上かを見て、閾値以上ならソート済み配列で小さい順から二分探索して順番になる位置に挿入。
全要素1000で閾値以上が100とかなら、ソートするのが100だけだから、かなり高速化する。
追加もソート済みに入れるだけなので、遅くは無いし、次に取り出す事考えると(追加と同時にソート済みにしておく)、ソート済みから取り出すだけになるので全体として速くなる。
と言う考えであってる。。。と思う。 >>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ではじかれる
わかった？
低学歴知恵遅れの書き込みはいつも浅はか ■ このスレッドは過去ログ倉庫に格納されています
