ページ 1 ／ 1
Count Sort でRuntime Error
Posted: 2016年11月09日(水) 12:09
by cotora
c++勉強のため、AOJ (Aizu Online Judge)にあるCount Sortという問題（
リンク）に取り組んでいるのですが、n=2000000のテストケースでRuntime Errorとなってしまいます。
一応、問題中にある擬似コードに沿っているつもりなのですが、どこがまずいのかご指摘いただけると嬉しいです。
私が書いているコードです。
コード:
#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX_ELEM 10001
int n;
void sort(int A[], int B[], int C[]){
for (int i=0; i<n; i++){
scanf( "%d", &A[i]);
C[A[i]]++;
}
for (int i=1; i<MAX_ELEM; i++){
C[i] = C[i] + C[i-1];
}
for (int i=n-1; i>=0; i--){
int idx = C[A[i]]-1;
B[idx] = A[i];
C[A[i]]--;
}
}
int main(){
scanf( "%d", &n);
int A[n];
int B[n];
int C[MAX_ELEM]; // 0 to 10000
sort(A, B, C);
printf("%d", B[0]);
for (int i=1; i<n; i++){
printf("%s%d", " ", B[i]);
}
printf("\n");
}
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 14:48
by みけCAT
巨大な自動変数を宣言しているため、スタックオーバーフローの疑いがあります。
main関数内のAおよびBを可変長配列ではなくポインタにし、new[]を用いてメモリを動的確保するようにするとどうなりますか？
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 14:52
by みけCAT
cotora さんが書きました:一応、問題中にある擬似コードに沿っているつもりなのですが
擬似コードではCがきちんと初期化されているのに、cotoraさんのコードでは初期化されていないですね。
初期化をしましょう。
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 16:14
by YuO
直接関係ありませんが，記述されているコードは C でしょうか。 C++ でしょうか。
- Cだと，using namespace std;は不正。また，通常<iostream>は存在しない。
- C++だと，int A[n];およびint B[n];は不正。
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 17:01
by みけCAT
オフトピック
YuO さんが書きました:C++だと，int A[n];およびint B[n];は不正。
C++標準規格では不正ですが、拡張があるGCCやclangでは使えます。
(個人的には使わないべきであると思いますが)
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 17:09
by みけCAT
オフトピック
ついでに蛇足を書くと、
YuO さんが書きました:Cだと，using namespace std;は不正。
コンパイルオプションによって定義されるマクロによっては、不正とは限りません。
もっとも、AOJではそんな変なマクロは定義されないでしょうが。
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 17:43
by あんどーなつ
私もやってみました。とりあえず、CountingSort関数以外をあげておきます。
ex1.cpp
コード:
#include <iostream>
#include <cstdint>
using namespace std;
typedef uint16_t INTK;
typedef uint32_t INTN;
typedef uint32_t INTC; // max(c) = 2 * max(n)
void CountingSort(INTK *a, INTK *b, INTC *c,
INTK k, INTN n)
{
(省略)
}
int main()
{
INTN n;
cin >> n;
INTK *a = new INTK[n+1]; //a[0]は使わない
for (INTN i = 1; i <= n; ++i) cin >> *(a+i);
INTK k = 0;
for (INTN i = 1; i <= n; ++i)
if (*(a+i) > k) k = *(a+i);
INTK *b = new INTK[n+1]; //b[0]は使わない
INTC *c = new INTC[k+1];
CountingSort(a, b, c, k, n);
for (INTN i = 1; i <= n; ++i) cout << *(b+i) << " ";
return 0;
}
大きな問題を生成するperlスクリプト
コード:
$n = 2000000;
$k = 10000;
print($n, "\n");
for ($i = $n - 1; $i >= 0; $i--) {
print(($i % $k), " ");
}
print("\n");
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 18:54
by あんどーなつ
すみません、return 0;の前に次の三行が必要です。
コード:
delete [] a;
delete [] b;
delete [] c;
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 20:17
by あんどーなつ
オフトピック
ちなみに今知ったのですけど、cinとscanfだと実行時間に10倍くらいの違いがあるようですね。
cin.cpp
コード:
#include <iostream>
int main() {
int n, tmp;
cin >> n;
for (int i = 0; i < n; ++i) cin >> tmp;
return 0;
}
scanf.cpp
コード:
#include <cstdio>
int main() {
int n, tmp;
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &tmp);
return 0;
}
実行結果 (test2は私がperlスクリプトで作成したテキストファイル)
コード:
$ g++ cin.cpp -std=c++11 -o cin
$ g++ scanf.cpp -std=c++11 -o scanf
$ time ./cin < test2
real 0m3.193s
user 0m3.156s
sys 0m0.015s
$ time ./scanf < test2
real 0m0.426s
user 0m0.390s
sys 0m0.000s
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 21:08
by あんどーなつ
オフトピック
自前の整数読み取り関数も作ってみました。
getint.cpp
コード:
#include <cstdio>
using namespace std;
inline int getint() {
unsigned char c;
do { c = getchar(); }
while (c == ' ' || c == '\n');
int res = c - '0';
while ((c=getchar()) >= '0' && c <= '9') {
res *= 10;
res += c - '0';
}
return res;
}
getint2.cpp
コード:
#include <cstdio>
using namespace std;
constexpr size_t BUFLEN = 1024;
unsigned char buf[BUFLEN];
size_t cnt = BUFLEN - 1;
inline unsigned char rd() {
++cnt;
if (cnt == BUFLEN) {
fread(&buf, 1, BUFLEN, stdin);
cnt = 0;
}
return buf[cnt];
}
inline int getint() {
unsigned char c;
do { c = rd(); }
while (c == ' ' || c == '\n');
int res = c - '0';
while ((c=rd()) >= '0' && c <= '9') {
res *= 10;
res += c - '0';
}
return res;
}
実行結果
コード:
$ time ./getint < test2
real 0m0.748s
user 0m0.734s
sys 0m0.015s
$ time ./getint2 < test2
real 0m0.085s
user 0m0.046s
sys 0m0.015s
Re: Count Sort でRuntime Error
Posted: 2016年11月09日(水) 23:35
by cotora
みけCAT様＞
ありがとうございます！
教えていただいたとおりnew[]を用いたところ、問題となっていたテストケースをパスすることができました。初期化についても指摘していただき、ありがとうございます。
YuO様＞
現在C++を勉強中です。C++だと，int A[n];およびint B[n];は不正、というのは知りませんでした。教えていただきありがとうございます！
あんどーなつ様＞
コードを上げていただきありがとうございます。scanfのほうが速いというのは私も最近知ったばかりなのですが、10倍も違うのですね。