  |
はてなキーワード: クイックソートとは
ワイ：
ChatGPT：
基数ソート（Radix Sort）は、分割統治法（Divide and Conquer）を利用しているとは一般的には考えられません。基数ソートは、数値や文字列などのキーを持つ要素を、そのキーの各桁について個別にソートすることによって全体をソートするアルゴリズムです。通常、最も下位の桁から始めて、各桁について安定ソート（たとえばカウンティングソートやバケットソート）を適用していきます。
分割統治法は、問題をより小さなサブプロブレムに分割し（Divide）、それらのサブプロブレムを解決して（Conquer）、最後にサブプロブレムの解を統合して（Combine）元の問題の解を得るアプローチです。典型的な分割統治法のアルゴリズムには、クイックソートやマージソートがあります。
基数ソートはこのアプローチに従わず、代わりに全体のデータセットに対して桁ごとのソートを繰り返すことで全体をソートします。各桁のソートはデータセット全体に対して行われ、データセットをサブプロブレムに分割してそれぞれを独立に解決し、後で統合するというプロセスはありません。そのため、基数ソートは分割統治法を利用しているとは一般的には見なされません。
ただし、基数ソートの各ステップでサブプロブレムに分けることなく全体のデータセットに対して操作を行うという点で、分割統治法の概念の一部と見ることができるかもしれませんが、これは分割統治法の典型的な使用法からは逸脱しています。
ワイ：
ChatGPT：
基数ソートを上の桁から開始して同じキーを持つグループに分割し、階層的に並べていくというアプローチは、実際には「Most Significant Digit (MSD) Radix Sort」と呼ばれる基数ソートのバリエーションであり、有効な手法です。MSD基数ソートは、最も上位の桁（Most Significant Digit）から始めて、各桁ごとにデータをグループ化し、それぞれのグループに対して再帰的に同じプロセスを適用していきます。このアプローチは、ある意味で分割統治法の考え方を取り入れています。
分割: 最も上位の桁に基づいてデータを複数のバケット（グループ）に分割します。各バケットは同じ桁の値を持つ要素を含みます。
統治: それぞれのバケットに対して、次に下位の桁に基づいてソートを再帰的に適用します。これにより、各バケット内の要素がさらに細かく分類されます。
結合: 最終的に、すべてのバケットを順序通りに結合して、ソートされた全体のリストを得ます。
このアプローチでは、データセットをサブセットに分割し、それぞれのサブセットに対して問題を再帰的に解いていくという分割統治法の原則に従っています。ただし、MSD基数ソートは、分割統治アルゴリズムの典型的な例（マージソートやクイックソートなど）とは異なり、再帰的な過程でサブセット間の「統合」ステップが必要ありません。各再帰的なステップでのソートが完了した時点で、要素は既に部分的にソートされた状態になっているため、最終的な結合は単純なリストの連結に過ぎません。
MSD基数ソートは、特に固定長のキーを持つデータや、文字列などの可変長データをソートする場合に有効な手法です。しかし、このアプローチは、特にキーの分布が均一でない場合や、データセットが大きい場合には、メモリ使用量が大きくなる可能性があるため、実際の使用状況に応じて適切なソートアルゴリズムを選択することが重要です。
分割統治法じゃん。
取り上げた技術は、本格的な開発でも役に立つもので、最も学習コストが低いものを選んだ。
重要度が低いものは載せていない。たとえばHTMLとCSSなんてググりながら書けば全く問題ない。Bootstrapなどのフレームワークも全くやる必要はなく、仮に就職先で使っていたら覚えればいい。
逆に言えば以下に挙げる技術は、そもそも概念自体がプログラミングにとって普遍的なものであり、（基礎的な部分を）調べながら使うようではエンジニア失格ということ。
基本的に現在では、バックエンド・フロントエンド・運用保守全てができないエンジニアに価値は無い。
以下に挙げた技術（①⑤⑥は他の言語やフレームワークで代替可能）が身に付いていなければまともな企業に就職することは難しい（もちろん、下らない業務システムを下請けで作ってる底辺企業には入れるだろうが）。
経験者でも、これらができない/わからないのは、相当恥ずかしいことだと思った方がいい。
特定の言語やフレームワークの書き方を知っていること自体に意味は無い。
重要なのは、他の言語やフレームワークにも共通する基礎を理解すること・保守性やセキュリティなどの品質を高める使い方ができること。
この2つは習得が容易だし、今覚えておけば向こう10年腐ることはないだろう。
基本的な構文や、よく使う標準ライブラリは勿論、高階関数・クラス・非同期処理等の発展的な機能も知り尽くしていなければならない。
言語のみではなく、パッケージ管理、単体テスト、タスクランナー等の周辺ツールの使い方も熟知している必要がある。
また、「リーダブルコード」や「コードコンプリート」に書いてあるような良い作法も身に付ける必要がある。
Gitを使えないのはプログラマーとして論外。細かい機能は調べればよいが、
多くの場合、本番環境やテスト環境はLinuxサーバーであるから、以下のような基本的な概念と使い方を知っておく必要がある。
環境構築、CI、デプロイなどは、現在コンテナを使って行うことが当たり前になっている。
これも細かいことをすべて覚える必要はないが、Dockerfileの書き方や、docker-composeの使い方などは知っておかなければいけない。
Flaskは、数あるWebフレームワークの中で最も簡単。本当に呆れるほど簡単で、Pythonさえ書ければすぐにアプリを作れる。
フレームワークを覚えること自体が重要なのではなく、Web開発の基本を習得することが重要。HTTP、ルーティング、データベース、SQL、認証、セッション管理などは当然すべて覚える。
データベースは、就職したらMySQLやPostgreSQLなどを使うことが多いかも知れないが、今はPythonの標準ライブラリにあるSQLite3を使えば十分。
作ったアプリを公開したければ、「Heroku」などにデプロイするのが良いだろう。
ブコメで指摘をいただきました。HerokuではSQLite3は使用できないようです。公式のドキュメントに従ってPostgreSQLを使用して下さい。
SQLite3はファイルにデータを持てる簡易DBなんだけど、Herokuにデプロイしてもストレージ的な使い方はできないから、結局PostgreSQLを使う必要あるから注意してね。（DAOを丸ごと書き換える羽目になる）
参考: https://devcenter.heroku.com/ja/articles/sqlite3
今の時代、フロントエンドをフレームワークなしで作るのはただのバカ。
2021年現在、実用的なフロントエンドのフレームワークはReactとVueしかない。Vueの方が少し簡単なのでこちらを選んだが、JavaScriptをしっかり理解しているなら大差は無い。
フロントエンドには膨大なパッケージ群があって全部覚えるのは大変だが、とりあえずまずはVueを完璧に使えればいい。Webpackの設定などは既存のものを流用すればいい。
アルゴリズムは全てのコンピュータ技術の基礎であり、絶対に知っていなければならない。
高速フーリエ変換のような高度な数学は必要ないが、クイックソートや木構造のような基本的なアルゴリズムは当然、その性質を知っていなければならない。
それらは言語の組み込み関数や標準ライブラリでも使われており、理解していなければ、それらの機能を正しく使うことができない。
また、プログラムを読み書きする際には、そのコードの計算量を見積もれなければならない。
セキュリティは言うまでもなく学ばなければならない。
有名な脆弱性や攻撃手法（XSS・SQLインジェクション・CSRFなど）が何だか理解していて、その対策を実装できなければならない。
各種暗号化技術や署名などについても、実装の詳細は知らなくていいが、共通鍵暗号や公開鍵暗号などの特性は理解する必要がある。
駄文なので最初にまとめておくと、知識ゼロ異業種から転職して何とかエンジニアとしての人生を始めました、という話。経歴がショボすぎて誰かの道標にすらならないだろうけど書き残しておく。実名で書く勇気はないので増田にて失礼。
PCを初めて触ったのは4歳の頃。
黒くてごついボディが幼心にぐっときたのを覚えている。この記憶があったためか、初めて自分で購入したPCはThinkPadだった。
我が家にインターネット開通。深夜に親が寝てからこっそり2chとニコニコ動画を見ていた。PS2でドラクエ8をやってグラフィックに感動する。まだプログラミングという言葉は知らない。母親のヒステリーと父親の拳骨に耐える日々だった。
地元の高校に進学。友人とﾎﾑﾍﾟ(死語)を作成。html/CSSで文字の色か変えられたりアニメーションをつけられることに気付く。この頃もまだプログラミングに目覚めない。プログラム？理系の人がやるお仕事なんでしょ？という雑な認識であった。
もちろん文系学部に進学。人の視線が怖かったので前を向いて歩けず会話もままならなかったが、制服が可愛いという理由だけでお洒落カフェでバイトを始める。私は阿呆だが、この阿呆さないしは無鉄砲さでエンジニアになったと言っても過言ではない。
新卒入社した会社を3ヶ月で退職。支えてくれる彼くんとかもいなかったので実家でお通夜してた。鬱も発症して薬漬けになった。対面で人と話すことが難しいため、テキストベースで仕事ができる職を探し始める。ここでやっとプログラミングに出会う。
何にせよ無職だから時間は腐るほどある。ヨドバシでカモ丸出しの顔をしてThinkPadを買い、Javaで簡単なアルゴリズムを実装することから始めた。フィボナッチ数列を生成するとかクイックソートを実装するとか。あと5日ぐらいかけてServlet/JSPとMySQLでTODOリストを作った。
2ヶ月ほどJavaをやった頃、無謀にも機械学習に手を出し始める。本を一冊買って隅々まで読み込んだ。この頃から鬱が寛解し始める。プログラミングに夢中になって、1日12時間以上はPCの前に座ってひたすらコードを書いていた。不思議と疲れはなかった。ゲーム用に買ったデスクトップPCにそこそこ良いGPUがついていることが判明したので、Tensorflowでモデルもどきを作り、AI（笑）を組み込んだポートフォリオ用webアプリを3ヶ月かけて作成した。サンプルコードを超える範囲はドキュメントを読む、適宜技術書で知識を補うなどしてなんとかオリジナルと言えるコードをひねり出すこともこの頃覚えたと思う。なお肝心のモデルはチューニングは一切していないわ当然精度も悪いわでその筋の人が見たら鼻で笑うレベルであるが、一人でアプリケーションを作り切ることができたのは大いに自信に繋がった。
ポートフォリオを持って5社ほど受け、うち1社の小さな受託系企業に内定を貰い、無事職にありつくことができた。文系未経験第二新卒を雇う勇気を出してくれた会社には感謝しかない。
会社規模が小さいからか、個人の裁量が大きく、設計から実装、テストまで何でも任せてもらえた。良き上司に恵まれ、主にUnityやスマホアプリの開発を担当し、技術の奥深さ面白さに触れさせてもらった。自身が実装を担当したアプリが世に出ていくことの喜びみたいなものも味わえた。この会社は昨年度退職し、現在は500人規模の自社開発系企業でiOSアプリエンジニアをやっている。スキルは未熟だし対人恐怖的なものも治ってはいないけど、私はプログラミングが好きで、エンジニアとして骨を埋めたいとか身の程知らずにも思っている。
ご覧の通り、私は幼い頃からプログラミングに触れたりモノづくりをしていたわけではない。むしろ目覚めは遅い方である。そういう人でも興味があるなら、ITエンジニア目指してもいいんじゃないか、そうであってくれ、という気持ちで書いた。読んでくれてありがとう。プログラミングはいいぞ。
メモリを使わないようにする バケツソートなどのアルゴリズムにたいして
ヒープソートなどヒープを使う
クイックソートなどようにツリーを使うなどメモリを使うと高速化される。
他方当然ではあるが、メモリーは有限のリソースであるから、メモリーを、ある一定以下におさえつつ、高速なロジックという考え方がある。
速度優先アルゴリズム
という２つの考え方が生まれる。メモリはどんどん消費しても良いから高速に完了すれば良いという考え方と、ある一定以内にメモリ消費を抑え、速度の高速化を目指すというものである。メモリを追加で消費しないことという制限条件が付くと、バケツソートもなかなか、すぐれたアルゴリズムである。
これを、あたまにいれないといけない。
アルゴリズムというものは、どういう条件下の場合、最速という考え方があり
さまざまな条件、それこそCであるアンドロイドであるサーバマシンであるなどにより、違ってくるので、機材に合わせて、調整するという仕事が必要になってくる。
