18 Nov
2008
18 Nov
'08
10:51 p.m.
On Tue, Nov 18, 2008 at 12:46 PM, Luke Palmer
But when these persistent data structures are used in a single-threaded way, why should we not hope for the performance to be comparable?
If you can guarantee single-threaded use, then you can just use ST and implement the ephemeral structure, right?
It may not be easy, but just saying "they are persistent" is not really an excuse.
You can generally make a persistent data structure with the same asymptotic bounds as the ephemeral structure, but the constant hidden inside the O() will generally be worse.