スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

C++で基数・バケットソートを実装したら速いのか?

はやいの?


事前知識

32bit整数をソートすることにする。
下位から4bitごとにバケットソートを行う。(よって、N=8)
データ数N。

基数・バケットソートの計算量%$O(MN)$%
クイックソートの計算量%$O(N \log(N))$%


STL君(quicksort) 1.47s



基数バケットソート 3.01s



だめじゃん・・・これ。

queueに突っ込んで、追い出して…あたりのメモリ操作に時間喰われている感じでしょうか?


基数要素を排除したバケットソート(0-255)なら何とか超えました。整数範囲がかなり制限されてしまいますが。
バケットソート 1s
http://ideone.com/za0Vxp 1文字変えただけなのでURLだけ


このくらいの差ならstd::sortで十分そうですね。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

ブログ移転のお知らせ
ブログをshonen.hateblo.jpに移転します. 新規の記事はこちらに投稿します.
プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
635位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
94位
アクセスランキングを見る>>
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。