A curious case of O(N^2) behavior which should be O(N) (2023)

More accidentally quadratic stories: <a href="https:&#x2F;&#x2F;www.tumblr.com&#x2F;accidentallyquadratic" rel="nofollow">https:&#x2F;&#x2F;www.tumblr.com&#x2F;accidentallyquadratic</a>

While taking a computational complexity course I wrote some python code that should have run in O(n) but was closer to O(n^2). After asking StackOverflow and some more experimentation it turns out the garbage collector turned it O(n^2) - turning it off manually yielded the correct O(n) runtime

Why was the solution not to get rid of the linked list and replace it with a red&#x2F;black tree?

Neat 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&#x27;s fixed.

Ah yes, the most reliable solution to a wrong choice of a data structure: add data-specific hacks until it works. For the life of me I can&#x27;t figure out why people never consider replacing linked lists. Even without worst-case O(n) insertion, they usually behave worse than vectors, deques, or hives.

I had something like this. I was making a script that would parse a standardized file describing a molecule and create the atoms and bonds and whatnots. I found out that they time an object is added it iterates through all the objects to update them of the addition. This was very noticable even around 1k objects. I later grouped all the duplicated objects (such as all the oxygens) into 1 discontinuous object, leading to O(1 [the bonds] + #elements) instead of O(#bonds * #atoms).<p>In the end I still lost out to another package that did the same function a lot faster. May be interesting to look back to see how they did it.

Why not just change the “%s.%u” to “%s.%010u” and no code changes?

&quot;Now, it should be clear that most of the time (28s-53s on the time line) of importing that particular USD file is spent in id_sort_by_name&quot;.<p>Luckily there&#x27;s a graph screenshot. But the graph it displays is incomprehensible. Without &quot;id_sort_by_name&quot; being on the one bar, I wouldn&#x27;t even know what I&#x27;m looking at.

2 questions I would look into before anything else:<p>1. Does this have to be sorted?<p>2. Why is it sorted alphabetically instead of naturally?

“alphebatically” is used 3 times, and otherwise no typos that I noticed. So I wondered if it’s a term I’m not familiar with.