Module ৮ · set আর multiset: sorted, unique, আর log n-এ খুঁজে পাওয়া

ভেতরের কথা: tree-র node, তার উচ্চতা, আর যে iterator টিকে থাকে

Proপড়াlesson ৫ / ৯

Kenji দশ লাখ sensor reading একটা set-এ রাখে, যে ক্রমে এসেছে সেই ক্রমেই insert করে। তারপর একটা loop দিয়ে সবগুলো যোগ করে। একই মানের একটা vector-এর উপর ওই loop নিয়েছে 0.23 ms। আর set-এর উপর, একবারের run-এ, 164 ms। দুইটা হাঁটাই তো O(n)। Maria ঠিক সেই প্রশ্নটা করে, যার উত্তর এই lesson: "কিন্তু কেন? একটা O(n) হাঁটা আরেকটার চেয়ে কয়েকশো গুণ ধীর হয় কী করে?"

আপনার জন্য এই lesson টা খোলা কি না দেখা হচ্ছে…

ভেতরের কথা: tree-র node, তার উচ্চতা, আর যে iterator টিকে থাকে এর ভেতরে কী আছে

একটা node: একটা রং, তিনটা link আর মানটা
Set object: একটা header node আর node-এর সংখ্যা
Red-black নিয়মগুলো, আর তাতে tree কতটা খাটো থাকে
++it কীভাবে পরের মানটা খুঁজে পায়
যে iterator টিকে থাকে: erase link বদলায়, কিছু copy করে না
Performance lab: Kenji-র সময় কোথায় গেল