patchGNU Octave - Patches: patch #8959, pkg-statistics: Replace kmeans...


patch #8959: pkg-statistics: Replace kmeans with more efficient implementation

Submitted by:  None
Submitted on:  Tue 29 Mar 2016 02:03:18 AM UTC  
Category:  Forge : other Priority:  5 - Normal
Status:  None Privacy:  Public
Assigned to:  None Originator Email:  -email is unavailable-
Open/Closed:  Open

Add a New Comment(Rich Markup)

You are not logged in

Please log in, so followups can be emailed to you.


Wed 20 Apr 2016 03:17:22 AM UTC, comment #4:

That's certainly an improvement worth pursuing.

If I get the time, I'll try to see why yours is so much faster, and then have a think about how to merge them.

Lachlan Andrew <lachlan>
Tue 19 Apr 2016 05:23:51 PM UTC, comment #3:

Also of note, I have some timing data if people want to see how much this is improved.

| k | Mine in Octave | Octave's | Mine in Matlab | Matlab's |
| 3 | 0.197 sec | 12.268 sec | 0.313 sec | 0.245 sec |
| 4 | 0.578 sec | 17.961 sec | 0.629 sec | 0.475 sec |
| 5 | 0.458 sec | 25.572 sec | 0.614 sec | 0.402 sec |
| 6 | 1.026 sec | 50.141 sec | 1.160 sec | 0.739 sec |
| 7 | 1.237 sec | 41.985 sec | 1.418 sec | 0.534 sec |
| 8 | 1.077 sec | 21.745 sec | 1.289 sec | 0.929 sec |

This timing experiment was done on a grid of 128x128 elements, each one having 16 channels. I call it with

[m,n,p] = size(params);
[elements, clusters] = kmeans(reshape(params, [m*n, p]), k);
elements = reshape(elements, [m,n]);

Michael Bentley <mikebentley15>
Tue 19 Apr 2016 05:14:56 PM UTC, comment #2:

I did not make an attempt to improve the current one, but rather rewrote it entirely. I basically had written this replacement for some homework for one of my classes, and thought that since Octave's implementation is so inefficient, I could contribute it back.

So since it is a rewrite, I think you would be better off implementing your patches to my version. If you are able to do that, it would be great. If it's up to me, then it will be some time before I have any free cycles.

Alternatively, if you want to take the approach I took in my implementation and do a more minimal patch to the current implementation, that could work too. But I think this approach will take more time.

Michael Bentley <mikebentley15>
Tue 19 Apr 2016 11:26:48 AM UTC, comment #1:

Michael, as Jordi mentioned, I submitted a patch (actually, a long series -- but the last one is usable) a while back in bug #43959. It would be good if we could merge your changes with mine.

Do you think it would be easier to apply your changes to my patch or vice versa?

Lachlan Andrew <lachlan>
Tue 29 Mar 2016 02:03:18 AM UTC, original submission:

The current implementation of kmeans() is incredibly inefficient. I reimplemented it and it runs much faster and gives the same results (as much as can be expected with randomization involved).



(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:

Attached Files
file #36789:  kmeans.diff added by None (8KiB - text/x-patch)
file #36788:  kmeans.diff added by None (8KiB - text/x-patch - Replace kmeans)


Depends on the following items: None found

   bug dependencies.


Carbon-Copy List
  • -email is unavailable- added by mikebentley15 (Posted a comment)
  • -email is unavailable- added by lachlan (Posted a comment)
  • -email is unavailable- added by None (Submitted the item)

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.




    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-07-07 lachlan CategoryNone => Forge : other
    2016-03-29 None Attached File- => Added kmeans.diff, #36789
    2016-03-29 None Attached File- => Added kmeans.diff, #36788

    Back to the top

    Powered by Savane 3.3