C에서 거대한 행렬을 구현하는 방법

Question

나는 C로 수치 시뮬레이션을위한 프로그램을 작성하고 있습니다. 시뮬레이션의 일부는 서로 다른 노드에 약간의 부동 소수점 값을 갖는 공간적으로 고정 된 노드입니다. 그것은 유향 그래프와 같습니다. 그러나 두 노드가 너무 멀리 떨어져 있으면 (컷 - 오프 길이 a보다 멀리)이 값은 0입니다.

이 모든 "상관 관계"또는 부동 값을 나타 내기 위해 2D 배열을 사용하려고 시도했지만 저는 100.000 이상의 노드를 가지고 있는데, 이것은 40GB 메모리 정도에 해당합니다.

이제 저는 그 문제에 대한 다른 해결책을 생각하려고합니다. 나는이 모든 값을 하드 디스크에 저장하고 싶지 않습니다. 나는 또한 그들을 즉시 계산하고 싶지 않다. 하나의 아이디어는 Matlab에서 사용할 수있는 것과 같은 일종의 희소 행렬이었습니다.

다른 값,이 값을 저장하는 방법이 있습니까?

저는 C가 처음이므로 너무 많은 경험을 기대하지 마십시오.

감사와 안부, 월 올리버

Answer 1

주어진 노드의 차단 거리 내에 평균적으로 몇 개의 노드가 있는지 확인하여 메모리 요구 사항을 결정하고 디스크에 페이지해야하는지 여부를 알려줍니다. 최소한의 메모리를 차지하는 솔루션은 아마도 한 쌍의 노드를 거리에 매핑하는 해시 테이블 일 것입니다. 거리가 각면에서 동일하기 때문에 해시 테이블에 한 번만 입력하면됩니다. 두 개의 노드 번호를 숫자 순서대로 놓은 다음 결합하여 해시 키를 만듭니다. 이상적인 것은 아니지만 해시 테이블에 Posix hsearch/hcreate/hdestroy 함수를 사용할 수 있습니다.

Answer 2

스파 스 매트릭스 방식이 이상적 소리. Wikipedia article on sparse matrices은 여러 가지 구현 방법을 설명합니다.

Answer 3

가능한 경우 스파 스 매트릭스를 사용해야합니다. scipy에서는 스파 스 매트릭스에 대한 지원을 제공하므로 파이썬으로 재생할 수 있습니다. 솔직히 말해서 거친 지원은 여전히 ​​거친 모서리를 가지고 있습니다.

matlab에 액세스 할 수 있다면 확실히 ATM이 좋을 것입니다.

스파 스 매트릭스를 사용하지 않으면 memap 기반 배열을 사용하여 40GB의 RAM이 필요하지 않지만 느린 속도를 유지할 수 있으며 낮은 수준의 희박성이있는 경우에만 실제로 이해할 수 있습니다 (100000x100000 행렬의 10-20 %에 항목이 있으면 전체 배열이 실제로 더 빨라지고 어쩌면 희소 행렬보다 적은 공간을 차지할 것입니다).

Answer 4

스파 스 인접성 매트릭스는 하나의 아이디어이거나 인접성 목록을 사용할 수 있으므로 잘라내 기 값보다 가까운 가장자리 만 저장할 수 있습니다.

Answer 5

또한이 노드와 관련된 다른 노드를 포함하는 각 노드에 대한 목록을 보유 할 수도 있습니다. 그러면 목록 항목의 전체 수가 2 * k이됩니다. 여기서 k은 가상 행렬의 0이 아닌 값의 수입니다.

전체 시스템을 해시/세트/맵의 조합으로 구현하는 것은 임의 액세스를 허용하는 "실제"매트릭스와 비교하여 속도/성능면에서 여전히 받아 들여질 것으로 예상됩니다.

편집 :이 솔루션은 스파 스 매트릭스 구현의 한 가지 가능한 형태입니다. (아래의 짐 발터의 노트를 참고하십시오.) 감사합니다, 짐.)