YoshikuniJujo

Haskell好き

Public Key

npub1a7y7u324paehw2zdx8jfl3t72ue0ls4etfalxhg0z2gad738savqhxfdm2

NIP-05 Address

YoshikuniJujo@yoshikunijujo.github.io

Profile Code

nprofile1qqswlz0wg42s7umh9pxnreylc4l9wvhlc2u457lnt5839ywklgncwkqpz3mhxue69uhhyetvv9ujuerpd46hxtnfduq3xamnwvaz7tmjv4kxz7tpvfkx2tn0wfnsawm3mg

Publishing to

relay.damus.io

relayable.org

Author Public Key

npub1a7y7u324paehw2zdx8jfl3t72ue0ls4etfalxhg0z2gad738savqhxfdm2

Show more details

Last Notes

2024-11-05 21:15:11

- reply

https://sorabatake.jp/6245/

2024-11-01 08:21:42

- reply

本当は、なんとなくLXCのほうが好きなんだけど、stackageがDockerを使ってるので、Dockerをまずはやろうかと。

2024-10-08 00:52:38

多分「自分が理解できないものを嫌う」という話で僕は保険というものが嫌いなんだろうな。
基本の基本はわかる。たとえば、1000万円持っている人が100人いて、そのうちの1人が全財産を失うとした場合、1人10万円出して、その1人の損失を補填するほうが全体としての幸福度が上がるという話。
限界効用曲線とかそんな感じの経済用語があったと思うけど、990万円から1000万円に資産が増えることで増す幸福度よりも、資産が0円から990万円になることで増す幸福度のほうが100倍以上大きいということが前提条件として、ある。
なので、たとえば、もしも「資産が1000万円に満たない人は強制収容所に送る」みたいな条件が追加されたとすると、上の議論は成り立たない。

2024-10-08 00:40:12

ぬるぽが画像生成 The car racing between ev and hv

2024-10-02 09:51:48

- reply

https://jp.reuters.com/world/ukraine/J4ZZKCLLO5MKJNHMZ7VMVQSRNI-2024-10-02/

2024-10-02 06:21:26

ウクライナについて。
ドネツクを取らせてクルスクを取ったという感じなのだろうけど、若干不謹慎な言い方にはなるけど、たとえば将棋で言うとどんな感じなんだろう。
飛車を取らせて角を取ったという感じなのか。あるいは、たとえば角を取らせて桂馬を取ったという感じなのだろうか。
そのあたりがわからないと、いろいろな記事にいろいろと書かれてる内容について吟味することが難しい。

2024-10-02 01:58:28

食べものとか、凍らせてから解凍すると、変質するのは、たぶん細胞内液が凍結して、細胞膜がやぶれるせいなんじゃないかな。
とくに、リソソームのなかには、いろんな物を分解する酵素が含まれる(たぶん)から、それが周囲のものを分解するってのもあるんだと思う。
ちなみに、寒冷地の植物は冬期には細胞内の水分を減らして、細胞内液の濃度を高めることで、凝固点を下げて、凍結を避けているらしい。

2024-10-01 04:43:45

コードを書くときに、「作る」はmakeとかcreateとかmkとかcrとかで表現することが多い。で、作る前の準備みたいなときにはprepareを僕は使う。で、「作る」だけじゃなくて、いろいろ設定もしますよってときは、provideあたりを使うといいのかもしれない。
英語よくわからないから、適当だけど。

2024-09-27 07:47:49

サーバ証明書とかも1年とか2年とかで無効になるようにするのがベストプラクティスだと思う。秘密鍵は確率論的には「いつかは公開されてしまう」と考えるべきかと。
なので、定期的にアカウントを引き継ぐ仕組みが必要だと思ってる。

2024-09-27 07:39:41

試しに応援して

2024-09-24 05:31:52

- reply

でも、「求人に書くことがない」ってことは、「あまり自慢できることがない」ということで、「ブラックの確率が高くなる」ということは、結果的にはあるのかもしれない。

2024-09-24 05:23:22

JOJOのスタンドで「相手に罪悪感を感じさせることで相手を支配する」みたいなのあったけど、この年齢になると「なるほど」と思う。

2024-09-18 01:17:34

RMSが言っていたことで「なるほど」と思ったことは、「ソースコードが公開されているということは何もプログラマにとってだけの利点ではない」「あなたはそのプロジェクトについてほかのプログラマに修正を依頼することができる」「車の修理を町の修理工場でできるのとおなじ」みたいな話。

2024-09-11 07:17:21

https://www.publickey1.jp/blog/24/mariadbk1ceo.html
MariaDBが買収される(た？)らしい。これはいいニュースなのか、悪いニュースなのか。

2024-09-11 06:51:07

https://jp.reuters.com/opinion/forex-forum/XQRYGRTM7RI2HDCEUPU5UV4HHY-2024-09-11/
日米でけっこう感覚の違いがあるのかな。
「医療は基本的な権利」という発言が「かなり左より」ととらえられるってのは驚きだ。
日本だと当然のことで論点にならないっていう感じがあるのだけど。

2024-09-11 04:06:57

りとりん、ぽいんと

2024-09-11 04:04:46

りとりん、次

2024-09-11 04:03:55

あとGoはチャンネルっていう仕組みが秀逸。Goで使ってみて良かったのでHaskellでもよく使うようになった。
はじめはChanを使っていたのだけど、これは「空かどうか調べる」とスタックして動かなくなってしまうので、どうなんだろうと思ってたのだけど、STM上で使えるTChanでそれは解決した。

2024-09-11 03:56:26

CシャープはC++++みたいに書かないとハッシュタグになってしまうな。

2024-09-11 03:51:14

- reply

C#はマイクロソフトで、Objective Cはアップルってことかな、とりあえず。
Linux派からするとWindowsもMacもあまり変わらないっていう感じがある。

2024-09-11 03:49:14

どっちも書いたことないし、Hello, world!程度のコードも見たことがない。
それもあってC#とObjective Cとを混同していた。

2024-09-11 03:20:28

個人的な意見を言うならば、トランプ氏は「アメリカや世界の病気の原因」と言うよりは、それらの「病気の症状」と言ったほうが当たっているのかもしれない。
何と言うか、「世界をすこしずつ良くしていこう」という動きに対して、「全部破壊してしまおう」という流れだと思う。「理性」というものに対する不信感がある。

2024-09-04 03:26:43

VulkanのTHREADING ERRORの話。完全に解決したわけではなかった。たぶんvkQueuePresentKHRの引数にFenceがないのが問題なのだと思う。

2024-09-04 02:49:49

同期とか非同期とかそのあたりの話で苦労して、コードが荒廃したという。
なんとかうまくいったので、あとはコードのおかたづけをすればいいのだけど、すこし休もうかと。
Vulkanを使うという話なのだけど、たとえばゲームパッドで回転させることのできる「時計」を考える。時計の部分はpangoとcairoを使ってイメージを書き出したうえで、それをテキスチャとしてはりつける。
イメージをvulkanのbufferにコピーしたうえでvulkanのimageにコピーするという処理を行う。この処理がイメージが大きいと0.5秒くらいかかったりする。
で、そのあいだ回転が止まるというのはユーザー体験としては良くない。それでテキスチャの内容の更新を別スレッドにしようとしたのだけど、そうすると「Queueを複数のスレッドから同時に使ってるよ」というエラーが出る。
そのエラーを解消するのにCPU側のセマフォを設定したのだけど、それだけだとうまくいかない。
GPU側に処理を依頼した段階でCPU側は次の処理にうつるので、CPU側がGPU側の処理の終了を待つ必要がある。そのために必要なのがVulkanのFenceだ。
つまり、CPU側でセマフォを用意するだけではなく、GPUをCPUが待つようにするためにFenceも設定しなくちゃならなかったという話。
そして、そこに到達するまでにコードがいろいろとぐちゃぐちゃになったということ。

2024-09-03 01:36:19

- reply

ここで行われている処理に限定の話なので、なにかの参考になるわけでもないけど、画像用のバッファをdestroyしてcreateするのに、1024x1024の画像で0.5秒くらいかかる。で、これはたとえば回転していたものが止まる秒数としては無視できない時間。
512x512の画像だと止まったのがわからないレベル。

2024-09-03 00:15:22

コンピュータが得意なのは数学よりもむしろ「お絵描き」だったという話。

2024-09-02 13:39:04

https://president.jp/articles/-/85384?page=1

2024-09-02 09:14:46

- reply

https://github.com/YoshikuniJujo/test_haskell/blob/986bf4db5728febe5e8b0ab954a5fca18d6a08c0/themes/gui/vulkan/try_using/try-vulkan-rectangles/src/UseCairo.hs#L1571

2024-09-02 09:09:26

Vulkanでゲームパッドからの入力で画像が回るようにしたんだけど、ときどき止まるなと思ったら、texture imageをdestroyしてcreateしている部分で時間がかかっているみたいだった。
画像のサイズは変えないので、この場合destroyしてcreateするのではなく、既存のbufferに画像をwriteする処理にする必要がある。
コードがあまりきれいではないので、わずかにめんどくさい。

2024-08-30 07:58:20

ぬるぽが画像生成 bitcoin puppet

2024-08-30 02:22:16

「物言えば唇寒し」みたいなのって、SNSやってるとよくある。

2024-08-30 02:17:37

foo = do
run1
run2
run3
みたいなとき、run1とrun2を1行で書きたいときに
foo = do
run1; run2
run3
みたいにすることもできるし
foo = do
run1 >> run2
run3
みたいにすることもできるけど、どっちのほうがきれいかな。
僕は後者を書きがちだけど。「do記法を使わないほうがスマート」みたいな感覚はどこかにある。

2024-08-30 01:53:30

RGBAで表現される色をそれぞれについて8-bitの符号無し整数であたえる場合、
Word8 -> Word8 -> Word8 -> Word8 -> RGBA
みたいに「失敗」を気にする必要はないのだけど、浮動小数点数であたえる場合には、
Double -> Double -> Double -> Double -> Maybe RGBA
みたいに「失敗」の可能性を考える必要がある。それぞれの値が0.0 - 1.0の範囲内になければならないので。
0.0から1.0までの実数を表現する型を作れば理論的にはよりきれいなのだろうけど。

2024-08-30 01:47:47

- reply

「実際はさらにもっと長かったりする」のくだりは「言いすぎ」だったかもしれない。今ちょっと見た感じだと長いので
vkGetDescriptorSetLayoutSupport
とか
VkDescriptorSetLayoutCreateInfo
なので、思ったほどは長くなかったかもしれない。32文字か。

2024-08-30 01:40:08

C言語とかだと、
fooapi_bartype_bazsubtype_hoge_piyo_run
みたいな感じの長い関数があったりする(実際はさらにもっと長かったりする)のだけど、Haskellから使うときには、FooApi.BarType.BazSubtype.Hoge.Piyoモジュールのrunとして定義するのが良さそう。そう定義しておけば、
import FooApi.BarType.BazSubtype.Hoge.Piyo qualified as Foo.Piyoみたいにして、Foo.Piyo.runで呼び出すことができるので。

2024-08-30 01:29:31

- reply

https://github.com/YoshikuniJujo/test_haskell/blob/master/themes/hetero-list/try-hetero-parameter-list/src/Data/HeteroParList/Constrained.hs
Data.HeteroParListとData.HeteroParList.Constrainedとに分けているのだけど、「空の型制約」が使えれば後者だけを定義しておけば前者は型シノニムで書ける(と思う)。

2024-08-30 01:17:42

コード書いてるなかで、「もっと抽象化できるのだろうけど、僕の頭ではここが限界」ってところもあるし、「理論的にはもっと抽象化できるのだろうけど、使っている言語の機能的にここが限界」というのもある。

2024-08-29 22:35:11

空の型制約みたいなのがあると、きれいになるコードがあるのだけど

2024-08-29 00:26:04

なんか、SSDの容量の増加が遅い気がする。
そのへんで売ってるノートだと500GBとかだけど、1TBはほしい

2024-08-28 01:23:52

RLS(行レベルセキュリティ)という機能は、なかなか「すてき」な機能だということだけはわかった。

2024-08-28 01:04:05

あの記事、何が問題だったかっていうと、「人の作ったもの」には人の思いがあって、それをサンドバックみたいにあつかっちゃだめってことだ。
MySQLとかって「大き」すぎて自然界にはじめから存在していたかのように見えるけど、それを作ってる人もいるということ。
たとえば三平方の定理をバカにしても傷つく人は多分いないけど、IT分野だと、そういう「自然界にもともと存在していた」かのように見える技術についても、その創始者が生きていたりするわけで。だからリスペクト大事。

2024-08-28 00:29:14

- reply

MySQL vs MariaDBの記事とか読んでみたいな

2024-08-28 00:28:16

MySQLが「どちらかと言うと異端」という話は聞いたことがある。
Postgresのほうが正統的という話だったかな。
あと、SQLiteはなぜか「余計な括弧」を受け入れないので、機械にSQLを生成させるような場合に「やっかい」だという話もあったかな。
うろ覚えだけど。

2024-08-28 00:05:28

- reply

https://zenn.dev/nem/articles/44b3ebbdaaff85
大変そう

2024-08-28 00:00:38

「MySQLで会社が潰れる」という話が今熱いらしい

2024-08-26 04:44:43

https://nishikiout.net/entry/2024/04/08/060000
RISC-Vを命令セットとするGPUを作るみたいな話なのかな。

2024-08-26 04:38:26

生成AIってのの「つまらなさ」ってのは、結局「強いものが力づくで勝つ」みたいな話で、知恵の力で一個人が組織に勝つみたいなロマンがないからだと思う。
でも、学習元になるデータとCPU-GPU時間とがオープンになって、誰もが自分のAIを作れるみたいな話になれば、そこにはロマンがあるかもしれない。

2024-08-23 08:42:37

回転行列を「左からかける」か「右からかける」かによって、回転軸が「世界上の軸」か「物体上の軸」かが決まるという話。
おもしろい。

2024-08-23 02:02:31

- reply

とりあえず無限小回転についてはよくわからないけど、glmのrotateを使って、保存してある回転行列を変換していくというやりかたをすれば目的は果たせるかな。アナログスティックをたおした向きと直交するような軸に対して回転させるようにすればいいわけなので。

2024-08-23 01:47:15

3次元での回転の話、ロール、ピッチ、ヨーの話がまあまあわかりやすいかな。

2024-08-23 01:41:48

- reply

無限小回転/無限小時間を積分するみたいな形で、実際の回転を求める感じなのかな。よくわからない。

2024-08-23 01:37:01

ゲームパッドのアナログスティックの入力によって3Dの物を回転させるのに、横回転と縦回転とを別々に保存して、「横回転させてから縦回転させる」みたいにすると、直観的な動きにならない。
横回転は「世界座標上の軸」で回転するのだけど、縦回転は「その物体上の軸」で回転するみたいな感じになってしまう。
たぶん、「ちょっと横回転」「ちょっと縦回転」「ちょっと横回転」「ちょっと縦回転」みたいにすればいいのだと思うのだけど、ここに無限小回転の考えかたが使えるのかもしれない。

2024-08-23 01:16:43

直交行列っていうものがあるのか。転置行列が逆行列になるようなものらしい。回転行列は全て直交行列らしい。

2024-08-23 01:07:27

- reply

https://hooktail.sub.jp/mechanics/infinitesimalRot1/
これだ。「無限小回転」って言うのか。

2024-08-23 01:06:03

いろんな軸に対する回転は可換ではないのだけど、回転を細かく分けて混ぜ合わせるようにすると可換になるっていう話、わりと好き。

2024-08-22 05:26:52

やまさきたかひろさんもいなくなったの?

2024-08-21 07:06:33

ケリフ選手の性染色体がXYであるという根拠として、IBAという組織が検査内容も明らかにせずに主張しているだけ、という以上の情報が得られないのだけど、それでもネット上では明らかな事実のように扱われてる。
それとも、僕の検索能力の問題で、上記以上の根拠が何かあるのかな?

2024-08-21 02:52:50

ITって言葉の意味、実のところよくわかってない。昔はInTernetを略してITだと思ってた時期ある。

2024-08-21 02:47:49

もちょぴさん、いなくなってしまったらしい

2024-08-21 02:45:02

- reply

プログラミングに適性のある人には、JavaScriptよりもHaskell渡すほうがいいように思う。
まずはHaskell 98の時代の牧歌的なHaskellがいいんじゃないかな。

2024-08-21 02:39:22

プログラミングに適性のある人が、クライアントサイドやって、プログラミングが嫌いになるってのはありそうな気がする。クライアントサイドってのは「あまりに人間的」すぎるところある。
考古学者とかなら好きになりそうな分野かも。

2024-08-20 15:39:08

- reply

マルチメディアカードってのもあったらしい。
これがSDカードの直接の先祖のようだ

2024-08-20 12:21:39

スマートメディア、コンパクトフラッシュ、メモリースティック、xDカード、SDカード
みたいに乱立してたけど、SDカードが全部持ってった

2024-08-20 08:41:44

USBメモリって正確にはUSBフラッシュドライブって名前らしい。たしかに、USBメモリだと、PCの主記憶領域の「メモリ」との性質が大きく異なるものへの命名としてはふさわしくないかもしれない。

2024-08-20 08:31:18

心に何もひっかかりがないときなんて、あんまりないので、何をするかと言えば、足をひきずりながらでも歩くということを学ぶことだ。
目の前がぱっと開けるときもあるけど、たいていは視界は曇っているものだ。

2024-08-20 07:59:09

https://amzn.asia/d/8zunODJ
最近はUSB-AとType-Cの両方の端子があるUSBメモリがあるようだ。PCとスマホの間での情報共有に役立ちそう。
Bluetoothとか使うほうがスマートなのだろうけど、USBメモリのほうが、たぶんかんたんかと。

2024-08-20 03:42:51

ぬるぽが画像生成 battle between Haskell programmer and JavaScript programmer

2024-08-20 03:40:16

PCはそのへんの家電量販店で買うことが多いのだけど、SSDが500GBのものばかりで辛い。1TBはないとつらいのだけど、あまり売ってない。
あとメーカーは以前はNECをよく使ってたのだけど、今はFUJITSU。
USBポートが多くあったりして「わかってる」感じがあるので。

2024-08-19 02:26:44

https://news.mynavi.jp/techplus/article/20240730-2995773/
キヤノンのナノインプリント・リソグラフィに期待してたんだけど、こっちのほうが可能性はありそうかも

2024-08-16 16:01:33

ぬるぽが画像生成 Lisp Olympic

2024-08-16 03:23:11

ぬるぽが画像生成 JavaScript Olympic

2024-08-16 03:22:13

ぬるぽが画像生成 Haskell Olympic

2024-08-16 00:07:37

「クリティカル」って言うのかな、宇宙、軍事、医療、金融の分野のプログラミングはほかの分野とはすこし違うように思う。
ミッションクリティカルとかセーフティクリティカルとか。

2024-08-15 06:56:54

- reply

https://qiita.com/YoshikuniJujo/items/e9639712a49ac0af2a9a

2024-08-15 06:55:16

とりあえず、実時間キューは熱い

2024-08-15 00:24:21

Gentooのインストール、過去の知識で自己流でやってたんだけど、だいぶ知識が古くなったようで、トラブルが増えてきた。
一度、まるっとハンドブックのやりかたでインストールしてみたほうが良さそう。知識のリセットみたいな感じで。

2024-08-13 08:34:32

- reply

あとtop-left, bottom-rightだからtlとbrにしたほうがいい気もするけど、座標の表現を(x, y)みたいにすることを考えると、lt, rbにしたほうがいいような気もする。

2024-08-13 08:28:15

r!next

2024-08-13 08:27:10

上下左右をupper lower left rightとするよりも、top bottom left rightとしたほうが一文字にしたときに、t, b, l, rみたいになるので良さそう。

2024-08-13 06:29:39

https://github.com/YoshikuniJujo/test_haskell/blob/master/themes/gui/vulkan/try_using/try-vulkan-compute/src/TryBitonicsortGpu.hs
バイトニックソートをHaskellでVulkanを使ってGPUにやらせるコード。
400行くらい。VulkanのコードはGPUに働いてもらうために、いろいろと申請用の書類を書く感じで、行数が多くなってしまう。
末尾のGLSLのコードをp, qを設定したうえで、iを0から要素数まで変化させて実行するみたいなのを、必要なp, qの組に対して行っている。
速度はメモリのコピーなども含めると、クイックソートよりすこし遅いくらい。

2024-08-11 09:45:07

- reply

「もし自分の帽子の色が青だったら、ほかの人たちにとってはn-1の場合の同様の問題になる」というのがこの問題のポイントというわけか。

2024-08-11 09:26:45

- reply

成立する。おもしろいな。
自分の帽子が青だった場合に、残りの人にとっての問題がn-1のときの同様な問題になるってことか。
もとの問題をすこし修正して書くと
三人の賢者が赤い帽子をかぶせられてて、自分の帽子の色はわからない。もしかすると青かもしれないと言われている。
そこで、全員に少なくともひとりは赤い帽子をかぶってるとつげて、そう全員に告げたということも知らせる。
そして、一日に一度「自分の帽子の色がわかったか」と尋ねる。尋ねる前には他の二人が前日にわかったと答えたかどうかも知らせる。
その場合、賢者たちは自分の帽子の色がわかるかという話。

2024-08-11 08:24:13

三人の賢者と帽子の話、4人以上でも成立するのかどうか、僕にはよくわからない。

2024-08-10 10:56:29

- reply

https://qiita.com/YoshikuniJujo/items/e9639712a49ac0af2a9a
昔書いた記事の一部に銀行家キューの説明があった

2024-08-10 10:46:14

- reply

すくなくとも銀行家の方はちがったようだ。
むしろ、「積み立て」ではなく借金にすることで、償却時間を保証する感じのようだ。

2024-08-10 10:28:03

- reply

よくわかってないけど、銀行家法は計算量がすくない処理のときにつみたてておいたぶんを、計算量の多い処理のときに使うって感じなのかな。
そして、物理学者法ってのは、データ構造の中にたまる「処理の重くなる構造」の総和が一定以上にはならないみたいな感じかな。

2024-08-09 05:13:18

https://www.peyoung.co.jp/products/000005.html
ペヨングは安い。100円くらい。

2024-08-09 05:11:52

ならし計算量の話で、銀行家法と物理学者法とがあるらしいのだけど、よく知らないので、どうちがうのかもわからない。

2024-08-09 04:36:36

- reply

https://github.com/YoshikuniJujo/test_haskell/blob/master/algorithms/try-algorithms-for-sns/src/Algorithms/Dijkstra/Heap.hs
ふたつめはこれ。
ヒープ関連のコードを外に出したのもあって、かなりシンプルに書けた。
これはちゃんと関数プログラミングできてる。
ヒープはAlgorightms.Heap.Skewで定義してある。
https://github.com/YoshikuniJujo/test_haskell/blob/master/algorithms/try-algorithms-for-sns/src/Algorithms/Heap/Skew.hs

2024-08-09 04:33:05

- reply

https://github.com/YoshikuniJujo/test_haskell/blob/master/algorithms/try-algorithms-for-sns/src/Algorithms/Dijkstra/Orig.hs
ひとつめはこれ。暫定的な距離を保存する構造をリストではなく配列にした。配列の要素の置換が必要なので、STモナドを使ってimperativeに書いた。

2024-08-09 04:30:37

ダイクストラ法の実装を修正した。2つの方向で修正した。
ひとつめとしては、オリジナルのダイクストラ法のロジックを踏襲するもので、O(V ^ 2)になる。
この場合、コードはかなりimperativeなものになる。
ふたつめは、ヒープを使う方法。これだとO((V + E) log V)になる。密なグラフだとEがO(V ^ 2)になるので、O(V ^ 2 log V)になって、実行効率はわずかに低下する。
ヒープにはskew heapを使用した。

2024-08-09 03:19:30

- reply

とりあえずskew heapを実装してみようかな。理論は難しそうだけど実装はまあまあ簡単そうなので。

2024-08-09 03:10:30

- reply

http://www.nct9.ne.jp/m_hiroi/func/haskell23.html
leftist heapとかskew heapとかがあるらしい。

2024-08-09 02:57:26

- reply

ヒープって概念的には「木」なのだけど、「配列」として実装したほうがシンプルで効率的になるという、なんか不思議な性質があるな。

2024-08-09 02:49:38

- reply

バランスを取るように作ったり削ったりするのがそもそもヒープの特徴ってことか。配列を使ったヒープは実装したことあるけど、木を使ったヒープはちゃんと書いたことないかもしれない。

2024-08-09 02:45:38

そういえば、ヒープの木としてのバランスってどう取るんだったかな。

2024-08-08 09:23:56

- reply

あ、この実装だとだめかもしれない。キューにごみがたまっていって、dequeueの効率がO(n ^ 2)とかになりそう。キュー(実際にはキューではないけど)を配列で実装しないとだめかも知れない。

2024-08-08 08:47:52

実用上、O(log n)はO(1)とほとんど変わらないと考えていいように思う。実用上は。

2024-08-08 08:45:45

- reply

オリジナルからヒープを使ったものに変更する場合には、グラフの表現を配列の配列ではなく、リストの配列にして、enqueue, dequeueをヒープを使ったものにすればいい。

2024-08-08 08:36:34

ダイクストラ法はオリジナルのものとヒープを使ったものとがあって、グラフが疎な場合には後者のほうが速い。
グラフが密になってくると、前者がO(n ^ 2)なのに対して後者がO(n ^ 2 log n)みたいに計算量が増える。
けど、実用的な見地からは、だいたいのグラフは疎な気がするし、さらに密な場合でもn ^ 2にlog nをかけたからって、焼け石に水というか、象に蟻を乗っけるみたいな話なので、たぶんヒープを使うもののほうが、実用的にはベターなのだろう。