_______ __ _______
| | |.---.-..----.| |--..-----..----. | | |.-----..--.--.--..-----.
| || _ || __|| < | -__|| _| | || -__|| | | ||__ --|
|___|___||___._||____||__|__||_____||__| |__|____||_____||________||_____|
on Gopher (inofficial)
URI Visit Hacker News on the Web
COMMENT PAGE FOR:
URI A curious case of O(N^2) behavior which should be O(N) (2023)
eska wrote 1 hour 53 min ago:
2 questions I would look into before anything else:
1. Does this have to be sorted?
2. Why is it sorted alphabetically instead of naturally?
rokkamokka wrote 2 hours 17 min ago:
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
purplesyringa wrote 3 hours 28 min ago:
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.
xigoi wrote 2 hours 2 min ago:
What is a hive in the context of data structures?
purplesyringa wrote 10 min ago:
I meant something close to [1] Perhaps a simple way to look at it
is that it's like a dynamic array, but when the capacity is
exceeded, you don't reallocate the array, just just allocate a new
(exponentially larger) chunk and keep the old one as-is. Then just
link the chunks in a (very short) linked list, or keep a separate
small list of chunks (you're never gonna need more than 48, so you
can just have a fixed allocation for it), or what have you. The
bonus here is that it reduces latency on pushing and has more
predictable performance.
URI [1]: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p...
masklinn wrote 1 hour 52 min ago:
I assume it's an autocorrect of heap.
mjevans wrote 2 hours 27 min ago:
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.
ojbyrne wrote 6 hours 5 min ago:
â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.
geuis wrote 6 hours 31 min ago:
"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".
Luckily there's a graph screenshot. But the graph it displays is
incomprehensible. Without "id_sort_by_name" being on the one bar, I
wouldn't even know what I'm looking at.
wtallis wrote 5 hours 32 min ago:
The timeline view in the upper screenshot is fairly straightforward:
the region of 28-53s is selected, other parts of the timeline are
grayed out, and the statistics for the selected time region down
below show 94.4% of "Total CPU" being in id_sort_by_name.
The lower screenshot is a flame graph. If you haven't encountered one
of those before, it's totally reasonable to not know how to read it.
But it's a standard and common way to present this sort of data. See
[1] for more information.
URI [1]: https://www.brendangregg.com/flamegraphs.html
nrdvana wrote 8 hours 34 min ago:
Why was the solution not to get rid of the linked list and replace it
with a red/black tree?
Epa095 wrote 1 hour 57 min ago:
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.
thayne wrote 7 hours 57 min ago:
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.
masklinn wrote 1 hour 54 min ago:
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.
dmitrygr wrote 10 hours 0 min ago:
Why not just change the â%s.%uâ to â%s.%010uâ and no code
changes?
consp wrote 4 hours 31 min ago:
You just created a fix up to a large, but arbitrary, number just
pushing the problem down the road instead of fixing it.
andrelaszlo wrote 9 hours 42 min ago:
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.
URI [1]: https://gist.github.com/bssrdf/397900607028bffd0f8d223a7acdc...
dmitrygr wrote 8 hours 49 min ago:
Yes, TFA says the issue is because "12345" sorts before "9888"
My solution avoids that.
Liftyee wrote 10 hours 32 min ago:
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's fixed.
bla3 wrote 8 hours 58 min ago:
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.
EdSchouten wrote 6 hours 45 min ago:
Just like âthis entire meeting could have been an emailâ, all
this effort writing this gist could have been spent creating a PR.
Sharlin wrote 11 hours 32 min ago:
More accidentally quadratic stories:
URI [1]: https://www.tumblr.com/accidentallyquadratic
samatman wrote 7 hours 19 min ago:
A classic. Every time I see that link I read the whole thing
starting from the new beginning.
...oops
itronitron wrote 6 hours 20 min ago:
Is there a way to do that without signing in?
dgfitz wrote 6 hours 43 min ago:
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?
masklinn wrote 2 hours 1 min ago:
> 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.
nneonneo wrote 6 hours 41 min ago:
Yes, very common. You've seen "time complexity"; it's very common
to talk about "space complexity" as well.
consp wrote 4 hours 37 min ago:
Fun bonus: they can be interchangeable, e.g. increasing space
to reduce time.
dgoldstein0 wrote 3 hours 38 min ago:
Yes, but total time is never going to be less than total
space, when expressed in big-O notation
deltaknight wrote 1 hour 29 min ago:
Iâm not sure this definition of Big-O for space
complexity is universal. When Iâve seen/used it, the size
of the initial data wasnât relevant, it was more about
the additional memory required for the algorithm.
For example, an in-place algorithm like Bubble Sort would
have a O(1) space complexity, because it requires no extra
memory (and 0 memory is a constant). Merge sort on the
other hand is O(n) because it always uses additional memory
for its intermediate stages, and that additional memory
scales with n.
Doing a quick google, the first few sites I find seem to
use a similar understanding
URI [1]: https://www.geeksforgeeks.org/time-and-space-compl...
xigoi wrote 2 hours 4 min ago:
Why couldnât it?
yxhuvud wrote 1 hour 41 min ago:
Because it takes n time to access n units of memory.
Heavily simplified due to caches etc. To the point where
people sometimes measure in cache misses instead as that
is usually what actually matters.
xigoi wrote 1 hour 36 min ago:
What if you allocate a huge chunk of memory and only
use a small part of it? For example, checking if a list
of numbers contains duplicates using a boolean array.
Sharlin wrote 25 min ago:
If your algorithm requires O(n) memory, any O(1)
amount of memory can never be enough, no matter how
huge. That's the entire point of O notation.
And if your implementation of an algorithm allocates
more space in the big-oh sense than it can actually
touch (eg. O(n) space for O(log n) time or whatever),
that's just a wasteful implementation. Doesn't make
the algorithm itself require more space than it has
time to actually use.
DIR <- back to front page