アルゴリズムが苦手な上、アルゴリズム解説自体C言語ベースで書かれ
ている物が多く処理のイメージが沸かずクイックソートもコピペや既存
の関数で処理していて、満足に理解出来ていないのですが。
以下の問題を、お解かりになるかた教えて頂けませんでしょうか?
■問題
2万件位の数値データの中から重複要素を削除しながら昇順または降順で、
ソートするアルゴリズム(※1)
■条件
BASIC的(※2)な記述やプログラム中のコメントなどの形式でも構いま
せん出来るだけ簡単に示して頂けると助かります。
補足
(※1)ソートする際、重複要素を消すともっと処理が早くなるのではと
思ったので。
目的は、処理の速さを求める事と、次回から応用が聞くよ
うにソート自体を理解したいのでクイックソートで無くても構いません。
(※2)実際に動かなくても構いません、イメージが掴みやすい方が良いと
いう意味でとって下さい。
No.8ベストアンサー
- 回答日時:
>pythonで実行してみたのですが、うまく行きませんでした。
>2行目のIf文でエラーが出るようです。
投稿するとインテンドがきえてしまいました。以下のタブをタブに替えてください。
def qsort(list):
タブif len(list) != 0:
タブタブlt_list = [x for x in list if x < list[0]]
タブタブgt_list = [x for x in list if x > list[0]]
タブタブreturn qsort(lt_list) + [list[0]] + qsort(gt_list)
タブelse:
タブタブreturn []
>他の言語で置き換えようと調べてみたのですが、
>以下の解釈が解からないためよろしければ、教えて頂けるとありがたいのですが。
>3行目、4行目→x for x in list if x
これはpythonのリスト内包表記といって配列の中からある条件の配列を取り出しています。
gt_list = [x for x in list if x > list[0]]
はVBでいうと
for each x in list
if x > list(0) then
gt_listにx追加
end if
next
と同じです。
>ちなみに、以下は
>qsort(lt_list) + [list[0]] + qsort(gt_list)
>ソートと重複削除済みのリストが戻されると解釈して良いのでしょうか?
そうです。[list[0]]にはひとつしか値が入らないし、
lt_list,gt_listにもlist[0]と同じ値は入ってませんよね。
No.7
- 回答日時:
クイックソートで同じもののリストを真ん中で足さずに
ひとつだけにしてつなげれば、そのまま重複削除になります。
pythonの例です。
def qsort(list):
if len(list) != 0:
lt_list = [x for x in list if x < list[0]]
gt_list = [x for x in list if x > list[0]]
return qsort(lt_list) + [list[0]] + qsort(gt_list)
else:
return []
samplelist=[8,4,5,2,4,7,8,4,4,1]
print qsort(samplelist)
ここで以下はlist[0]よりも小さい値を集めた配列です。
[x for x in list if x < list[0]]
有難うございます。
pythonで実行してみたのですが、うまく行きませんでした。
2行目のIf文でエラーが出るようです。
他の言語で置き換えようと調べてみたのですが、
以下の解釈が解からないためよろしければ、教えて頂けるとありがたいのですが。
3行目、4行目→x for x in list if x
ちなみに、以下は
qsort(lt_list) + [list[0]] + qsort(gt_list)
ソートと重複削除済みのリストが戻されると解釈して良いのでしょうか?
No.6
- 回答日時:
★ソート後について
・重複チェックは2万件のデータを1回順番に調べ重複した値は 0 に書き換えます。
2回目のシークで 0 以外は詰める処理を行えば良いでしょう。
こうすれば重複するたびに削除詰めしなくて良いので早くなります。
・なお、この場合は2万件のデータで 0 という値が無いことが前提です。ある場合は
ソートの最初が 0 ならゼロ有無フラグを ON にして削除詰めの時に最初の 0 は詰めない
ように工夫すればよい。その他、数値データで絶対利用しない値を『重複』で削除用の
値に使えば良い。
・以上。
お陰様で、アルゴリズムの方も理解できそうな所まで来ました。
>こうすれば重複するたびに削除詰めしなくて良いので早くなります。削除詰めの回数を減らせば良いのですね。
どういった処理が遅くなるのか解かっていませんでした。
> 0 という値が無いことが前提です。
0と言う値はありますがある事が解かっているので消しても構いません
後から付け足せます。
>★ソート後について
と言う、事なのですがソート前では、無いのでしょうか?
どちらにしろ、今のレベルではアルゴリズムをソートと重複
削除に別けるしか無いようですね。
結果を報告できればと思いますので、
このスレは、2~3日締め切りせずに置いときます。
有難うございました。
No.5
- 回答日時:
クイックソートを前提にすると, 「分割するときにピボットと同じ値がいたら消す」という処理と「部分列のソートが終わったあとで詰める」という処理をしなきゃならないですね. 素直に「単純にソートしてから重複した要素を消す」のとあんまり処理時間はかわらないような気がします. 下手すると, 移動時間が増える分だけ処理時間が長くなる可能性があります.
「ソートしつつ重複要素を消す」のなら, 一番簡単なのはマージソートじゃないかなぁと思います. マージするときに「同じ要素があったら一方を捨てる (もう一方は自動的に移動すればよい)」だけで済むので. もっとも, 配列でマージソートをしようとするとメモリを使う可能性があるのでリストの方が安全な気はします.
ヒープソートも, ちょっと今一つって感じがします. クイックソートと同様, 「不要になった要素を捨てて残った要素を詰める」処理がどのくらい時間を使うかの勝負です.
う~ん, やっぱり「後処理として重複した要素を消す」のが安全な気がします.
ありがとうございます。
>「後処理として重複した要素を消す」のが安全な気がします
なるほど、どちらに組み合わせた物をつくってみて、
その上でパフォーマンス改善を考えてみたいと思います。
現状
言葉では、解かっているつもりなのですが、プログラムが正しく
動きません^^;
まずは、マージソートだけに絞ってみます。
No.4
- 回答日時:
1)数値データテーブルと同じサイズのフラグ用テーブル
を準備して通常のソート手順でソートを行い、フラグ用
テーブルの並べ替え処理も同時に行う。
2)比較時に数値の値が同じ且つフラグ用テーブルの値が
共に初期値の場合には、片方に削除フラグをセットする。
3)ソート終了後にフラグ用テーブルに値がセットされて
いないのと同じ添字の数値データのみを出力。
具体的な手法を提示して頂きありがとうございます。
しかし、現時点私の理解度では何故そうするのか?
どのソート法に対しての回答かすら解かっておりません。
ソートと重複処理を分けて考える手もあるのですが
重複処理を組み合わせるとアルゴリズム自体の構造が
変わってしまう気がして二つの問題を組み合わせた
プログラムを動作検証をして理解したいのですが。
よろしければ、引き続きご教授下さい。
No.3
- 回答日時:
>重複判定とソート2つの比較演算を同ループ内で行うと
>スワップ回数が減らせて処理が少なくなるとイメージしたのですが、
まさに、その通りでして、それを行うには、#1で書いたように、ソートのアルゴリズムを、ヒープソート、マージソート等にする必要があります。
ソートのアルゴリズムとしてクイックソートを使うと、重複判定とソートを同時に行うことができません。(できませんはいいすぎか。少なくともかなり厄介になると思います。)
まずは、いろいろなソートのアルゴリズムを勉強されてはどうでしょうか。
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC% …
http://www1.cts.ne.jp/~clab/Contents/Sortindex.h …
度々、ありがとうございます。
アルゴリズムが理解できなかったので(解かってるような解かってい
ない様な)、コードを入力して動作検証したいと思っていたのですが。
C言語が使えないため、ベーシックのフローを頂けると自作できると
考えて投稿したのですが。
>厄介になると思います。アルゴリズムの比較演算のパターンを
改良しないといけないと言うことですね、確かに複雑そうです。
クイックソートが一番早いと思いますのでクイックソートで実現した
かったのですが、今のレベルでは無理そうです。
教えて頂いた、マージソートやヒープソートも解説見たのですが、
やはり、自己でコードが組めず動作検証まで至っておりません。
何処が解かっていないかも、うまく説明できませんが、
標準的な「BASICコード」なら動作イメージが出来ますので、
図々しいお願いですが、教えて頂けませんでしょうか。
●重複処理の部分はこんなイメージですが
for i = 0 to 最大配列数 - 重複回数
while data[i] = data[比較対象データポインタ] //重複が無くなるまで
data[比較対象データポインタ] = data[最大配列数] //最後尾と入替
data[最後尾] = null //重複内容削除
重複回数 = 重複回数 +1
end-while //重複判定ここまで
ソート処理 // ※ヒープ?マージ?
i = i + 1
next
No.2
- 回答日時:
>以下の処理では、動かないですかね、
もちろんOKですけど、「重複判定」てのはどうやるつもりですか?
n番目の要素が重複要素かどうか調べるには、もっとも単純にやれば、1番目からn-1番目の要素を全て調べる必要があります。
これをやるのは、ほとんどソートするのと同じくらい大変です(処理時間がかかる)
この回答への補足
我ながら、意味が不明だったので補足させてください。
※重複判定とソートのループを組み合わせる。
重複判定とソート2つの比較演算を同ループ内で行うとスワップ
回数が減らせて処理が少なくなるとイメージしたのですが、
そういった、問題ではないのでしょうか?
ソートのアルゴリズムが頭に入っていないので、なにを言ってるの
的な質問になってたら申し訳ありません。
>「重複判定」てのはどうやるつもりですか?
重複判定とソートのループを組み合わせる(同じループ内で)、
アルゴリズムて出来ませんでしょうか?
No.1
- 回答日時:
>重複要素を削除しながら
これは大変そう。
クイックソートだと、削除した要素の分の空き詰めるのは難しそうです。分割統治なんで、自分と関係ない部分でいくつ要素が削除されたかを知る方法がない。
速いソートが望みなら、マージソート、ヒープソート等であれば、重複用の削除をしても、それほど処理に影響を与えないでできると思われます。
>クイックソートだと、削除した要素の分の空き詰めるのは難しそうです。
以下の処理では、動かないですかね、ソートのアルゴリズムが解からない
のでテストできませんが、重複判定をして最後尾の内容と入れ替えるから
先に進めません。
for i=0 to (初期の要素数-重複回数) ←ここは、ループ中に変更出来ない?
重複判定(重複なら配列の最後尾の内容とスワップ)
重複回数 カウンター
配列最後尾要素削除(言語によると思いますが。)
ソート
next
↑↑
ソート(アルゴリズム不明の為入れ子になるかもしれませんが)
※追記で申し訳ありませんが、配列の要素と中身は、
対応してなくて良いため、この様に処理は出来ないでしょうか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Excel(エクセル) 重複しているか否かをソートせずに判断する方法ありますか? 2 2022/07/06 21:16
- Excel(エクセル) エクセルのソート方法について 1 2023/01/13 00:01
- 教えて!goo 【回答が書きにくいのはなぜ】投稿内容に不適切な表現など・(中略)・投稿内容の修正をお願いいたします 9 2023/05/09 08:41
- その他(プログラミング・Web制作) プログラミング能力とアルゴリズム能力って違うのでしょうか? プログラミングの能力の一部にアルゴリズム 10 2023/03/31 14:34
- Ruby 初心者プログラミング 3 2022/10/12 11:31
- 哲学 説得力を修辞の巧みさまたは論理の強さの2つに分析するにはどうすると良いでしょうか? 0 2022/07/20 05:46
- 数学 複素関数にロピタルの定理を使おうとしている回答者は、複素関数論はおろか微積分学もよく分かっていない、 5 2022/12/28 18:02
- 美術・アート オリキャラ見てください&設定付けで困ってます②(再掲) ※色々不手際があったのと結構早めに過疎っちゃ 2 2023/02/22 16:11
- その他(データベース) 業務用のデータベースサーバーの選び方について 4 2022/11/22 10:22
- 発達障害・ダウン症・自閉症 中学の時にIQ82の境界知能と診断されました。 今の私も、やはり境界知能でしょうか? そしてこれは、 3 2023/02/19 00:37
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
配列の問題
-
System.IO.Directory.GetFiles...
-
C# DataGridView のヘッダーセ...
-
VB.NETでファイル名順にファイ...
-
C言語・要素除去
-
csvファイル内にてソートす...
-
VBA基本構文の作り方 2列の...
-
C++ 入力した3つのint型の整数...
-
プログラミングについて 配列を...
-
あるディレクトリ内のファイル...
-
高速検索アルゴリズムとデータ...
-
Excelですべての組合せ(重複組...
-
excel VBA リストビューの行...
-
数字文字列のソート方法
-
構造体配列のソート
-
自己参照型構造体とソート
-
listboxの並び替え
-
4番目以降の並べ替え
-
VB6でデータを昇順に並べ替える
-
DataGridViewの複数列を連動し...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
VB.NETでファイル名順にファイ...
-
C# DataGridView のヘッダーセ...
-
なぜ?counterintuitive
-
ファイル名「1.jpg ~10.jpg~...
-
Excelですべての組合せ(重複組...
-
C# DataTableの行をソートしてD...
-
n番目に大きい数を求めるアル...
-
リスト構造のソートで悩んでま...
-
C言語・要素除去
-
10個の整数を入力して小さい順...
-
VBA基本構文の作り方 2列の...
-
あるディレクトリ内のファイル...
-
excel VBA の条件をつけての列...
-
excel VBA リストビューの行...
-
数字文字列のソート方法
-
Excel VBAで並べ替えをしたい
-
VBScriptで重複レコードを削除...
-
vbでDataTableの抽出コピー
-
構造体配列のソート
おすすめ情報