strlen とlenの違い

Question

C言語では、strlenの処理速度はO(n)ですが、PythonではlenのスピードはO(1)になると知りました。この原因は何でしょうか？？ なぜこの点処理についてはC言語よりPythonの方が早いのか、ご存じの方はいらっしゃいますでしょうか。

Answer 1

C言語で文字列を扱う場合、ヌル終端文字列という'\0'を終端の目印にした単純なcharの配列として表します。この構造は非常に単純です。しかし、長さを調べるには、先頭から一つ一つ'\0'でないか調べていく必要があります。だからstrlen()はO(n)の計算量が必要になるのです。

これに対して、Pythonを含めた後々の言語で文字列を表すとき、文字列の長さの情報も一緒に持つようにしました。ある文字列を生成したり、長さが変わるような処理を行った場合は、長さも同時に計算して文字列の実体と一緒に入れておくようにしたと言うことです。なので、長さを求める関数の演算では、その情報を取り出すだけで済むため、len()等はO(1)で済むことになります。

Cで表現すれば、

struct string {
  size_t len;
  char str[0];
};

のような構造体で構成されているという感じです(これは一例で、実際はもっと複雑だったり、言語によって異なります)。文字列の操作の時に毎回lenも一緒に計算しておけば、すぐに長さを求める事ができます。逆に言うと、その処理分、単純なヌル終端文字列よりも遅くなってしまう場合があるという欠点もあり、必ずしも有利ではありません。それに、C言語であっても長さを別途自分で計算して別途変数に入れておけば、strlen()を使わなくてもその場でO(1)で取り出すことができるでしょう。しかし、それはO(n)の処理を前倒しにしているに過ぎません。他の言語は常に前倒しにした方が有利と判断して、文字列に長さの情報も一緒に入れているというわけです。

なお、C言語以外がヌル終端文字列を使わない理由の一つに、'\0'を扱えないからと言うのがあります。通常のテキストデータで'\0'が現れる事はありませんが、'\0'が現れるバイナリデータや特殊なテキストデータ(通信のプロトコルによっては、区切りに'\0'使う物がある等)を扱おうとすると、ヌル終端文字列では処理がそこで停止してしまいます。'\0'を終端の目印にせず、別途長さを記憶していれば、'\0'が現れても処理を継続することができます。

他情報は最初の方にあるリンク先のWikipeidaも参考にしてみてください。

Comments

[arare000]

ありがとうございます。驚くほど詳細な内容で、大変勉強になりました。