文字列の比較の高速化

Question

質問内容

AtCoderの以下のリンクにおける過去問を解いていました．
最初に書いたコード１では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;
}

Answer 1

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

重複を除いて勘定するトコは(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] でソート完了。

Comments

[asm]

ソートアルゴリズムがバブルソートより遅いんで
競プロやるのならソートアルゴリズムくらい勉強しといた方がいいんじゃないですかね

[episteme]

Cで競プロはツラそう...

[grape_ll]

sortの速度も気にしなくてはいけないのですね．
教えていただいたものを使って試してみようと思います．

[grape_ll]

教えていただいたqsortでTLEの問題は解決しました．ありがとうございます．
この質問の大本が解決したうえでの質問で申し訳ないのですが，改良したコードでは今度は不正解がいくつかのパターンで出てしまうようになったのですが，なぜこのようなことが発生するのか教えていただけませんでしょうか．sortの部分しか触れていないのに，以前の二つのコードで正解していたところが不正解になってしまう理由が分かりませんでした．

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

char **str;

int str_compare(const void* left,const void* right){
char *left_char=(char *)left;
char *right_char=(char *)right;
return strcmp(left_char,right_char);
}

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]);
qsort(str,N,sizeof(char*),&str_compare);
for(int i=1;i<N;i++){
if(strcmp(str[i],str[i-1])!=0) count++;
}
//for(int i=0;i<N;i++) printf("%s\n",str[i]);
printf("%d\n",count);
return 0;
}

[episteme]

char *left_char=(char *)left;
char *right_char=(char *)right;
ココ↑、正しくは↓
char *left_char=*(char **)left;
char *right_char=*(char **)right;

[grape_ll]

https://qiita.com/goforbroke/items/422861c4af9b155e8f56
このサイトも参考にして書かせて戴いてました．
ご指摘通り
*を増やしてみても不正解の問題は減らなかったようなので，他にも何か原因になりそうな点があれば教えていただきたいです．
よろしくお願いいたします．

[episteme]

問題なさそうなんやけどな...
sortのあと、str[0]～str[N-1]は確かにソートされていますか?

[grape_ll]

解決できたみたいです！ありがとうございました！

[episteme]

「みたいです」って? なんかバグってた?

[grape_ll]

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

[episteme]

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

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

[grape_ll]

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

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

Answer 2

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での実装方法を探してみて下さい。

Comments

[episteme]

C++では:
ハッシュ　:　 std::unordered_set
二分木　:　 std::set

[raccy]

あ・・・

[raccy]

> epistemeさん

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

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

[episteme]

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

[grape_ll]

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

Answer 3

Pythonでは1行で済みますけどね。
https://atcoder.jp/contests/abc164/submissions/41716460