アルゴリズム・ネストループ方式とは？

前へ 次へ
このQ&Aのポイント
  • アルゴリズム・ネストループ方式は、プログラムの性能改善に使われる手法です。
  • ネストループ方式は、for文などのループを入れ子にして使用する方法で、複数の処理を繰り返し行います。
  • ネストループ方式は効果的な手法ですが、適切に使わないと処理時間が増える可能性があるため注意が必要です。
回答を見る
  • ベストアンサー

アルゴリズム・ネストループ方式って何？

プログラムの性能改善の課題が出ているのですが、アルゴリズムとしてネストループ方式、もしくはその延長上のものを用いること、とあります。 図書館でアルゴリズム関係の本を見てみたのですがどこにもネストループに関して説明がなく、大変困っています。 プログラム自体は、ファイルを読み込んで、表示させるだけの簡単なものです。 簡単に抜き出すと、 for (i=0;; i++){ if ((st = read_a(fd_name, &name_buf, i)) <=0) break; for (j = 0;; j++){ if ((st =read_a (fd_home,&home_buf ,j)) <= 0) break; if (!strcmp(name_buf.a , home_buf.b)){ printf("%s =%s (%s)\n", name_buf.a, name_buf.c , home_buf.c); } } if (st <0) break; といったものです。 注意事項として、break文を入れる手法を使わないこととあります。 お願いします。ネストループって何でしょう？教えてください。

質問者が選んだベストアンサー

  • ベストアンサー
回答No.2

ネストループはリレーショナルデータベースでジョインを行うアルゴリズムと してよく知らせています。 RDBMS で使われるネストループのアルゴリズムを簡単に説明すると、ファイル でも表でもいいんですが２つあって、次のような感じのデータが入っていたと します。 ファイル（表）１ ID　名前 3 佐藤 1 鈴木 5 中村 2 高橋 : ファイル（表）２ ID 住所 1 東京都 2 大阪府 3 長野県 4 神奈川県 5 北海道 : ここから 名前 住所 佐藤 長野県 鈴木 東京都 中村 北海道 高橋 大阪府 : という出力を得る場合に、ファイル（表）１の１行目を読み込んで ID が 同じ行をファイル（表）２の先頭行から探していき、ID が同じ行が見つ かったら、ファイル（表）１とファイル（表）２のデータを出力し、ファイル （表）１の次の行の ID と同じ ID を持つ行をファイル（表）２の先頭行から 再度読み込んで探し、.... という繰り返しをするアルゴリズムです。 この方法だと、ファイル（表）１の行数 * ファイル（表）２の行数回の 比較が必要であるのと、ファイル（表）２は１度読み込んだ行をもう一度 読む必要があるので非効率的です。 データがソート済みであったりするともっと効率的なソートマージという アルゴリズムが適用できます。またハッシュを使ったりするようなアルゴリズム もあります。

kanyako
質問者

お礼

回答ありがとうございます。（＾＿＾） なるほど。IDをファイル１から一行ずつ読み込んでファイル２とあわせていけばいいのですね。 とてもわかりやすかったです＠ レポートなんで、効率とかは気にしません。自信のある人はハッシュクラスタリングを実装しても良い、とか先生は言うけど自信なんてないし（・＿・；） このくらいのプログラミングならできるかな・・・？ 卒業がかかっているんでホントありがたかったです。 少しいじってみます。わからなくなったらまたお願いします。

kanyako
質問者

補足

ありがとうございました。 なんとかレポートは完成しました。（＾＿＾）/

その他の回答 (1)

  • asuca
  • ベストアンサー率47% (11786/24626)
回答No.1

ある文の中に同じ文を組み込むことをネスト（入れ子）と呼びます。 ですからネストループとはループの中にループを入れた物です。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • read()メソッドを使ったループの抜け方

    通信のプログラムを作っています。 送信側では、指定した数のバイトデータを作成し、送信します。 受信側では、そのバイトデータを受信して、受信にかかった時間を計測します。 送信側では、次のようにしてデータの最後の文字をsとして、作っています。 受信側では、sを読み込んだら、受信完了と見なし、受信処理を終了します。 送信と受信処理のコードを見てください。 送信側(Dataは指定したバイトデータの数値です) for (int i = 0; i < Data-1; i++) { 　　out.write(i); 　　out.flush(); } out.write('s'); out.flush(); 受信側 while((part = in.read(buf,0,buf.length)) != -1) { 　　total += part; } 受信側のコードだと、送信されたバイトがすべて読み込んだらループを抜けるのですが、 そうではなく、sを読み込んだらループを終了させたいのです。 read(buf,int,int)の戻り値を使って受信されたバイト数を確認したいため、 どうしてもread(buf,int,int)を使って受信したいのです。 read(buf,int,int)を使いつつ、送信バイトの最後の文字sを読み込んだら ループを抜けるようにするには、どうすればよいでしょうか？ アドバイスをお願いします。 自分で考えたコードを載せます。 読み込んだバイトをbufに入れる。 そして読み込んだバイト数を合計する。 bufの最後の文字がsならループを抜けるというようにしたいのですが、 指定したデータ分を読み込みません。 for(;;){ part = in.read(buf); total += part; if(buf[total] == 's'){ break; } } こちらの方も、指導していただきたいです。

    • ベストアンサー
    • Java
  • アルゴリズムの名前を教えてください

    16ビットのデータが、たとえば1000個、配列で与えられているとします。 unsigned short data[1000]; このデータをしらべて、重複するものを除いて何種類の値があるかを数える場合、一番素朴な方法だと、次のようにやると思います。 int i, j; int count = 0; for(i = 0; i < 1000; i++) { 　for(j = 0; j < i; j++) { 　　if(data[j] == data[i]) { 　　　break; 　　} 　} 　if(i == j) { 　　count++; 　} } この方法だと、２重のループがあって処理に時間がかかります。そこで、メモリに余裕があれば内側のループをやめて、 int i; int count = 0; int flag[0x10000]; int n; for(i = 0; i < 0x10000; i++) { 　flag[i] = 0; } count = 0; for(i = 0; i < 1000; i++) { 　n = data[i]; 　if(flag[n] == 0) { 　　flag[n] = 1; 　　count++; 　} } これだと、２重のループを使うものよりは速くなりますが、データが1000個しかないのに、65536個のflagをクリアするのに時間がかかり、今ひとつです。 ところが、次のような賢い方法があり、２重のループも配列のクリアも無くすことができます。 int i; int count = 0; unsigned short flag[0x10000]; unsigned short link[0x10000]; int n; for(i = 0; i < 1000; i++) { 　n = data[i]; 　if(flag[n] >= count || link[flag[n]] != n) { 　　flag[n] = count; 　　link[count] = n; 　　count++; 　} } 私がこのアルゴリズムを知ったのはかなり昔なので、どこで知ったのか思い出せないのですが、これほど賢いアルゴリズムだから何か名前がついていると思うのですが、それがわかりません。 名前がわからないので、人に頼んだりする時、上のような長い説明をしなくてはなりませんが、名前がわかっていれば「？？法でやっといて」、と言えばいいのですけど。

  • アルゴリズムの正当性について

    線形探索法のアルゴリズムの擬似コードを書いて、そのアルゴリズムの正当性をループ不変式を用いて証明するという課題があります。 擬似コードは以下のような流れにしようと思いますが、この場合成り立つループ不変はどのようなことになりますか？ 配列A[a1..an]に対してv=A[i]ならば添字iを、vがAの中になければNILを出力するアルゴリズムです。 for i ←1 to N if A[i] = v return i return NIL

  • forループに慣れるには

    初めまして。 今資格を取ろうと思い独学でJavaを勉強してるんですが、 つまらない部分でつまずいています。 それは少々複雑なfor等のループです。 変数を追っていくうちにこんがらがってしまい、 変数の正しい値を見失ってしまいます。 例えば… Loop: for(int i = 0; i<5; i++) { for(int j =0; j<5; j++) { if(i==j) continue Loop; System.out.println("i = " +i+ "j = " +j); if(i > 3) break Loop; } } や、 int i,j; for(i = 0, j = 0; i<3;) { if(i++ == 2 || j++ == 2) break; } System.out.println(i); System.out.println(j); の様なループです。 試験範囲は大方勉強出来てるんですが まぬけな事にループがイマイチ理解出来てなくて（恥） 皆さんはどうやって慣れてこられましたか？ つまらない質問ですが何か良いコツやアドバイスがあれば よろしくお願いします。

  • ループが回らない

    #include<stdio.h> #include<string.h> #define HASH_SIZE 100 #define NAME_SIZE 20 char name[ HASH_SIZE ][ NAME_SIZE ]; i int hash_func( char str[] ) { } void main() { char s[ NAME_SIZE ],i; int index ; while(1){ printf("文字を入力！"); scanf("%s",s); if( s[0]='.') break; index = hash_func(s); strcpy( name[ index ],s) ; printf("*\n"); } } このプログラムの 無限ループのところがぜんぜん回らないんです。 自分なりに試行錯誤してみたのですが 限界に達しましたので助言をいただきたいです。 上の関数は今はなにも書いてないですが、 書いてあっても動かないです。 月曜日提出の課題なので なるべく早め回答いただけると幸いです。 アドバイスお待ちしております。

  • TCP/IP通信型電話番号検索プログラムを作りたいです。

    TCP/IP通信型電話番号検索プログラムを作りたいです。 クライアントは以下のようで大丈夫みたいなのですが、サーバの方を修正しなければなりません。 この質問で「TCP/IP通信型大文字・小文字変換プログラム」を発見しました。 サーバー側プログラム #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <unistd.h> #include <sys/socket.h> #include <arpa/inet.h> #define SOCK_NAME "./socket" int main() { int i; int fd1, fd2; struct sockaddr_in saddr; struct sockaddr_in caddr; int len; int ret; char buf[1024]; if((fd1 =socket(AF_INET, SOCK_STREAM, 0)) < 0 ){ perror("socket"); exit(1); } memset((char *)&saddr, 0, sizeof(saddr)); saddr.sin_family = AF_INET; saddr.sin_addr.s_addr=INADDR_ANY; saddr.sin_port=htons(1357); unlink(SOCK_NAME); if(bind(fd1, (struct sockaddr *)&saddr, sizeof(saddr)) < 0) { perror("bind"); exit(1); } if(listen(fd1,5) < 0 ) { perror("listen"); exit(1); } while(1){ len = sizeof(caddr); if((fd2 = accept(fd1, (struct sockaddr *)&caddr, &len)) < 0){ perror("accept"); exit(1); } fprintf(stderr, "Connection established: socket %d used.\n", fd2); while((ret = read(fd2, buf, 1024)) > 0 ){ fprintf(stderr, "read: &s\n", buf); for(i=0; i<ret; i++) if(islower(buf[i])) buf[i] = toupper(buf[i]); if(isupper(buf[i])) buf[i] = tolower(buf[i]); fprintf(stderr, "write: %s\n", buf); write(fd2, buf, 1024); } close(fd2); } close(fd1); return 0; } 先生によると、クライアントは同じもので良いそうです。 誰か、助けて下さい。

  • HTTPレスポンスの終端はどうわかる？

    MacOSX、C言語でsocket(),writeなどを使ってサーバにリクエストを送り レスポンスを標準出力しようとしています。 とりあえずレスポンスをbuf[BUFSIZ]にreadさせようとしているのですが、 レスポンスの内容のサイズがBUFSIZ以上だった場合、繰り返しreadさせる 必要があります。 なので(かなり簡潔に書きますが) while(1) if(buf[i]==EOF){break;} n=read(socket,buf,sizeof(buf)-1); みたいなことを考えました。がこれだとループが止まってくれません。 延々と読み込んでは表示してくれます。。。 たぶんHTTPレスポンスの終端がEOFだと思ったのが違うのだと思います。 HTTPレスポンスの終端というのはどう判断したらよいのでしょうか。 よろしくお願いいたします。

  • selectを使った文がうまくいきません

    C言語でselectを使ってチャットサーバを実現したいのですが、うまくいきません。 以下にメッセージの受信と新しいクライアントの受付を処理するループのコードを示します。 以下のコードのif(select(FD_SETSIZE,&rfds,NULL,NULL,&tv)>0) { ... } の分岐に入って1回目の処理を行った後、以降のループでメッセージを送ってもこの分岐に入らなくなります。 どなたか原因がわかるかたよろしくお願いします。 while(1){ FD_ZERO(&rfds); /* rfds を空集合に初期化*/ FD_SET(sock,&rfds); /* 接続要求を待つソケット*/ /* クライアントを受け付けたソケット*/ /* 監視する待ち時間を1 秒に設定*/ tv.tv_sec = 1; tv.tv_usec = 0; /* 標準入力とソケットからの受信を同時に監視する*/ max = sock; for(i = 0;i = k ; i++){ if(max > csock[i]){ max = csock[i]; } } if(select(FD_SETSIZE,&rfds,NULL,NULL,&tv)>0) { /* s3 */ if(FD_ISSET(sock,&rfds)){ /* s4 */ /* クライアントの受付*/ clen = sizeof(clt); if ( ( csock[k] = accept(sock,(struct sockaddr *)&clt,&clen) ) <0 ) { perror("accept"); exit(2); } FD_SET(csock[k],&rfds); if(k < MAXCLIENTS){ strcpy(jusin,"REQUEST ACCEPTED\n"); write(csock[k],jusin,strlen(jusin)); /* s5 */ read(csock[k],nbuf,sizeof(nbuf)); check = 0; for(i = 0;i < 5;i++){ for(j = 0; j < 100;j++){ if(name[i][j] != nbuf[j]){ check = 1; break; } if(nbuf[j] == '\n'){ break; } } } if(check != 1){ strcpy(userkyohi,"USERNAME REJECTED\n"); write(csock[k],userkyohi,strlen(userkyohi)); write(csock[k],nbuf,strlen(nbuf)); close(csock[k]); } else{ i = 0; while(rbuf[i] != '\n'){ name[k][i] = nbuf[i]; i++; } name[k][i]= '\n'; strcpy(toroku,"USERNAME REGISTERED\n"); write(csock[k],toroku,sizeof(toroku)); k++; } }else{ strcpy(kyohi,"REQUEST REJECTED\n"); write(csock[k],kyohi,strlen(kyohi)); close(csock[k]); } } for(i = 0;i < k;i++){ if(FD_ISSET(csock[i],&rfds)){ read(csock[i],mbuf,sizeof(mbuf)); if(mbuf[0] == 'E'&& mbuf[1]=='O' && mbuf[2] == 'F'){ /* s7 */ for(;i == k ; i++){ csock[i]=csock[i+1]; memset(name[i],0,sizeof(name[i])); j = 0; while(name[i+1][j] != '\n'){ name[i][j] = name[i+1][j]; } } close(csock[k]); k--; } else{ memset(msg, 0, sizeof(msg)); j = 0; while(name[i][j] != '\n'){ msg[j] = name[i][j]; j++; } msg[j] = ' ';j++; msg[j] = '>';j++; l = 0; while(mbuf[l]!='\0'){ msg[j]= mbuf[l]; j++; l++; } msg[j] = '\0'; for(t = 0; t < k;t++){ write(csock[t],msg,sizeof(msg)); } } } } } }

  • 逆行列のアルゴリズム

    現在逆行列を求めるアルゴリズムを勉強してるんですが、全然わかりません。 とあるサイトさんから逆行列を求めるソースを拝借させていただきました。 実際に２行２列の値を入れて手計算でプログラムを追っていったら23行目で対角成分に1を代入したり、33行目で対角成分以外の成分に0を代入しているのはわかるんですが、わかるのはその程度で、もっと詳しくアルゴリズムを教えていただきたいです。 わかりやすいサイトなどでも結構なんで教えていただけると助かります！ よろしくおねがいします。 #include <stdio.h> 01:int main(void) 02:{ 03: 04: double exp_At[2][2]={{1,3},{2,1}}; //入力用の配列 05: double inv_exp_At[2][2]; //ここに逆行列が入る 06: double buf; //一時的なデータを蓄える 07: int i,j,k; //カウンタ 08: int num=2; //配列の次数 09: //単位行列を作る 10: for(i=0;i<num;i++) 11: { 12: for(j=0;j<num;j++) 13: { 14: inv_exp_At[i][j]=(i==j)?1.0:0.0; 15: } 16: } 17: /* 掃き出し法 */ 18: for(i=0; i<num; i++) /* 逆行列をexp(-At)求める */ 19: { 20: buf=1/exp_At[i][i]; 21: for(j=0; j<num; j++) 22: { 23: exp_At[i][j] *= buf; 24: inv_exp_At[i][j] *= buf; 25: } 26: for(j=0; j<num; j++) 27: { 28: if(i != j) 29: { 30: buf=exp_At[j][i]; 31: for(k=0; k<num; k++) 32: { 33: exp_At[j][k] -= exp_At[i][k] * buf; 34: inv_exp_At[j][k] -= inv_exp_At[i][k] * buf; 35: } 36: } 37: } 38: } 39://逆行列を出力 40: 41: printf("逆行列exp(-At)=\n"); 42: 43: for(i=0;i<num;i++) 44: { 45: for(j=0;j<num;j++) 46: { 47: printf(" %f",inv_exp_At[i][j]); 48: } 49: printf("\n"); 50: } 51:}

  • ループの回数の問題についてです。

    SUN教科書 javaアソシエイツP102についてです。 Helloが何回表示されるかという問題です。 i=1　j=1の時、continue文によりouterへ移動するという 所までは理解出来ます。 分からないのはその後、解説によるとiが２ということです。 そして内側のforループは0から2の間、実行されるというのです。 iが２になるなら、内ループに入った時jも ２になるのではないのでしょうか。 よろしくお願い致します。 class LoopSample{ public static void main(String[] args){ outer: for(int i=0; i<5; i++){ for(int j=0; j<3; j++){ if(i==1 && j==1){ continue outer; } System.out.println("Hello"); } if(i==1 || i==2){ break; } } } }

    • ベストアンサー
    • Java

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する