Constant time 'cons'

다음 'cons'함수가 O (n) 시간이 아닌 일정 시간이 걸릴 수있는 방법 (예 : 인수 유형 수정)이 있습니까? 즉, 목록을 작성하는 것은 O (n^2) 시간이 아닌 O (n) 시간이 걸릴 것입니다.Constant time 'cons'

나는 다음과 같은 조건에서 수행 할 수 있습니다 :

(1) 아니오 동적 메모리 없습니다 할당
(2) x는 여전히
(3) 입력 HEAD (즉 임시직에 대한 참조가 없을 수 있습니다) 유효합니다 (inlinable되지 않음) 개별적으로 컴파일되어 생성자의 작동 방법에

#include <type_traits> 

template <typename HEAD, typename TAIL> 
struct List 
{ 
    List(HEAD head, TAIL tail) : head(head), tail(tail) {} 
    typename std::remove_reference<HEAD>::type head; 
    typename std::remove_reference<TAIL>::type tail; 
}; 

template <typename HEAD, typename TAIL> 
List<HEAD, TAIL> cons(HEAD head, TAIL tail) 
{ 
    return List<HEAD, TAIL>(head, tail); 
} 

struct Empty {}; 

int main() 
{ 
    auto x = cons(1, cons(2, cons(3, Empty()))); 
    // x should still be valid here 
}

예를 가질 수있다.

컴파일러는 x의 유형을 알고 있으므로 스택에 공간을 할당합니다.

그래서 스택은 다음과 같습니다

p가 임의의 주소입니다

| Int1 | Int2 | Int3 | 
| p | p+4 | p+8 |

컴파일러는 cons(2, cons(3, Empty()))이라는 호출을 생성하고 반환 값을 p+4으로 지정합니다.

cons(2, cons(3, Empty())) 내부 컴파일러는 cons(3, Empty())에 대한 호출을 생성하여 p+8으로 반환합니다.

이렇게하면 cons이 호출 될 때마다 tail을 복사 할 필요가 없습니다.

컴파일러가이 최적화를 수행 할 수 있도록 코드를 잘 모르겠습니다. 일정한 실행 시간을 얻는 다른 방법이 있다면, 나는 그것을 사용하게되어 기쁠 것이다.

출처

2011-08-08 Clinton

"동적 메모리 할당 없음"요구 사항을 이해하지 못합니다. 'cons'는 정상적으로 * 않습니다 * 않습니다? –

현재 'cons'가 정확히 선형이라는 것을 설명 할 수 있습니까? 어떠한 방식 으로든 검사되지 않는 고정 된 수의 논쟁이 있습니다. 최종 표현 이요? –

그래서 당신은 연결된 목록을 만들고 있습니다. 그리고 그것은 사물에 대한 언급이 아니라 그 사본을 포함합니다. 따라서 O (n^2)는 모든 중첩 된'cons' 호출이 이전에 생성 된 모든 객체를 새로운 것으로 복사하는 인수의 복사본을 수행한다는 사실에서 비롯된 것 같습니다. –

조사 후 내 자신의 질문에 대한 답변을 드릴 것입니다. 그러나 누군가가 더 좋은 방법을 알고 있다면 나는 여전히 관심을 가질 것입니다.

(1) List에서 TempList으로 이름을 바꿉니다.
(2) 생성자 (이동 및 복사 포함)를 TempList으로 비공개로 만듭니다.
(3) TempList의 친구 cons으로 지정하십시오.
(4) HEAD 및 TAIL의 회원을 참조로 만드십시오.

이제 TempList에는 참조 만 있기 때문에 복사본이 없습니다. 그러나 이것들은 임시 변수에 대한 참조 일 수 있습니다. 그러나 임시 변수가 표현식의 끝까지 지속되기 때문에 OK입니다. TempList에는 개인 생성자 만 있기 때문에 식의 LHS에 할당 할 수 없습니다. 만 cons는 TempList 만들 수 있으며이 만들어집니다 식을 오래 살 수 없습니다.

지금 함수 save 또는 TempList 소요 진짜 List을 반환 효과의 무언가를 만들고, 저장 그것의 데이터가 다른 종류의 가치에 의해.

그래서 우리는

auto x = save(cons(1, cons(2, cons(3, Empty()))));

이 데이터는 전체 구조가 지금 O(n) 인, 복사 또는 대부분 한 번 (저장에 의한)에서 이동합니다. 구조는 아마도 cons과 save이 인라인되어있는 한 최적화 된 상태 일 것입니다.

출처

2011-08-08 05:07:02 Clinton

이것은 이것이'std :: tuple (1, 2, 3)'보다 낫지는 설명하지 않습니다. –

@Nicol Bolas : 죄송 합니다만, 좋은 예는 아니지만'cons '대신'f1','f2'와'f3'을 사용한다고 가정 해 보겠습니다. 'join','remove','insert' 등을 말하십시오. 각 단계에서 복사본을 수행하지 않고 std :: tuple과 같은 함수를 작성하는 방법은 무엇입니까? – Clinton

'List'에는 실제 객체 자체가 포함되어 있고 참조는 포함되어 있지 않으므로 어쨌든 여기에서 수행하는 내부 작업으로 복사 또는 이동을 수행해야합니다. 복사, 이동, 포인터없이'join','remove','insert'를 구현할 수 없습니다. 그리고 가능하다면, 이미'std :: tuple'의 일부가 될 것입니다. –

std::make_tuple 도우미로 std::tuple을 다시 작성하는 것 같습니다. 대신 사용하십시오. 표준은 std::tuple의 전달 생성자 또는 std::make_tuple에 대한 복잡성 보장을하지 않지만 두 가지가 완벽한 전달을 사용하므로 요소 당 정확히 하나의 move/copy/emplace 생성이 std::make_tuple에 대한 호출로 만들어 지므로 다소 의의가 있습니다. 나머지는 주변 참조를 걷고 있습니다. 그것은 최소한 구조적인 수의 선형 구조입니다.

물론 컴파일러가 모든 참조 셔플 링을 정상적으로 처리하지는 않지만 어쨌든 잘못된 레벨에서 최적화하고 있습니다.

설명을 위해

거의 아니지만 꽤 무슨 일이 :

template<typename... T> 
class tuple { 
    T... members; // this is not correct, only here for illustration 

    // The forwarding constructor 
    template<typename... U> 
    explicit 
    tuple(U&&... u) 
     : member(std::forward<U>(u)...) 
    {} 
}; 

template<typename... T> 
tuple<typename std::decay<T>::type...> 
make_tuple(T&&... t) 
{ return tuple<typename std::decay<T>::type...>(std::forward<T>(t)...); }

을 따라서 호출 auto tuple = std::make_tuple(1, 2, 3)에 세 일시적 int의 세 int&& xvalues가에서 다음 make_tuple에 대한 호출에서있다 먼저 std::forward<int>(t)... 안에있는 make_tuple을 호출하여 생성자의 인수를 int&& xvalues로 다시 전달하여 std::tuple<int, int, int>의 개념적 세 멤버에 전달합니다.

그냥 제가 구조물의 수에 대해 말한 것은 단지 std::make_tuple에 대한 호출이 아닌 전체 표현식 auto tuple = std::make_tuple(...);을 적용 것을 깨달았다. 튜플은 함수에서 반환되기 때문에 최종 변수로 이동/RVO가 필요할 수 있습니다. 여전히 선형 적이며 여전히 최적화를 원하는 컴파일러 중 하나이며 최적화에 대해 걱정할 여지는 여전히 있습니다.

그러나, C++ 0X는 그래서 이미 당신이 당신의 대답은 무엇을 설명 할 수있는 선 (善)으로 가득 :

이

int i = 3; 
std::tuple<int, int, int> tuple = std::forward_as_tuple(1, 2, i);

forward_as_tuple에 대한 호출이 std::tuple<int&&, int&&, int&>를 반환합니다. 이 도우미는 결코 값이있는 튜플을 반환하지 않으며 참조의 '얕은'튜플 만 반환합니다. std::tuple<int, int, int>의 적절한 변환 생성자는 두 개의 이동 및 사본으로 '구성원'을 초기화합니다. 이 바보 (un) 최적화는 두 개의 매달린 참조가있는 튜플 인 auto tuple = std::forward_as_tuple(1, 2, i);을 작성할 위험에 처하게됩니다.

출처

2011-08-08 06:22:20

Constant time 'cons'

답변

관련 문제