一定の時間内に文字列をコピーしますか？

Question

O（n）と記述された文字列をコピーする操作を見てきました。ここでnは文字列の長さです。文字列の各文字を繰り返し処理して個別にコピーする必要があるためです。しかし、コンパイラが一定時間にメモリブロック全体をコピーできる命令を生成することはできないのでしょうか？このような機能は、今日の一般的なアーキテクチャにも存在しますか？

Answer 1

私の知る限りではありません。

ただし、O（）表記が意味を持つためには、まず各基本操作のコストを定義する必要があります。これはしばしば省略されます。「明らかです」。そして、それは本当に大部分です。あなたの（架空の）シナリオは、コストの定義が不可欠な状況の良い例です。

もう1つ、もう少し有用な例は、ディスクまたはテープストレージの検索/ソートアルゴリズムの分析です。

Answer 2

任意の大きさのデータブロックをコピーする命令を使用すると、その単一命令はO（n）時間かかるようにバインドされます。

Answer 3

一部のCPUアーキテクチャでは、1つの場所から別の場所にメモリブロックをコピーする命令が1つしかありませんでしたが、その1つの命令には多くのサイクルがかかったため、依然としてO（n）でした。何があっても、CPUはアドレスバスを介して各文字を読み取らなければならないので、O（n）を回避する方法はありません。

Answer 4

1. O（n）が線形なので、あなたは一定の時間を意味すると思います。

2. メモリの仕組みのため、できません。あなたが何かをコピーするときには、何かがメモリのすべてのセルにアクセスし、それを別のセルにコピーする必要があります。いくつかの細胞が並行して何かを作ることは可能ですが、可変数の細胞を作ることはできません。結局、すべてのビットは電線を使用してコピーしなければならず、メモリがシステムに接続するワイヤの数よりも多いと仮定する必要があります。 DMIのような独立した要素があり、プロセッサ時間を解放し、他のものを並行して計算させるので、必ずしも計算時間を消費する必要はありません。

P.S.あなたの質問は、理論的なコンピュータサイエンスと実際の技術と実装を混在させているので、質問の精神で答えにくいですが、私はあなたが提起したポイントに対処しようとしました。

Answer 5

.NET文字列では、不変参照オブジェクトです。参照のみをコピーする必要があるため、一定時間内に "コピー"されます。