Design an algorithm to randomly select people in a city such that the probability of selecting someone from a given district is proportional to the district's population size. Additionally, discuss how you would test your implementation and optimize its runtime, considering repeated calls to the selection function with an acceptable error margin.