C++相談室 part162

■ このスレッドは過去ログ倉庫に格納されています
1sage (ﾜｯﾁｮｲ fbf0-ofdD)
垢版 |
2022/10/31(月) 14:29:35.57ID:J5sgTSch0
!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512
↑同じ内容を3行貼り付けること

次スレは>>980が立てること
無理なら細かく安価指定

※前スレ
C++相談室 part161
https://mevius.5ch.net/test/read.cgi/tech/1653135809/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
2022/11/30(水) 02:43:16.08ID:ZNMRPtWe0
>>379
これまでの話に「関係ない」質問をいきなりされてもねw
2022/11/30(水) 07:26:27.66ID:/Q74hFM3d
>>381
int a=1,b=1;
このとき&a!=&bで
おまえさんの言うハッシュは不一致だが
a!=bを証明しない
2022/11/30(水) 08:02:03.99ID:GLbLL33e0
ただの配列はアレイだろｗ
385デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-FutQ)
垢版 |
2022/11/30(水) 08:19:43.48ID:SGXzBjU4a
配列がハッシュだってのは、a[0]とa[1]は0とか1っていうアドレスにあるわけじゃなくてaとかa+(型サイズ)のアドレスにいるってことでしょ
2022/11/30(水) 08:48:42.04ID:HrCmlG76d
意味わかめ
2022/11/30(水) 09:16:36.00ID:b9q4n/fOa
つまりstd::vectorはハッシュだった？
2022/11/30(水) 10:27:12.52ID:7ZJsRDega
そんな重要な問題か？これ
2022/11/30(水) 10:30:58.80ID:3Q6Tcmrep
ハッシュが切り刻んでるって意味なら配列の部分だけみたらそりゃあ切り刻んでる罠
2022/11/30(水) 10:39:14.60ID:PugumI+Zd
配列がハッシュだなどとぬかす
糖質っぽいのがいて
後進に有害なので排除中なんだよ
2022/11/30(水) 10:58:53.94ID:3Q6Tcmrep
まあ、別言語の用語を不用意に持ち出すのが良くないんだけどな
392デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-zuBb)
垢版 |
2022/11/30(水) 11:15:38.95ID:D6E9fHT2a
HAGEYO
2022/11/30(水) 11:17:02.00ID:D6E9fHT2a
>>363
コピーってゼロックスですか？って本があったな
2022/11/30(水) 13:33:30.83ID:M9o3gjq4d
>>391
不用意にというより
あいつはPerlスレでうだつが上がらず
こんなところへマウント取りに来た
ヘタレの中のヘタレだろw
395デフォルトの名無しさん (ﾜｯﾁｮｲ 9701-zuBb)
垢版 |
2022/11/30(水) 18:59:26.64ID:YZNvxpbg0
PerlでC++にマウントですと！？
2022/11/30(水) 19:13:15.73ID:ZrFvGDs4d
あたおかの論理を分かろうとしても無駄だ
何でC++スレがタゲられたのか俺もわからん
2022/11/30(水) 22:13:23.44ID:ZNMRPtWe0
>>391
ただそれだけのことなのになw
2022/11/30(水) 22:24:11.50ID:lYG/Gr5c0
そこに逃げるしかねえもんな
2022/12/01(木) 05:58:18.98ID:jAeBwf3w0
そりゃPerlでの連想配列の呼び方の話に
> で、配列はハッシュなのか？ y/[N]
なんて言ってもない事で絡まれたら逃げるわなw
2022/12/01(木) 06:39:11.77ID:GVUgh1ntd
スレチの話題を持ち込んで散々引張っといて
このヌケサクはなに言ってんだ
2022/12/01(木) 06:52:39.37ID:jAeBwf3w0
そう言うのは糖質でとんちんかんな
> で、配列はハッシュなのか？ y/[N]
みたいなこと言うやつに言ってくれよw
2022/12/01(木) 07:10:43.57ID:K5eb9zSvd
嫌われ者
2022/12/01(木) 08:04:02.01ID:jAeBwf3w0
そういうこと言い出すのは反論できない白旗にしか見えないよw
2022/12/01(木) 09:53:27.47ID:KyNjFts3d
配列がハッシュかどうか答えに窮してんのおまえじゃんw
はい／いいえのどちらでもバカにされんの確定してて
2022/12/01(木) 09:55:51.97ID:KyNjFts3d
自分の身の丈より高い評価を貰おうと思うな
バカにされるようなこと言ったんだから
まず当たり前の結果を受け入れろ
2022/12/01(木) 10:15:41.20ID:jAeBwf3w0
>>404
> 配列がハッシュかどうか答えに窮してんのおまえじゃんw
配列がハッシュなんて言ってる奴はお前しかいないが？w
2022/12/01(木) 11:33:26.84ID:K0S28fMrM
ハッシュというのは、ある種のデータ構造の一種に名付けられた名前で、
検索を速くするためにハッシュ値を使う方式。
unsigned int hash = CalcHash(key);
でハッシュ値を計算し、
Node *p_hash_table[hash];
でデータのリストに即座にたどり着くような方式。
普通に線形検索する場合と比べて検索が劇的に速くなる。
なので連想配列が必ずハッシュ方式であるとは限らない。
また、配列はコンピュータ科学ではメモリー上でデータを連続的に隣接して配置する
単純なデータ構造に名付けられたものであって、ハッシュ構造(方式)とは区別されている。
2022/12/01(木) 11:39:01.75ID:K0S28fMrM
>>407
訂正:
誤: Node *p_hash_table[hash];
正:
constexpr unsigned int HASH_MAX = 4096;
Node *p_hash_table[HASH_MAX];
・・・
// 典型的なハッシュ方式による検索関数 :
Node *SearchData(string &key) {
　unsigned int hash = CalcHash(key);　// とても高速にkeyに対するハッシュ値を計算。
　Node *pNode = p_hash_table[hash];　// 同じhash値に属する全てのNodeのリンクリスト
　while (1) {
　　if (pNode->key == key) {
　　　return pNode;
　　}
　　pNode = pNode->pNext;
　}
}

テキトーに書いたのでまだ書き間違いが残っているかも知れないが、大体こんな感じ。
2022/12/01(木) 11:42:25.52ID:K0S28fMrM
>>408
[補足]
連想配列に良く使われる方式には、大きく分けて二つ有る:
1. ハッシュ構造　>>408 参照。
2. バランス木(赤黒木、B木(2,3,4木など)、AVL木)

C++では、
1は、map、set、multimap、multiset
2は、unorderd_map、unorderd_set、unorderd_multimap、unorderd_multiset
2022/12/01(木) 11:58:47.42ID:z3JhSYjVd
>>406
俺は言ってない
おまえに聞いてるんだよ
答えらんねーの面白がっておちょくってんのw
もがくほどＳっ気を刺激するだけだぜ
2022/12/01(木) 12:01:17.00ID:DPfpWvvy0
>>409
逆じゃね？
map、set～が2で、unorderd～が1じゃないの？
2022/12/01(木) 12:15:49.58ID:cs2lswThM
>>411
Yes。
最後は逆だった。つまり正しくは:
1は、unorderd_map、unorderd_set、unorderd_multimap、unorderd_multiset
2は、map、set、multimap、multiset
2022/12/01(木) 13:40:04.60ID:jAeBwf3w0
>>410
言ってないの？
では何のためにいきなりそんなとんちんかんな質問したんだ？w
で、俺はNoと答えるがそれでどうなるんだ？
2022/12/01(木) 13:41:01.80ID:mifNHULm0
>>407
>ハッシュというのは、ある種のデータ構造の一種に名付けられた名前
みなここの部分に賛同できなくて議論になってたんでないの？
あとハッシュ構造ってあなたの造語？
2022/12/01(木) 14:11:29.45ID:cs2lswThM
>>414
MD5などのハッシュとハッシュ法の役割や目的が結構違いまっせ。
前者はデータが改竄されてないかをチェックするために用い、
後者は検索・探索の高速化のために用いる。
恐らく、もとは後者から用いられ始めたのだと思う。知らないけど。
2022/12/01(木) 14:14:27.23ID:AUjqBN3gp
目的が違えどハッシュ関数的には同じ事だよな
417デフォルトの名無しさん (ﾜｯﾁｮｲ 5701-L9hK)
垢版 |
2022/12/01(木) 15:09:39.09ID:9MCw0pWF0
>>227が最初だからおまいらもう1週間もやってるんだなw
スレの途中を読む気もしないので論点も把握してないのだが
C++にはstd::hashがあるので用語は厳密に使う必要があるとは思う
2022/12/01(木) 15:12:17.53ID:vIp4VJD/d
>>413=247
さっさと謝ればこんなに恥かかずに済んだのになw
2022/12/01(木) 15:13:34.54ID:vIp4VJD/d
227もおまえだろ
2022/12/01(木) 15:27:34.21ID:jAeBwf3w0
>>418-419
>>227は俺じゃねーしそもそも>>231で当人謝ってるのに今更そんなもんだしてきて恥ずかしくないのか？w
で、連想配列の話はもういいんだな
なら話はもう終わりだろ
2022/12/01(木) 16:24:34.04ID:aZoVsAyUd
そう来ると思ったよ
わかりやすい奴だなw

はいはい、別人なんでちゅねー
2022/12/01(木) 16:53:17.94ID:jAeBwf3w0
>>421
あれれ？
> はい／いいえのどちらでもバカにされんの確定してて
はどうしたんだ？
Noだから はい／いいえ のどちらでも無いってオチかなw
2022/12/01(木) 17:54:20.55ID:lhJJhxvyd
何がハッシュおじをここまで駆り立てるのか。
2022/12/01(木) 18:24:44.11ID:DTbt9ryPd
>>422
バカにして欲しいんなら別人のふりやめろよ
そんな誠実さは持ち合わせてないから
とぼけてるんだろうがな
予想どおりのクズで却って安心してるぜ
2022/12/01(木) 18:51:12.68ID:paGUeF47p
もうハッシュの話はお腹いっぱいだから打ち止めようぜ
2022/12/01(木) 18:59:15.32ID:LzodZf+Q0
はい次
2022/12/01(木) 19:04:03.61ID:jAeBwf3w0
>>424
あらら、話誤魔化すのに必死やねw
もう他人のフリって言い張るしかなくなってて草
428デフォルトの名無しさん (ﾜｯﾁｮｲ 9701-zuBb)
垢版 |
2022/12/01(木) 19:12:45.42ID:mPKw+fm50
ハッシュのおかげで今週は皆楽しかっただろ。
ちゃんとお礼言っとけよ。
2022/12/01(木) 19:46:37.26ID:/Yq43jiI0
ハッシュも知らんのか
近頃の若造は
2022/12/01(木) 20:11:16.69ID:V7pPuh7Ha
ハッシュ！ハッシュ！ドラッケン！
431デフォルトの名無しさん (ﾜｯﾁｮｲ 9701-zuBb)
垢版 |
2022/12/01(木) 22:28:42.84ID:mPKw+fm50
ハッシュは配列のことだろ？
2022/12/01(木) 23:01:45.25ID:zH8jCNhA0
ハッシュドビーフのことだろ
2022/12/02(金) 00:20:40.99ID:h6/3aIZ1M
>>416
英語の辞書でhashを引くと、「細切れ」「細かく切る」と出てくる。
これは、検索を高速化するためのHash法のHashテーブルが細かく切って
データを格納していることと対応しているようだ。
つまり、Hashという言葉の由来はこのHash法から来ていると推定できて、
Hash関数や、Hash値という言葉もHash法由来のはず。
だから、MD5などのHash値は、Hash法よりも後発のはず。
つまり、Hashというのは、もともと「Hashデータ構造」に対応していて、
MD5などの値を「Hash値」と呼ぶのは「あとづけ」と考えられる。
2022/12/02(金) 00:33:19.34ID:h6/3aIZ1M
>>433
[補足]
何が言いたいかというと、もともとHashという言葉は、Hash法由来で、
Hash値という言葉も、Hash法から来ていて、
Hash値やHash関数が先でHash法が後、ということ「ではない」。
Hash法を実現したいために、Hash値を求める方法が工夫された。
Hash法 ---> Hash 値 (by Hash関数)
が正しい起源。
もう一度言う、Hash値を使っているからHash法なのではない。
Hash法を実現するために作る値がHash値。
2022/12/02(金) 00:34:37.55ID:eNwFIhhK0
>>433
別に
2022/12/02(金) 00:35:31.14ID:eNwFIhhK0
>>434
いや全く？
全然？
2022/12/02(金) 00:45:49.71ID:eNwFIhhK0
>検索を高速化するためのHash法
しかしねえハッシュは本来は実用的なメモリ使用量でメモリに乗りきらないサイズの集合の要素を取り扱うためのしくみなのだから、
入力集合の全単射写像ならハッシュにする意味が無いのだから、
検索を高速化する用途の方が後付けなのだから、
2022/12/02(金) 00:48:00.35ID:eNwFIhhK0
ｳｨｷの冒頭にあるようにハッシュというのは検索というよりは区別のためのしくみなのだから、
MDとかSHA-1とかの方こそが本来の意味でのハッシュなのだから、
2022/12/02(金) 00:50:17.77ID:eNwFIhhK0
キャッシュメモリもキャッシュメモリに収まりきらないデータをキャッシュメモリに収めるためにハッシュなのだから、
2022/12/02(金) 00:50:49.40ID:VfaFcsHC0
Perl のハッシュは、もともとは連想配列 (associative array) という名前で呼ばれていましたが、
この名前は長すぎるので、1995 年頃に、Perl コミュニティの中でハッシュ (hash) と呼ぼうということになりました。
Perl5 の時代からはハッシュと呼ぶことになっています。
ハッシュという名前は、連想配列の「実装」に使われるハッシュテーブル (hash table) に由来しています
以上、あくまでもPerl コミュニティの話で、他のコミュニティで流用したら、こんな風にひと悶着起こすわけです
2022/12/02(金) 00:51:31.02ID:eNwFIhhK0
いやしつれいキャッシュメモリのハッシュ利用は検索のためやなｻｰｾﾝ；；；
2022/12/02(金) 01:06:10.28ID:eNwFIhhK0
どういうことかというとxの検索ではxそのものが取り出されねばならないからxのハッシュはxの検索を利用するユーザーからは見えないから脇役
（別段ハッシュを使わない検索手段で実装してもユーザーにはそれはわからない

一方MD5とかSHA-1とからは長いデータが実用的に無視できる確率でしか衝突しない短いハッシュになるというのがウリなので
MD5とかSHA-1を利用するユーザーはMD5とかSHA-1とかのハッシュそのものを目の当たりにするという違いがある、

というしくみ、
2022/12/02(金) 01:47:39.50ID:h6/3aIZ1M
>>437
>検索を高速化する用途の方が後付けなのだから、
Hashが「細かく切る」という意味なのだから、その説は何かおかしい。
細かく切ることによって検索を高速化したものがHash法なのであって。
2022/12/02(金) 02:01:39.85ID:cil6LVtpa
ハッシュ関数の操作にハッシュ感があるんじゃ？
2022/12/02(金) 02:17:32.59ID:h6/3aIZ1M
>>444
Wikipedia英語版のHash tableの項目を見てみると、
The idea of hashing arose independently in different places.
In January 1953, Hans Peter Luhn wrote an internal IBM memorandum
that used hashing with chaining. Open addressing was later proposed
by A. D. Linh building on Luhn's paper.[7]: 15 

となっていて、「hashing」がhash tableの概念をそのまま対応していると
考えられる。hashingのアイデアそのものがhash tableのために生み出されたようだ。
446デフォルトの名無しさん (ﾜｯﾁｮｲ 9701-zuBb)
垢版 |
2022/12/02(金) 07:20:08.20ID:DFt0sUTo0
要約すると、ハッシュ法とは配列のことで良いだろ？
2022/12/02(金) 07:32:42.95ID:7ZxLA8W50
インデックスじゃなくてキー式の配列な
2022/12/02(金) 09:21:43.88ID:7d7w3eSQa
>>445
なるほど
勉強になるね
2022/12/02(金) 10:47:13.00ID:pILexyP1p
とある辞書のインデックス
2022/12/02(金) 12:51:51.38ID:PuSvdAs7M
>>446
JSでは、
a[key] = val
でハッシュ法を使ったデータに書き込めるから形式的に配列と同じになっているが、
「アルゴリズムとデータ構造」では、ハッシュ法は配列とは完全に区別されている。
2022/12/02(金) 12:56:29.48ID:5fL6YCldd
C++スレだから用語の定義もC++が前提
2022/12/02(金) 16:13:02.65ID:ahpGcODy0
ハッシュはキー長固定が前提だけど、配列は(概念的には)固定長前提では無いので、この２つを同一視するのは無理がある。

そもそも配列にキー衝突の概念無いだろ。
配列の場合、キーが異なれば衝突しない。
2022/12/02(金) 16:14:30.69ID:ahpGcODy0
>>452
自己フォロー。固定長は用語がおかしいね。
キーの要約くらいの話か。
2022/12/02(金) 17:48:37.71ID:u75NJDvrd
>>427
いじめて欲しければと言ったろ
別人のふりをするのは構わんが

いいか？ 配列はハッシュじゃねえぞ
わかったな？
2022/12/02(金) 18:11:06.69ID:tKD1RDkG0
まあせいぜい逃げ回ってりゃいいんじゃね？w
2022/12/02(金) 18:16:29.52ID:V13bE4eep
まだやってんw
2022/12/02(金) 18:24:41.37ID:tKD1RDkG0
>>456
なぜか
> いいか？ 配列はハッシュじゃねえぞ
と言う>>227以外の誰でも知ってることを必死に布教してるらしいw
2022/12/02(金) 18:29:46.96ID:l1cskCXdM
>>452
数学的概念としては、独自に同一視して理論を展開することも可能だが、
そもそも、配列のa[idx]はマシン語の1命令でアクセスできて、1クロックなのに
対して、ハッシュの x[key]は、150クロック〜数千クロック程度かかる。
(少なくとも後者はCPUで1命令(1クロック)では処理できない。)
2022/12/02(金) 18:31:22.54ID:V13bE4eep
>>458
配列の型によるだろ、嘘教えるなよw
2022/12/02(金) 18:45:28.13ID:tKD1RDkG0
そもそもメモリーアクセスが1クロックでできるかどうかは状況によるしハッシュの計算に150クロック以上とかどこから出てきたんだ？
2022/12/02(金) 18:47:05.45ID:l1cskCXdM
>>459
配列の場合、要素のサイズが任意バイトの場合は、一般には明示的な掛け算が必要だから
1クロックではなかった。
スマソ
462デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-tFPE)
垢版 |
2022/12/02(金) 20:50:07.24ID:mpDpMcgja
シッタカが自爆するスレ
2022/12/02(金) 21:13:31.85ID:7ZxLA8W50
ハッシュはキーがぶつかった時にネストして候補を洗ってく時間がかかるから一意に150クロックってワケでもない
464デフォルトの名無しさん (ﾜｯﾁｮｲ d75f-JadS)
垢版 |
2022/12/02(金) 21:26:41.80ID:OAAJQcGw0
Pythonで経過時刻を測る場合、以下のような方法を使いますが
C++でPythonと同じ計測手法を使うにはどうしたら良いですか？

import time
startTime = time.time()
nowTime = time.time() - startTime
print(nowTime)
2022/12/02(金) 21:29:14.69ID:jlYcEgfQp
OSに依るからなぁ
2022/12/02(金) 21:30:36.64ID:RyVNohK20
なんか面倒くさい<chrono>でがんばる
467デフォルトの名無しさん (ﾜｯﾁｮｲ d75f-JadS)
垢版 |
2022/12/02(金) 21:33:56.38ID:OAAJQcGw0
>>465
Windows限定で使用する予定です。
2022/12/02(金) 21:36:34.16ID:m95xgUV8M
boost::timer::cpu_timerとか？
2022/12/02(金) 21:41:06.49ID:110d0P8E0
>>467
C++ 関係ないけどパフォーマンスカウンターでggrと良いんでは？
2022/12/02(金) 21:45:16.03ID:FW7hEQSS0
std::time とか?
2022/12/02(金) 21:48:04.00ID:0Xa+fucj0
>>460
全然関係ないんだが
鼻で笑えないのか？
2022/12/02(金) 22:24:02.82ID:eNwFIhhK0
OpenMPの一部であるomp_get_wtime()がじつはパフォーマンスカウンタと同じ精度……

ポータブル……
2022/12/03(土) 00:29:43.64ID:dPKr1JJoM
>>460
keyが10文字の文字列の場合だと大体そんなくらい行くであろうと予想したが、
もうちょっと速い場合もあるかも知れない。
2022/12/03(土) 01:21:25.79ID:dPKr1JJoM
>>463
要は、JSなどで配列とHash法が同じ書き方が出来るが故に、Hash法が
「配列」みたいには高速ではないということを知らない人が居るのではないかと
思って書いただけ。
x86系の場合、配列は、要素サイズが1,2,4,8の時はa[i]がマシン語の1命令で
1クロック、それ以外の一般サイズだと2命令で、今のCPUだと、
4クロック〜20クロック程度。
ハッシュ法だと、keyが10文字の文字列の場合で、最低でも、まあ、100クロック位
はかかると見ておいたほうがいい。最高だと上限は無いが、まあ、数千〜数万
クロック程度になると考えた方がいい。
これは、マシン語まで見たときの常識的な間隔。
2022/12/03(土) 02:42:14.20ID:ngGiofKr0
マシン語の1命令で1クロックって、いつの何のCPUだ
2022/12/03(土) 08:52:01.00ID:+FzzA9JIM
0 以上 64 以下の整数 n に対して 2^n-1 （ビットごとの排他的 OR 演算子ではなく累乗の意味 2**n-1 です）を std::uint64_t 型で返す関数って場合分け無しでスッキリ書けませんかね？
2022/12/03(土) 09:18:16.49ID:riW5om/o0
>>476
こうかな？
std::uint64_t(-1) >> (64-n)
2022/12/03(土) 09:23:14.36ID:qMCuKdke0
std::uint64_tの加算オーバーフロー時の挙動がunsigned intと同様にwrap aroundなんなら普通に
std::uint64_t foo(const int n) { return ((std::int64_t)1 << n) - (std::int64_t)1; }
で良くねconstexpr的な何かとかでマズい？
2022/12/03(土) 09:26:37.99ID:riW5om/o0
すまぬ。 >>477 だと n が 0 のときは未定義なのでそれだけ場合分けが必要になってしまうな。
だからといって (std::uint64_t(1) << n) - 1 だと 64 のときが駄目だし、
場合分け無しという条件だと思ったよりめんどいかも？
2022/12/03(土) 09:43:52.56ID:qMCuKdke0
違った加算オーバーフローの話やなかったorz

シフト演算については
If E1 has an unsigned
type, the value of the result is E1 × 2E2, reduced modulo one more than the maximum value representable
in the result type.
E1 が符号なし型を持つ場合、結果の値は、E1 * 2E2 の、結果の型で表現可能な最大値より 1 大きい値を法とする剰余となる
なので言語規格上は (uint64_t)1 << 64は合法なはず……
2022/12/03(土) 09:49:24.58ID:qMCuKdke0
訂正orz
誤： 2E2
正： 2**E2 （2のE2乗）

符号付きの型はオーバーフローで例外を発生するアーキテクチャーがあるから
表現できるビット数からあふれるコーディングは未定義動作か何かやが
符号無し型はモジュロ演算になるから溢れてもおk
と言う印象（記憶モード
※ 個人の感想です
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況