Algorithms and data structures implemented in many programming languages | Hacker News Reader

Algorithms and data structures implemented in many programming languages

the-algorithms.com

229 pointsfeross45 comments

The 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).

I don't think any claims were made to the an optimal approach nor utilize optimal language features.

there'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.

Arithmetic 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.

They have FastFibonacci as a separate category (with only a Python implementation, currently).

Right; the page https://the-algorithms.com/algorithm/fibonacci-numbers details a smart algorithm using matrix powers and then lists implementations for many languages. But the Haskell implementation is the dumb exponential one rather than the smart one shown.

Btw, another less cryptic way to generate the list of Fibonacci numbers is

    fibs = f 0 1 where f a b = a : f b (a+b)

Isn't this an open source library? Why are you gripping here instead of making a PR?

Also worth checking out: https://rosettacode.org

Also The Quick Snippet Reference:

https://github.com/snippetfinder/The-Quick-Snippet-Reference

I 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

yeah 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

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

Unfortunately that is pretty much C++ as it still gets taught in many places.

Not an excuse.

It isn't an excuse, rather a sad fact, and many people don't know any better.

That is exactly why Val, Carbon and Cppfront aren't copy-paste compatible with C.

Herb Sutter even mentions this at the end of his keynote.

Looks like it's licensed under the X11 license: https://github.com/TheAlgorithms/Python/blob/master/LICENSE....

The URLs are pretty shitty: https://the-algorithms.com/algorithm/show-response

What I wanted to link to there was 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/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.

The 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.

Thanks! I was looking for something like that but didn't find it.

That is not X11. It is just the original MIT.

MIT 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

So maybe I should have called it "the Expat license".

This 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?

NIST 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-r...

It 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.

Don't you need to know the balance factor before you know which rotation to do?

Once 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)

This is something that the compiler could optimize.

If you have all the temporary ingredients of the data, you could work out when height(left) height(right) needs to be evaluated.

Bummer 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.

This needs more moderation. I searched for “Dijkstra” and got many separate results with only one implementation each, despite presumably being the same algorithm.

Hmm, many languages but no common lisp.

Yeah, 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.

Common 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

We use common lisp in production at https://graphmetrix.com and use one of the fastest webservers available (one of many libraries) woo https://github.com/fukamachi/woo

I hate this argument - who ((uses) -L this) in practice?) aka, nobody working a job does this.

> nobody working a job does this.

https://common-lisp.net/lisp-companies

I 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.

Well, there's always Rosetta Code (see: https://rosettacode.org/w/index.php?title=Category:Common_Li...) which is essentially the same thing.

So, 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.

The 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.

I 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#collectio...

Curious 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.

I 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.

Yeah 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.

Correct (actually a linked list of blocks[1]). It supports insertion and removal from both ends in O(1), which is very useful. However, it does not support insertion and removal from the middle (via an iterator) in O(1), so it's not a complete replacement for doubly-linked lists.

[1]: https://github.com/python/cpython/blob/a4ac14faa5c2be433738d...

Linked lists are popular because they are useful in teaching basic data structures and complexity analysis. They can be compared to array lists.

But in real life the extra cost of allocating a node is way higher than simply copying over a block of memory, for most realistic sized workloads, which are small.

report

Reply on news.ycombinator.com