Performance promises of marker interfaces
Meikel Brandmeyer
is there some page explaining the performance characteristics one has
to fulfil for the different marker interfaces?
My guesses are:
- Indexed: O(n), since nth might be O(n)
- ILookup: O(1) (or O(log32 n)) since get is O(1)
- Reversible: O(1) since rseq is O(1)
For example I have a data structure which is faster to reverse than
O(n) but not O(1). So at the moment I cannot provide this faster
operation transparently via reverse and I believe I would violate the
contract of Reversible. So also no transparent hook-in for rseq.
Similar for ILookup: it is on average O(1) (or O(log32 N)), but could
be O(n) in the worst case. So it would be - as I believe - a violation
to implement ILookup.
Any pointers for further guidance?
Thank you in advance.
Sincerely
Meikel
Michał Marczyk
> is there some page explaining the performance characteristics one has
> to fulfil for the different marker interfaces?
Great question, I'd really like to see something like that!
> - Indexed: O(n), since nth might be O(n)
Actually I'd expect Indexed.nth to be more performant than O(n) (at
least O(log n)). For O(n), Sequential seems to be the correct
interface. The current behaviour of clojure.core/nth seems to support
this view (it only performs linear searches for things which are
Sequential but not Indexed).
Sincerely,
Michał
Meikel Brandmeyer
Am 07.09.2010 um 21:50 schrieb Michał Marczyk:
>> - Indexed: O(n), since nth might be O(n)
>
> Actually I'd expect Indexed.nth to be more performant than O(n) (at
> least O(log n)). For O(n), Sequential seems to be the correct
> interface. The current behaviour of clojure.core/nth seems to support
> this view (it only performs linear searches for things which are
> Sequential but not Indexed).
Well, the performance guarantee of of nth is O(n) because of the way it treats Sequential. So there's no reason why Indexed should be faster. I see it basically as a hook for data structures, which can provide some improved lookup. And in fact I know a datastructure, where the "usual" access time is O(1) (or O(log_s n) for a reasonable s, similar to vectors), but in the worst case it might be O(n). Just like quicksort is O(n^2) in the worst case, but is usually faster. I don't see a reason, why this data structure should not implement Indexed. It would not break the contract of nth.
But my background on these questions is quite limited. So by asking I'm on the save side. :)
Sincerely
Meikel