정렬되지 않은 목록에서 정렬 된 목록으로 전환 할시기는 언제입니까? [최적화]

Question

복셀의 3D 볼륨을 분해하는 알고리즘을 구현해야합니다. 알고리즘은 절단 계획의 각면에있는 정점과 절단 계획을 통과하는 두 번째 단계에서 식별하는 것으로 시작합니다.

이 프로세스는 정렬 된 목록의 이점을 사용하여 최적화 할 수 있습니다. 분리 점을 식별하는 것은 O log (n)입니다. 하지만 축마다 하나의 정렬 된 목록을 유지해야하며 꼭지점과 가장자리에 대해이 목록을 유지해야합니다. 이것은 GPU에서 사용하도록 구현 될 것이므로 메모리 관리 (예 : CUDA)에 대한 제약도 있습니다. 침입 목록 M/trees 및 C가 부과됩니다.

완전한 "voxelization"으로 ~ 4000 포인트와 12000 개의 가장자리로 오래 갈 것입니다. 다행히도 똑똑한 전략을 사용하여 처리 된 복셀을 제거하고 잔량을 최소화하여 주문 수량을 최소로 유지함으로써 최적화 할 수 있습니다. 이 경우에는 100 점 미만과 300 개의 가장자리를 가질 것으로 예상됩니다. 따라서 프로세스를 관리하기가 더 복잡해 지지만 더 효율적으로 처리 할 수 ​​있습니다.

따라서 정렬 된 데이터 구조를 사용하면 얻는 이점이 간단한 침입 링크 된 목록과 비교할 때 노력과 복잡성 오버 헤드가 필요할 때를 결정하는 데 도움이되는 질문입니다.

Answer 1

질문은 언제나 가장 일반적인, 액세스 또는 추가라는 종업원이됩니다. 순서가 지정되지 않은 목록이있는 경우 추가하는 데 시간이 걸리지 않으며 특정 항목에 액세스하는 데 시간이 더 걸립니다. 정렬 된 목록이있는 경우 추가하는 데 시간이 오래 걸리지 만 액세스하는 것이 더 빠릅니다.

데이터를 추가하는 대신 대부분의 시간을 소비하는 대부분의 응용 프로그램은 정렬 된 목록을 만들 때 (실행되는) 시간 오버 헤드가 일반적으로 균형을 이루거나 목록에 액세스 할 때 저장되는 시간으로 처리된다는 것을 의미합니다. 데이터에 많은 변동이있는 경우 (소리가 나지 않는 경우) 정렬 된 목록을 유지 관리하는 것이 반드시 권장 할만한 것은 아닙니다. 사용자가 지속적으로이 목록을 상당한 CPU 비용으로 사용하기 때문입니다.

은 유용한 방법으로을 정렬 할 수없는 경우에만 데이터 구조의 복잡성이 중요합니다. 그들이 정렬 할 수 있습니다 경우에, 당신은 액세스의

수의 발견으로 이동해야합니다 : 정렬 좋은 생각 인 경우 변경

의 수를 결정합니다.

Answer 2

chmike,이 방법은 처음에는 간단한 방법으로 수행하고 싶은 동작과 비슷합니다. 어떤 종류의 GPU voxelization 접근법이라도 적어도 한 번 큰 볼륨으로 들어가면 시스템 세부 사항에 꽤 취약합니다 (사용자에게는없는 것으로 보입니다). 당신의 신발에 나는 확실한 이유가 없는지를 확인하기 위해 먼저 직접 구현을 원할 것입니다 ....

Answer 3

모든 대답을 고려한 후에 중복 계산을 피하는 데 사용 된 나중의 방법은 데이터 구조를 유지 관리하고 탐색하기 때문에 효율성이 떨어지는 결과를 초래한다는 것을 알게되었습니다. 게다가 초기 방법은 몇 가지 작은 커널 루틴과 병렬 처리하여 GPU 구현에 더 적합합니다.

초기 방법 확인 볼륨 최적화 방법을 잘 수행 할 수있는 중요한 최적화 기회를 발견했습니다.

나는 하나의 대답을 선택해야했기 때문에 그는 질문에 대답했기 때문에 devinb를 선택했지만, Tobias Warre 주석이 백업 한 Simon의 의견은 나에게 가치가있었습니다.

이 문제를 해결할 수 있도록 도와 주신 모든 분들께 감사드립니다. 스택 오버플로가 인상적인 서비스입니다.