6 ms·
Algorithms and data structures implemented in many programming languages
- smitty1110 4y agoAlso worth checking out: https://rosettacode.org https://rosettacode.org
- ffhhj 4y agoAlso The Quick Snippet Reference: https://github.com/snippetfinder/The-Quick-Snippet-Reference https://github.com/snippetfinder/The-Quick-Snippet-Reference
- kragen 4y agoLooks like it's licensed under the X11 license: https://github.com/TheAlgorithms/Python/blob/master/LICENSE.md https://github.com/TheAlgorithms/Python/blob/master/LICENSE.... The URLs are pretty shitty: https://the-algorithms.com/algorithm/show-response https://the-algorithms.com/algorithm/show-response What I wanted to link to there was https://github.com/TheAlgorithms/Python/blob/master/audio_filters/show_response.py https://github.com/TheAlgorithms/Python/blob/master/audio_fi..., where we see that evidently doing an FFT in Python requires... matplotlib? And in https://github.com/TheAlgorithms/Python/blob/master/backtracking/coloring.py https://github.com/TheAlgorithms/Python/blob/master/backtrac... we see a graph-coloring algorithm statically typed to use (lists of) the built-in lists, so you can't store your graphs in a Numpy matrix or a sparse matrix. On the other hand, the doc strings are great, and seem to include doctests for just about everything. So I suspect that this is not going to be a very useful repository for reusable code, but it should be wonderful as a learning resource.
- voski 4y agoThe README has a section about the code > Implementations are for learning purposes only. As they may be less efficient than the implementations in the Python standard library, use them at your discretion.
- kragen 4y agoThanks! I was looking for something like that but didn't find it.
- thrdbndndn 4y agoThat is not X11. It is just the original MIT.
- kragen 4y agoMIT has used a wide variety of licenses on different software, one of which is the X11 license: https://www.gnu.org/licenses/license-list.html#Expat https://www.gnu.org/licenses/license-list.html#Expat So maybe I should have called it "the Expat license".
- d_burfoot 4y agoThis is very cool! One thing I would be interested in: is there some guarantee that the algorithms are properly implemented? Have you thought about doing some kind of CI/CD to test that each new version responds with the same results as all the others?
- tomrod 4y agoNIST actually provides a lot of things like this -- what _should_ your method provide as an output -- it's pretty cool to dig through! Example: https://www.nist.gov/itl/sed/products-services/statistical-reference-data-sets-strd https://www.nist.gov/itl/sed/products-services/statistical-r...
- lamontcg 4y agoIt looks like the AVL tree implementations do the lazy coding way of updating balance factors and recursively descend to recompute the heights of the left and right nodes constantly. The balance factor can be updated directly from the kind of rebalancing rotation being used. I would not call that properly implemented since it is wasting a lot of cycles on that.
- samsquire 4y agoDon't you need to know the balance factor before you know which rotation to do?
- lamontcg 4y agoOnce they're done with the rotation they're recomputing the balance factor by calling something like height(left) and height(right) which recursively descend to count the height on both sides. You don't need to do that. Given the old balance factor and the rotation you can compute the new balance factor. (Some really bad implementations don't even store the old balance factor in the node and call a recursive height function to figure it out beforehand as well, I just skimmed the implementations I looked at so I didn't check to see if they were doing that as well)
- gibsonf1 4y agoHmm, many languages but no common lisp.
- tmtvl 4y agoYeah, I was also kind of hoping to see Scheme or CL. If I get some free time I may see if I can contribute some code.
- klipt 4y agoCommon Lisp has a really tiny community despite showing up a lot on hacker news (the shadow of Paul Graham talking it up years ago?) It's not even in the top 50 GitHub languages. And today I learned its main web server library Hunchentoot has a huge unpatched security bug? https://news.ycombinator.com/item?id=32950465 https://news.ycombinator.com/item?id=32950465
- gibsonf1 4y agoWe use common lisp in production at https://graphmetrix.com https://graphmetrix.com and use one of the fastest webservers available (one of many libraries) woo https://github.com/fukamachi/woo https://github.com/fukamachi/woo
- daguava 4y agoI hate this argument - who ((uses) -L this) in practice?) aka, nobody working a job does this.
- klyrs 4y ago> nobody working a job does this. https://common-lisp.net/lisp-companies https://common-lisp.net/lisp-companies
- kazinator 4y agoI think if you want to see an algorithm there in some language, you have to find out how to contribute that yourself. People starting projects like this don't know every language and don't have time.
- politician 4y agoSo, will this finally provoke reform in the typical corporate software developer interview process? It’s been decades since using a library became the right answer to deploying a well-known data structure or algorithm.
- kccqzy 4y agoThe implementation of Fibonacci numbers in Haskell doesn't use memoization at all. It's the dumbest possible implementation. Here's an optimized one: fibs = 0 : scanl (+) 1 fibs It also showcases Haskell's lazy list and recursive definition of data (not your usual recursive function).
- gmiller123456 4y agoI don't think any claims were made to the an optimal approach nor utilize optimal language features.
- xdavidliu 4y agothere's a reasonable expectation that a repo named "cool algorithms" won't use extremely dumb exponential-time versions when linear-time ones exist. Also in this case there's a logarithmic-time one that does repeated squaring of a 2x2 matrix.
- im3w1l 4y agoArithmetic on bignums is not O(1), but rather depends on the size of the numbers. This is important when considering say the repeated matrix squaring vs an evaluation of the closed form. They both beat naive exponential time algos, of course.
- ianai 4y ago
- green_on_black 4y ago? The implementation is the dumb thing though?
- deleted 4y ago[deleted]
- 4y ago
- VirusNewbie 4y agoBummer that it’s missing so many languages for many common algorithms. My friend and I were just talking today about how you would do a (variable sized) sliding window in Scala in a functional way.
- wodenokoto 4y agoThe other day I was surprised to find that Python doesn’t come with linked lists and apparently there isn’t anything like an agreed upon `pip install linked-list` solution.
- mazokum 4y agoI believe that collections.deque is implemented as a double linked list. I have used that data structure as a linked list a couple of times. https://docs.python.org/3/library/collections.html#collections.deque https://docs.python.org/3/library/collections.html#collectio...
- maxbond 4y agoCurious why both of you need linked lists in Python? Are you doing a lot of list insertion operations or something & allocations are bringing it to a crawl? I'm quite tickled by the idea that you need a linked list because your allocator is spending too much time - traversing a linked list.
- wodenokoto 4y agoI thought one of the advent of code challenges needed a linked list, but other than that, I have never needed one. I was just surprised as I thought it was a basic structure, so it just seemed like there ought to be a `from collections import linkedlist` because python just feel like the kind of language where you just do that without even consulting the docs.
- maxbond 4y agoYeah for sure. I think your intuition is almost right. Python does have a "batteries included" philosophy, but it's also not usually clear or documented what data structures something is using. Like I presume that Python's sets are syntactic sugar over dictionaries where the values are None, but when I skimmed the docs just now I didn't find any mention of the implementation details. Python doesn't want you thinking in terms of data structures, just in terms of functionality. Which I think is unfortunate and limiting.
- xzghfat 4y agoreport
- pasc1878 4y agoI looked at a graph algorithm Bellman-Ford under C++ Why is Graph->edge a pointer not a std::vector Why does the Graph constructor not use member initializer lists but assignemnt in the constructor body. So confidence in the quality of the code is not high. Then I see ``` this->edges = (Edge )malloc(E sizeof(Edge)); ``` This is not C++. Just stop reading it is not worth it. Find another source
- xdavidliu 4y agoyeah I agree. I think it's because they pretty much allow contributions of algorithms from various people and the code review standards are not super high. I recall at one point the BFS algorithm in Java actually used an ArrayList (roughly equivalent to std::vector) for the queue, which is silly because popping from the front is O(N), so I had to submit a fix for that: https://github.com/TheAlgorithms/Java/pull/3231 https://github.com/TheAlgorithms/Java/pull/3231 but I agree that basic low-hanging issues like this (and the exponential-time fibonacci that another commenter pointed out) really prevents me from taking this repo very seriously
- pjmlp 4y agoUnfortunately that is pretty much C++ as it still gets taught in many places.
- Timwi 4y agoThis needs more moderation. I searched for “Dijkstra” and got many separate results with only one implementation each, despite presumably being the same algorithm.