관리자 (IP : 126.96.36.199)
[C#][스크랩] List Removal Performance - 대량 목록에서 요소 삭제 최적화
Recently I implemented a blue noise sampler based on the paper Fast Poisson Disk Sampling in Arbitrary Dimensions. Part of the algorithm involves selecting random indices from a list and then removing them. This can be a fairly expensive operation in the standard
This poisson implementation isn’t the only algorithm I have implemented that requires a large amount of random element removal, and past benchmarks have shown it can eat up a significant amount of time.
A Faster Removal
So how can we speed it up? Well there is a simple solution if the order of the list does not matter. Simply swap the value at the “removed” index with the value at the back, and then remove from the back.
A quick performance comparison later, and we can see the difference. The table shows how long it took to remove all elements from a list of a given size, in random order. All time is in milliseconds.
At a million elements, the unordered removal is a 99.987% reduction in runtime.
Assuredly this is not a novel solution, but I personally had not seen it before. However after coming up with
위 처럼 마지막 항목을 삭제 항목 위치로 옮기고 마지막 항목을 삭제 함으로써 처리 시간을 크게 개선할 수 있습니다.