Union-Find không tự nhiên O(1): bản naive để cây thoái hóa thành chuỗi, đường find trung bình 9999 (=n/2), find hết mất 88 ms. Hai tối ưu vài dòng ép đường find về ~1, nhanh 3000 lần — và đẹp nhất, ở 10 triệu phần tử đường find trung bình vẫn phẳng lì ở 1,01. 'Gần O(1)' là sự thật đo được. Tôi đo.
Tra chuỗi chính xác, bảng băm nhanh hơn trie 3,4 lần và tốn ít bộ nhớ hơn 40 lần — trie nhảy con trỏ từng ký tự, mỗi bước một cache-miss. Nhưng đếm mọi khóa có tiền tố cho trước, trie nhanh hơn 32 lần vì băm phải quét cả bảng. Lợi thật của trie là tiền tố, không phải tốc độ tra. Tôi đo.
Đổi tiền bằng cách chộp đồng xu lớn nhất luôn đúng với hệ {1,5,10,25}. Nhưng đo hệ khác thì nó sai 25-40% số tiền — hệ {1,7,10}, số 14: tham lam 5 xu, tối ưu 2 xu. Tham lam nhanh hơn quy hoạch động 100 triệu lần cho một truy vấn (2,1 ns so 228 ms), nhưng nhanh mà sai thì vô dụng. Tôi đo.
Heapsort nghe như hoàn hảo: O(n log n) bảo đảm và tại chỗ — hơn quicksort có ca xấu, hơn merge tốn bộ nhớ. Nhưng đo ra nó chậm nhất trong ba (1,43× tới 2,37× quicksort), và tỉ số tăng theo n vì sift-down nhảy khắp mảng phá cache. Vai trò thật của nó là lưới an toàn, không phải tốc độ. Tôi đo.
Cây tìm kiếm nhị phân được dạy là O(log n). Nhưng đổ khóa đã sắp (id tăng, timestamp — rất thường gặp) vào thì nó thoái hóa thành xâu: chiều cao 40000 thay vì 34, tra 32672 ns thay vì 51 ns, chậm 640 lần đúng bằng quét tuyến tính. Và một mảng nhị phân đẹp cache cũng không nhanh hơn cây cân bằng. Tôi đo.
Tưởng shared memory tự nó là IPC nhanh nhất vì zero-copy? Tôi đo: shm một-buffer lockstep chỉ 14 GB/s, THUA cả Unix socket 21 GB/s (phải copy nhưng chồng lấn được); chỉ khi dùng ring buffer lock-free (24 GB/s) shm mới thắng. Zero-copy là cần, chưa đủ.