Re: Can Octave (Matlab code) be added to C++ as a library?

[michaell]

As to how Octave does it: for m-code functions, it is easily found out: you
say "help ismember", and in the top line you see the file that implements
the function. And then, if you can read m-code, you just read that function.
Beware: Octave is published under the GPL, so if you ever would want to (i)
publish your code and (ii) under a different licence than the GPL, you
should rather not do that. But I can definitely tell you the idea: It is
just my suggestion where you sort one of the arrays (always the second one)
and do a lookup by bisection.

It should not take 20 minutes to sort a million entries (and a sortrows
should not be much more effort than just a sort). This sounds like a
O(N^2)-algorithm, and what you linked to indeed is. The best general purpose
sorting algorithms are O(N*log(N)), and they do not need to be very
complicated. The algorithm Octave uses is quite sophisticated, but this
sophistication is to a large part just to run very good in a number of
scenarios (presorted data, unsorted data, reversely sorted data, partially
sorted data and so on). If you know for example that your values are
uniformly distributed over an interval and practically perfectly random, you
could use a very simple quicksort where you use bisection of the interval in
all but the last stages instead of the typical choice of the first entry as
pivot (this would practically be the optimum pivot, thus giving you less
stages). And you get a sortrows out of that by comparing the rows in the
lexicographic sense. I am quite certain that you should be able to write
something like that in twenty lines of code, that will be faster than Octave
can ever be (again, because you know your situation). 

And yes, generally it can be stated that if you use an O(N*log(N)) algorithm
for sorting, it will be "infinitely fast" in the sense that it will always
take much more time to get the entries into RAM than to sort them.





--
Sent from: https://octave.1599824.n4.nabble.com/Octave-General-f1599825.html