ভেতরের কথা: প্রতিটা node-এ একটা pair, আর না পেলে কত খরচ

Kenji-র game server দশ লাখ খেলোয়াড়ের score রাখে একটা map<int, int>-এ। দিনে বহুবার সে জানতে চায়, কোনো খেলোয়াড় আগে খেলেছে কি না, আর জিজ্ঞেস করে if (scores[id] > 0) দিয়ে। একদিন দশ লাখ প্রশ্ন এল, আর প্রতিটাই একজন নতুন খেলোয়াড়কে নিয়ে। Compiler Explorer-এ একবারের run-এ সেগুলোতে লেগেছে 2,032 ms, অথচ find দিয়ে লাগে 1,224 ms। Map-টা 1,000,000 খেলোয়াড় থেকে ফুলে হয়েছে 2,000,000, আর এরপর সব খেলোয়াড়ের উপর দিয়ে একবার হাঁটতে লেগেছে 154 ms-এর জায়গায় 331 ms। Kenji জানতে চায়, সময় আর byte-গুলো গেল কোথায়।