質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.37%

文字列の比較の高速化

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 1,477

score 81

質問内容

AtCoderの以下のリンクにおける過去問を解いていました.
最初に書いたコード1ではTLEとなってしまい,解説をみてソートをしてから比較しないとTLEになってしまうと書いてあったので,コード2ではソートしてから比較するようにしてみたのですが,コード1よりもTLEになってしまうケースが増えてしまいました.どのようなところが実行時間を引き延ばしている原因なのか教えていただきたいです.

問題

コード1

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(void){
    int N;
    char **str;
    int count=1;

    scanf("%d",&N);
    str=(char **)malloc(sizeof(char *)*N);
    for(int i=0;i<N;i++){
        str[i]=(char *)malloc(sizeof(char)*11);
    }
    for(int i=0;i<N;i++){
        scanf("%s",str[i]);
        for(int j=0;j<i;j++){
            if(strcmp(str[i],str[j])==0) break;
            if(j==i-1) count++;
        }
    }
    printf("%d\n",count);
    return 0;
}

コード2

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

    char **str;

void sort(int num){
    char tmp[11];
    for(int i=1;i<num;i++){
        for(int j=1;j<num;j++){
            if(strcmp(str[j-1], str[j])>0){
                strcpy(tmp, str[j-1]);
                strcpy(str[j-1], str[j]);
                strcpy(str[j], tmp);
            }
        }
    }

}
int main(void){
    int N;
    int count=1;

    scanf("%d",&N);
    str=(char **)malloc(sizeof(char *)*N);
    for(int i=0;i<N;i++){
        str[i]=(char *)malloc(sizeof(char)*11);
    }
    for(int i=0;i<N;i++) scanf("%s",str[i]);    
    sort(N);
    for(int i=1;i<N;i++){
        if(strcmp(str[i],str[i-1])!=0) count++;
    }
    printf("%d\n",count);
    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+4

どのようなところが実行時間を引き延ばしている原因なのか教えていただきたいです.

重複を除いて勘定するトコは(loopの入れ子がなくなることで)確実に早くなってるでしょうから、
「ソート自体に時間を食ってる」と考えられます。

sort(N); 改め、もっと速い
qsort(str, N, sizeof(char*),(int(*)(const void*,const void*))&strcmp);
に置き換えてはいかがでしょう。

[追記] sort() 内の文字列の交換:

  strcpy(tmp, str[j - 1]);
  strcpy(str[j - 1], str[j]);
  strcpy(str[j], tmp);


において、文字列のコピーを三回やってるのが時間を食ってるかもです。
コピーを行わずポインタを入れ替えるだけ↓にすれば、かなり速くなる可能性があります。
※ qsort には敵わんでしょうけど

  char* tmp = str[j-1];
  str[j-1] = str[j];
  str[j] = tmp;

[追記]

qsort(str, N, sizeof(char*),(int(*)(const void*,const void*))&strcmp);
に置き換えてはいかがでしょう。

ごめんなさい、これマチガイ。
正しくは:

int str_compare(const void* pa, const void* pb) {
  const char* a = *(const char**)pa;
  const char* b = *(const char**)pb;
  return strcmp(a, b);
}


を定義したうえで
qsort(str, N, sizeof(char*), &str_compare);
に置き換え、です。

おわびついでに、質問に呈示されたsort(バブルソートかな)で
ランダムシャフルされた 要素数10000 / 文字列長9 の配列をソートしてみました。

Windows10(64bit) / ぽんこつ i7-2600K で 1800[ms]
問題で定められた制限時間ギリギリです、問題にあった最大要素数200000だととうてい間に合いません。

標準関数 qsort なら要素数 200000 でも80[ms] でソート完了。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/08/16 20:58

    すいません,言い方が悪かったですね.
    きちんと解決できたのでバグ等はございませんでした.
    ありがとうございます.

    キャンセル

  • 2020/08/16 20:59

    > *を増やしてみても不正解の問題は減らなかったようなので,他にも何か原因になりそうな点があれば教えていただきたいです.

    コレ↑は何だったんです?

    キャンセル

  • 2020/08/16 21:07

    頭を冷やすために時間を空けて,他の方法で完了させてしまいました.
    お手数おかけしてしまい申し訳ございません.

    ちなみにstrのソートは正しく実行できていました.

    キャンセル

+1

Cではやりたくない問題ですね。Rubyなら7行で済みますから。

まず、解き方が間違っています。文字列を一つ一つ比較していくとなるとO(N^2)の時間計算量が必要です。これではどんなに頑張っても時間内に終わらすのは難しいです。しかし、この問題はO(N)に抑えることができます。

どうすれば良いのかというとハッシュ値を使います。ハッシュテーブルは聞いたことがありますか?そうです、ハッシュテーブルの仕組みと同じような物を使えば、前と同じ文字列があるかどうかがO(1)で判断できます。その繰り返しなので、最終的にはO(N)になると言うことです。

他言語であれば、C++ならstd::unordered_set、Javaならjava.util.HashSet、Pythonならset、RubyならSetを、JavaScriptならSetというものが標準で用意されていますので、こちらを使うと簡単に書けます。しかし、Cにはこのような便利なオブジェクトの型は用意されていません。ですので、自分で作る必要があります。

ハッシュテーブル、セット、等のキーワードでCでの実装方法を探してみて下さい。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/08/10 21:48

    > epistemeさん

    サンクスです。直したっす。

    ハッシュじゃなくて二分木でも間に合いそうな気がしますが、O(N log N)なのでちょっと遅い?うーん、このあたりは難しくてわからないです。

    キャンセル

  • 2020/08/10 21:54

    問題の設定では 20万要素を2秒間 ですから O(N logN) ならいまどきの計算機でイケそうな。

    キャンセル

  • 2020/08/12 16:00

    ご回答ありがとうございます.
    Javaを勉強していたのでHashSetを扱ったことはあります.しかし,Cだと用意されていないのですね.
    調べて作ってみようと思います.

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.37%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る