1

I believe that out there we have algorithms implementations (e.g. a c++ implementation of a particular sorting algorithm) which might not be as efficient as they could be.

I would like to write a research paper discussing how such an implementation might be improved. This could be in any programming language, however C, C++, Python, Java or anything non-proprietary language would be ideal.

Do you know of any algorithm implementation that you feel might have room for improvement?

Jacob
  • 34,255
  • 14
  • 110
  • 165
Gia
  • 525
  • 1
  • 4
  • 13
  • 1
    Just to confirm you wish you improve the algorithm's _implementation_ without effectively changing the algorithm itself (or its main "spirit" anyway), right ? – mjv Nov 19 '09 at 00:32
  • 4
    Generally, the library implementations of basic algorithms (like sorting algorithms) are already very highly optimized since they are so frequently used. – James McNellis Nov 19 '09 at 00:34
  • Hi, yes, I wish to improve an implementation rather than improving the algorithm. I feel it would be too difficult to improve the algorithm, but there might be room for improvement in some implementation. This might be true specially for new frameworks, not very popular algorithms or new algorithms. Thank you. – Gia Nov 19 '09 at 00:57
  • James, yes I agree with you. However, I believe this might not be true for not very popular algorithms, new algorithms and new libraries. – Gia Nov 19 '09 at 01:03
  • 1
    So you want to do some software engineering, not computer science, something that might be useful but not of theoretical interest... Excuse me, but why would this be worth a research paper? – Beta Nov 19 '09 at 01:07
  • Beta: I could certainly see a rigorous approach to implementation optimization as a worthwhile CS research subject, especially if it is machine-implementable. – Vatine Nov 20 '09 at 09:25
  • Oh, now I understand. You want to develop an algorithm for optimizing code, and you're looking for inefficient code to practice with. Well, if you don't want to write it yourself, I'm sure you'll find plenty of volunteers here. Is that what you want? – Beta Nov 20 '09 at 21:14

3 Answers3

1

In my experience:

And specifically in MATLAB, you can speed things up by writing C/C++ functions which can be accessed through MEX-functions.

I realize that some of them are proprietary!

Jacob
  • 34,255
  • 14
  • 110
  • 165
1

Jon Bentley has (somewhere) an example of how a traveling-salesman algorithm was increased in performance by a factor of 50 while still keeping the same big-O signature.

In one lecture he said of the academics who were poo-poohing that result that they probably wouldn't mind their salary being improved by a similar factor!

I personally have optimized some programs by factors of 100s without changing their big-O.

Here is an example of optimizing by a factor of about 40, without changing big-O.

You can do this to any program if it hasn't already been done. The bigger it is, the better.

Does that help?

Community
  • 1
  • 1
Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135
0

There are plenty of papers that already exist that describe when and where certain sorting algorithms are better/improved. For example: up to a certain point linear search bests quicksort. (Blasphemy I know, but that depends on the order (if know prior to), and small datasets.)

My advice, do the research finding these papers, before you try to invent something new. The probability of your work would either be that you are incorrect or it has already been published. There is a small chance that your work would be new.

monksy
  • 14,156
  • 17
  • 75
  • 124
  • Hi Steven, thank you for taking the time. However, I am not trying to improve the algorithm. I am just attempting to find an implementation that might be flawed from an efficiency perspective. – Gia Nov 19 '09 at 00:59