Re: [changeset] histc

[Jaroslav Hajek]

On Sun, Mar 8, 2009 at 7:28 PM, Søren Hauberg <address@hidden> wrote:
> søn, 08 03 2009 kl. 19:14 +0100, skrev Jaroslav Hajek:
>> Several comments:
>>
>> 1. your test for sortedness will gripe for descending arrays. I think
>> it can simply go like this
>
> It is supposed to gripe for descending arrays.
>
>> if (! issorted (edges))
>>   warn (...)
>>   edges = sort (edges);
>> endif
>
> This approach might still be better than what I have. It should,
> however, look something like this
>
>  if (! issorted (edges) || edges (1) > edges (2))
>    ...
>
> to ensure we gripe for descending arrays.
>
>>  Do you have a good reason why you wnat this
>> function in 3.2?
>
> Well, I've been given some code that requires the function :-)

Actually, I needed it too, but I wanted to implement my solution.

>> Of course, we may also go with this implementation and I'll contribute
>> a more optimal one after 3.2.
>
> A more optimal solution would be nice, but I don't think a function like
> this is going to be the bottleneck of much code.

Maybe not. But mark you, this is not just hunting constant factors,
the lookup solution is asymptotically better.

With N edges and M datapoints, your solution is O(M*N).  With lookup +
accumarray you get O(M*log(N)) and can even get to O(M) if M >> N and
M is partially sorted (this is common in the applications I need).
Actually, with the current accumarray, you get O(M*(log(M) + log(N))),
which for M large and M >> N is even asymptotically worse than O(M*N),
but accumarray *can* work in linear time. Hence I didn't want to do it
until I also optimize accumarray, because I didn't like the idea .

> I pushed the function before reading your mail. Should the change be
> cancelled due to feature freeze?
>

I don't think so. After all, 3.2 is mainly in John's hands, so if he's
OK with it, it's fine. I wonder, John, would you be fine with me
optimizing accumarray and improving histc as well.

cheers

-- 
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz