내가하고있는이 프로그램은 소셜 네트워크에 관한 것으로 사용자와 프로필이 있음을 의미합니다. 프로파일 구조는 UserProfile입니다.그래프 구조를 어떻게 변경해야합니까 (매우 느리게 삽입합니까?).
이제 다양한 Graph 구현이 가능하며 최상의 그래프를 사용하고 있다고 생각하지 않습니다. Graph 구조체가 있고 내부에 Vertex 유형의 연결 목록에 대한 포인터가 있습니다. 각 Vertex 요소는 값을 가지며 다음에 대한 포인터 Vertex과 Edge 유형의 연결 목록에 대한 포인터를 갖습니다. 각 Edge 요소에는 값이 있습니다 (따라서 가중치를 정의 할 수 있습니다). 다음 Edge에 대한 포인터와 Vertex 소유자에 대한 포인터입니다.
처리 할 데이터가있는 2 개의 샘플 파일이 있고 (CSV 스타일) 그래프에 삽입됩니다. 첫 번째는 사용자 데이터 (한 줄에 한 명의 사용자)입니다. 두 번째 것은 그래프에 대한 사용자 관계입니다. 첫 번째 파일은 그래프에 빠르게 삽입됩니다. 왜냐하면 항상 머리에 삽입하고 ~ 18000 명의 사용자가 있기 때문입니다. 두 번째 파일은 나이가 들지만 머리 부분에 여전히 가장자리를 삽입합니다. 이 파일에는 약 520000 줄의 사용자 관계가 있으며 그래프에 삽입하려면 13-15 분이 소요됩니다. 빠른 테스트를했고 데이터를 읽는 것은 매우 빠르고 즉각적이었습니다. 문제는 삽입에 있습니다.
이 문제는 꼭지점에 대한 링크 된 목록으로 구현 된 그래프가 있기 때문에 발생합니다. 관계를 삽입해야 할 때마다 2 개의 꼭지점을 조회해야하므로 둘을 연결할 수 있습니다. 이것은 문제입니다 ~ 520000 관계에 대해 이것을하는 것은 시간이 좀 걸립니다.
어떻게 해결해야합니까?
솔루션 1) 어떤 사람들은 그래프 (정점 부분)를 링크 된 목록 대신 배열로 구현할 것을 권장했습니다. 이 방법으로 모든 꼭지점에 직접 액세스 할 수 있으며 삽입이 상당히 떨어질 것입니다. 그러나 [18000] 요소가있는 배열을 할당하는 아이디어가 마음에 들지 않습니다. 얼마나 실제적입니까? 내 샘플 데이터는 ~ 18000이지만, 훨씬 더 적거나 많이 필요하다면 어떻게 될까요? 연결된 목록 접근법에는 유연성이 있기 때문에 메모리가있는 한 원하는 크기를 가질 수 있습니다. 그러나 배열은 그런 상황을 어떻게 처리 할 것인가? 당신의 제안은 무엇입니까?
링크 된 목록을 사용하면 공간 복잡성에는 좋지만 시간 복잡성에는 좋지 않습니다. 그리고 배열을 사용하는 것은 시간 복잡성에는 좋지만 공간 복잡성에는 좋지 않습니다.
이 솔루션에 대한 의견이 있으십니까?
솔루션 2) 또한이 프로젝트에서는 이름 인덱스와 ID 인덱스를 기반으로 한 빠른 검색을 허용하는 데이터 구조가 필요합니다. 이를 위해 해시 테이블을 사용하기로 결정했습니다. 내 테이블은 충돌 해결로 별도의 연결로 구현되며 0.70의로드 요소가 도달하면 일반적으로 테이블을 다시 작성합니다. 이 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html에 다음 표의 크기를 지정합니다.
현재 두 해시 테이블 모두 사용자 프로필 자체의 복제 대신 UserProfile에 대한 포인터를 보유합니다. 그건 바보 같을 것입니다. 변화하는 데이터는 세 가지 변화가 필요하며 그렇게하는 것은 정말 바보입니다. 그래서 포인터를 UserProfile에 저장합니다. 동일한 사용자 프로필 포인터는 각 그래프 Vertex에 값으로 저장됩니다.
그래서 3 개의 데이터 구조, 하나의 그래프와 두 개의 해시 테이블을 가지며 그 중 하나의 테이블은 모두 정확히 UserProfile을 가리 킵니다. 그래프 구조는 해시 테이블이 이름과 ID로 빠른 인덱스 역할을하는 동안 이와 같은 최단 경로와 항목을 찾기위한 목적으로 사용됩니다.
내 그래프 문제를 해결하기 위해 해시 테이블 값이 UserProfile을 가리키는 대신, Vertex을 가리킨다. 여전히 포인터입니다. 더 이상 공간을 사용하지 않으며, 제가 지적한 바를 바꿉니다.
이와 같이 필자는 필자가 필요로하는 각 꼭지점을 쉽고 빠르게 찾아서 링크 할 수 있습니다. 그러면 ~ 520000 관계가 꽤 빠르게 삽입됩니다.
해시 테이블을 이미 가지고 있기 때문에이 솔루션을 생각해 보았습니다. 그런 다음 사용자 프로필 대신 그래프 정점을 인덱싱하는 데 왜 해시 테이블을 활용해야합니까? 기본적으로 똑같은데, 나는 여전히 UserProfile에 액세스 할 수 있습니다. 바로 Vertex으로 이동 한 다음 UserProfile으로 이동하십시오.
하지만 첫 번째 해결책에 대한이 두 번째 해결책에 대한 단점이 있습니까? 또는 첫 번째 솔루션에서 장단점을 압도하는 찬성?
기타 해결책 다른 해결책이 있다면, 나는 모두 귀입니다. 그러나 앞의 2 번에 비해 그 해결책의 찬반 양론을 설명해주십시오. 저는 지금 당장 이걸 낭비 할 시간이별로 없어요. 저는이 프로젝트를 계속 진행해야합니다. 변화, 정확히 무엇을 바꾸어야하는지 그리고 그것이 정말로가는 길인지 이해할 필요가 있습니다.
아무도 잠을 자다가 브라우저를 닫지 않았 으면 좋겠다. 큰 유감스럽게 생각한다. 그러나 나는 이것에 대해해야할 일을 정말로 결정할 필요가 있으며 나는 정말로 변화를 필요로합니다.
P.S : 내 제안 된 솔루션을 대답하면 내가 그래서 당신이 무슨 말을 정확히 알고 이미 나보다 내 스스로 더 혼동하지 마십시오처럼이 그들을 열거하십시오.
두 번째 솔루션은 내가하는 것처럼 들립니다. 그래프의 정점은 각각 소셜 네트워크에서 한 명의 사용자를 나타냅니다. – caf