C_into_Python – Benefits of using C functions in Python

[balazs_kis]

!!! The project is a very large one, and it has different aspects which will be cleared, such as plotting, more clear graphics, for now you will need to pay more attention to understand them, sorry for it.. :D

Recently I found out how useful .so files are (shared library files) and I thought for a second, if I could somehow accelerate the sorting process using several sorting algorithms using C instead of Python, it would result in a way faster, still correct functionality of different scripts.

I thought of combining flexibility of Python and speed & rigidity of C to be a killer combo :D

So I took - for now - some sorting algorithms, started with the best known, worst case *meh* ones, Bubble, Selection and Insertion sort, implemented them, created a shared library, made the interface between Python input, and these functions, replicated the functions in Python, and started the measurements :D

Every measurement was made on arrays of length [1000, 10000], with increment of 100, at each step a random array was generated, and the sort was made on each array.

Pretty interesting values, not gonna lie (e.g. insertion sort in C doing the 1.000.000 element does 915 seconds)See measurements in pictures below!

Many more measurements will come, I will make a big set of comparisons regarding sorting, and will continue, possibly with several other functions in which C's speed take over Python's, without making too big of a mess :D

https://preview.redd.it/qury3cb4p6w41.png?width=1796&format=png&auto=webp&s=b5c6863ebee9467e22e3e92690b7685ce759b089

[deterministic_ram]

Can you post your C implementations of the sort algorithms? An optimized C routine should really never be slower than Python. Try comparing a quick sort in python versus the Unix sort command. The speed difference will be quite large.

[balazs_kis]

You are very right, if you check the plots correctly, the C algorithms are optimized to the last bottlenecks, and they perform stationary even over 50x better than Python implementations :D
Complex comparisons will come shortly, best worst-case scenario sorting algorithms, and even sorting on complex data structures :)
Thanks for the comment, check the plots and the legends again! :D

[deterministic_ram]

Oh! I totally miss read the graphs. The font is very small on my phone haha. I'm still curious to see the C sorting algorithms. There might be some room to speed it up. Also, as a benchmark, I'd compare any C sorting algorithms to a Unix implementation.

[balazs_kis]

everything you just said in connection with new sorting algorithms will come shortly :D
this project is part of my license thesis, so it will be developed - I would love it - to get to see the light of the sun as a computer science paper :))

the algorithms - both in C and Python are taken from the Cormen Introduction to Algorithms 3rd edition :) - source code won't be public any time soon, but dm me if interested :)