はてなキーワード: バブルソートとは
Qiitaで下らない記事を見つけたとき、その投稿者のプロフィールを見てみると、高確率で他も下らない記事ばっか書いている。
しかも、そいつらの記事を書くスピードは早い。息するゴミ製造機である。
初学者が学習メモを投稿しているのではなく、当の本人は彼なりの「理解」と「拘り」に基づいて書いていることが伝わってくる。だから、余計に痛々しい。
目立つゴミ記事の特徴は、とにかく実質的に何も説明していないこと。そして、キーワードとキーワードをつないで、技術的なトレンドを把握したような気になっていることだ。
たとえば、明らかにCPUやコンパイラの仕組み、アセンブリ等の知識のない人たちが、「コンピュータは二進法で動いている」みたいな表面だけの全く内容のない記事を量産している。
もちろん「まだ学習途中で、大雑把な仕組みは知っていますが、詳細は分かりません。より詳しく知りたい人はパタヘネとか読んで下さい」とでも言っているなら、まだ好感が持てる。
しかし、ゴミ記事は内容を説明せずに、とにかくたとえ話や関連キーワードの羅列に走る。書いている本人にとっては、それこそがコンピュータの技術を勉強することなのだという気迫と拘りだけは伝わる。それだけに、傍から見るとすごくイタい。
これは検索エンジンのしくみ上仕方ないのだが、そういう記事はSEO効果がめちゃくちゃ高い。何せ、人が検索するようなキーワードが散りばめられているし、馬鹿でも読めるので多くの人がアクセスするから。だから余計に目立つ。本当に迷惑。
こういうのは現実にもいて、色々知っててすげえなあと思って実際会ってみたら、バブルソートとクイックソートの計算量の違いも説明できない人だったみたいなことが幾度となくある。
もう、こういうのやめませんか?誰の得にもなってない。
そういうこと クイックソート系のアルゴリズムは ざっくり最悪値は N^3に近づく場合がある(重複の計算時にもう1回ループをしなければいけない場合があるので3重目のループ=重複計算)がある場合がある それをおしなべると初期は重複木が1でしかないから N^2
いわゆるバブルソートの場合何があっても順列のN*N-1になるけど クイックソートの場合 著しく偏ったソートの場合 偏った木を延々と処理しなければならずメモリ空間がランダムアクセスになっていわゆるIntel系の1次2次キャッシュを破壊してメインメモリから読み出さなきゃいけないからすさまじいスピンアントを引き起こす
圏とアーベル圏についてざっくり調べてみたけどわからんな(当たり前だが)。この後はわかってない人間の勘違いを多分に含んだ与太話だ。
多分計算機は群と関数の集まりだとみなせるんで圏の一種だと思うことはできそう。
ただ、計算機の世界には計算中という状態が存在するけれど、数学は抽象的になるほど状態を気にしないというか、計算が一瞬でできるものの様に扱っていそう。
情報学にはその計算がどのくらいの時間でできるのかということをざっくり表すオーダー(計算量。Oって書く)という考え方があるけど、圏論にもオーダーの概念を取り込んで見ると面白いかも知れない。
例えば、クイックソートとバブルソートをする計算機があったとして、多分普通に圏論の世界で考えると計算機の中身は気にせず結果は同じだから同じ計算機だと考えそうだけど、情報学の世界だとクイックソートはO(n log n)でバブルソートはO(n^2)なんで、同じソート計算機でも別物として扱う。
アルゴリズムはなぜアルゴリズムであって関数と呼ばれていないのか?それは俺も知らんのだけど、関数に計算量の概念を付け加えてみると今まで同じだと思われていたことが実は違ったみたいな話になってますますカオスになるのかも。
実業界で起きる様々な事例を教えるのにソートなど学術的な問題は最適
ソート以外でもこんなにいろいろな事例があるんだよって
言い方を変えれば
なのでアドバイスするとあいてのよさや、やりたいことを壊してしまうことがある。
そのため
速くしてほしい場合などは
XXという条件下でXX秒以内になどという言い方をする
性能条件をいってやりかたはあいてがとくいなものにまかせることがある
最悪なのはクックソートはやいなーとか、クックソートクイックソートなどとつぶやくことである。
こういう場合はクイックソートを使うようになどと指揮命令しなければならない
クイックソート体操!とかいいはじめるひとがめんどくさいと思った業界
べつだんいってくれればやるのにという
↓
だから、外部に良く知られているバブルソートですらN=1,Bigっていう特殊解(一般的ではないが現場では良く使う)がある。
選択用の項目が16個あるだけで6万通りの組み合わせがある。
部品ひとつでそんな感じなものを、1つ1つ大学で教えてもらうような理論を初歩として多数組み合わせて選んで
比較的楽な、オープンソースですら内部をけっこう読み込んでいって合わせこむか、こまないかで
他の職業だってそうだけど、ITは大学で学問があるくらい大変なコース。
みんなと、お話し合いができる簡単なバブルソートでこのざま。もうちょっといくと『木の均衡』とかがでてくるけどこの辺になってくると
アルゴリズムの中でも簡単で有名なソートのなかでも、さらに簡単なバブルソートを見ても
N=1,N=Big Dataのときはそれまでならっていたアルゴリズムどおりの評価式ではなく特殊解になる
ということを学んだ。この辺は だいたい子の量でもしっかり学ぶと大学で1単位か2単位
バブルソートだけ見ても、特殊解はこのN=1,Bigという1組だけではなく、たくさんの特殊な事例があるだろう(構成による)
選択と言うのは2択であったとしても16個懸念要素があったら6万通りぐらい
32個合ったら40億通りぐらいの組み合わせがあるので
とてもじゃないが、総当りでは一般的には終わらない(当然この理屈にも特殊解はアル)
IT分野は、ようするにこういう沢山の基礎知識にもとづいた特殊解の理解が必要になるので
基礎的なkとだけでも、学問として教えると大学4-6年となるし
さて、これでようやく、ITの勉強に入る前に、基礎的なことを教え終わったんだけど
ITの何を教えればいい?
なんでこんなことをいうかというと2週間で作ったものは
自分たちでも3-4週間もあればできるだろうという人が
こういう話をしないといけなくなる業界なので注意
この仕様を作るの大切さにもバブルソート、バケツソートのN=1,Bigは関係する。この辺の問題を教えるのに
ソートアルゴリズムの選び方、例外的な数値をとる場合、などは丁寧に教えて、さらに最適化について簡単に理解したうえで
じゃぁ、どのアルゴリズムが今回は適当か?とベンチマーク結果を参考に決めていく 使用決定について
きちんと学んでおく必要がある。
時間 | 記事数 | 文字数 | 文字数平均 | 文字数中央値 |
---|---|---|---|---|
00 | 70 | 10867 | 155.2 | 33.5 |
01 | 42 | 6540 | 155.7 | 32 |
02 | 39 | 6506 | 166.8 | 53 |
03 | 31 | 2389 | 77.1 | 45 |
04 | 54 | 4121 | 76.3 | 45 |
05 | 19 | 1175 | 61.8 | 31 |
06 | 20 | 5386 | 269.3 | 61.5 |
07 | 43 | 2654 | 61.7 | 31 |
08 | 99 | 6623 | 66.9 | 43 |
09 | 52 | 4907 | 94.4 | 57 |
10 | 82 | 9828 | 119.9 | 34.5 |
11 | 87 | 8823 | 101.4 | 36 |
12 | 101 | 6363 | 63.0 | 43 |
13 | 134 | 8853 | 66.1 | 29 |
14 | 88 | 7149 | 81.2 | 36 |
15 | 131 | 7822 | 59.7 | 42 |
16 | 173 | 14619 | 84.5 | 48 |
17 | 115 | 6583 | 57.2 | 31 |
18 | 143 | 9188 | 64.3 | 28 |
19 | 154 | 11370 | 73.8 | 31.5 |
20 | 159 | 9924 | 62.4 | 26 |
21 | 119 | 8215 | 69.0 | 32 |
22 | 161 | 9371 | 58.2 | 27 |
23 | 188 | 18314 | 97.4 | 42 |
1日 | 2304 | 187590 | 81.4 | 36 |
金婚式(5), ブランカ(6), マギアレコード(3), 実際主義(6), バハムート(3), つたわる(3), バブルソート(7), 書名(3), ドラム缶(3), less(3), 振袖(5), パーティー(8), いちおう(6), ワシ(8), むずかしい(6), 2020年(7), Z(5), 参加者(7), ワイン(5), イケ(6), 依存症(4), 主婦(11), 成り立つ(7), 布団(11), 眼鏡(7), 大学院(6), CD(7), アルコール(8), おじ(9), 捏造(7), フリーランス(7), 調整(13), 専業主婦(14), おもう(22), コーヒー(11), 投資(12), おもっ(17), 1つ(8), 家賃(8), 声優(11), 予約(8)
■42才男性だけど誰か目標を自分に作ってほしい /20200113205934(30), ■無能がTOEIC900点取ってから人生狂った話 /20200114020713(17), ■CDをやめさせるにはどうしたらいいのか /20200114132345(15), ■みんなの東京に居続けるメリットって何なの? /20200114161652(14), ■あなたのメガネを直す前に言っておきたいことがある /20200114111410(12), (タイトル不明) /20200114165359(12), ■安アパートで寒すぎる、どうしたらええんだろ /20200114220825(11), ■好きなことだけして嫌なことを全て避けて生きてみた結果 /20200114132919(10), ■結局セックスするだけの場所なんだろ! /20200114131001(8), ■おっぱいの描写が上手な作家 /20200114175822(8), ■スポーツのループもの /20200114090735(7), ■声優のラジオを聴いてみた /20200114101606(7), ■人と比べないで生きると幸せ /20191126154559(6), ■自分の母親が食洗機とドラム缶洗濯機を買わせない /20200114150533(6), (タイトル不明) /20200114185238(6), ■浅慮で短絡的な奴がよく言う役に立たない解決策 /20200114120516(6), ■他人と仲良くなれるゲーム教えて /20200114175834(6), (タイトル不明) /20100114233157(6), ■日本の大学や企業の研究でコレ凄い!金さえ集まれば世の中変わる!ってのあるの? /20200114215118(5), ■何故腐向けを意識した少年漫画を腐女子は「腐女子向けではない、男にも人気」にしたがるのか /20200114140924(5), ■女を信用できると思うのはどんな時? /20200114115900(5), ■適当に人を殺して自殺したい /20200114065752(5), ■anond:20200114132623 /20200114132926(5), ■娘が化粧したいと言ってくる /20200114134810(5), ■anond:20200113162255 /20200114094004(5), ■不安で眠れないので日記 /20200114011817(5), ■年齢を偽るときは12年単位で /20200113180026(5)
6949563(3742)
なんていうところは
どうしてライブラリを使わないんだ?など
他社の知的財産をうっかり、バグと間違えて聞く事故なんかもある。(理由を答えようとすると智材をいわないといけない)いっても別にいいんだけど
★
ソートがまさにそうだけど、バブルソートの特異領域N=1,Bigがそうだけど(例示)
ソートアルゴリズムも1つじゃなくて、テキストでもあれだけ教えている。
現場ではどうするか?といえば
採択されたものがソースコードに書かれる。それいがいはブランチに合ったりする。
これらがあるので、いわゆるバイナリやリバースからはソースコードの複雑さは推し量れないし
こういう膨大なテストがあったりするので(俺の場合は少ないが)
リバースだけから学ぼうとするな、ソースコードとアセンブリ結果から学べ
というのはそういうこと
いくつかいったけど、コンパイラの最適化を期待したりしてソースを書いたりするので
そういう書き回しをまなんでいくことも重要
ソースだけになw
バケツソート(バブルソートを含むとする)のような単純なソートプログラムを例にとっても
N=1,Bigのときは例外となる。プログラム教育ではこういう例外は良くおきるので準正常系のようなものだが、慣例的に例外と呼ぶ
どうように1,1,1,1、のような偏りの大きいデータにたいしてもソートプログラムは特異な処理時間を必要とする。
ソートは、そのデータの量や質、大きすぎる、小さすぎる、偏りが大きすぎる、小さすぎる
などによって、一般的に言われている特性とはことなる特性を示す。
データや偏りが小さいときはコンパイラなどの最適化により、さらに異なる特性を示すことがある。
一般的にはコンパイラの最適化は気にする必要がないが、こういう例外にはなりやすいので、納品などがある場合は1度確認しておいたほうがよい(アセンブラレベルでコード確認など方法は任意