プログラマ専用SNS ミクプラ

☆さんの質問を受けて、数値が入力されるたびにソートして表示するという問題を考えてみました。

毎回ソートして表示するよりも、線形リストで途中に挿入していったほうが早いのではないかという結論になったのですが、

線形リストの代わりに配列を使った方が早いのではないかと思い、時間を測定してみました。
(こうなるとソートと呼ぶのはふさわしくない気がしますが)

配列は毎回全部のデータをfree、全部のデータをコピー、しなければならないので、一見遅そうに思えますが、測定してみて、意外な結果になりました。

3000回入力(rand()による自動入力)でソート表示、これを1000回行った計算時間です。


線形リストを使ったソート

計算時間　32.453秒



配列を使ったソート

計算時間　5.187秒



各測定に使用したコードはこちらです。大量にログが出てしまうので、printf文は省略してあります。


線形リストを使ったソート

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
	int data;
	struct node *next;
} node_t;

//新規リストを作成．
node_t *list_new(void){
	node_t *list;

	if((list = (node_t *)malloc(sizeof(node_t))) == NULL)
		exit(9);
	list->next = NULL;

	return list;
}

//node の後ろに，data を保持する節点を追加し，その節点を返す．
node_t *node_insert_after(node_t *node, int data){
	node_t *new_node;

	if((new_node = (node_t *)malloc(sizeof(node_t))) == NULL)
		exit(9);
	new_node->data = data;
	new_node->next = node->next;
	node->next = new_node;

	return new_node;
}

//リスト解放
void list_delete(node_t *list)
{
	node_t *node, *next;

	for (node = list; node != NULL; node = next) {
		next = node->next;
		free(node);
	}
}

int main(void){
	
	int x;
	node_t *list, *node,*copy;
	clock_t t1,t2;

	t1=clock();

	for(int j=0;j<=1000;j++){

		/*1回分のソートここから*/

		list = list_new();

		for(int i=0;i<3000;i++){

			x = rand();
			copy=list;
			if(list->next==NULL){//一番最初なら
				node_insert_after(copy,x);
			}
			else{
				for (node = list->next; node != NULL; node = node->next){
					if(node->data>x){//比較で見つかった値の一つ前に挿入
						node_insert_after(copy,x);
						break;
					}
					else if(node->next==NULL){//最後まで比較で見つからなかったら最後に挿入
						node_insert_after(node,x);
						break;
					}
					copy=node;
				}
			}
			if(j%10==0)
				printf("作業進行率%3d％\r",j/10);
		}

		list_delete(list);

		/*ここまで*/
	}
	t2=clock();
	printf("\n\n計算時間　%.3f秒\n",double(t2-t1)/1000);
	return 0;
}

配列を使ったソート

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void sort(int *p,int num,int x){
	int i,j;
	for(i=0;i<num;i++)
		if(p>x) 
			break;
	for(j=num;j>=i;j--)
		p[j+1]=p[j];
	p=x;
	return ;
}

int main(void){
	int i,j,num=0,*p,x;
	clock_t t1,t2;
	t1=clock();

	for(int s=0;s<=1000;s++){

		p = (int *)malloc(sizeof(int)*(num+1));

		for(int t=0;t<3000;t++){

			x=rand();
			if(num>0){
				p=(int *)realloc(p,sizeof(int)*(num+2));
				sort(p,num,x);
			}
			else p[0]=x;
			num++;

		}
		if(s%10==0){
			printf("作業進行率%3d％\r",s/10);
		}
		num=0;
		free(p);
	}
	t2=clock();
	printf("\n\n計算時間　%.3f秒\n",double(t2-t1)/1000);

	return 0;
}

私としてはこの結果から線形リストより配列を使うほうがかなり早いのかと思いましたが、どこかに無駄があるために線形リストが遅くなっていたりするのでしょうか・・。

この問題の解答として一番早いソートのしかたはなんなのか気になったので調べてみました。

何かご意見くだされば光栄です。

線形の方が6倍も時間かかるんですか!!!!おどろきました!!!

時間などを気にしなくても、勉強し、理解する側としても、配列を用いた方が分かりやすいです。

パパっと作ったものなので、どこかに間違いや、無駄があって遅くなっている可能性もあるので、家に帰ってちょっとゆっくり確認してみます＾＾；

確かに配列を使った方が書く量も少なくてすむし、わかりやすいですね。
一応今回の課題について

・実際にソートしながら表示
・リストによる表示
・配列による表示

の３種類のプログラムを作ってみると勉強になると思いますよ。

　配列版とリスト版の大きな違いはメモリの確保回数が大きく影響していると思われます。

　リスト版は毎回アロケートをしていますし、リストの破棄時には全てを解放しなければならず、この処理に時間がかかっている物と思われます。
（試しに freeをコメントアウトするとちょっと早くなります）

　配列版でも毎回 reallocをかけていますが、Windowsの場合仮想メモリの領域を拡張するだけ「メモリ確保、領域（実体）の移動」をしなくて済む場合があります。
　その為、reallocによる負荷は仮想メモリ制御だけで済むので、高速なのだと思います。
（つまり、reallocを使わずに、新領域を malloc、新領域にコピー、旧領域を破棄、を行って領域を伸長すると重いはずです）

ソートアルゴリズムっていうのは

バブルソート
バケットソート
基数ソート
ヒープソート
マージソート
クイックソート

などいろいろありますけど、このように配列で並び替えるソートに名前は付いているんでしょうか？

おお～実際に試してるのですね＾＾

>配列で並び替えるソートに名前・・・
ってデータが配列でもリストでも関係ないんじゃないですかねー？
ソートはアルゴリズムですしね。

データ構造（リストや配列やハッシュなど）とソートの種類はそれぞれ向き不向きがあるので目的に応じて使い分けるのがいいですよね。

今回の
>数値が入力されるたびにソートして・・
に関しては、データが単純に増加するだけなので、データ構造としては配列を選択するのがよいかと思いますね～

これが、例えば途中のデータを削除して～なんてことが頻繁に必要ならば全体的にはリストがいいかも知れないですしね。
（まーハイブリッド的に持つのもいいですけどね＾＾）

＞このように配列で並び替えるソートに名前は付いているんでしょうか
　原理的には挿入ソート（インサーションソート）だと思います。

＞Justyさん

なるほど、挿入ソートですか。
それに付随してシェルソートっていうのもあるんですね。
色々調べてみたら数え切れないくらいアルゴリズムがありそうですね。

やはりこんな簡単なアルゴリズム・・名前付いてますよねｗ


＞ま～くさん

挿入、部分削除などするたびに後の要素をすべてコピーしないといけないので
量が多くなってくるとリストの方がいいんですかね？
しかし配列で計算するとこんなに時間短縮されるとは実際びっくりでした。

一回探せるだけ探して、どのソートがどれ位の性能を持っているか表で表してみたいです＾＾

まぁそのアルゴリズムは状況によって得意不得意がありそうですね。

＞色々調べてみたら数え切れないくらいアルゴリズムがありそうですね
　新しいより高速でより汎用的なアルゴリズムを開発してみると、面白いかもしれません。
　うまくいけば、特許がとれる・・・かも（ｗ

＞量が多くなってくるとリストの方がいいんですかね？
　それはあると思います。
　個人的にはデータの管理で配列系では辛いなぁと思ったときは、単純なリストより二分木系の方が検索が早いことが多いという理由で好きです。
　それに二分木なら、自動的にソート済みになりますし。

＞うまくいけば、特許がとれる・・・かも（ｗ

先日教授に「新しいソートアルゴリズム研究して学会で発表してみたら。ハッハッハ」って言われたのでちょっとソートに興味持ってました。
こんな事で画期的なアルゴリズムが見つかるとは思えませんけどｗ

世界中でこんな研究してる人ごまんといるんでしょうねぇ(;￫～￩)

ソート一つで特許とった人いるんでしょうか？
研究して特許とるっていう仕事もありなのかもしれませんがバクチないきかたですねぇ・・。

　
　リストを使ったほうは、かなり早くなりました。
配列を使ったほうは、ほとんど変わりませんが、気持ち早くなってるかも。

/* リスト */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct data{
        int n;
        struct data *next;
    } DATA;

int Add(DATA *work, int n)
{
    DATA *newdata;
    
    for( ; work->next != NULL; work = work->next){
        if(work->next->n > n) break;
    }
    if((newdata = (DATA *)malloc(sizeof(DATA))) == NULL) return 0;
    newdata->n = n;
    newdata->next = work->next;
    work->next = newdata;
    return 1;
}

void Clear(DATA *head)
{
    DATA *work;
    
    for(work = head->next; work != NULL; work = head->next){
        head->next = work->next;
        free(work);
    }
    return;
}

int main(void)
{
    DATA head = {0, NULL};
    clock_t t0, t1;
    int i, j;
    
    srand((unsigned)time(NULL));
    t0 = clock();
    for(i = 0; i <= 1000; i ++){
        for(j = 0; j <= 3000; j ++){
            if(!Add(&head, rand())) return 1;
        }
        Clear(&head);
        if(!(i % 10)) printf("作業進行率%3d％\r",i / 10);
    }
    t1 = clock();
    printf("\n\n計算時間  %.3f秒\n",(double)(t1 - t0) / 1000);
    return 0;
}

　
　

/* 配列 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void Add(int *list, int l_num, int n)
{
    int i;
    
    for(i = l_num - 1; i >= 0; i --){
        if(list > n) list[i + 1] = list;
        else{
            list[i + 1] = n;
            return;
        }
    }
    list[0] = n;
    return;
}

int main(void)
{
    int *list, *temp;
    int l_num, alloc_num, i, j;
    clock_t t0, t1;
    
    srand((unsigned)time(NULL));
    t0 = clock();
    for(i = 0; i <= 1000; i ++){
        if((list = (int *)malloc(sizeof(int) * 1024)) == NULL){
            puts("Alloc Error");
            return 1;
        }
        alloc_num = 1;
        for(l_num = 0; l_num <= 3000; l_num ++){
            if(l_num >= 1024 * alloc_num){
                temp = (int *)realloc(list, sizeof(int) * 1024 * (++ alloc_num));
                if(temp == NULL){
                    puts("Realloc Error");
                    return 1;
                }
                list = temp;
            }
            Add(list, l_num, rand());
        }
        if(i % 10 == 0) printf("作業進行率%3d％\r", i / 10);
        free(list);
    }
    t1 = clock();
    printf("\n\n計算時間  %.3f秒\n",(double)(t1 - t0) / 1000);

    return 0;
}

　

>先日教授に「新しいソートアルゴリズム研究して学会で発表してみたら。ハッハッハ」って言われたのでちょっとソートに興味持ってました。

卒論等のテーマにはいいかもしれませんね。


>ソート一つで特許とった人いるんでしょうか？
>研究して特許とるっていう仕事もありなのかもしれませんがバクチないきかたですねぇ・・。

ソートの特許はないんじゃないでしょうか。
＃でないと参考書に載せるだけでも使用料が発生する！？？

特許申請にもかなりのお金がかかるようなので、却下されるとかなりショックかも。

＞ソートの特許はないんじゃないでしょうか
　ソートはあまり見かけませんね。

　ぐぐってみたらと高速なソートを発明した会社が出願中らしいです。
http://www.thinkplan.co.jp/htm/index_SlipStream.htm

　あとはこれらでしょうか
http://jstore.jst.go.jp/cgi-bin/patent/ ... rication=1

http://jstore.jst.go.jp/cgi-bin/patent/ ... rication=1

＞フリオさん

う、リストややこしいことしなくても、それでよかったのですか・・。
どちらとも早くなってますね。
配列も1024ずつですかぁ、なるほど。

最初から3000回なら3000回って解っている状況ならsizeof(int)*3000先に確保しといた方が早そうですね。

＞Yukiさん

そうですねぇ、テーマに一時期私も考えましたけど、
色々なアルゴリズムのソートの時間計測をいろんな状況でしたり
使う状況による変化を研究したりすると面白そうですね。

＞＃でないと参考書に載せるだけでも使用料が発生する！？？

う、これはありえませんねぇ・・。こんなことになったらサイトでも紹介できない！？
どんなソートも紹介されているのなら特許はなさそうですね・・・、あ、そういうことなら特許のソートがあるとしたら公に出ないから知らないだけなのかも＾＾；

＞特許申請にもかなりのお金がかかるようなので、却下されるとかなりショックかも。

なるほど・・、何でも気軽に申請できるわけじゃないんですね；
無料に近い金額だったらダメ元でなんでもかんでも申請する人がふえそうですもんね；

＞最初から3000回なら3000回って解っている状況ならsizeof(int)*3000先に確保しといた方が早そうですね
　それはそうですね（ｗ


＞配列も1024ずつですかぁ
　C++なんかではこれと似たようなことをするクラスに std::vectorがあります。
　実装によって異なりますが、挿入時にメモリが足らなければ現在の 1.5倍とかの領域を確保しなおしているようです。


＞何でも気軽に申請できるわけじゃないんですね
　専門家に頼むと数十万とかかかります。
　自分で申請すれば数万くらいです。でもものすごく面倒らしいです。

　申請しても認められるとは限らないですし、審査にも時間かかりますから、だからなかなか一般の人は申請しにくいですね。

＞＞最初から3000回なら3000回って解っている状況ならsizeof(int)*3000先に確保しといた方が早そうですね

そういえば、元々、何回入力があるか解らないものという事が前提なの忘れてました；
・・・しかし手入力なんてそう何万回も出来ないし、多めに確保しても数KBも取らないですよね。


＞C++なんかではこれと似たようなことをするクラスに std::vectorがあります。

あ～JAVAに同じような機能がありますね。名前忘れましたけど・・。
Ｃ++早いとこ勉強しなければ・・。管理人失格(_ _|||)

＞専門家に頼むと数十万とかかかります。
　
特許申請に専門家とかいるんですかぁ。
数十万・・よほど自信がないと出せませんねｗ

そういえば祖父の弟が特許いくつも取ってそのお金で東京にでっかいマンション３つも建ててオーナーやってました。
医学部を滑り止めにして東大に受かった人で親戚の中では有名人でした。
おいしい特許取ればそうとうなものなんでしょうね。
確かパンパースの濡れると青くなるあれを発明したと言ってました。
後、冷凍の魚や肉のしたにしくシートを発明したとか。
・・・あのシートは何の役目をしているのかよく知りませんが＾＾；

しかし、あの頭よかったおじさんも毎日毎日研究所に引きこもって研究していたせいで体を悪くして死んでしまいました・・。
寝ずに食べずに研究してたとか。エジソンか？＾＾；
いくつも特許とる位発明するには日々人一倍の努力が必要なんでしょうけど、あそこまでやって体壊してしまったのでは意味が無いですねぇ(_ _|||)

クイックソート遅ぉ！

・・・というわけでクイックソートとの比較もしてみました。

作業進行率 100％

計算時間 100.218秒

やっぱクイックソートとはいえ、毎回全てがソートされるようなアルゴリズムを使うと遅くなってしまうんですね。

今回の場合、１個だけ挿入すればいいわけで、前回までの処理で他の部分は全てそろってるんですものね。

フリオさんのお書きになったプログラムを実行した配列のソートプログラム

作業進行率100％

計算時間 3.765秒

でした。

/*　　配列　　*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void){
	int n, list[3000] , num=0; clock_t t0, t1;
	t0 = clock();
	for(int i = 1; i <= 1000; i ++){
		for(int l_num = 0; l_num < 3000; l_num ++){
			n=rand();
			for(int s = l_num - 1; s >= 0; s --){
				if(list > n) list[s + 1] = list;
				else {list[s + 1] = n; break;}
			}
			list[0] = n;
		}
		if(i % 10 == 0) printf("作業進行率%3d％\r", i / 10);
	}
	t1 = clock();
	printf("\n\n計算時間  %.3f秒\n",(double)(t1 - t0) / 1000);
	return 0;
}

固定[3000]にして、短く書き直しました(掲示板のスクロールが長くなってしまうので；)

/*　クイックソート　*/

#include  <stdio.h>
#include <stdlib.h>
#include <time.h>
void sort(int l, int r, int x[3000]){
	int i,j,p,t;
	i=l;j=r;p=x[(l+r)/2];
	while(1) {
		while(x<p) i++;
		while(p<x[j]) j--;
		if(i>=j) break;
		t=x,x=x[j],x[j]=t;
		i++ , j--;
	}
	if(l<i-1)	sort(l,i-1,x);
	if(j+1<r)	sort(j+1,r,x);
}
int main(void){	
	int x[3000];	clock_t t0,t1;
	t0 = clock();
	for(int i=1;i<=1000;i++){
		for(int j=0;j<3000;j++){
			x[j]=rand();	sort(0, j, x);
		}
		if(!(i % 10)) printf("作業進行率%3d％\r",i / 10);
	}
	t1=clock();
	printf("\n\n計算時間  %.3f秒\n",(double)(t1 - t0)/1000);
 	return 0;
}

　

＞おいしい特許取ればそうとうなものなんでしょうね
　自分でとるのが面倒な場合、所属する会社で取ってもらうというのも手です（そういう精度がある場合、ですが）。
　権利は会社になってしまいますが、とある会社では社員が会社経由で（どんな役に立たないものでも）特許を申請しただけで以後ずっと月給＋５０００円、申請が通ると以後ずっとＸ万円加算されるという制度があるそうです。
　１件でそれなので、数件～数十件申請してる人と全くしてない人では生涯給与で結構差が開く、なんてこともありそうです。

＞＞パンパースの濡れると青くなるあれを
　おー、それはまた凄いですね。


＞＞いくつも特許とる位発明するには日々人一倍の努力が必要
　勿論血のにじむような努力が必要なこともありますけど、結構特許を申請できそうなことって思いついたりしてると思います。


　http://www.ipdl.ncipi.go.jp/で検索してみるとわかりすいところで、ゲーム関連だと

「特許公開２００３－３３４３８１」
　まんま PS2のゲーム SHINOBIですよね。

「特許公開２００５－１００１３３」
　塊魂ですかね。

　こんなゲームの仕組みというかルールのようなものも申請対象になるようなので、意外と思いついていても気付かないでそのまま・・・・ってことも多そうですね。

＞結構特許を申請できそうなことって思いついたりしてると思います。

そうですよね。ひらめいても、うまく応用できなかったりするだけで、特許につながる要素はいくつも思いついているかもしれませんね。

＞特許電子図書館で・・

そんなものがあるんですね！
こういうサイトも面白そうですね。是非覗いてみます。

まさしくありましたよ！！！
http://www2.ipdl.ncipi.go.jp/begin/BE_D ... st&sTime=0

>特許電子図書館
「・特許・実用新案公報ＤＢ」で、
「文献種別」にA、「文献番号」にH18-39894を入力すると、↑の詳細な特許情報が閲覧できます。
「●全項目」をクリックすると、【発明の詳細な説明】が表示されます。

クイックソートとか知ってる言葉もあるのですが、まだ完全に起きていない頭では日本語が難しいです・・・。

おぉ！ホントですね。
しかも公開日が今年の２月とは新しい。

んん・・図が縮小されていて見えない；