Скопировать строку в постоянное время?

Question

Я видел операцию копирования строки, описанную как O (n), где n - длина строки, потому что предполагается, что нам нужно перебирать каждый символ строки и копировать ее отдельно.Однако не может ли компилятор генерировать инструкции, которые могут копировать весь блок памяти за постоянное время?Существует ли такая возможность даже в современных общих архитектурах?

Answer 1

1. Я думаю, что вы имеете в виду постоянное время или меньше, чем линейное, потому что O (n) является линейным.

2. Это невозможно, из-за того, как работает память. Когда вы копируете что-то, вам нужно получить доступ к каждой ячейке памяти и скопировать ее в другую ячейку. Можно сделать то, что будет несколько ячеек параллельно, но не переменное количество ячеек. В конце концов каждый бит должен быть скопирован с помощью электрического провода, и вы должны предположить, что ваша память больше, чем количество проводов, соединяющих систему. Это не обязательно должно занимать время вычислений, так как у вас есть независимые элементы, такие как DMI, которые могут высвободить процессорное время и позволить вам вычислять другие вещи параллельно.

P.S. Ваш вопрос сочетает теоретическую информатику с технологиями и реалиями реального мира, поэтому было сложно ответить в духе вопроса, но я попытался ответить на вопросы, которые вы затронули.

Answer 2

Некоторые архитектуры ЦП имели одну инструкцию для копирования блока памяти из одного места в другое, но эта единственная инструкция занимала много циклов, поэтому она все еще была O (n). Независимо от того, что процессор должен будет прочитать каждый символ через адресную шину, так что нет никакого способа обойти O (n).

Answer 3

Не так, как я знаю.

Однако, чтобы нотация O () была значимой, вы должны сначала определить стоимость каждой базовой операции. Это часто опускается, потому что «это очевидно». И большую часть времени это действительно так. Ваш (гипотетический) сценарий является хорошим примером ситуации, когда определение затрат имеет важное значение.

Другой, несколько более полезный пример - анализ алгоритмов поиска / сортировки дискового или ленточного хранилища.

Answer 4

Если вы используете инструкцию, которая копирует произвольно большой блок данных, то эта единственная команда обязательно займет O ( n ) времени.

Answer 5

В .NET строки являются неизменяемыми ссылочными объектами. Они «копируются» в постоянное время, потому что нужно скопировать только ссылку.