A curious case of O(N^2) behavior which should be O(N) (2023)
1–10 of 46 posts
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#2More accidentally quadratic stories: https://www.tumblr.com/accidentallyquadratic
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#3Neat find! This proves to me a huge benefit of open source software: individual developers can satisfy their curiosity towards particular issues (with additional motivation from being personally affected) and improve the package for everyone once it's fixed.
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#4Why not just change the “%s.%u” to “%s.%010u” and no code changes?
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#5Why not just change the “%s.%u” to “%s.%010u” and no code changes?
If I understood the article correctly it caused problems when the same file was imported multiple times, or when another file with the same base name was imported.
https://gist.github.com/bssrdf/397900607028bffd0f8d223a7acdc...
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#6Neat find! This proves to me a huge benefit of open source software: individual developers can satisfy their curiosity towards particular issues (with additional motivation from being personally affected) and improve the package for everyone once it's fixed.
Except it wasn't improved in this case, if I'm reading the gist correctly. The author didn't like their fix enough to make a pull request.
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#7Why not just change the “%s.%u” to “%s.%010u” and no code changes?
If I understood the article correctly it caused problems when the same file was imported multiple times, or when another file with the same base name was imported. https://gist.github.com/bssrdf/397900607028bffd0f8d223a7acdc...
Yes, TFA says the issue is because "12345" sorts before "9888"
My solution avoids that.
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#8Why was the solution not to get rid of the linked list and replace it with a red/black tree?
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#9Why was the solution not to get rid of the linked list and replace it with a red/black tree?
Or hash table, or any other kind of tree.
My guess would be because it was implemented in c, where the usual practice if you need a container type other than a fixed size array is to implement it yourself. IME, c code tends to use linked lists for a lot of things that in most other languages would be implemented using a better suited, and more performent, container type from the standard library.
One way that other languages can outperform c, is it is easier to use the right data structure.
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#10More accidentally quadratic stories: https://www.tumblr.com/accidentallyquadratic
A classic. Every time I see that link I read the whole thing starting from the new beginning.
...oops