문자열을 일정 시간에 복사 하시겠습니까?

Question

문자열의 각 문자를 반복하여 개별적으로 복사해야한다고 가정하기 때문에 O (n)으로 설명 된 문자열을 복사하는 작업을 보았습니다. 여기서 n은 문자열의 길이입니다. 그러나 컴파일러가 일정 시간 동안 전체 메모리 블록을 복사 할 수있는 명령어를 생성 할 수 없습니까? 오늘날의 일반적인 아키텍처에도 이러한 기능이 존재합니까?

Answer 1

제가 아는 한 멀쩡합니다.

그러나 O() 표기법이 의미가 있으려면 먼저 각 기본 작업의 비용을 정의해야합니다. 이것은 "생략 가능"하기 때문에 종종 생략됩니다. 그리고 대부분의 시간은 정말로 그렇습니다. 귀하의 (가설적인) 시나리오는 비용을 정의하는 것이 필수적인 상황의 좋은 예입니다.

또 다른 유용한 예제는 디스크 또는 테이프 저장소 검색/정렬 알고리즘을 분석하는 것입니다.

Answer 2

임의로 큰 데이터 블록을 복사하는 명령어를 사용하는 경우 해당 단일 명령어는 O (n) 시간 자체를 취하도록 바인딩됩니다.

Answer 3

일부 CPU 아키텍처는 하나의 위치에서 다른 위치로 메모리 블록을 복사하는 단일 명령을 가지고 있지만 그 단일 명령에는 많은 사이클이 걸렸으므로 여전히 O (n)이었습니다. 무슨 일이 있어도 CPU는 주소 버스를 통해 각 문자를 읽어야하므로 O (n)을 벗어날 방법이 없습니다.

Answer 4

1. O (n)이 선형이므로 일정 시간 또는 선형 미만이라고 생각합니다.

2. 메모리가 작동하기 때문에 불가능합니다. 복사 할 때 무언가는 기억의 각 세포에 접근하고 그것을 다른 세포에 베낄 필요가있다. 여러 셀을 병렬로 만들 수는 있지만 가변 개수의 셀을 만들 수는 없습니다. 결국 모든 비트는 전선을 사용하여 복사해야하며 메모리가 시스템을 연결하는 와이어의 수보다 크다고 가정해야합니다. DMI와 같은 독립 요소가 있기 때문에 프로세서 시간을 절약 할 수 있고 다른 것들을 병렬로 계산할 수 있으므로 계산 시간을 소비 할 필요가 없습니다.

P. 귀하의 질문은 이론적 인 컴퓨터 과학을 실제 기술과 구현과 혼합하여 질문의 정신으로 대답하기는 어렵지만 제기 한 요점을 다루려고 노력했습니다.

Answer 5

.NET 문자열은 변경 불가능한 참조 개체입니다. 참조 만 복사해야하므로 일정 시간에 "복사"됩니다.