スレ立てるまでもない質問はここで 158匹目

**デフォルトの名無しさん** · 2021/10/26(火) 05:30:43.46

この板はプログラムを作る人のための板です。
あらゆる質問はまず
スレ立てるまでもない質問はここで
スレにしてください。

【前スレ】
スレ立てるまでもない質問はここで 157匹目
https://mevius.5ch.net/test/read.cgi/tech/1624024239/

次スレは>>980が立てること

**デフォルトの名無しさん** · 2021/11/23(火) 16:49:29.76

>>258
その程度なら今時たいていのコンパイラはやってくれるよ
Visual Studio 2017 でやると a, b, c はそれぞれ 1000.0, 5000.0, 5120.0 の定数に展開されるし
int y = (x * (int)c) / 1024;
は
y = x * 5;
に展開される
ちなみにこの式はシフトどころか
lea ax, [eax+4*eax]
の１命令にコンパイルされる

>>270
const は単に書込しちゃだめだよって指示するだけで予め計算することを指示するわけじゃない
const volatile なんて指定すらできるんだし
コンパイル時に計算さておくことを保証したいならC++にしてconstexprを使えばいいかと

**デフォルトの名無しさん** · 2021/11/23(火) 16:51:36.40

赤あげて、白下げないで、赤下げない！

**ハノン** ◆QZaw55cn4c · 2021/11/23(火) 20:04:50.54

>>272
それは数論ですか？

**デフォルトの名無しさん** · 2021/11/23(火) 20:32:56.22

ほんとに初歩的な質問ですいません
AtomでDart Sassってどうすれば使えるのでしょうか
@importは問題なく使えるのですが、@useが使えません

**デフォルトの名無しさん** · 2021/11/23(火) 22:42:27.45

「dart sass use」で検索！

**277** · 2021/11/23(火) 22:59:46.57

SASS は、@import を廃止して、@use へ変わるのか

@importでは、読み込んだ異なるファイルに、同じ変数名があると、ヤバイのか。
それで、@useで接頭語に、読み込んだファイル名・名前空間を付けるのか

@import "a";
@import "b";

.abc {
color: $color-main;
}

@use "a";
@use "b";

.abc {
color: a.$color-main;
background-color: b.$color-main;
}

**デフォルトの名無しさん** · 2021/11/24(水) 00:10:56.17

今のご時世フレームワークやライブラリを活用した開発が主流だし
マイコンですらArduinoフレームワークやMicroPythonなどを使用していれば
低レイヤーの知識を持たずともそれなりの物は作れる
またネットの検索結果もそれに準じた物になっている

と考えれば低レイヤーにまつわる用語の理解がない人がいてもおかしくないんじゃないかな

**デフォルトの名無しさん** · 2021/11/24(水) 00:17:57.18

Notionを使ってデータベースというものを使いはじめたんだけど
データベースを分ける意味ってあるの？
全部同じところにブチ込んで検索して使うってやり方は間違い？

**デフォルトの名無しさん** · 2021/11/24(水) 01:06:28.19

>>280
「データベースを分ける」って何のこと？（違う種類の情報を違うテーブルに入れること？）
なんにせよ、やりたいことがそのやり方でできるならそれでいいよ
マシンパワー向上に連れて段々と効率を追及する必要が減って利便性を取っていくものだし

**デフォルトの名無しさん** · 2021/11/24(水) 01:09:32.20

少なくとも、第3正規形までは勉強すべし！

基本情報技術者・データベース技術者などの資格のテキストも読む

**デフォルトの名無しさん** · 2021/11/24(水) 01:32:07.76

1つのテーブルに色んなデータを入れるとカラムが増えて見にくくなりそう
あるレコードに関係するカラムが他のレコードに関係ない場合、無駄なカラムを持つことになる
プログラム上でデータ取得するならカラムが多くても問題ないけど、
Notionで画面操作して閲覧編集するなら使い勝手が悪くなるんじゃなかろうか

**デフォルトの名無しさん** · 2021/11/24(水) 03:23:50.96

>>282
++1
join

**デフォルトの名無しさん** · 2021/11/24(水) 23:37:30.86

>>281
一つのテーブルに全ての情報を入れる
タグを付けて検索したりする
今は困ってないから、まだいいのかな

>>282
リレーションがどうのこうのってやつか
それしなくても困ってないんだよなｗ

>>283
カラムもWEBページのタイトルとタグとURLしかない
プログラミングも料理もその他もろもろも全部ブチ込んで
タグとか検索でデータ取り出してる
これで将来困らないか心配してる

**デフォルトの名無しさん** · 2021/11/25(木) 01:08:20.48

普通の関連付け・association は、多対多、1対多とかだけど、
Ruby on Rails では、1対1 も出てくる

例えば顧客に、顧客の名前などの基本情報・自宅住所・勤務先の属性があって、
自宅住所・勤務先は、多くの属性が似ている場合、

1. 顧客表にすべてを格納する
2. 顧客表には基本情報だけを入れて、他を自宅住所・勤務先の、合計3つの表に分ける
3. 顧客表には基本情報だけを入れて、他を住所表に入れる。
ここで、住所表のtype 列の値で、自宅住所・勤務先を区別する

Rails では、3を単一テーブル継承と言う

**286** · 2021/11/25(木) 01:20:01.72

Ruby on Rails は、DRY 原則。
Don't Repeat Yourself（繰り返しを避けよ）

だから、自宅住所・勤務先は、多くの属性が似ているので、2 を採用したくない。
どちらかの表構成が変更された場合、もう一方も変わる可能性が高い

だから、同じようなものをまとめて、3のような構造にする

**デフォルトの名無しさん** · 2021/11/25(木) 15:30:49.84

C99でリングバッファぽく
struct A {
int a;
int b;
・・・
};

struct A obj[4];
int p;

struct A *enqueue(void) {
p = (p + 1) / 4;
return &obj[p];
}

void fn(void) {
(*enqueue()) = (struct A){.a = 1, .b = 2}; //※1 消える
struct A *ptr=enqueue();
*ptr = (struct A){.a = 3, .b = 4}; //※2 消えない
・・・
}
みたいに書いて最適化レベルを上げると※1の方が消えちゃうんだけど
自分の書き方が悪いの？それともコンパイラの解析が変なの？

**デフォルトの名無しさん** · 2021/11/25(木) 15:59:15.57

**デフォルトの名無しさん** · 2021/11/25(木) 16:01:35.09

p がいつまでたっても 0 で
常に同じ場所に上書きだから
一行目が不要と判断されてるのか？
コンパイル時に？

**288** · 2021/11/25(木) 18:38:31.77

並べたいので可読性を考えると
(*enqueue()) = (struct A){.a = 1, .b = 2};
(*enqueue()) = (struct A){.a = 3, .b = 4};
(*enqueue()) = (struct A){.a = 5, .b = 6};
(*enqueue()) = (struct A){.a = 7, .b = 8};
みたいに書きたいのにこの部分がごっそり消えちゃってどうしよう状態
memcpy(enqueue(), &((struct A){.a = 1, .b = 2}), sizeof(struct A));
みたいにmemcpy使っても消える。enqueue()の戻り値を変数に入れれば消えないっぽいけど無駄に行が増える
dstが関数の戻り値になることを想定していないのか？それはそれでどうかと思うけど

struct Aの中で可変のメンバは1つなのでポインタ＋変数の構造体にすれば構造体をコピーするコストを
節約できるけど見やすく書ける気がしない・・・

**デフォルトの名無しさん** · 2021/11/26(金) 13:06:18.62

プログラムがひど過ぎる・・・

**デフォルトの名無しさん** · 2021/11/27(土) 08:06:47.92

pythonのコード（ttps://pastebin.com/Dg4HSZML）を参考にjava（ttps://pastebin.com/m8ni9vwi）で作成しているのですが、
pythonの実行画面と同じようにはなりません。
paintComponent(Graphics g)の中が式が間違っているのですが、どこが違うのでしょうか？

**デフォルトの名無しさん** · 2021/11/27(土) 10:31:58.16

自社製APIがヘッダーにAuthorizationヘッダーとは別にプレーンテキストの機密情報を載せてリクエストする仕様なんだけど不安を感じる
アプリケーション固有の機密情報をサーバーに送信するときの定石的な手順ってありますか？
こういうのってHttpsで保護されてればそんなに気にしなくてもいいものなんですかね？

GET /examples
Authorization: bearer xxx
X-OREORE-SECRET-KEY: yyy

**デフォルトの名無しさん** · 2021/11/27(土) 11:14:51.31

>>294
仕方ないかと
トークンみたいなものは送らないとそもそも認識出来ないだろうしね
クッキーにしても同じだから

**デフォルトの名無しさん** · 2021/11/27(土) 11:41:22.05

ヘッダも暗号化されてるから大丈夫だよ
そこを疑ったらHTTPSが意味ないということになりボディも同じだけ危険ということになる

**デフォルトの名無しさん** · 2021/11/27(土) 12:20:45.49

>>294
心配ならその機密情報とやらを暗号化しとけばいいんじゃね？

**デフォルトの名無しさん** · 2021/11/27(土) 12:51:23.13

>>294
それがダメならAWS標準のAuthorizationヘッダ自体もダメということになる事からも安心していいよ

**デフォルトの名無しさん** · 2021/11/27(土) 13:16:49.36

ポイントは大きく2つあって、
1. 正しい相手と通信していること
2. 通信を傍受されないこと
このうち2については他の人のレスの通り、HTTPSならTLSにより暗号化されているからOK
1については見落とされがちだけど非常に重要で、これが確認できてないと相手をAWSだと思って機密情報を送ったら実際には中国の雑居ビルに送られていたということがありうる
それについてもTLSでサーバーの検証を行っていれば一般的にはOK

**デフォルトの名無しさん** · 2021/11/27(土) 13:32:55.63

あと、>>299はあくまでクライアントが正しく実装・運用されていれば安全であるという話で、
例えばクライアント側が勝手にサーバーの検証を無効化していて誤って中国の雑居ビルに機密情報を送ってしまうことは必ずしも防げないわけ
そうなったときの被害をできるだけ低減することも重要で、例えば>>298のAWSのAuthorizationヘッダの例では、APIキーをそのまま送るのではなくキーと日付とリクエストの内容を混ぜてハッシュ化した値を署名として送るようになっている
そうすることで仮に漏れてもそのリクエストでしか有効でない認証情報になるわけだね
やらかしたとしてもあくまでクライアント側の責任なんで、そこまでやるかはサービスのポリシー次第

**デフォルトの名無しさん** · 2021/11/27(土) 18:22:20.55

>>295-300
ども
参考になりました

**デフォルトの名無しさん** · 2021/11/27(土) 21:50:48.12

Ruby on Rails のCSRF(Cross Site Request Forgeries, シーサーフ)対策では、

get 以外のフォームには、
あらかじめ、サーバーからセキュリティトークン(authenticity_token)を送っておいて、
それを送り返してもらう事で、Railsアプリから送信されたものである事を証明する

これによって、クラッカーのリンクを踏んで、
クラッカーのサーバーから送信されるのを防ぐ

**デフォルトの名無しさん** · 2021/11/27(土) 23:56:56.73

いや、ものごっつ伝統的な手法じゃねトークン
あまりに実装が面倒だと敬遠
普通の実装だと戻るボタンで戻るとエラーにならんか？

**デフォルトの名無しさん** · 2021/11/28(日) 17:49:43.20

GoogleのYouTubeなどのためのAPIを使うには「APIキー」を取得する必要が
あるけど、仮にAPIを使って行うプログラムの作成を受注した仕事などで
こっちのローカルPCからGoogle Cloudにアクセスしてテスト用にそれを
作成した場合、プログラムを納品する際にはどうしたらいいのだろう？

1. そのAPIキーをそのまま使うように相手に言う。
2. 相手が専用のものを作り直す。
3. 相手にAPIキーを譲渡する方法が有る？

2とする場合、オンラインで納品する場合、その作業を相手にやって貰う？
相手がPC音痴でそれが難しい場合、どうする？
それとも、相手の場所に行ってこっちが手作業でAPIキーを作る？

もし、1にする場合、こっちのトラブルでAPIキーが消えてしまったりすると
困るし、一生消えないことを保証するのは責任がとても重くなってしまうが。

**デフォルトの名無しさん** · 2021/11/28(日) 18:34:10.40

**デフォルトの名無しさん** · 2021/11/28(日) 20:23:11.54

登録までの手順も納品物件だとか言い出す客もいるから、会議とかの記録はしっかり取っとけよ

**デフォルトの名無しさん** · 2021/11/28(日) 22:48:24.91

例えば、不動産の名義変更を司法書士に頼む場合、
自分で法務局から必要書類を取り寄せて、司法書士に送ると、2, 3万円安くなる

それを司法書士に任せると、高くなる

**デフォルトの名無しさん** · 2021/11/29(月) 17:06:02.87

自分の人件費も交通費も自腹

**デフォルトの名無しさん** · 2021/11/30(火) 09:55:27.33

過去問道場について質問です。

応用情報技術者試験の過去問道場で午後試験を試験回指定して出題できますか？

基本情報技術者は午後問題も試験回を指定して出題できました。

応用情報技術者はどこで午後問題の試験回を指定して出題できるかわからないです。

**デフォルトの名無しさん** · 2021/11/30(火) 10:31:27.22

IPAは情報リテラシー教育にもっと力を入れるべきだな

本来は義務教育の範疇だとは思うがそこはIPA以上に期待できないので

**デフォルトの名無しさん** · 2021/11/30(火) 12:31:10.61

セキュリティに関しては「安全な」シリーズで頑張ってると思うけどなぁ

**デフォルトの名無しさん** · 2021/11/30(火) 12:34:41.37

あー、作り手じゃなくリテラシー教育か
一応色々とやってるよ
https://www.ipa.go.jp/security/keihatsu/features.html

**デフォルトの名無しさん** · 2021/11/30(火) 15:22:38.78

>>312
まずは情報リテラシーとは何かを勉強したほうがいいんじゃないの？
https://en.m.wikipedia.org/wiki/Information_literacy

**デフォルトの名無しさん** · 2021/11/30(火) 20:35:08.83

質問なんですけど、データベースのバックアップって毎日行ったとしても、データが飛んだ時にバックアップを取っていないデータはなくなってしまうと思うのですが、googleやMicrosoftのような企業はどのようにしてるのですか？
同時に２つのデータベースに書き込んでいるとかしてるのですか？データベースが壊れた際には自動で修復するプログラムとか走らせてるのでしょうか？質問多くてすいません

**デフォルトの名無しさん** · 2021/11/30(火) 22:27:27.75

複数のストレージに書き込んでそのうち何割かが成功したら成功とみなす
あとはストリーミングレプリケーションで遅延数ミリ秒以内のバックアップを取ったり
といった感じかな
GoogleやMicrosoftがどうやってるかは知らんが一般的にはこの程度やね

**デフォルトの名無しさん** · 2021/11/30(火) 22:55:47.28

コミットという命令はそのためにある
処理を確定させる
コミットする前にトランザクションが中断すると
トランザクション自身がなかったことになる

**デフォルトの名無しさん** · 2021/12/01(水) 02:07:08.15

Amazon S3 は、3重にデータを書き込むので、お手軽。
確か、東証のシステム・富士通arrowhead も3重

Ruby on Rails 6 からは、複数データベースにも対応した。
同じデータベースを2つ作って、primary/read replica 用に分ける

基本は、様々なRAID

Kubernetes はネットワーク分断に備えて、多数決システム

司令塔を偶数にしない。
例えば、4つなら、2対2に分かれた時に、どちらが正しいか判別できないから

**デフォルトの名無しさん** · 2021/12/01(水) 11:11:25.46

ありがとうございます。
勉強になりました。個人で一からやるには難しそうなので、AWSのs3について調べてみます。

**デフォルトの名無しさん** · 2021/12/01(水) 12:17:12.83

あう、クラウドの講習で聞いたはずなんだけど疑問が
>>317 でネットワーク分断が発生したとき、多数側で偶数個のノードが残った場合どうするんだっけ？

**デフォルトの名無しさん** · 2021/12/01(水) 18:17:51.53

>>319
過半数の賛成が必要ってだけだから
7ノードが4:3で分断されたら4ノード側でオペレーション継続可
4ノードのうち3ノードの合意でクラスタの状態が更新可

**デフォルトの名無しさん** · 2021/12/01(水) 19:09:37.83

>>320
いや、その4ノードが残っていた場合に更に2:2で分断される場合を考慮した挙動をなんか説明うけた記憶があるんだけど
でもどうやるんだったか思い出せないんで

**デフォルトの名無しさん** · 2021/12/02(木) 14:35:40.44

グラフの閉路について質問です

グラフに閉路が存在する場合、常にグラフ自体を閉路と呼ぶのですか？

それとも閉路はグラフの一部分というグラフもありますか？

**デフォルトの名無しさん** · 2021/12/02(木) 14:59:06.88

メルカソで２重課金請求するプログラム書いちゃって怒られました人か

**デフォルトの名無しさん** · 2021/12/02(木) 16:03:59.79

>>322
グラフの一部分でない閉路なんてないだろ
幾何学的に大雑把に言えば、グラフの中で輪になっている部分なんだから

**デフォルトの名無しさん** · 2021/12/02(木) 16:48:41.42

>>324
グラフの一部に閉路があってもそのグラフに閉路ではない経路がある場合はありますか？

**デフォルトの名無しさん** · 2021/12/02(木) 19:25:21.06

グラフに閉路が存在するからといって、そのグラフが閉路グラフとは限らない
厳密に定義されてるかどうかはあやしいけど、閉路を含むだけのグラフ全体を指して閉路であるとは言わないはず

**デフォルトの名無しさん** · 2021/12/02(木) 19:41:24.08

>>325
例えば9という形とか、そりゃもう腐るほどある

**デフォルトの名無しさん** · 2021/12/02(木) 19:50:47.25

>>326
>>327
ご返信ありがとうございます！
いい感じにメモができました

**デフォルトの名無しさん** · 2021/12/03(金) 02:41:18.49

ngenしたらstrong name validation failedって怒られるんだけどレジストリいじるしか回避方法ない感じ？

**デフォルトの名無しさん** · 2021/12/04(土) 12:07:27.65

Cのstructにmethodぶら下げられるようにしたら生産性軽く10倍になりそうですがなぜやらないんですか？

**デフォルトの名無しさん** · 2021/12/04(土) 12:11:52.27

C++で

**デフォルトの名無しさん** · 2021/12/04(土) 12:43:32.13

Cで仕事してたら関数テーブルなんて基本だと知ってないとおかしいから、他の言語持ち上げるか何かのためにディスってるんだよ
触るな

**デフォルトの名無しさん** · 2021/12/04(土) 14:00:56.12

数字上、直径32cmの円の円周は100.48cmですが、
直径32ドットの円を描くと外周100ドットからはかなり離れますよね

-0.5したり奇数偶数でどうにかしたりでこの差を縮める事は出来ますかね

**デフォルトの名無しさん** · 2021/12/06(月) 12:47:40.78

>>330
Rustを使いましょう

**デフォルトの名無しさん** · 2021/12/06(月) 16:07:09.17

Gitに入ってるVimがなんでもクリップボードに入れてしまい使いづらいです。
cwとかで単語を書き換えたいときに元の単語が勝手にクリップボードに入ってしまい、単語書き換えができないのです。
クリップボードを使う設定はあちこちで見るのですが設定されてしまっているクリップボードをクリアするにはどうしたらいいでしょうか？
.vimrcにはクリップボードの設定は書いてません。

**デフォルトの名無しさん** · 2021/12/06(月) 23:03:54.91

質問なのですがアキネーターの仕組みをまったくプログラミング知らない人間が説明できる事って普通でしょうか？それとも特別でしょうか？

**デフォルトの名無しさん** · 2021/12/06(月) 23:47:27.19

しらんけどアホのたわごとだろ
適当なことしか言ってねーよ

**デフォルトの名無しさん** · 2021/12/07(火) 00:41:52.19

普通。仕組みにプログラミングは関係ない。

**デフォルトの名無しさん** · 2021/12/07(火) 08:46:15.52

>>336
仕組みの事をアルゴリズムと言うんだよ

**デフォルトの名無しさん** · 2021/12/07(火) 09:46:48.67

Twitchの配信者のアーカイブを全部保存したいんですけど何かおすすめのツールありますか？

**デフォルトの名無しさん** · 2021/12/07(火) 10:05:28.13

>>340
LINEなら簡単

【LINE Pay】約13万人の決済情報が「GitHub」で公開状態に　グループ会社従業員が無断アップロード【ITmedia NEWS】 [少考さん★]
https://asahi.5ch.net/test/read.cgi/newsplus/1638796061/

**デフォルトの名無しさん** · 2021/12/07(火) 11:02:56.03

こういう事故が起きると自社のルール見直しがかかって作業環境が悪くなるから困る
セキュリティは透過的になっているべきなんだが何故か長老会は面倒な手順を増やしてルール遵守を徹底することで対処させようとする

**デフォルトの名無しさん** · 2021/12/07(火) 12:54:48.01

上からの指示で生じた結果は上が責任を持つべきだがそうなっていないのが問題
結果、不可能な指示とルール無視が横行しある日に炎上して会社が傾く

>>342
コスト無視で秘密にすれば問題ないと考えている人が多いからね
秘密にするにも金がかかるという理解が無い人の多いこと多いこと

**デフォルトの名無しさん** · 2021/12/07(火) 14:56:28.48

Google Oauthについて質問です。
Google Oauth2.0を用いて、組織ドメインのgmailアカウントだけがログインできるwebアプリがあります。
そのアプリに、組織以外の単なるgmailアカウントをログインさせたいです。
そのgmailアカウントを組織に属させることは出来ません。
これを実現するにはどのような方法がありますか？
（GCPコンソールからの単なる設定でいけるもんでしょうか..）

**デフォルトの名無しさん** · 2021/12/07(火) 16:19:21.47

バッチファイルで引数の数に応じた処理分岐はどうやるんでしょう
4個目が記述無しとした場合 %3 == ""
ではバッチが走りませんでした
よろしくお願いします

**デフォルトの名無しさん** · 2021/12/07(火) 16:23:59.93

if not "%~9"=="" goto arg9
if not "%~8"=="" goto arg8
if not "%~7"=="" goto arg7
...

**デフォルトの名無しさん** · 2021/12/07(火) 16:26:45.88

ありがとうございます！

**デフォルトの名無しさん** · 2021/12/07(火) 17:51:38.19

>>344
そのwebアプリの認可ロジックや認可ルールがどう管理されてるかによる
もし認可ルールがGoogleのIAMだけで管理されてるならIAMのコンソールから設定変更で対応可

**デフォルトの名無しさん** · 2021/12/07(火) 18:02:01.86

エラーレベル1を使ったファイル名文字列検索はElseifのように何度も条件分岐するのは不可能ですか？

echo %~n1 | find "検索ワード" 1>nul
if not ERRORLEVEL 1 (
goto process
)

**デフォルトの名無しさん** · 2021/12/07(火) 18:03:02.81

FORで該当の複数ファイルを抽出し、特定のファイルに特定の処理を割り当てたいと思っています

**デフォルトの名無しさん** · 2021/12/08(水) 06:40:17.81

バッチの質問は、このスレではなく、バッチのスレで聞けば？

**デフォルトの名無しさん** · 2021/12/08(水) 19:15:06.24

クライアント側でリソースのIDを決めてPOSTできる仕様のREST APIがあるんだが↓どっちがいい？

URI https://…./hoges/{id}

URI https://…/hoges
BODY { id: “…” }

**デフォルトの名無しさん** · 2021/12/08(水) 19:31:10.56

Ruby on Rails では、scaffold すると、
CRUD で、7つのアクションが出来る

show は、/a/1
edit は、/a/1/edit
など

**デフォルトの名無しさん** · 2021/12/08(水) 20:44:19.89

URIってなもんだから前者でしょう

**デフォルトの名無しさん** · 2021/12/09(木) 09:48:01.08

質問です
Xは、X.aとX.bという値をもつとして
こういうXが多くあり(たとえば10万個)
aまたはbの値が一致すれば同じグループというように分けたいんですが
どうやれば短時間でできるんでしょうか?

**デフォルトの名無しさん** · 2021/12/09(木) 12:41:57.48

素集合データ構造を使います

**デフォルトの名無しさん** · 2021/12/09(木) 14:18:01.94

>>355
X(a, b)と表記するとして
x1 = X(1, 1)
x2 = X(1, 2)
x3 = X(2, 1)
x4 = X(3, 3)
とあったらx1, x2, x3, x4をどういう風にグループ化したいの？

**デフォルトの名無しさん** · 2021/12/09(木) 16:27:01.21

>>357
それだと{x4} 、 {x1 , x2, x3}ですが

**デフォルトの名無しさん** · 2021/12/09(木) 16:35:18.54

素集合データ構造はしらべたんですがよくわかりませんでした
aの値でソートして同一の物をぬきだした後、
それらのbの値と一致するするものを合併すればいいかと思いました
aとbの値でのソートと、二分探索を複数回、くらいのコストになりますか

**デフォルトの名無しさん** · 2021/12/09(木) 16:47:23.50

>>358
じゃ x5 = X(2, 3) が追加されると
{x1, x2, x3, x4, x5}の1グループになるってこと？

**デフォルトの名無しさん** · 2021/12/09(木) 17:24:53.15

>>360
そうです

**デフォルトの名無しさん** · 2021/12/09(木) 18:19:47.02

じゃ>>356が書いてる素集合データ構造使うパターンなので
1回のUnion(a, b)が実質ほぼO(1)で、Xがn個あればほぼO(n)
arrayで実装してる解説を読むといい

**デフォルトの名無しさん** · 2021/12/09(木) 19:35:58.53

ありがとうございます
素集合、ざっくりとはつかめました
つながりを木構造で表し、なるべく高さを抑えるということですか

**355** · 2021/12/10(金) 00:00:29.58

素集合でグルーピングできたんですが
ソートに時間がかかってます

https://ideone.com/hoId2P

**355** · 2021/12/10(金) 00:16:04.56

ソートが遅いのは配列要素が大きく重いからでPHP特有かとおもいました
参照でソートできれば早くなりそうです

**デフォルトの名無しさん** · 2021/12/10(金) 14:06:13.92

DBにでも入れたらgroup byで簡単に出来るのでは？

**デフォルトの名無しさん** · 2021/12/10(金) 17:53:15.64

>>364
ソートは何のため？

**355** · 2021/12/10(金) 20:50:06.85

ソートは同じ値を集める為です
ソートせずにsize * (size-1)のループで値を比較してみたところ、桁ちがいに遅くなります

**デフォルトの名無しさん** · 2021/12/10(金) 21:11:06.33

ソートするのと、ループで値の一致をみる、比較です

https://ideone.com/5y6ZwL

**デフォルトの名無しさん** · 2021/12/10(金) 22:29:17.97

>>368
ソートも2重ループも必要ないよ
ついでにunionするかどうかの条件式も必要ないし
disjoint setのサイズも違うと思う

**デフォルトの名無しさん** · 2021/12/11(土) 00:00:11.77

ふとお題がどっちなのか気になった
x1 = X(1, 2)
x2 = X(2, 3)
もし有向で、a同士が一致しない、b同士も一致しないから同じグループにはしない、という要件の場合、Union-Findの応用で解けるんだろうか

**デフォルトの名無しさん** · 2021/12/11(土) 12:36:32.98

>>371
disjoint setとは別にaとbの各値がどのグループに属するかを配列で管理すればいいと思う

0番目:(1, 2)
a[1] == -1 && b[2] == -1なので a[1] = 0, b[2] = 0

1番目:(2, 3)
a[2] == -1 && b[3] == -1なので a[2] = 1, b[3] = 1

2番目:(1, 6)
a[1] != -1 && b[6] == -1なので b[6] = a[1], union(a[1], 2)

3番目:(2, 6)
a[2] != -1 && b[6] != -1なので root = union(a[2], b[6]), a[2] = root, b[6] = root, union(root, 3)

2番目・3番目の最後のunionはroot設定専用の関数でも可