memmove는 (for-loop와 같은 방식으로) 요소를 시프트합니까? 아니면 전체 메모리 블록을 한 번에 잡아낼 수 있습니까?

Question

내 알고리즘 클래스에서 정수 목록의 중복을 제거하고 최대한 낮은 복잡도로 촬영하는 알고리즘을 사용해야합니다. 내 알고리즘에서, 중복 된 정수를 볼 때 for 루프를 사용하여 복제 된 요소를 삭제하기 위해 그 정수 다음에있는 모든 요소를 ​​하나의 인덱스로 이동합니다. like :

내 알고리즘이 memmove를 사용하는 것이 더 효율적입니까? 또한 알고리즘을 설계하는 것이 내 직업이라면, memmove를 사용하여 알고리즘의 복잡성을 낮추면 memmove를 '부정 행위'로 보일 수 있습니까?

Answer 1

부정 행위에 대해서는 잘 모르지만, memmove은 기본적으로 루프가하는 일을보다 효율적으로 수행합니다.

게다가 가장 기본적인 유틸리티 함수 중 하나이기 때문에 사용하지 않아야합니다.

복잡도는 알고리즘의 순서가 변경되지 않으며 간단합니다. memmove은 어셈블리에서 구현되며 정렬을 최대한 활용하여 바이트 당 바이트 대신 단어 당 단어를 복사합니다.

편집 :

잘 알았지 설명서 사본 memmove에 대한 호출보다 짧은 명령의 몇 가지있을 경우가있을 수 있습니다,하지만 당신은 메모리에 주위에 데이터를 이동 시작하면, 당신은 본질적으로하고있는 값 비싼 작업이므로 CPU주기를 두 배로 멀리하여도 큰 그림에는 아무런 차이가 없습니다.

디자인에 성능이 중요한 데이터를위한 내부 이동이 포함 된 경우 복사본을 모두 피하는 (목록, 트리, 해시 테이블 등) 기본 데이터 구조를 변경하는 것이 좋습니다.

Answer 2

여러분의 프로그램은 벽시계 시간까지 memmove를 사용하여 더 빨리 실행될 수 있지만 for 루프는 기본적으로 동일한 것을 달성합니다. 알고리즘의 복잡성은 변하지 않습니다.

Answer 3

기능적으로, memmove는 루프가하는 것과 정확히 일치합니다. 그러나 컴파일러 및/또는 C 런타임은보다 효율적인 기계 코드를 사용하여 memmove를 구현할 수 있습니다. 일부 아키텍처는 단일 명령으로 이러한 작업을 완전히 수행하는 특수 명령을 가지고 있습니다. 컴파일러도 인라인 될 수 있습니다.

알고리즘의 복잡성을 변경하지 않고 더 빨리 처리 할 수 ​​있습니다.

과제에서 부정 행위로 간주 될 수 있는지 여부는 교수님의 질문입니다. 여기 아무도 당신에게 말할 수 없습니다.

Answer 4

이 아닌 중복 저장하는 auxillary을 사용할 수있는 것보다 여러 개의 중복이있는 경우 : -

int aux[arr_size],cnt=0; 

for(int i=0;i<arr_size;i++) { 

    if(arr[i]!=dup) { 

     aux[cnt++] = arr[i]; 
    } 
} 

당신이 올바른 위치해야하는 경우 : -

int i = dup_index; 
int j = dup_index+1; 
int dup = arr[i]; 

while(j<arr_size) { 

    if(arr[j]!=dup) { 

     arr[i++] = arr[j]; 

    } 

    j++; 

} 

Answer 5

라이브러리 함수는 (같은 memmove(3))입니다 신중하게 최적화. 좋아하는 컴파일러가 어셈블리 언어로 다양한 길이 (상수로 주어짐)로 쓰는 방법을 살펴 본다면 아마도 큰 놀라움을 얻게 될 것입니다.

말하자면, 한 장소에서 다른 장소로 $ n $ 바이트를 복사하는 것은 시간이 많이 걸리는 데이터를 피하는 데 도움이되는 것을 알지 못하는 한 시간당 $ \ Theta (n) $를 사용합니다. 고정 된 비율로.