C言語なら俺に聞け 146

2018/04/30(月) 04:47:37.50

C言語の話題のみ取り扱います C++の話題はC++スレへ
質問には最低限の情報(ソース/コンパイラ/OS)を付ける
数行で収まらないソースは以下を適当に使ってURLを晒す
https://paiza.io/
https://ideone.com/
http://codepad.org/

C11
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf

C99
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
http://kikakurui.com/x3/X3010-2003-01.html

C FAQ 日本語訳
http://www.kouno.jp/home/c_faq/

JPCERT C コーディングスタンダード
https://www.jpcert.or.jp/sc-rules/

前
C言語なら俺に聞け 144
https://mevius.5ch.net/test/read.cgi/tech/1514025223/

次スレを立てる時は本文の1行目に以下を追加して下さい
!extend:on:vvvvv:1000:512
-
※前スレ
C言語なら俺に聞け 145
http://mevius.5ch.net/test/read.cgi/tech/1519046038/

VIPQ2_EXTDAT: default:vvvvv:1000:512:----: EXT was configured

◆QZaw55cn4c (ﾜｯﾁｮｲ 4a60-Y8gp) · 2018/07/15(日) 17:20:53.28

>>350
まず集合の要素を何にするか？
集合自体の表現をどうするか？
そこからスタートするべきだと思います
C++ https://mevius.5ch.net/test/read.cgi/tech/1434079972/33

2018/07/15(日) 18:24:43.00

C++ちゃうやろ

2018/07/15(日) 18:43:53.92

C++のstd::setを参考にしない手はないな。
集合をデータとして保持したいなら、要素の個数と、動的配列かリストが必要になる。

2018/07/15(日) 18:50:09.68

集合は順序列の順序を無視したものと考えられる。
比較する場合は、ソート済みにしてから比較する必要がある。
多重集合ではない場合は変更の際に要素を単一化しないといけない。

2018/07/15(日) 18:57:55.11

setは赤黒木だけど、実装したことある奴いるの？俺はaddだけ実装して満足して諦めたよ。

hashtableのほうが遥かに簡単だからオススメ。
整列済みの配列も簡単でいいと思うよ。

でも一番楽なのは、ライブラリを拾ってくること。

2018/07/15(日) 20:00:12.79

std::unordered_set

2018/07/15(日) 23:33:22.03

>>350
積集合の方が比較的簡単
和集合は同一要素であるかをどうやって判別するか
要素を構造体で表した時に
異なる構造体でも同一要素である判別が出来なくてはならないので

単純な例だと
複素数型と実数型と有理数型とcharとintとfloatとdoubleとか

2018/07/15(日) 23:57:35.35

>>357
意味が全くわからんわ。
そもそも和集合も積集合も補集合考えたら手間が変わるはずないし。

2018/07/15(日) 23:59:45.37

>>358
ああ、直積と勘違いした

2018/07/16(月) 00:10:17.99

型が限定されていれば簡単
(>>353や>>356)

>>357みたいに、
いろんな型が混ざった和集合だと
いろいろと大変

2018/07/16(月) 00:41:17.49

一般論で言えば、集合の実装はハッシュを実装することに限りなく等しい。

どんなオブジェクトであれ、シリアライズ（要は文字列化）できる。
そうすればハッシュで一意な比較的小さい非負整数の番号に写像できる。（←条件により、ここが難関になりうる。ハッシュを使わずに済む番号が用意されていればそれが最適）
逆写像も用意できる。
最大番号までの要素数を持つ整数配列で0/1で要素の有無を表現したものが一つの集合を表す。
2つの集合の和と積は0/1の|と&で表せる。
配列サイズと計算時間の節約にはビットマップ化すればok。

2018/07/16(月) 12:41:40.20

視野の狭いアホ

◆QZaw55cn4c (ﾜｯﾁｮｲ 4a60-Y8gp) · 2018/07/16(月) 13:40:42.48

>>361
＞ハッシュで一意な比較的小さい非負整数の番号に写像できる。

ハッシュ関数は一般に衝突するもの、と考えるものですが、範囲を小さくすれば特に…

2018/07/16(月) 13:45:32.02

ハッシュの逆写像て何よ

2018/07/16(月) 15:04:36.42

>>362
広い視野で具体的な提案をどうぞ。

>>363
要素が固定なら完全ハッシュ関数が構成可能。

>>364
和集合とか積集合とか求めてもそこから要素リストが作れなければ無意味というだけ。これは逆写像を作ってるのと同じ。

2018/07/16(月) 16:32:35.47

>>350
ビット演算使えば良いのでは？
特に要素数が32とか64以下に収まるようなら今どきのPC用コンパイラならunsgnedのintやlongで行けるよ。
uint32tみたいなビット数保証するtypedefされた型使った方が良いけどね。

2018/07/16(月) 16:42:31.55

うわっ
また特殊な条件でしか使えない方法を

まあ>>350が悪いわけだけど

2018/07/16(月) 16:58:23.91

>>365
オペランドが入力されたら都度完全ハッシュを求めるの？
地味に和積集合計算するよりはるかにコスト高だろ…

2018/07/16(月) 17:09:01.83

全順序化が簡単か
効率的なハッシュが(簡単に)作れるか
想定する集合の大きさ
比較のコスト
ノードのデータサイズ

この辺が違うと適した実装が全く異なる
この辺をヒアリングするのが先と思う

2018/07/16(月) 20:33:05.89

>>368
「要素が固定なら」と条件付き。よく読んでね。
そうじゃない場合は難関になりうることも言及ずみ。よく読んでね。
衝突してもハッシュ表は実装できるわけで、全順序化が不可能なわけではない。

2018/07/16(月) 20:35:21.92

>>369
これ。

これら含めて最大限一般化したら>>361になるよね。

2018/07/16(月) 21:05:16.49

>>370
何に対して固定なのか、いつ固定されるのか、稚拙な日本語から読み取れと？
それに>>361にはそんな条件は書いてないぞ。にもかかわらず、ハッシュから写像ができると書いてある。意味不明すぎるわ。

2018/07/16(月) 21:29:45.38

>>371
ならねーよ
>>355も書いてるけどこの手のやつの定番は赤黒木とかB-Tree
ハッシュはデータ量が見込めないとハッシュテーブルサイズが決められないから使い辛い

2018/07/16(月) 21:50:26.80

>>355
作ったことあるけど使えない程度に遅かったわ

Cで赤黒木ならLinuxかfreeBSDから拝借するのがよさそう

2018/07/16(月) 21:56:55.25

c++のmapとsetの実装アルゴリズムだぜ。
検索速度はハッシュテーブルに劣るけど、使えないほど遅いってことはないだろ。

2018/07/16(月) 22:18:00.48

C言語初心者です。

typedef struct{
int tate;
int yoko;
double *mat;
} Mat;

void　read(int x,int y,Mat *a){
for(int i=0;i<x;i++){
for(int j=0;j<y;j++){
printf("[%d][%d]->",i+1,j+1);
scanf("%lf",&a->mat[i][j]);
}
printf("\n");
}
return;
}

プログラムの一部を抜粋したものなのですが、これでコンパイルすると
subscripted value is neither array nor pointer
というエラーが出てしまいます。
二次元配列はポインタで表せないものなのでしょうか？

2018/07/16(月) 22:23:31.47

sageをつけ忘れました
申し訳ございません。

2018/07/16(月) 22:43:27.11

>>376
メモリ空間は1次元だから。
arr[y][x]は*(arr+y*WIDTH+x)と同じ。WIDTHがわからないとできない。

2018/07/16(月) 23:01:36.27

>>376
matがdouble型へのポインタだからだよ。
結果mat[i]はdouble型になり、mat[i][j]はdouble型に[j]を付けたことになるので、配列でもポインタでもないのに[]つけるなって怒られてる。

きっとmatのメモリ確保は
mat = malloc(sizeof(double) * tate * yoko);
みたいにやってるだろうから、i列j行目にアクセスするときは
&a->mat[i + j * yoko]
みたいにしないといけない。

あと、上の例ならjを外側、iを内側のforにしたほうが最適化されやすいと思うよ

2018/07/17(火) 00:14:58.01

>>375
作りが悪くて目標に届かなかっただけ
100万件のinsertに1秒程度が目標だったけど2.5秒ぐらいだった

2018/07/17(火) 00:50:16.45

>>376です
お二人とも丁寧に教えていただきありがとうございます。
>>378さんの方法で改良してみたのですが複数のMat構造体を作り,tateとyokoの値のそれぞれ別にしたときにプログラム実行中に入力が強制終了されてしまうのですが、配列の作り方に何か不都合があるのでしょうか

2018/07/17(火) 01:14:22.91

>>381
あるあるネタだね。
何処かでx/y、i/j、tate/yokoが逆になってる。

2018/07/17(火) 03:42:30.44

Ruby のハッシュでは、データ数と共に、バケット数を増やしていく。
バケット数は、2 の累乗の次に現れる素数。
2^n + a, 2 <= n <= 30

8 + 3 = 11
16 + 3 = 19
32 + 5 = 37
64 + 3 = 67
128 + 3 = 131
256 + 27 = 283
512 + 9 = 521

データ数が、バケット数の5倍を超えると、ハッシュが再構成される。
再構成時には、極端に遅くなる

11 * 5 = 55 だから、データ数が56 個になると、バケット数が19 になる。
19 * 5 = 95 だから、データ数が96 個になると、バケット数が37 になる

2018/07/17(火) 04:09:19.94

AVL では、左右部分木の高さの差を、1 以内にしなければならないから、
2 になると、木の回転・縮約など、再構成をしなければならない。
つまり、しょっちゅう再構成が起こるので、遅くなる

赤黒木では、左右部分木の高さの差を2 倍以内にしたから、再構成が起こりにくい。
左が10 なら、右は20 まで、再構成が起こらない

タスクスケジューラーに使われる

例えば、100個のスリープしているタスクがある所に、
木に実行するタスクを追加して、重みに従ってソートすると、
追加したタスクが選ばれて、木から削除される

つまり、ほとんどの葉の順位が変わらなくて、
追加した葉が、すぐに削除されるようなものに適している

2018/07/17(火) 21:50:50.91

makefileってPowerShellで作れないとかないですか？

2018/07/18(水) 13:02:52.94

>>385
君が何を言わんとしているのかがよくわからない

2018/07/18(水) 13:22:02.69

わからないならかくなあほ

2018/07/18(水) 13:27:22.37

>>387
あれで人に言葉が通じていると思い込んでる可能性があるから書くべきだろう

2018/07/18(水) 15:13:21.80

>>385
作れますよ

2018/07/22(日) 17:00:55.76

なんとなく、コマンド行をタブで始めてなくて(スペースで空白を作ってて)、
makeがエラー出してるような気がするなぁ。
エディタのTab→スペース自動変換が効いてるとか。

PowerShellとは直接関係なくて。

2018/07/23(月) 07:43:37.05

C++　C言語　C#の初心者用スレはないんですか？
探してみたけどそれらしきスレが見当たらないです

2018/07/23(月) 08:25:03.57

>>391
まずはどうやって探したのか聞こうか

2018/07/23(月) 18:37:31.75

>>392
まずスレッド一覧を開いてCTRL＋FでC++と入れて検索しました
一応それらしき所を見つけたんですが書き込んだ瞬間変なおっさんに噛みつかれたので
初心者スレじゃないのかな。。。と。
入門にあったスレはないでしょうか

2018/07/24(火) 00:16:29.41

無ければ作ったら良い

2018/07/24(火) 00:25:40.41

初心者歓迎なのと甘えた初心者に手とり足とり教えるのとは違うよ

2018/07/24(火) 10:50:38.33

回答者も甘えてる奴がほとんどだしな

2018/07/24(火) 12:49:34.60

初心者といいつつそれ以前だったりするから

2018/07/24(火) 12:52:10.55

回答する気が無いヤツは黙ってろ
目障り

2018/07/24(火) 22:27:17.58

>>393
ここでの『初心者』はANSI Cの規格を読み込んでいること前提
プログラム未経験者は取り合えず柴田茫洋の明解C言語を読め

2018/07/24(火) 22:55:24.02

回答する気が無いヤツは黙ってろ
目障り

2018/07/25(水) 14:04:28.05

明解C言語は分かりにくいからやめとけ
苦Cの方がいい

2018/07/25(水) 15:50:06.17

明解と
書いてる方が
不明解

2018/07/25(水) 18:17:36.85

今からC言語覚えて何に使うの？

2018/07/25(水) 18:38:39.52

デバドラを書く
低速言語のボトルネックをカバーする

2018/07/25(水) 19:01:18.88

こういう連続線をクリックで描きたいなんか参考になる本だとかサイトってありませんか？
https://i.imgur.com/Emj85bk.jpg

2018/07/25(水) 19:07:02.74

>>405
それをCで書こうって考えている？

2018/07/25(水) 19:11:06.73

>>403
小規模マイコンのプログラミング
とか

2018/07/25(水) 19:19:25.92

>>405
環境は？
OSやコンパイラは？

2018/07/25(水) 20:53:24.83

>>407
揚げ足とるわけじゃないけれど
なんで小規模マイコン限定？

2018/07/25(水) 20:53:47.05

大規模は違うの？って意味ね

2018/07/25(水) 20:57:49.18

まずint(4バイトとする)とmalloc(4)の違い教えて
話しはそれからだ

2018/07/25(水) 21:01:13.33

>>411
mallocは使い終わったらfreeで解放しないといけない。

2018/07/25(水) 21:02:09.90

Windows Win32 GDIで作ってみた
中身はいい加減だけど、マウスのボタンクリックイベントでポインタ座標を取得して順に直線で繋げているだけ
http://codepad.org/QqqOuloX
https://i.imgur.com/J8woM1h.png

2018/07/25(水) 21:04:29.51

101回目のバッファオーバーフロー？

2018/07/25(水) 21:09:14.98

エラー処理なし
ウインドウハンドラ作成もメッセージループの処理も適当なのでプロシージャもいい加減な作り

2018/07/25(水) 21:13:14.68

俺の言い方がまずかったようだ。
int* a = (int*)malloc(4);
これはわかる

int* a = (int*)malloc(5);
この場合でもコンパイルは通るし実行も出来る。

でも、やっていいことなんだろうかってね。
余った1バイトは気にしないでいいのだろうか？

2018/07/25(水) 21:18:04.56

>>416
余分に確保しても大丈夫。連続したメモリーブロックと呼ばれるものだよ。頭に構造体を使ってもいいし。

2018/07/25(水) 21:21:01.07

例えば、int *p = (int*)malloc(5*sizeof(int));と書けば、pは、int p[5];のように使える。

2018/07/25(水) 21:24:03.17

>>418
そう。これは分かる。インクリメントで確保した変数にアクセス出来るのも分かる。
>>416の下の例で、例えばa++した時、そしてそのアドレスの中身を変更すようとすると
何か途轍もなく悪いことが起きそうな気がするんだけど大丈夫なんだろうか？

2018/07/25(水) 21:29:51.06

連続したメモリーブロックからはみ出るから、そのアクセスは違法になるね。

2018/07/25(水) 21:32:51.80

ああ、なるほど。そういう時はエラー出るのね。
今試しにインクリメントしたら確かにエラーになった。なるほど良く出来てる。
なんか試すのも怖かったんだわ。ありがとう！

**デフォルトの名無しさん** (JP 0H2b-GemW) · 2018/07/25(水) 21:33:37.75

>>419
未定義だから鼻から悪魔が出てもおかしくないよ

冗談はおいといて、現実には5バイトじゃなく、64バイトとかのサイズをとったりするので、何事もなく動く。ただし、動くのはたまたま。

2018/07/25(水) 21:36:12.00

>>422
エラーをちゃんと出してくれるのが分かったから良かった。
まぁ適当な数字入れることなんか絶対ないだろうけど、これが動いたらやべぇなって心配だった

2018/07/25(水) 21:36:50.93

ただし、アクセスにおいてエラーが出ない事もあり、この手のバクはやっかいで、下手をすると数億円が吹き飛ぶことがある。
だから、最近ではなるべく生ポインタを使わないでやるのがプロ。

2018/07/25(水) 21:39:44.99

アクセス制御の貧弱なOSでは、不正アクセスは感知されない。

2018/07/25(水) 21:55:12.69

>>409
大規模はC++の率が高くなる

2018/07/25(水) 21:56:03.32

>>406
>>408
すみません。ここCでしたね。C♯でした。場所間違えました。

2018/07/25(水) 21:57:27.86

>>413
すげぇ。わざわざありがとうございます。

2018/07/25(水) 23:13:13.16

>>421
一般にエラーは出ないぞ

2018/07/25(水) 23:32:18.85

>>416
このれいだと.引数が 4でも 5でも、バウンダリが不安かな...
mallocは 4とか 16バイトの境界にアジャストされたアドレスを返しそうだけど

2018/07/25(水) 23:53:34.35

>>430
430ですが、mallocの返す番地は、大概の型にキャストできる境界になってるんだろうね、知らんけど

2018/07/26(木) 11:01:17.82

C11はアラインメントが決めれるmallocがあるよ
普通は8の倍数になってる。

2018/07/26(木) 12:52:49.36

ま、しかし、intが4バイトの保証はないし、malloc()で確保した範囲外がどうなってるかもライブラリ依存だし、変な事に挑戦しない方が良いと思うw

2018/07/26(木) 15:59:28.57

mallocの返すアドレスはワード教会に揃ってるように
POSIXで決まってなかったっけ？気のせいか

**デフォルトの名無しさん** (JP 0H8f-+hvm) · 2018/07/26(木) 16:54:25.22

>>432
aligned_alloc()だね

2018/07/26(木) 17:01:26.31

>>434
決まってる

**デフォルトの名無しさん** (JP 0H8f-J6FL) · 2018/07/26(木) 17:03:12.87

C99には
The pointer returned if the allocation succeeds is suitably aligned
so that it may be assigned to a pointer to any type of object and
then used to access such an object or an array of such objects
in the space allocated (until the space is explicitly deallocated).
とあるので、どんなオブジェクトでもその場所に置けることは保証されている。
ただ、アラインメントがずれてるとアクセスできるけど遅くなるとかいう
変態環境でどうなるかとかは規定されていない。
（ふつうの実装ならまともにアラインメントされていると思うが）
これをどうしても合法的に確実にアラインメントしたい人向けなのが、aligned_alloc()。

2018/07/26(木) 17:08:47.42

>>437
そうなんだ
おれはてっきりもっと全然違う基準、例えば64バイトとか16KBとかで
アライメントしたいときaligned_allocの方を使うものかと思ってた

**デフォルトの名無しさん** (JP 0H8f-J6FL) · 2018/07/26(木) 17:17:59.96

>>438
そりゃもちろんそういう用途にも使えるよ

2018/07/26(木) 19:04:38.15

>>437
パフォーマンスはCの仕様で規定されてないから
そんな事を心配したら標準ライブラリも使えないぞ
memcpyが劇遅かもしれないとか

2018/07/26(木) 19:07:36.39

普通の用途は>>438みたいなヤツ

zmmレジスタのサイズ
キャッシュのラインサイズ
HDDのセクタサイズ
FIFOのサイズ

なんかにしたい場合

2018/07/27(金) 00:14:41.96

家でC言語の独学してたけど眠くなって続かないから週末だけ学校にいこうと思う。関西でお勧めはどこですか？

2018/07/27(金) 07:12:56.09

金の無駄遣い

2018/07/27(金) 09:20:14.17

大阪大学基礎工学部情報科学科

2018/07/27(金) 09:52:20.15

勉強を成功させるには強い動機付けが必要
やる気も効率も上がらないのはまずそこに失敗してる

◆QZaw55cn4c (ﾜｯﾁｮｲ b260-tjON) · 2018/07/27(金) 20:31:18.69

>>445
動機付け、ですか…
そんなものは初めからありませんでした…

2018/07/27(金) 21:04:40.28

個人的にはLinuxのデバドラから入るのがおすすめ
分かってくると俺の方が上手く書けるとか拗らせる

2018/07/28(土) 02:43:37.63

動機を自分で意識的に付けようとしても中々出来ないのが普通なのでは？
何かそれなりのメリットがあると信じられないと何もしないのが普通の人間だろうし。
例えば何かをするとモテモテになるだとか、そういう自分にとってのメリットがあるならその何かをやる気は出るだろうけど、そんなのがないなら、あるいはもしあってもそれに気付けないなら普通はやる気は起きんでしょう。

2018/07/28(土) 07:47:22.78

C言語、あるいはプログラムそのものの入門書で、文庫か新書サイズの良書はありますか？

2018/07/28(土) 08:07:15.42

C++ならこれならわかるC++があるが・・・