동적 배열이 너무 많아지는 것은 언제 위험합니까?

Question

저는 현재 도시와 교량을 다루는 과제 코드를 작성하고 있습니다. 나는 도시를 인쇄해야하고 같은 자신의 존경받는 지역에서 다리 : 프로그램을 통해 실행 후에는 다음과 같이 정렬됩니다

//unorganized inputs from user given the # of "paths" we need 
4  // the # of paths 
1 2 5 // 1 = city , 2 = city, 5 = bridge length 
6 7 5 // 6 = city , 7 = city, 5 = bridge length 
2 3 7 // 2 = city , 3 = city, 7 = bridge length 
6 9 7 // 6 = city , 9 = city, 7 = bridge length 

: 이제

first district 
1 2 5 
2 3 7 

2nd district 
6 7 5 
6 9 7 

, 나는이 입력을 읽을 수 있습니다 cin을 통해. 1 2 5와 같은 가능한 모든 경로를 배열에 저장 한 다음 프로그램을 통해 정렬 및 구성하려고합니다. 문제는 사용자로부터 50 만 개가 넘는 경로가있을 수 있다는 것입니다. 500k 동적 배열을 만들고 싶습니다. 이것이 기억의 측면에서 심각한 문제를 일으킬 것입니까?

나는 kruskal의 알고리즘과 분리 된 세트 (가장 유용하다고 생각한다)와 같은 다른 가능한 해결 방법을 살펴 보았다. 분리 된 세트의 코딩을 이해하는 데 어려움을 겪고 있습니다. 더 익숙한 방식으로 시도했습니다.

어디에서 값을 저장하고 비교하고 정리할 수있는 도움이 될 것입니다. 이 정보를 읽은 곳으로 연결되는 링크가 도움이 될 것입니다. 나는 지난 며칠 동안 많은 것을 읽었습니다. 많이 도움이되지 않았다.

이 모든 것을 요약하면, 내 질문은 :

• 윌 50 만 동적 배열 원인이 메모리의 측면에서 심각한 문제가?
• 값을 저장하고 경로를 비교하여 정리하는 위치는 어디입니까?

Answer 1

500k 동적 배열은 메모리 측면에서 심각한 문제를 일으 킵니까?

각 문제가 3 개의 정수로 이루어진 것으로 가정하면 문제가 없습니다. 일반적으로 과도하기 때문에 이것을 별도의 할당으로 사용하지 마십시오. 약간 느리고 필요한 부기도 상당한 양의 메모리를 소비합니다. 더 나은 접근 방식이 있습니다 :

값을 저장하고 경로를 비교하여 정리하는 위치는 어디입니까?

그 3 개의 필드를 보유하는 struct/class로 시작하고 그 중 std::vector을 사용하십시오. 그러면 모든 값이 하나의 연속 할당으로 저장됩니다. 비교할 때 생성, 검색 및 할당이 매우 빠릅니다.

Answer 2

일반적으로 앱에 2 기가 메모리가 있다고 가정하면 값에 32 비트를 사용한다고 가정 할 때 12 바이트의 500K 레코드가 문제가되지 않습니다.
당신이 당신의 데이터 세트의 크기를 줄이고 싶다면, 당신은 할 수, 예를 들어, 사용 데이터 형식과 같은 : 도시 세트의 크기로

struct { 
    unsigned short city_a; 
    unsigned short city_b; 
    char length; 
} 

봐 (도시 수), 최대 두 도시 사이의 길이.
또한 도시 쌍 색인 생성 (A-B가 Pair_ID가 됨)과 같은 작업을 수행하면 데이터 집합도 줄일 수 있습니다.

Answer 3

이것은 귀하의 질문과 직접적으로 관련이 없을 수도 있지만, 귀하가 성취하려고하는 것은 - http://en.wikipedia.org/wiki/Connected_component_(graph_theory입니다.그래프를 인접 행렬로 모델링하면 500k 동적 배열을 할당 할 필요가 없습니다. 데이터를 저장할 때 다음 형식을 고려하십시오.

int city_map [MAX_NO_OF_CITIES][MAX_NO_OF_CITIES]; 

city_map[i][j] = length_of_brigde_connecting_city_i_to_j; 

이렇게하면 500,000 개의 항목을 저장하면 1MB를 약간 넘게됩니다.