Background 

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 System.Collections.Generic.List<T> data structure as it requires a renumbering (shifting) of all elements behind it.

When you call RemoveAt to remove an item, the remaining items in the list are renumbered to replace the removed item. For example, if you remove the item at index 3, the item at index 4 is moved to the 3 position. In addition, the number of items in the list (as represented by the Count property) is reduced by 1. (source)

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.

public static class ListExtensions
{
    public static void RemoveUnorderedAt<T>(this List<T> list, int index)
    {
        list[index] = list[list.Count - 1];
        list.RemoveAt(list.Count - 1);
    }
}

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.

Benchmark Source 

Notes 

Assuredly this is not a novel solution, but I personally had not seen it before. However after coming up with RemoveUnorderedAt I came across this in the accompanying source of the paper listed at the start of this ramble.

util.h

template<class T>
void erase_unordered(std::vector<T> &a, unsigned int index)
{
   a[index]=a.back();
   a.pop_back();
}

위 처럼 마지막 항목을 삭제 항목 위치로 옮기고 마지막 항목을 삭제 함으로써 처리 시간을 크게 개선할 수 있습니다.
(다만 항목의 순서가 바뀝니다. 항목의 순서가 중요하지 않을 경우 사용할 수 있습니다)