We use your LinkedIn profile and activity data to personalize ads and to show you more relevant ads. You can change your ad preferences anytime.
QuickSort Killer
We use your LinkedIn profile and activity data to personalize ads and to show you more relevant ads. You can change your ad preferences anytime.
qsortを撃墜し(最悪ケースを与え)てみた。 - 簡潔なQ
glibcのqsortをターゲットに、クイックソートの最悪ケースO(n^2)を与えてみた。 先日の記事の通り、glibcのqsortはマージソートだが、非常に大きいデータのときはクイックソートを利用するので、そのように仕向けてみた。 実行した結果、約5億バイトの配列が確保され、ソートにかかった時間は以下のようになった。 マージソート(非アタック用データ)：37126ミリ秒 マージソート(アタック用データ)：46724ミリ秒 クイックソート(非アタック用データ)：39189ミリ秒 クイックソート(アタック用データ)：中断(507514ミリ秒以上) 明らかに最悪ケースである。 環境は OS: Debian GNU/Linux (sid/unstable) Compiler: gcc version 4.3.3 (Debian 4.3.3-8) C Library: glibc version
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
