C++에서 트리를 deserialize하는 가장 빠른 방법은 무엇입니까

Question

저는 C++로 구현 된 매우 작은 나무 구조 (Burkhard-Keller-Tree, 메모리에서 100MB 이상)로 작업하고 있습니다. 각 노드의 하위에 대한 포인터는 QHash에 저장됩니다.

각 노드 x는 n 개의 자식 y [1] ... y [n]을 가지며, 자식 노드의 가장자리는 편집 거리 d (x, y [i])로 레이블되어 있으므로 해시를 사용하여 노드는 분명한 해결책입니다.

class Node { 
    int value; 
    QHash<int, Node*> children; 
    /* ... */ 
}; 

또한이 파일을 직렬화하고 비 직렬화하여 파일로 만듭니다 (현재 QDataStream을 사용하고 있습니다). 나무는 단지 한 번 지어졌고 변경되지 않습니다.

트리를 만들고 deserialize하는 것은 다소 느립니다. 나는 트리를 명백한 방법으로로드하고있다 : 재귀 적으로 각 노드를 구축한다. 나는 이것이 new 연산자로 별도로 생성 된 많은 노드들 때문에 차선책이라고 생각한다. 나는 어딘가에서 new가 꽤 느리다는 것을 읽었다. 초기 빌드는 트리가 다소 안정적이어서 자주 다시 빌드 할 필요가 없기 때문에 큰 문제는 아닙니다. 그러나 파일에서 트리를로드하는 것은 가능한 한 빨리해야합니다.

이 작업을 수행하는 가장 좋은 방법은 무엇입니까?

인접한 노드가있는 단일 메모리 블록에 전체 트리를 저장하는 것이 훨씬 더 좋습니다. 직렬화와 직렬화를 줄이면 전체 블록을 저장하고로드 할 수 있습니다.이 블록은 한 번만 할당해야합니다.

그러나 이것을 구현하려면 QHash, AFAIK를 다시 구현해야합니다.

역 직렬화의 속도를 높이려면 어떻게해야할까요?

부록 몇 가지 프로파일 링을 할 수 귀하의 제안에 감사드립니다. 다음 결과는 다음과 같습니다

파일에서

1 % of the time is consumed by my own new calls 
65 % is consumed by loading the QHash objects (this is implemented by the 
    Qt Library) of each node 
12 % is consumed by inserting the nodes into the existing tree 
20 % is everything else 

를 트리를 재 구축하는 것은 그래서 definitly 지연의 원인이 있지만, QHash 모든 노드에서 객체의 재 구축 나의 새로운 통화 아니지만. 이것은 기본적으로 다음과 같이 수행됩니다 :

QDataStream in(&infile); 
in >> node.hash; 

QHash를 파고 거기에서 무슨 일이 일어나는지 살펴야합니까? 최선의 솔루션은 내부 데이터 구조를 다시 작성할 필요없이 단일 읽기 및 쓰기 작업으로 직렬화 할 수있는 해시 객체가 될 것이라고 생각합니다.

Answer 1

또 다른 방법은 포인터를 직렬화하고로드 할 때 복원하는 것입니다.내 말은 :

직렬화 :

nodeList = collectAllNodes(); 

for n in nodelist: 
write (&n) 
writeNode(n) //with pointers as-they-are. 

직렬화 복원 :

//read all nodes into a list. 
while (! eof(f)) 
    read(prevNodeAddress) 
    readNode(node) 
    fixMap[prevNodeAddress] = &node; 
    nodeList.append(node); 

//fix pointers to new values. 
for n in nodeList: 
    for child in n.children: 
     child->node = fixMap[child->node] 

당신이 한 번 벡터 및 사용을 할당 할 수있는 새로운 노드를-제거 삽입하지 않는 경우이 방법이 (rpg가 말한 것처럼, 목록이나 벡터를 사용하는 것이 더 빠를 수도 있습니다).

Answer 2

나는 매우 boost serialization library을 권장합니다. 사용중인 솔루션과 함께 작동해야합니다.

Answer 3

serialize/deserialising의 가장 빠른 방법은 말 그대로 연속 된 메모리 블록을 디스크에 쓰는 것입니다. 트리 구조를 변경하여 (아마도 커스텀 할당 루틴을 사용하여) 이것을 만들었다면 이것은 매우 쉬울 것입니다.

불행히도 저는 QHash에 익숙하지 않지만 그것을 보는 것으로부터 나무가 아닌 Hashtable처럼 보입니다. 내가 너를 오해 했니? 이것을 사용하여 중복 노드를 매핑합니까?

난 당신이 시간을 사용하는 곳 찾기 위해 프로파일을 (지금하여 Rational 그러나 PurifyPlus라는 정량화를 사용하는 데 사용하지만, 많은 listed here가) 사용하는 거라고,하지만 난 그것을 여러 메모리 할당이 아닌 중 하나입니다 추측에는 요 단일 할당, 또는 단일 읽기가 아닌 다중 읽기. 앞에서 설명한 두 가지 문제를 해결하기 위해 필요한 수의 노드를 미리 알고 있으므로 올바른 길이의 노드 배열을 쓰거나 읽습니다. 각 포인터는 메모리의 포인터 대신 배열에 대한 인덱스입니다. .

Answer 4

다른 해결책은 메모리 공간을 연속적으로 사용하는 자체 메모리 할당자를 사용하는 것입니다. 그러면 메모리를 그대로 덤프하고 다시로드 할 수 있습니다. 플랫폼 (즉, 빅 엔디안/리틀 엔디안, 32 비트/64 비트)에 민감합니다.

Answer 5

당신이 말했듯이, 새로운 개체를 할당하는 것은 느릴 수 있습니다. 이는 풀이 고갈 될 때까지 개체 풀을 할당 한 다음 미리 할당 된 개체를 사용하여 향상시킬 수 있습니다. 이 클래스의 새/삭제 연산자를 오버로드하여 백그라운드에서 작동하도록 구현할 수도 있습니다.

Answer 6

우선 무엇보다 시간이 오래 걸리므로 응용 프로그램의 프로필을 작성하십시오. 느린 속도로 읽을 수도 있고 반복을 통해 충분하지 않을 수도 있으므로 새 항목에 대한 의문을 제기하십시오.

IO 작업 일 가능성이 있습니다. 파일 형식이 올바르지 않거나 비효율적 일 수 있습니다.

어딘가에 결함이있을 수 있습니다.

어쩌면 문제의 원인에 대해 기억하지 못하는 이차원 루프가있을 수도 있습니다. :)

사례에 실제로 소요되는 시간을 측정 한 다음 문제에 접근하십시오. 많은 시간을 절약 할 수 있으며 찾기 전에 존재하지 않는 성능 문제를 해결하기 위해 디자인/코드를 위반하지 않아도됩니다. 진짜 원인.

Answer 7

오버로드 된 연산자 new() 및 delete()가있는 자신의 메모리 할당은 저렴한 옵션 (개발 시간)입니다. 그러나 이것은 메모리 할당 시간에만 영향을 미치며 Ctor 시간에는 영향을 미치지 않습니다. 마일리지는 다를 수 있지만 시도해 볼 가치가 있습니다.

Answer 8

내 의견을 조금 확장됩니다 : 당신의 프로파일이 QHash 직렬화가 가장 시간이 걸리는 것을 제안 이후

는

, 나는 직렬화 속도에 올 때 QList와 QHash를 교체하는 것은 상당한 개선을 얻을 것이라고 생각합니다.

QHash 직렬화는 키/값 쌍을 출력하지만 역 직렬화는 해시 데이터 구조를 구성합니다.

빠른 하위 조회가 필요하다고해도 QHash를 QList>를 테스트로 바꾸는 것이 좋습니다. 각 노드마다 자식이 많지 않은 경우 (예 : 30 개 미만) QList를 사용해도 조회가 여전히 빠릅니다. QList가 빠르다는 것을 알게된다면, (de) serializaton을 위해서만 사용할 수 있고, 트리가로드되면 나중에 해쉬로 변환 할 수 있습니다.