【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.21004

効率的なソート
投稿者---SOP(2005/05/11 21:19:08)


「32個の既に整列(降順)されたデータに、ランダムなデータ1個加えて再整列し、値の一番小さいデータを削除する。」
という処理を最も効率的に行いたいのですが、良い方法はないでしょうか。
制限として、配列33個とデータ仮保存用変数を数個しか用意できない。というのがあるのですが。どうでしょうか。
私が考えた方法は、
1)0から31番目まで整列されたデータをセット
2)32番目に加えるデータをセット
3)31番目のデータと32番目のデータを比較して交換
4)交換がなくなるまで、配列をさかのぼっていく
5)交換がなくなったら32番目のデータを削除(0埋め)
なのですが、これよりも効率的な方法はありますでしょうか?
「データを加えて削除」を複数回繰り返したいので、一回にかかる処理をできるだけ抑えたいのです。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:効率的なソート 21005 まきじ 2005/05/11 21:40:59
<子記事> Re:効率的なソート 21013 たいちう 2005/05/12 09:35:18
<子記事> Re:効率的なソート 21016 επιστημη 2005/05/12 13:22:42
<子記事> Re:効率的なソート 21018 ぽへぇ 2005/05/12 19:07:51


No.21005

Re:効率的なソート
投稿者---まきじ(2005/05/11 21:40:59)


>「32個の既に整列(降順)されたデータに、ランダムなデータ1個加えて再整列し、値の一番小さいデータを削除する。」
>という処理を最も効率的に行いたいのですが、良い方法はないでしょうか。

整列済みのデータに新たにデータを加えるのでしたら、
「挿入ソート」呼ばれるソートが良いと思います。

という事でSOP さんが仰ってるやり方

>1)0から31番目まで整列されたデータをセット
>2)32番目に加えるデータをセット
>3)31番目のデータと32番目のデータを比較して交換
>4)交換がなくなるまで、配列をさかのぼっていく
>5)交換がなくなったら32番目のデータを削除(0埋め)

で、ほぼ良いと思います。
新しく加えるデータは、配列の最後じゃなくてもよいと思います。
一番小さいデータを削除するのでしたら、配列の前か比較していくのが
良いと思います。


この投稿にコメントする

削除パスワード

No.21013

Re:効率的なソート
投稿者---たいちう(2005/05/12 09:35:18)


『最も効率的』とわざわざ指定しているので、出題者は二分探索を意図しているのかも。
たった32個のデータでは差は出ないでしょうが。


この投稿にコメントする

削除パスワード

No.21014

Re:効率的なソート
投稿者---SOP(2005/05/12 10:32:17)


まきじさん、たいちうさん、回答ありがとうございます。

最終的に行いたいのは、
「あるフォルダから、名前(YYYYMMDDHHMISS)の大きいファイルから順に最大32個だけ残し、
残りを全て削除する(新しいファイルを最大32個のみ残す)」
という処理です。(32個残した後ファイルを操作していろいろ処理するわけですが。)
ただ、メモリが貧弱で大きなサイズは確保できず、ファイル書込みも極力避けたい、その上である程度の速度も確保したい。
という環境上の問題があり、この中で考えたのが、

1)FindFirstFile()でフォルダ内のファイルを検索して順に配列0〜31にセット
2)ファイル名を格納した配列内をソート
3)フォルダ内に検索していないファイルがあるようなら配列32番目にセットして再ソート
4)32番目に格納されたファイルを削除
5)3、4をフォルダ内のファイルが32個以下になるまで繰り返す

という方法でした。
この3、4の繰り返しは不確定なので3の再ソートをできる限り効率的に行いたいのですが、
私の知らない、素敵な方法があるかもしれないと思い、投稿しました。

まずは作成して、その上で速度など考慮してテストしたいと思います。
ありがとうございました。


この投稿にコメントする

削除パスワード

No.21023

Re:効率的なソート
投稿者---かずま(2005/05/13 10:39:07)


32個程度なら挿入ソートで十分ではありませんか?
#include <stdio.h>
#include <string.h>
#include <windows.h>

#define N_FILE  32

int main(void)
{
    char *file[N_FILE+1], buf[N_FILE+1][MAX_PATH], *p;
    int i, n = 0;  WIN32_FIND_DATA fd;

    HANDLE h = FindFirstFile("*", &fd);
    if (h == INVALID_HANDLE_VALUE) return 1;
    for (i = 0; i <= N_FILE; i++) file[i] = buf[i];
    do {
        if (fd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) continue;
        p = file[n];
        strcpy(p, fd.cFileName);
        for (i = n; i > 0 && strcmp(fd.cFileName, file[i-1]) > 0; i--)
            file[i] = file[i-1];
        file[i] = p;
        if (++n > N_FILE) printf("remove('%s')\n", file[--n]);
    } while (FindNextFile(h, &fd));
    FindClose(h);
    //for (i = 0; i < n; i++) puts(file[i]);
    return 0;
}

実際のプログラムでは、上の printf を remove(file[--n]); に置き換えてください。

> まずは作成して、その上で速度など考慮してテストしたいと思います。

テスト結果の報告をお待ちしています。


この投稿にコメントする

削除パスワード

No.21039

Re:効率的なソート
投稿者---SOP(2005/05/13 17:21:39)


サンプルソースありがとうございます。

う〜ん。美しいソースだ。。。
特にこの辺が↓
for (i = 0; i <= N_FILE; i++) file[i] = buf[i];

そっか〜。1個1個交換していかなくてもポインタ使えばいいのか。
ポインタを駆使して考えてなおしてみます。


>32個程度なら挿入ソートで十分ではありませんか?
<pre>
>#include <stdio.h>
>#include <string.h>
>#include <windows.h>
>
>#define N_FILE 32
>
>int main(void)
>{
> char *file[N_FILE+1], buf[N_FILE+1][MAX_PATH], *p;
> int i, n = 0; WIN32_FIND_DATA fd;
>
> HANDLE h = FindFirstFile("*", &fd);
> if (h == INVALID_HANDLE_VALUE) return 1;
> for (i = 0; i <= N_FILE; i++) file[i] = buf[i];
> do {
> if (fd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) continue;
> p = file[n];
> strcpy(p, fd.cFileName);
> for (i = n; i > 0 && strcmp(fd.cFileName, file[i-1]) > 0; i--)
> file[i] = file[i-1];
> file[i] = p;
> if (++n > N_FILE) printf("remove('%s')\n", file[--n]);
> } while (FindNextFile(h, &fd));
> FindClose(h);
> //for (i = 0; i < n; i++) puts(file[i]);
> return 0;
>}
</pre>



この投稿にコメントする

削除パスワード

No.21016

Re:効率的なソート
投稿者---επιστημη(2005/05/12 13:22:42)


ヒープの方がが速くはないか?

/* C++でごめんなさい */
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>

int main() {

  // 元データ
  int input[50];
  for ( int i = 0; i < 50; ++i ) {
    input[i] = i;
  }
  std::random_shuffle(input, input+50);

  std::vector<int> result;
  std::greater<int> descend;
  for ( int i = 0; i < 50; ++i ) {
    // 大きい方から32個を保持する
    while ( result.size() > 32 ) {
      std::pop_heap(result.begin(), result.end(), descend);
      result.pop_back();
    }
    // ヒープに追加する
    result.push_back(input[i]);
    std::push_heap(result.begin(), result.end(), descend);
  }

  // ソートして出力
  std::sort_heap(result.begin(), result.end(), descend);
  for ( int i = 0; i < 32; ++i ) {
    std::cout << result.at(i) << ' ';
  }

  return 0;
}





この投稿にコメントする

削除パスワード

No.21018

Re:効率的なソート
投稿者---ぽへぇ(2005/05/12 19:07:51)



配列に使うデータ型がどうでも良いという条件であれば、
リスト構造にするとデータ交換の手間が少なくなります。

>「32個の既に整列(降順)されたデータに、ランダムなデータ1個加えて再整列し、値の一番小さいデータを削除する。」
>という処理を最も効率的に行いたいのですが、良い方法はないでしょうか。
>制限として、配列33個とデータ仮保存用変数を数個しか用意できない。というのがあるのですが。どうでしょうか。




この投稿にコメントする

削除パスワード

No.21019

Re:効率的なソート
投稿者---επιστημη(2005/05/13 07:42:11)


>配列に使うデータ型がどうでも良いという条件であれば、
>リスト構造にするとデータ交換の手間が少なくなります。

要素数が少ないので、全体のパフォーマンスは配列の方が優れてるかもです。



この投稿にコメントする

削除パスワード

No.21066

Re:効率的なソート
投稿者---SOP(2005/05/14 20:06:25)


皆さん、丁寧なアドバイスありがとうございました。
思うように動作するソースを作成することができました。

全体的なパフォーマンスを考慮して当初私が考えていたバブルソート(でいいのかな?)ではなく「挿入ソート」を使用しました。
(ソースの公開はご容赦を。誓ってサンプルソースをそのままは使用はしていません。)
作成したモジュールのレスポンスは100ファイルで体感約1秒程度(ソート以外の全体的な処理含む)で問題ない速度でした。
また、1000ファイルで約4〜5秒程度(ただし運用上これはありえない)でした。

今回はかずまさんのサンプルソースを参考にさせて頂きましたが、
(特に配列要素をひとつずつ後ろにずらしていく部分↓)
>for (i = n; i > 0 && strcmp(fd.cFileName, file[i-1]) > 0; i--)
> file[i] = file[i-1];
>file[i] = p;
επιστημηさんのヒープソートやぽへぇさんのリスト構造についても引き続き勉強していこうと思います。

ありがとうございました。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧