« first day (1725 days earlier)      last day (3227 days later) » 

9:00 PM
you use a kind of tree like std::map uses
 
ITT I don't care to learn but I have an opinion anyway
 
@JerryCoffin Nice
 
you're asking me to learn something completely orthogonal to what I'm having an opinion on
 
lol
@Jefffrey Yeah I guess
Inserting in the middle would suck a lot tho
 
Oh right
 
9:01 PM
Which happens a lot in maps
 
aaaaaaand I'm screaming live
 
Woops
 
Ohai
 
Forgot about that little detail
 
@Jefffrey Actually, it is fairly popular. Modern C++ Design had one, and Boost Flatmap provides roughly the same. Best used for situations where you insert everything, then only after they're all inserted, you do searches.
 
9:01 PM
> Maps are usually implemented as red-black trees.
... I guess this was obvious
since std::_rb_tree
IIRC
 
That's implementation details
 
I wonder why no skip lists
 
@CatPlusPlus yea but jeff was asking about implementation details
 
@AlexM. ...but can be AVL trees, etc.
 
Ordered array wouldn't fit in complexity requirements
 
9:02 PM
and I mentioned that tree-like structures are used instead of sorted arrays
 
@CatPlusPlus stupid is what stupid does
 
even if you can bsearch a sorted array
and technically get O(logn) access
 
@Jefffrey Because there's a vast gulf between "sexy" and "I actually need that"
 
@milleniumbug If memory serves, they provide good average complexity, but don't meet the worst case requirements.
 
@JerryCoffin Can't verify that, but sounds convincing
 
9:04 PM
@Puppy Well, there was that talk about Chandler ranting on std::map and std::unordered_map. In that talk he also talks on how cache locality is important, and arrays should be preffered. That's what I was referring to.
 
maybe in his area of work?
 
@JerryCoffin Yeah, but the cost of adding elements is huge, due to the "insert in the middle, shift everything" problem.
 
@Jefffrey Meh, it's just a slightly different interface with slightly different performance characteristics. It's not especially interesting or critical, and you could get much the same effect by simply providing a proper allocator.
 
Would an insert be O(n + log(n))?
 
what, in the proper allocator case?
 
9:06 PM
@Jefffrey I have, however, in the past pointed to a hybrid structure with amortized O(log n) operations. Use a sorted array, and an un-sorted chunk you limit to ~log N elements. When you add elements, you just add them to the un-sorted chunk. When you need to search, you do a binary (or interpolating) search in the sorted part, and a linear search in the un-sorted part. When the unsorted part gets full, you sort it and merge it into the rest of the sorted part.
 
@Puppy No, in the ordered array case
 
well, it would probably be worse like O(2n)
 
@JerryCoffin Clever!
 
@JerryCoffin So you basically have a small unsorted buffer to avoid resorting everything every time.
Nice
 
@Jefffrey Exactly.
 
9:07 PM
@JerryCoffin That's how something like an octree works.
 
@Puppy Which would be O(n), no?
 
@Jefffrey So would O(n + log(n)).
 
I guess
 
wait a minute
 
@Puppy I think you had a memory error there--an octree is a tree where every node has 8 children. It's basically like a binary tree for 3D data.
 
9:08 PM
Well no actually
 
if you do a log transforming algorithm on a O(n^2) does that mean that it reduces the final thing?
 
you do what
 
Depends on what you transform the log into
Planks? Dust?
 
function_that_takes_logarithmic_time(function_that_takes_n_squared_time(n)) is O(n^2) due to properties of Big O notation
 
@JerryCoffin Well, it doesn't have 8 children. It has up to 8 items and 0 children, and then after you insert a 9th item, then it has 8 children and only the items that don't fit in any of the children.
 
it's the same approach of "Just chuck it in a list until we actually have a need to process this in the algorithmically optimal way".
 
Is n + log(n) part of the O(n) set? The question basically boils down to, is there a constant k for which kn is an upper bound from (possibly from some point of the function on)?
 
front page hacker news: someone had a cool idea but not the time to implement it yet
 
Assuming the function_that_takes_n_squared_time returns the transformed data (of O(n) size)
 
And the answer is no.
 
9:10 PM
slow day I guess
 
@VermillionAzure Pffffr, blah blah blah
 
@Mr.kbok Damn, they went full rightfold.
 
So O(n + log(n)) is not in O(n), amirite?
 
oh hey @Puppy I didn't realise you went on holiday
 
@Puppy Ummm...okay.
 
9:11 PM
@Jefffrey No, you're definitely wrong.
 
@Jefffrey It is in O(n)
 
@Jefffrey pretty sure only the highest factor is considered
 
no, it's O(n).
 
as n -> infinity
 
log(n) is clearly of far smaller magnitude than O(n), so it is discarded.
 
9:11 PM
@EtiennedeMartel lol
 
O(n^3 + n^2) is O(n^3)
 
@Mr.kbok I'm really gonna start using that more.
 
as n approaches infinity, the runtime will be dominated by n and not log(n).
 
@EtiennedeMartel Glad to hear it's a thing. It didn't took long.
 
but like I said
 
9:12 PM
@Puppy ^ Good mark!
 
@Puppy So what would be this constant k?
 
:\ the kids out side are chanting like some sort of cult...
 
@Jefffrey you've read about it two days ago btw
 
@Jefffrey for example 2
 
9:14 PM
 
2n > n + log n
 
when you posted this
what puppy tells you is a couple of paragraphs below that
 
@milleniumbug So you think that 2n >= n + log(n) always?
 
@thecoshman Cargo cults are heavily sticking things.
 
@Jefffrey L'Hopital I think.
 
9:14 PM
@AlexM. That has to do with the master theorem.
 
Use L'Hopital
 
@Jefffrey No. You just have to pick a c such that for all n > c, that's true.
 
Why not just use L'Hopital
 
@Jefffrey It's enough to find a number where that's true for every case from this on
 
@Jeremy The point from which it has to be true is different from the constant you have to pick
 
9:15 PM
taking the derivative of both sides, it becomes 2 >= 1 + 1/n
as n -> infinity, 1/n -> 0
 
@milleniumbug And what's this number from which that holds true exactly?
 
since 2 >= 1, 2n is progressively slower than n + log n
@Jefffrey It's not too hard to find I think.
2n = n + log n
the number n = log n
 
@VermillionAzure wat
 
@Jefffrey bad memory on my side
it was actually a page after that part
 
9:16 PM
@VermillionAzure why not you just go insane upon such repeating complexity, and leave us still sane people out?
 
So M = 2, x_0 = (e.g.) 2.
 
@Jefffrey For the dataset you have, the number where the performances are the same, we get n = log n
 
@Jefffrey Can't be bothered to think now, but Cinch provides a good advice
 
Dude, it's just calculus/math.
 
9:17 PM
@Jeremy Exactly
 
what's a derivative of log n
 
@milleniumbug 1/n
 
@Jefffrey To say otherwise would be to say that log(n) > n, and I'm not sure if that's possible and it's certainly not possible for positive integers.
 
@VermillionAzure That makes no sense. You have to find the constant k and x0
 
@Jefffrey No, it does.
 
9:17 PM
@Jefffrey 2
 
We're comparing 2n vs. n + log n
 
@Jeremy So k = 2 and x0 = 2?
 
We're asking when 2n = n + log n
 
@VermillionAzure Which clearly simplifies to n vs log n.
 
@Puppy No.
Use algebra.
 
9:18 PM
yes
 
@Jefffrey M = 2 and x0 = 2, yeah.
 
Forget the O, it's just math.
 
simply subtract n from both sides...
 
it's not vs, it's n where n = log n
if we e^k both sides, we get e^n = n
 
@Jefffrey You don't have to provide specific k and x0. You just have to provide one of them.
 
9:19 PM
you said "vs" in the message I replied to.
 
nvm, pedantic
 
@milleniumbug I don't think that's true.
 
but e^n = n when n is?
 
you can use WA too shrug
2n >= n + log(n) holds for every n > 0
 
e^n is never equal to n.
e^n is always greater than n.
therefore, 2n >= n + log n is always true.
 
9:21 PM
Why do you even bring up e^n
 
but as n -> infinity, we get infinity = infinity + log infinity
 
@VermillionAzure You're actually multiple persons? That's seriously scaring me, and I seriously think you should be banned for chat and main site.
 
@CatPlusPlus because the inverse of log/ln x is e^x
 
Who cares about derivatives
It's true because n >= log n
There's literally nothing else needed
 
@CatPlusPlus Ah, but what if we start getting into more complex analyses?
 
9:22 PM
you can even go on to say n > logn actually :P
 
@milleniumbug You have to provide both of them, but x0 is not a problem to find usually.
 
@πάνταῥεῖ I'm two people; Cinch and me. I don't go on Cinch anymore. Cinch is question-banned.
 
WHAT IF EARTH SUDDENLY EXPLODES
 
@Jefffrey provide them where?
to whom?
 
@CatPlusPlus It's perfectly applicable to complex algorithms with complex running times.
Double-hash for a player-player pairing database.
 
9:23 PM
12 mins ago, by Jefffrey
Is n + log(n) part of the O(n) set? The question basically boils down to, is there a constant k for which kn is an upper bound from (possibly from some point of the function on)?
 
@AlexM. What? No. Subtract N from both sides to get n > log(n). That's true if and only if N >= 1. For 0 < N < 1, log(n) < N.
 
@JerryCoffin Put in 1 into 2n >= n + log n.
 
@Jeremy Sure it is. If the hypothesis is true either for (k = 2, x0 = 20000) or (k = 200, x0 = 200), it doesn't matter which I choose. /cc @Jefffrey
 
log n decays exponentially past <1
 
Math is hard and you're all nerds
 
9:24 PM
@Jefffrey can't you just say yes because it's obvious that n > logn
 
@VermillionAzure @VermillionAzure Didn't really approve over @Chinch!
 
@AlexM. No, because they're both O(n) time.
 
1 min ago, by Jerry Coffin
@AlexM. What? No. Subtract N from both sides to get n > log(n). That's true if and only if N >= 1. For 0 < N < 1, log(n) < N.
 
@milleniumbug Oh, that's true. I interpreted what you said to mean you don't have to find x_0 AND M - you just needed to give one. I agree you only need one pair (M, x_0).
 
@Jefffrey yes, that's what I said too
 
9:25 PM
@AlexM. If you've taken Calc 1/2, you'd use L'Hopital
Which is based on the rate of changes of growth/decay
 
@Jeremy Yeah, only thanks to Jefff's message I could see the ambiguity of my message
 
@AlexM. Yeah, so you need that x0 = 1, otherwise your claim that n > log(n) is false
 
Communication is hard
 
Basically, take the derivatives of everything if you end up with infinity forever.
@Jefffrey log(0) is, like, -inf
 
@Jefffrey are there any algorithms where n is not supposed to be in [1...inf)?
 
9:26 PM
@AlexM. doesn't make sense.
n is an absolute quantity.
it's like saying I can go -12 mph. This can be good for vector/velocity, not its magnitude.
 
@VermillionAzure You're making this chat room less enjoyable. I'm gonna plonk you.
 
Quantity is magnitude, not direction
 
@AlexM. Don't think so. If that was the case, they could have chosen a different letter, not n
 
@AlexM. n can be 0
 
@milleniumbug or just call them O(1) since that's what I'd call something that doesn't execute at all :P
 
9:27 PM
@JerryCoffin Uh you wrote the same thing twice
 
it takes a constant 0 time to execute
 
@Puppy You usually study for n -> inf, but when you try to find x0 n can also be 0
 
@Jefffrey Not... really. It's pretty clear that inserting into a vector of a constant number of items will take constant time, so nobody really cares. 0 is not special in this regard.
 
Logarithms of fractions are negative so n is still bigger than its logarithm
 
seriously I had a boner before all this started and you killed it with this silly algorithm thing
jesus christ
JEFFREY
 
9:28 PM
lol
 
@AlexM. why would you
shame
 
this is like
 
are you studying for school or something
 
@AlexM. Whip it up again. Easy! :D
 
@Jefffrey but 0 doesn't make sense.
 
9:29 PM
"Hey guys, I had a boner, and then I went to some random place on the Internet, now for some reason it's not here?!"
 
n is valid for all natural numbers
 
damn there's marple syrup everywhere
 
@VermillionAzure That's why you have to specify x0
 
@Puppy Sounds like a good candidate for an SO question to me
 
@VermillionAzure (0 is a natural number)
 
9:29 PM
@Prismatic I heard they like questions like this on meta
 
@Jefffrey if you want an authoritative answer you can always
 
@Jefffrey or starts from 1.
 
@AlexM. Nah, I'm conviced.
 
I didn't even know you found the answer
 
Depends. I can speicify N > 0
 
9:30 PM
so complicated your question is
 
I'm convinced that I have a fetish for having as many people as possible against me.
 
@Jefffrey I love you.
 
@Puppy I have not seen last five or so episodes of Battlestar Galactica yet. Probably never will.
 
@wilx It's good.
 
lol BSG
 
9:31 PM
@VermillionAzure From what I have heard the ending sucked.
 
The final episodes are crap
 
@Jefffrey You like it rough, it seems
 
@wilx It's fine. Better than some other series. I liked it.
 
The entire last season verges on total garbage
 
I'm actually serious. I always try to pick unpopular opinions and defend them to the death of the topic.
 
9:31 PM
@CatPlusPlus Grumpy old cat cannot be taken seriously but in this instance it is probably right.
 
That's called trolling
 
I even forgot what was the question
 
Maybe it's a call for being at the center of attention or something.
 
@wilx It's mostly OK, not obviously terrible. Just don't watch the part after the final battle and mentally insert "AND THEY ALL LIVED HAPPILY EVER AFTER" instead.
 
> It will be implemented [...]
Definitely.
 
9:32 PM
Note: playing devil's advocate for the sake of being a contrarian is annoying
 
@Jefffrey it's really weird
you also have an annoying tone in your writing when you ask questions
 
Yeah, I know.
 
I'd virtuaslap you but I can't
 
@Jeremy Yeah. Also HN wetting itself after something that has not even been written
 
I actually get off a little when people get mad because I'm not of their opinion.
 
9:33 PM
@Jefffrey Most of us do. I prefer to have gorgeous young women against me though. Of course, when I say "against me", I'm thinking in a little more...physical fashion.
 
In real life though.
 
Instead of watching garbage you can watch Rick and Morty instead
 
Hm, assuming I identify all code points representing combining marks/things...are they always unambiguously attached to one preceding code point, or how does it work?
 
haha hahha you're implementing unicode
 
@JerryCoffin Old women for old farts only!
 
9:33 PM
rip
 
@melak47 Basically, you start with a non-combining codepoint, and then you just keep combining.
 
@JerryCoffin You dirty bee
I hope that's a bee
 
but the real protip here is "Don't do Unicode".
 
@Jefffrey Wasp.
 
@Jefffrey Me too.
I also really get off on being wrong about stuff.
 
9:34 PM
@Jeremy meta is no fun allowed
 
@Jeremy Oh I have it. Maybe we want to be unique snofleks
 
73
Q: The site should not make speculative statements about its users

1999The redesigned user profile sees it fit to speculate about the motives and inclinations of the user. E.g. here: Apparently, this user prefers to keep an air of mystery about them. We respect a laser-like focus on one topic. Keeping a low profile. This user hasn't posted... yet. ...

 
@Prismatic Yeah - I was being sarcastic
 
it would be nice if all unis made their courses public
like MIT does
they have all kinds of nice stuff like recorded lectures transcripts assignments readings etc.
 
I posted a link about StackOverflow on HackerNews. :D
 
9:35 PM
@Puppy I guess I can turn off "unicode character set" and get "multibyte character set" instead...but then I don't have a clue what I'm getting :D
 
@Jefffrey I think I just did too much math in university. Math usually means trying a bunch of things that don't work out or even make sense.
 
@AlexM. Never get mad at me though, please. :3
I love ya
 
Or, we're unique snowflakes that both get off.
 
@AlexM. I think most universities post their course content in a way that can be crawled by a search engine
 
@Prismatic The PC plague. :(
 
9:36 PM
@Prismatic This user is an idiot
 
@CatPlusPlus stop speculating
 
@Prismatic yea but MIT does it in a "here's all our stuff for free! please donate if you like" kind of way
 
@melak47 Definitely don't do that.
 
@Jefffrey I probably won't anytime soon :P
 
I guess you were thinking more like "use a library"
 
9:37 PM
Also you get antipoints for making wilx post irrelevant garbage
 
@AlexM. Yeah the OCW is pretty nice. I think curating the content and making it available in a complete way takes a decent amount of effort though, which is why more unis don't do it.
 
@CatPlusPlus What?!
 
I think with Khan academy and all the educational content available online, the value proposition of universities has kind of changed. Now if only people could address the degree problem
 
The problem is old farts
 
@Prismatic Tbf those are unfunny messages
There I did it again.
 
9:40 PM
@Jefffrey Are they supposed to be funny? Or just a casual way of providing some very basic information about the user?
 
@AlexM. good to know
 
@Prismatic Don't mind me
in Lounge<Factorio>, 33 mins ago, by thecoshman
just been playing a good bit myself :P
Well, I was thinking
 
Congrats
 
With regards to having arrays everywhere, you could have a red black tree implemented as an array
 
For what
 
9:43 PM
@Jefffrey Sure you could. That wouldn't help with the locality though.
 
here we go again?
 
@AlexM. What?
 
nothing
 
@milleniumbug Would help with having your data compact instead of nodes in random places on a heap
 
wait wasn't this where your previous question started
 
9:44 PM
@AlexM. Nah, that was about ordered arrays
This is about red black tree as an array
 
@Jefffrey He is probably having a boner again and wants us to know. :)
 
You still lose insertion characteristic hth
 
@CatPlusPlus Well, no because you always insert at the end
 
What about B+-trees then?
 
hot tamale hero
 
9:45 PM
And always remove from the end
 
I have no idea what you guys are talking about.
 
Uh trees don't work like that
You can remove any node, not just last inserted one
 
Balanced trees do. At least one of them. I don't recall which one it is.
 
It's not a queue
 
@CatPlusPlus Yes, but you reorder the tree so that the empty space of the removed node is filled. And that operation is O(log(n)) IIRC
 
9:47 PM
in a tree you start from the top and travel until you find the insertion spot that you want
then you re-balance if needed after the change
 
So you still have a compact tree
 
I can't think of any tree where you insert at the end unless you're actually trying to build something like a complete Nary tree and you don't care about order
 
@AlexM. On a binary tree you insert at the end
 
It's still not very localised because you jump all over that array
 
On the leafs
@CatPlusPlus Well, the data is more localized than single cells in different places
 
9:48 PM
Unless all of your tree fits in a cache line, you're still incurring misses
 
Which is what a node structure would do
 
@Jefffrey CPU doesn't care if your data is 600 or 760000 bytes apart
 
@Jefffrey I can insert wherever I want in a binary tree
perhaps you want to be more specific?
 
It's either in the cache or not
 
you can make a given node the child of another and make all old children the children of the new node if you want
 
9:49 PM
It's called random access memory
It already behaves like an array in that regard
Access to any index takes the same amount of time
Locality is purely a cache thing
 
@AlexM. The usual implementation of binary search trees is that you have left node <= that the parent and the right node is > than the parent. And you always add at the leaves
@CatPlusPlus I see
 
@Jefffrey ok, that's one case
 
So cache locality is only really useful when the caching algothm loads a block of memory and you access sequential data right next to each other and so it happens to be in the same block it was loaded before.
 
@Jefffrey No, it's also useful if you use the same data a lot in a short temporal period.
if your working set fits in cache, even if you don't sequentially access it, you get a big win.
 
But then again if it's not in the same cache line then it doesn't matter how apart it is
 
9:52 PM
it's just that sequential access is the most effective means of loading new data into the cache
 
@Puppy Because the cache loads blocks/lines of memory and it could load multiple used data at once, instead of having to generate misses.
 
yep.
 
I should post my mike acton meme
 
your what meme?
 
9:55 PM
So hash tables also have the same issue.
 
Also image macros and memes are not synonymous
 
Unless you have a linear hash function, but that has huge cons anyway.
 
That'd be called an array yes
 
@Jefffrey Not necessarily, there are some hash collision resistance strategies that put all the elements of a bucket into an array
 
I meant an hash function like: hash(x) = x mod M where M is the size of the hashes values set.
 
9:56 PM
ALL THE EGGS IN ONE BASKET
 
meh
it's not very uesful to design your hash table so that only integers can be keys.
 
@Jefffrey uh won't it collide with another leaf if they're put too close together? or...?
 
It's a rubber tree
 
@Puppy The idea is that you can interpret any data as unsigned integers.
 
Good luck with that
 
9:57 PM
well, you can, but it's not especially useful to do so and the integers you'd get back would be effectively totally random.
 
@Jefffrey That's not very fun
 
It's all bytes anyway :P
 
@Puppy Might not be, but that's what the premise my current algorithms book begins with.
 
then I would burn it immediately
 
It's a crappy book
 
9:58 PM
@VermillionAzure Whaaaaaat
 
@Jefffrey Algorithms... hm...
I should learn them
But idk where to start or why
 
nah
learning "algorithms" is useless.
you need to have a problem, and then learn only algorithms that solve that problem.
 
I don't agree with that
 

« first day (1725 days earlier)      last day (3227 days later) »