performance problem with unique on sparse arrays

[John W. Eaton]

The unique function performs poorly on sparse arrays:

  octave:1> x = sprand (1e5, 1, 0.3);
  octave:2> tic; unique (x); toc 
  Elapsed time is 10.8679 seconds.
  octave:3> tic; unique (full (x)); toc
  Elapsed time is 0.036339 seconds.

I "fixed" this problem with the following patch so that if unique is not
operating on rows and we don't need the index vectors, it just
converts the nonzero elements to a full vector instead of working on
the sparse array directly:

  http://hg.savannah.gnu.org/hgweb/octave/rev/1f11fabfa349

The real performance problem in unique appears to be the following two
operations:

  match = (y(1:n-1) == y(2:n));
  y(idx) = [];

It would be good to find a way to improve these, then maybe my quick
fix to unique could be removed and performance would also be improved
for the case when index values are requested.

Comments?

jwe