Answer to: How to choose between brute force and efficient solution that has overhead?

Make a prototype, favoring simplicity and correctness over efficiency. It must still be fast enough for the most basic constructed test though. Test it until it works, then scale up the test until it breaks the true performance goals or gets safely beyond peak production workload. If you have to replace it with something more efficient and complex, you now have a known good test-suite to find the inevitable bugs. Either way, you might have to add a guard against DOS attacks if you cannot rely on an existing one.