Petr Jelinek <petr@2ndquadrant.com> writes:
> On 31/08/14 22:33, Tom Lane wrote:
>> Petr Jelinek <petr@2ndquadrant.com> writes:
>>> The difference between my generic and Tom's generic is because Tom's is
>>> slowed down by the deconstruct_array.
>> Meh. It looked to me like your version would have O(N^2) performance
>> problems from computing array offsets repeatedly, depending on exactly
>> which array element it ended up on. It would avoid repeat calculations
>> only if it always moved right.
> I actually think that worst case (when you go always left) for my
> version is O(N) since you only need to seek for the half of previous
> interval (it's doing binary search after all) and you do O(N) in the
> deconstruct_array.
[ thinks about that for awhile... ] Hm, I think you are right.
If there are N elements in the array then we will scan over N/2 of them
to locate the midpoint element for the first comparison. After that,
we will go either left or right, and in either case we will need to scan
over N/4 elements to find the second-level midpoint. The third-level
midpoint will be found after scanning N/8 elements, and so on. So the
number of elements scanned over to compute their lengths is N/2 + N/4 +
N/8 ..., or asymptotically N, the same as for the deconstruct_array
approach. deconstruct_array might have some small advantage from tighter
inner loops, but this is probably more than blown by the need for a
palloc and pfree.
So I was wrong and your way is better for navigating the array in the
variable-width case, assuming that we're not concerned about spending
some more code space to make this function a shade faster.
BTW, was there a reason for not noticing the case of exact match in
the search loop, and falling out early? As it stands the code will
reliably choose the leftmost match if there are multiple equal items
in the search array, but do we care about such cases?
regards, tom lane
