Data.Arrayの速さはどれくらいですか？

Haskellは、そのドメイン整数の連続するサブセットに同形である関数と考えることができるインデックス可能なアレイを提供します。このように制限された機能は、効率的に実装することができます（）。特に、プログラマは、コンポーネントに迅速にアクセスすることを合理的に期待することがあります（）。

(!)と(//)はどれくらい速いのですか？ O（1）の複雑さから、私は彼らの命令的な対応者と同じようなものがあると思いますか？

一般的には、O（1）が!から期待できるはずですが、標準で保証されているかどうかはわかりません。

（ストリーム融合を使用して）より高速な配列が必要な場合は、ベクターパッケージが必要です。それはまた、より良い設計です。

//はおそらくO（n）ですが、（命令的プログラムと同じように）リストを走査しなければならないためです。突然変異がたくさん必要な場合は、MArrayまたはMVectorを使用できます。

2011-09-02 21:21:13 alternative

'（//）'は配列の新しいコピーを作る必要があるので、実際にはarray_の_sizeのリニアです。しかし、変更可能な配列を使用すると、更新の数が線形であることが期待されます。 – hammar

@ハマーそれはリストを反復するだけでなく、配列をコピーする必要があるので、両方とも線形です。しかし、一括更新機能を必要としないので、MArrayではむしろ無駄です。 – alternative

はい、もちろんです。しかし、いくつかの要素を複数回更新している場合は、それは本当に問題になります。 – hammar

答えて