VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
458(1): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)00:07 ID:iZGlVtrY(1/7)調 AAS
バブルソートの一本槍でどこまでいけるか試してみたい
そう口にするピッコロの眼差しは熱を帯びて筆者は思わず
手元にあったアイスコーヒーを飲んだ
とたんその冷たさに喉奥が刺激されさきほどまで感じていた
眠気は完全に吹き飛んだ
筆者が感じていたなんとも形容しがたい漠然としたけだるさは
活力を失っていたからだそのことには自分でも気づいていたが
どうしようもないものだと諦めてもいた
だがピッコロの熱い眼差しに射すくめられて自分に足りなかったものが
いまはっきりとわかった
――挑戦を諦めない不屈の心――
不撓(ふとう)という言葉がある
どのような困難にあっても屈しないこと
今風に言えばフィジカルが強いこと
諦めるという言葉そのものが自分を弱くしていたと気づいた
これがピッコロと対談して筆者が感じたすべてだ
バブルソートを口にするピッコロの眼差しは魔貫光殺砲だったのだ
筆者はそれに貫かれた
461(1): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)02:10 ID:iZGlVtrY(2/7)調 AAS
>>456
O(2n)の実装があるならすごいと思ったし
それを知りたいと思ったから教えてもらうのが良いと思ったんだよね
どういうアルゴリズムかわかってないのにそれはダメと指摘するのはキチガイじゃん
ピッコロはキチガイじゃないから教えてもらおうと思ったの
462(2): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)02:10 ID:iZGlVtrY(3/7)調 AAS
>>456
>>419の問題はソートがどうしようもないんだよね
ソートがあるから計算量の限界はn*log(n)になるかと
それはそれとして計算量はデータ量が増加したときに
計算資源の消費量がこういう比率で増加しますってものだから
あくまでもデータ量とセットで考えてこそ意味があるものだよ
一般的に計算量がよいアルゴリズムはデータ量が少ないときに時間がかかる傾向があって
たとえばクイックソートの平均計算量はn*log(n)で挿入ソートの計算量はn^2だけれども
件数が少ないときは挿入ソートの方が速い
各種標準ライブラリのソートでも要素数が少ないときは挿入ソートが使われてて
挿入ソートを使うときの閾値はライブラリによってまちまち
.NETは16以下
https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/ArraySortHelper.cs
Javaは46以下
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/DualPivotQuicksort.java
FreeBSDは6以下
挿入ソートじゃなくてノームソートになってるけどまあ似たようなものだしまあいっかということで
https://github.com/freebsd/freebsd/blob/master/lib/libc/stdlib/qsort.c
Rubyはソースをきちんと追えなくて不確かだけれども
FreeBSDのqsortを使ってるっぽい気がする
今回の問題の要素数は6なので挿入ソートが最適かと
計算量はn^2で良い
465(1): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)02:17 ID:iZGlVtrY(4/7)調 AAS
>>460
C教えてもらえますか？
468(1): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)03:29 ID:iZGlVtrY(5/7)調 AAS
>>467
勉強になります！
もしよろしければそのソースコードどこで見れるのか教えて欲しいです
472(1): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)21:09 ID:iZGlVtrY(6/7)調 AAS
>>471
まあちょっと落ち着いていただいて
∧＿∧
(´･ω･) _｡_ ﾄﾎﾟﾄﾎﾟ
/ つ つc(＿_ｱ?
しーＪ 旦〜
473(1): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)23:30 ID:iZGlVtrY(7/7)調 AAS
>>471
一般的なソートの計算量の限界はn log nだよ
計算量はデータ量が増えていったときに
この式の値は誤差みたいなものだから無視できるよね
っていうふうに考えて式を消してくもの
n*は省いたら値が全然違ってしまうので省けないの
計算量にはデータ量の増加を考えて消された定数項があって
計算量の良いアルゴリズムは往々にしてその隠れた定数項が大きくて
データ量が少ないときに計算効率が悪い傾向があるんよ
クイックソートもその一例
「少ない」件数は例に示したとおりで
ソートでは6〜46が閾値として有名どころのライブラリで使われてるよ
今回の問題に限ったことではなく
計算量の話をするときはデータ量も一緒に議論する必要があるんよ
たとえばお仕事で大量のデータを処理するから効率の良いロジックを
組んでくれと言われて計算量のよいアルゴリズムを実装したけれども
サーバーの処理が遅くレスポンスの遅延が常態化してしまった
調査してみたら要素数の少ないデータを大量に処理していて
計算量の悪いアルゴリズムを使ったら改善されたなんてことも起こり得るよ
計算量はデータ量とセットで考えるこれ大事
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.540s*