C言語なら俺に聞け 153
■ このスレッドは過去ログ倉庫に格納されています
「オメーの気持ちなんてしったこっちゃねー
オレに分かるように話せ」
が今の潮流
分からないように反為さないヤツは無視していいし排除していい
なんつったってオレが理解出来ないヤツは何言ってるか分からないコミュニケーション不可能な敵に近いからな
気持ち悪いから排除してもいいし、何よりオレに理解されようと思ってない
だから排除していいでしょ
……という思考で動くのが現代の日本社会 いやクライアントの意向を無視して好き勝手やっていたら仕事干されるだろ 保存とは書かれているが圧縮とはどこにも書かれてない件 てか皆さん「フーリエ変換くらい当然知ってる」って雰囲気なのが凄いわ。 圧縮しないなら
保存でフーリエ変換使う意味がわからんがな フーリエ変換そのものは理系の大学卒であれば誰でも知ってる
具体的な数値計算のアルゴリズムを知っているかはその人の専門分野による 専門課程ではなくても一般教養の数学系の講義で学んでると思うけど 微積と線形代数ぐらいで触らんかったぞ
大学なんか講師次第だからなあ 文系だと無いと思うな
統計学や代数幾何、微積分
この辺まで はるか前なので忘れたが、大学ではフーリエ級数って名前だった希ガス 理系の大学卒だが
フーリエ変換を大学で習った記憶はないなあ
覚えてないだけかな？ フーリエ変換はフーリエ級数展開の一般化
フーリエ級数展開の基本周期を無限大まで拡大すると周波数成分は離散から連続となる
要するに周波数成分を連続スペクトルとして扱うのがフーリエ変換 数学科院卒だがフーリエ変換には掠りもしてない
工学部の一部しか触ってないだろう 工学部では厳密な理論よりも応用が重要なので表面的な触りだけで深入りはしない
厳密な議論はやはり数学者の分野だと思う 画像処理はOpenCVとかで済ましちゃうから細かい数式は気にしない それには同意
フーリエ変換の利用にはFFTの概要だけ理解していれば十分
ただ数学の専門家が掠りもしてないというのは如何なものかとは思う >>468
数学的にはとっくの昔に解決してるから
あとは工学系の仕事 >>470
応用数学とかそういう分野ならまだしも
純粋な数学者はそんなことには興味がない ラプラス変換やz変換あたりだと完全に工学分野だけどフーリエ変換くらい汎用なものは数学分野でも活用されてると思うけどね
フーリエ級数はローラン級数などと同じ複素解析の基本的な考え方でしょ
べきに展開するか指数に展開するかの違いくらいのもの 無理を言ってはいけない
数学者には楽器は作れても名曲を作る事はできない 名曲を作るのは数学者でも物理学者でも工学博士でもない
発明家や企業だ 沖縄音階は適当にランダムに音出しても曲に聞こえちゃうけどな >>479
それは沖縄音階に馴染みがないから、沖縄音階が使われているだけで沖縄っぽいと感じてるだけなんじゃないかな？
沖縄の人からしたら、そんなデタラメでは曲として成り立ってないと思わないのかな。 そういった抽象的な感覚を数値化して扱うための手段がフーリエ解析やスペクトル解析と呼ばれる分野
音楽の音階(周波数)やリズム(時系列)を分解して客観的に評価するのが科学的なアプローチ 確かにフーリエ解析では周波数成分の変化の時系列データを扱うのは難しい
少し浅はかだったなすまん
それにしても数学者が理論を確立して証明しそれをベースに開発が進むという典型例だな 200年くらいかかってるな
ベイズで100年ちょっとか >>480
さあ？まあ、実際にやってみな。自分でピアノやオルガンのキーを沖縄音階で適当に押すだけでわかる。 自分で弾いたら曲になるように弾いちゃうからランダムじゃない
本当にランダムで弾いたら曲にならない 質問失礼いたします。
以下のpopcountは引数xを2進数で表したときの1の数を返す関数なのですが、
動作原理がよく理解できないため考え方のヒントなどをいただけないでしょうか。
int popcount(unsigned long long x)
{
x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
return (int)(((x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f)) % 0xff);
}
以下のpopcount2は自分で作ったもので、これならうまくいくことは分かるのですが、
上のpopcountも本質的には同じことをやっていると考えていいものなのでしょうか。
int popcount2(unsigned long long x)
{
int n = 0;
for (int i = 0; i < 64; i++)
{
if ((x & 1ull << i) != 0ull)
{
n++;
}
}
return n;
}
どうぞよろしくお願いいたします。 https://ideone.com/8LfIh0
こんにちは。
ちょっと思いついたので、こういうコードを書いたのですが、
普段からreallocを使わないのでこのコードがあっているか解らないのです。
これで大丈夫ですか？ >>490
reallocが成功した場合古いポインタに対してfreeは呼ばなくていいと思いますよ。
reallocの戻り値は古いポインタと異なるものになる保証はないはずなので、
freeを呼んでしまうとせっかくreallocした領域まで解放されてしまうかも。 >>492
ちゃんとコードを読んだら↓の部分はケアされてましたね。失礼しました。
> reallocの戻り値は古いポインタと異なるものになる保証はないはずなので、
ただ、reallocが成功したらfreeは呼ばなくていいのは間違いないと思います。 >>489
超高速ビットカウント
でググって出てくるページでちゃんと解説してくれてる
この手のよく見るやつはちょっとググれば解説見つかる
何を本質と置くかによるけど両者はそもそもアルゴリズムが違うのでその観点からなら違う
どちらのコードも結果は同じでも前者のほうが圧倒的に処理速度が早い
ビット数などが必要になる処理では速度が重要になるケースも多々あるので結果が同じでも後者は使い物にならない場合もある >>496
レスありがとうございます。紹介していただいた記事を読ませていただき、大変勉強になりました。
ただ、>>489 の場合だと「ビットカウントするデータ列がある程度長い場合」には
当てはまらないため記事の前半の内容がアルゴリズムの基本になるとか思うのですが、
私が理解した範囲で記事の内容を参考にして関数を作成しても以下のようにしかできませんでした。
int popcount(unsigned long long x)
{
x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f);
x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff);
x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff);
return (int)((x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff));
}
しかし >>489 の関数はこれを途中で打ち切って % 0xff をくっつけたような形になっており、
やはり完全な理解には至っていない状況です。
もし可能であれば、この部分についてもヒントをいただけると大変嬉しく思います。
たびたび申し訳ありませんが、どうぞよろしくお願いいたします。 >>497
64ビット長のビットカウントの最大値はたかだか64なので8ビット(最大255)で表現できる
一方、64ビットデータの分割統治による畳み込み計算は1回目で2ビット×32組、2回目で4ビット×16組、3回目で8ビット×8組の結果が得られる
ビット数を求めるだけなら3回目の結果が得られた時点で8ビットの最大数(255)で3回目の畳み込み結果の剰余を求めてやればそれぞれの組の重み(ビット数)が計算できる
(64を超えることはないことが明らかなので) >>498
わかりやすいご説明どうもありがとうございます！ほぼ理解できたと思います。
たとえば十進数の123を十進数文字の最大値9で割った余りは
1+2+3と等しくなりますが、これと同じ原理ということですよね？
ただよくよく考えてみると、そもそも十進数の各桁の合計を9で割った余りが
元の数を9で割った余りと等しくなることについても
お恥ずかしながら豆知識として知っているだけで原理を理解できていませんでした。
ただこれに関してはもはやC言語ではなく算数の問題なので、
その方面の解説サイトをググって勉強しようと思います。
なにはともあれ、回答してくださった皆様方、どうもありがとうございました。
>>495
読みやすい記事を提供してくださっているので、もう少しだけコメントさせてください。
現状だと、MemoryReAllocateを呼び出す側は関数の成否を確認するために
Mem->Memoryを覚えておく必要がありますので、MemoryReAllocateの引数に
参照渡しを使われるならMemoryReAllocateの戻り値はMomeryではなくて
成否を表すboolなどにされてはいかがでしょうか。
また、reallocは第一引数としてNULLを許容しているので
MemoryReAllocateは入力のMem->MemoryがNULLであっても
Mem->ElementSizeが正しい値であれば正常に動作しますが、
その一方でMemoryAllocateは失敗するとElementSizeがゼロの構造体を
返すので少しアンバランスかなと思いました。
あと、MemoryFreeがboolを返すのであれば、freeの前にNULLチェックを入れて
その結果をMemoryFreeの戻り値としてもいいかなと思いました。
（free関数自体はNULLを渡しても何もしないだけで問題は起こりませんが）
以上お目汚し失礼しました 1回進むごとに
2bitずつに区切って、1の数を各2bitに入れる
4bitずつに区切って、1の数を各4bitに入れる
8bitずつに区切って、1の数を各8bitに入れる
...
となるので
>>489だと各バイトの1の合計が、各バイトに入る
各バイトなので256バイトのテーブルを使う方法もある
チープなCPUだとこちらの方が速い
逆にリッチなCPUだと数える命令が最初から備わってたりするしベクタ化も可能
Icelake以降だとAVX512VBMIの命令を使って
超高速に64バイト分カウント出来る >>500前半
なんか違う
10進数の各桁に関しては
1000a+100b+10c+d
=999a+99b+9c+a+b+c+d
=9(111a+11b+c)+(a+b+c+d)
これを2進数でやると
9のところが1になるからあまり意味がない 分割統治っていうより
レジスタ内の桁数を使ってSIMD演算してるって感じ
01020304 + 02040608
2桁ずつの4個の足し算になってるでしょ？ vpsrld
vpermb
vpermb
vpaddb
AVX512VBMIを使うと
レジスタに値がある状態で
4命令で64バイト分 >>501 >>504
レスありがとうございます。
> 各バイトなので256バイトのテーブルを使う方法もある
確かにある程度のビット幅ごとにテーブルを使って計算する方法は
シンプルですが効果が高そうですね。
> 逆にリッチなCPUだと数える命令が最初から備わってたりするしベクタ化も可能
> 4命令で64バイト分
勉強になります。本当に速さが必要ならCPU自体の理解から始めるべきなんですね。
このあたりのハードウェアの違いは標準ライブラリ関数が吸収してくれると最高なのですがｗ
>>502
10進数の話の数式どうもありがとうございます！大変勉強になりました。
そうすると、>>489 の popcount の最後にやっているのは
2進数というか0x100進数で、
0x1000000*a+0x10000f*b+0x100*c+d
=0xffffff*a+0xffff*b+0xff*c+a+b+c+d
=0xff*(0x01010x*a+0x0101*b+c)+(a+b+c+d)
ということになると思うのですがいかがでしょうか。 >>505 の数式が変でした。正しくは以下のとおりです。失礼しました。
0x1000000*a+0x10000*b+0x100*c+d
=0xffffff*a+0xffff*b+0xff*c+a+b+c+d
=0xff*(0x010101x*a+0x0101*b+c)+(a+b+c+d) 最後の % 0xff を見てなかった
なので各バイトの1の個数と勘違いしてました
>>506はその通り
%は、除算命令を使うと遅いので
コンパイラは
0x0101010101010101
との乗算とシフトに置き換えそうです
PCの64bit環境だとPOPCNT命令がそのまま1命令
Icelake以降だとVPOPCNTQで8個を1命令
で出来ます x % 0xff
よりは
x * 0x0101010101010101 >> 56 & 0xff
の方が直接的でコンパイラを頼らない記述でしょう それだと
剰余 x % 0xff
ではなくて
商 x / 0xff >>507-508
レスありがとうございます。
> x % 0xff
> よりは
> x * 0x0101010101010101 >> 56 & 0xff
> の方が直接的でコンパイラを頼らない記述でしょう
コンパイラの最適化によって一行目が三行目に
置き換えられる可能性があるということですか！？
難しそうですがちょっと考えてみたいと思います。
> PCの64bit環境だとPOPCNT命令がそのまま1命令
> Icelake以降だとVPOPCNTQで8個を1命令
本当に速度を求めるならCPUの命令を直接使えということですね。
覚えておきます。 >>511
コンパイラは普通、定数の除算は乗算に置き換えます
乗算、シフトは1クロック、除算は数十クロックかかるのが普通なので
ただ、
>>508 にまでは最適化されないかも
なので>>508の方が良いです >>512
ありがとうございます。そのようにしたいと思います。
ご親切に甘えてしまい申し訳ないのですが、
もう一つ質問させてください。今、
① = x % 0xff
と
② = x * 0x0101010101010101 >> 56 & 0xff
について考えていたのですが、
x = 0xff のとき、
① = 0x00, ② = 0xffのように、別の値になりませんか？
これは、どこか書き間違いがあるとういことでしょうか。
それとも、この違いは今回の用途では問題にならないということでしょうか。 >>512
立て続けにすみません。。。たった今理解しました。
「この違いは今回の用途では問題にならない」が正解ですね。 除算命令、
Skylakeで最大90クロックだそうで...
簡単な命令だと1クロックで3～4個実行出来る事を考えると劇遅ですね
Icelakeだと18クロックなので
改善されてるみたい >>515
> 除算命令、
> Skylakeで最大90クロックだそうで...
なんと！しかも、「最大」という表現が付くんですね。
つまり、ただの数値計算なのに
クロックの数がデータに依存する可能があるということ…？ >>516
除算命令の実行時間はデータに依存します
内部的にループしてるようなものなので
SIMDの除算は多分一定
Icelakeももしかしたら一定かもしれません
SIMD乗算も非常に小さな値だと遅い事があったような >>517
小さい値だと遅い！？
すみません、ハードウェアの知識がなさすぎて
タイプミスをされたのか本当にそうなのかの判断すらつかないです。。。 そりゃ並列処理できるような相互依存性の低い大量のデータでもあるならともかく
小さなデータ塊対象だとパック化やアンパック化する手間が掛かる分だけ
総合的にはSIMD使った方が遅くなるだろ
馬鹿となんとかは使いようと言うだろ >>520
馬鹿がSIMD使うと遅くなる
それはそうかも >>519
勉強になります。
非正規化数という言葉はちらっと聞いたことはありますが、こういうデメリットもあるんですね。
そして、それでも非正規化数を使うのは
「浮動小数点数の加減算は決して『アンダーフローによるゼロ』にならない」
という理由があるのだということも初めて知り、とても興味深く感じました。
ところで、ビット演算に関してもう一つ相談させていただいてもよろしいでしょうか。
動的メモリ再確保のコストを減らすために確保するメモリのサイズを必ず 2ⁿ-1 の形にしたくて、
与えられた数を下回らない最小の 2ⁿ-1 の値の値を返すような関数を作って使っています。
つまり引数xを2進数で表したときの一番上位の1以下をすべて1に置き換えるような関数で、
具体的には以下のように記述しています。
int fill_lower_bits(int x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x;
}
この関数は割と使用頻度が高いので、PCの64bit環境にPOPCNT命令があるように、
もしfill_lower_bitsと似た振る舞いをする命令があれば名前を教えていただけないでしょうか。
（続く） （続き）
また、こちらはあまり使い道は思いつきませんが、
int fill_higher_bits(int x)
{
x |= x << 1;
x |= x << 2;
x |= x << 4;
x |= x << 8;
x |= x << 16;
return x;
}
という関数を考えることもできて、これなら
int fill_higher_bits(int x)
{
return -(x & -x);
}
のように簡単な書き方に変更できます。
fill_lower_bitsについてもこういうテクニックがあればいいなと思っているのですが、
もし何かご存知であれば教えていただけると嬉しいです。 >>523
BSR命令といくつかの命令を組み合わせて出来ます
Cからだと _BitScanReverse64
>>524
x | -x
の方が良いと思います >>525
何度も本当にどうもありがとうございます。大変勉強になります。
> _BitScanReverse64
こんな命令があったとは！
この名前で検索したら、今まで知らなかった興味深いページがたくさんヒットしました。
ReverseじゃなくてForwardというのもあるみたいですが、
Forwardの方はマイナスを使う方法でも十分高速になりそうなので、
どちらが速いか検証してみようと思います。
> x | -x
確かに…。
ド・モルガンの法則で ~(x & ~x) が ~x & x に書き換えられるのはすぐに分かるのですが、
もしかしてそれと同じことがマイナスでもできるのでしょうか。
-x が ~x + 1 と同じになることは理解しているので、ちょっと考えてみたいと思います。 >>526
> ド・モルガンの法則
-(a & b) = -a | -b が成り立つかなと期待したのですが、
a = 0, b = 1 のときにつまずいてしまいました。
でも、>>525 に書いていただいた -(x & -x) = -x | x は間違いなさそうです。
こういう式の変形って、どこかテキストに載っていたりするのでしょうか。 自分で頑張って探すんです
~x
x-1
-x
&
|
^
これらを組み合わせれば
一番右のビット関連がいろいろと出来ます
???10000
に対して
11110000
11100000
00010000
00011111
00001111
これらを得る最小回数の演算を考えてみてください ド・モルガンと似た問題で、
「君たち2人は注意されないならば、君たち2人は私語を止めない」
の対偶、
「君たち2人が私語を止めるならば、君たち2人は注意される」
って矛盾にちょっと考えてしまったわ。 >>523
メモリ確保やアクセスの時間に比べれば
サイズ計算の時間は無視出来る
ビット演算の趣味として楽しむ分には良いけど
普通にループでもパフォーマンスは変わらない
パフォーマンスが重要じゃないところ
(つまりほとんどの部分)は
移植性、見やすさ、工数、...
などが優先される
ということは知っておいた方が良いですね 分野によってはループや比較による分岐は遅すぎて使えないなんてことままあるよ 動的メモリ再確保
のサイズ計算の話
オーダーnに対して係数の小さなオーダーlog nは無視して良い
って話 C言語というか、WindowsのCですが、
たとえば strcpyの lstrcpyと _tcscpyの違いは何なのでしょうか
前者は WindowsAPI、後者は VC++CRTという説明を見たのですがよくわからないのです
両者とも UNICODE(後者は_UNICODE) の有無で charとwchar_tを切り替えるようですが、どちらをどんな時に使用するのかが分かりません。 crtへの依存を減らせる分、常にlstrcpyを使えばいいと思うよ。lstrcpyは不正アクセスしたときに例外投げてくれるみたいだし。
自分なら依存減らす＆安全性のためにstrncpyとwcsncpyを選ぶけど >>540
ありがとうございます。
539です。
今後は気をつけようと思いますが、過去に書いたコードは何ともいたし難く…orz
なぜ先に lstrcpyを見つけなかった 2014年のオレ…
でも、内容が古いのかもしれませんが、ある記事によると CRTの依存を断ち切るのも容易ではないようで。。。 むしろlstrcpyなんて16bit時代から引きずってる過去の遺物なんじゃ？
今はlstrcpyも非推奨、代替のStringCchCopyはWindowsAPIの体だけどkernel32.dll等を呼び出すのではなくstrsafe.h内にコードが書いてある変わり種なのでtchar.h系の_tcscpy_sでよくね？っていう そうか？ 古くからMSCは「高いが安心」というポジションだったが 何の変哲の無いコードを書いてコンパイラのバグが顕在化するMicrosoftのCが安心とは、茶がヘソを沸かす。 唯一のECMA-372対応コンパイラ
壮大なマッチポンプだが… そもそもCはUNIXの為に作られた言語だから
UNIX系以外のOSで使うと齟齬が出るよね ■ このスレッドは過去ログ倉庫に格納されています
