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'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.
A curious case of O(N^2) behavior which should be O(N) (2023)
21–30 of 46 posts
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#22Ah 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'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.
There's also the choice of data structure that appears to force multiple copies of the same thing rather than thin references and ideally copy on modify.
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#23While 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
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#24Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#25Ah 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'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.
What is a hive in the context of data structures?
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#26Earlier quoted context omitted.
A classic. Every time I see that link I read the whole thing starting from the new beginning. ...oops
I opened the link and just started reading. I have a really dumb question that may expose common knowledge I don’t have, about this quote: > The total amount of space needed to represent this collection of strings is O(k n^2). I haven’t seen O-notation ever represent ram usage, just algorithm complexity. Is this common?
> Is this common?
Very. For instance if you look at sorting algorithms on wikipedia they pretty much all list performance (best, worst, average) but also worst-case space complexity, in O notation.
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#27Why was the solution not to get rid of the linked list and replace it with a red/black tree?
I got the impression that the expected performance of the double linked list insertion is actually O(1), since in most cases the elements arrive in sorted order. It's been a time since my algorithm courses, but I think all the 'normal' trees have log(n) insertion in that case.
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#28Why 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 l…
Blender's not even in C (the snippets are clearly C++), I wonder what the logic of having a sorted doubly linked list is: unless it's a skip list it's not like you can do bisection searches.
I guess a flat array could still be debatable if you're usually inserting near but not at the end, as it'll still need to move all the following elements. But it seems dubious.
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#292 questions I would look into before anything else:
1. Does this have to be sorted?
2. Why is it sorted alphabetically instead of naturally?
Re: A curious case of O(N^2) behavior which should be O(N) (2023)
#30Ah 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'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.
What is a hive in the context of data structures?
I assume it's an autocorrect of heap.