mojavy.com

C言語の文字列初期化について

January 21, 2013 at 08:00 PM | categories: C, programming |

なんとなく気になったので以下ひとりごと。

Cで文字列を初期化するときは以下のように書く。

char str[] = "xyz";

こう書けばNULL終わりのchar配列としてスタックに格納してくれるので、以下のように書くのと同じことになる。

char str1[4] = "xyz";
char str2[4] = {'x', 'y', 'z', '\0'};

文字列はcharのポインタで扱うからといって、

char *str = "xyz";

のように書くと違う意味になる。 こう書くと"xyz"が格納されているアドレスでポインタを初期化する。文字列リテラルで宣言したデータが格納される領域は通常はread onlyなので*str='X'などとするとセグフォするが、通常の代入と同じ意味なので違和感はない。

でも、char str[] = "xyz"; のほうはは冷静に考えると気持ち悪い。初期化と代入は違うといってしまえばそれまでだけど、この式だけみても予備知識がないとなにがおこるのかわからないと思う。

以下のような挙動も合理的とは思えない。そもそもCに配列なんて必要なかったのではないか。

void f1(char s[]) {
    /* 意味はないけどエラーでもない */
    s = "baz";
}

void f2(void) {
    char s[] = "foo";
    /* これはエラー */
    /* s = "bar"; */
}

などということを今更ながら考えて悶々としていたのだけど、結局のところこういう類の便利機能は欲しくなってくるわけで、便利さのために不合理を許容するとなるとこのあたりが妥当な落とし所のような気もしてきた。

まとめ：プログラミング言語を考える人はすごい

Common Lisp練習 - CodeChef : TSORT

October 24, 2012 at 06:00 PM | categories: programming, common lisp |

codechef

Common Lispの練習にCodeChefの↓の練習問題をやってみた。

http://www.codechef.com/problems/TSORT

問題自体は全然難しくないけど、Common Lispで解こうとしたらTime Limit Exceededでおちてしまった。

最初は以下のように書いて、

(let ((_n (parse-integer (read-line)))
      (lis ()))
  (dotimes (i _n)
    (push (parse-integer (read-line)) lis))
  (setf lis (sort lis #'(lambda (x y) (< x y))))
  (dolist (x lis) (format t "~a~%" x)))

以下の用にして時間を測ったところ

$ time ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}' | sbcl --script turbosort.cl > /dev/null
ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}'  1.19s user 0.01s system 91% cpu 1.311 total
sbcl --script turbosort.cl > /dev/null  3.42s user 0.43s system 97% cpu 3.938 total

ローカルだと3.42s程度だった。codechef上での制限は5secなのでセーフかと思ったけどTime Limit Exceededだった。

そこで、vectorを使うように改良

(let* ((_n (parse-integer (read-line)))
       (lis (make-array _n :fill-pointer 0)))
  (dotimes (i _n)
    (vector-push (parse-integer (read-line)) lis))
  (setf lis (sort lis #'(lambda (x y) (< x y))))
  (loop for i across lis do (format t "~a~%" i)))

$ time ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}' | sbcl --script turbosort.cl > /dev/null
ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}'  1.21s user 0.01s system 94% cpu 1.289 total
sbcl --script turbosort.cl > /dev/null  2.64s user 0.44s system 98% cpu 3.137 total

若干改善されたが、まだTime Limit Exceededだった。

read-sequenceで読み込んだほうが早いかと思って以下のように書いてみた。

(defun parse-input (str)
  (loop
     for i = 0 then (+ 1 j)
     as j = (position #\Newline str :start i)
     as k = (parse-integer (subseq str i j) :junk-allowed t)
     if (not (null k))
     collect k
     while j))

(let* ((_n (parse-integer (read-line)))
       (lis (make-array (* _n 20) :element-type 'character))
       (nums ())
       )
  (read-sequence lis *standard-input*)
  (setf nums (sort (parse-input lis) #'(lambda (x y) (< x y))))
  (loop for i in nums do (format t "~a~%" i)))

$ time ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}' | sbcl --script turbosort.cl > /dev/null
ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}'  1.13s user 0.01s system 97% cpu 1.159 total
sbcl --script turbosort.cl > /dev/null  3.67s user 0.48s system 96% cpu 4.297 total

残念ながら逆に遅くなってしまった。parse-inputの部分で60%くらい時間がかかっていた。 あと、#'(lambda (x y) (< x y))の部分を #'<にするとなぜか遅くなる。

まだ誰もlispではパスしてない模様。こういうのをもっと高速に書く方法あるのだろうか。

ちなみにCだと余裕。ローカルだと0.2秒くらいだけどリモートでは3秒くらいかかってた。そもそもCodeChefの実行環境がしょぼすぎる疑惑が。。

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

int f(const void *i, const void *j) {
    return *((int*)i) > *((int*)j);
}

int main(void) {
    char buf[256];
    int num = atoi(fgets(buf, 256, stdin));

    int lis[num];
    for (int i = 0; i < num; ++i) {
        lis[i] = atoi(fgets(buf, 256, stdin));
    }
    qsort(lis, num, sizeof(int), f);
    for (int i = 0; i < num; ++i) {
        printf("%d\n", lis[i]);
    }

$ time ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}' | ./a.out > /dev/null
ruby -e 'n=1000000;puts n; n.times{puts (rand * 10000000).to_i}'  0.99s user 0.01s system 99% cpu 1.006 total
./a.out > /dev/null  0.18s user 0.01s system 17% cpu 1.116 total

About Me

pic
mojavy

Recent posts



Categories

Badges