« first day (760 days earlier)      last day (4183 days later) » 

7:00 PM
@MooingDuck And the ambiguities you told me, in my statement :)
 
@VinayakGarg what?
@VinayakGarg chat.stackoverflow.com/transcript/message/6222685#6222685 was the key that told me what my bug was
 
@MooingDuck You pointed out several ambiguous things in the problem.
 
@VinayakGarg oh, pft
 
@VinayakGarg On an unrelated note, I glanced at your blog. Since you're apparently interested in optimization, you might want to consider writing a bottom-up version of your merge sort. With a recursive merge sort like yours, the recursion basically adds a lot of overhead to getting to the point of taking every other item in the input, and swapping them if they're out of order. You can, instead, just walk through the array, arrange every two, then merge the first pair with the second pair (etc.)
 
@VinayakGarg nishant10's answer uses an impressively small amount of memory, I'll have to examine it later
 
7:05 PM
Greetings++
 
@JerryCoffin Oh man! Do you know I prepared for interviews by reading your answers on SO. Thanks for pointing it out :)
 
@VinayakGarg I had no idea -- hope it was helpful. You're certainly welcome.
 
@Chimera What's up?
 
@Chimera Hello.
 
@DeadMG Who dropped off the planet?
 
7:06 PM
@Chimera You arrived after he dropped off the planet, so I doubt you have met him.
 
@R.MartinhoFernandes Ah same old. Getting the house ready for foster children etc. You?
@JerryCoffin Hi Jerry!
@R.MartinhoFernandes ah
I haven
I haven't seen @Drise in a long time.
 
@Chimera Trying to bore myself to sleep :)
 
@MooingDuck That's because it uses C.
 
@R.MartinhoFernandes Oh man... sorry to hear that.. Good luck!
 
7:09 PM
@VinayakGarg uh, no. The language used is not relevant to the fact he used half as much memory as everyone else, including those who used C.
 
@MooingDuck Half of what? 1 byte?
 
@DeadMG This is so weird.
 
Ell
gah! Making a game is too hard!
 
@Mysticial most of the answers use 2.6Mb. A few use more, but there's one outlier at 1.6Mb.
 
@MooingDuck Hehe, you want to look at 1398.5M solution
 
7:10 PM
@EtiennedeMartel yeahano
 
@VinayakGarg well, that's Java :P
 
lol, I am amazed it managed to beat several C++ solutions in time
 
@VinayakGarg he's last place on the practice page
 
@MooingDuck No look at the live contest link, I gave.
 
@VinayakGarg oh, that is impressive
 
7:14 PM
@VinayakGarg The top solution is really written in C.
 
@MooingDuck meh... at least in my terms, I can't be bothered with memory optimizations unless it becomes on the order of GBs... or is a performance issue.
 
@DeadMG If you open more solutions, most are really written in C.
 
"C++ 4.3.2"
Well, well.
 
Hmm, I think you can leave C++11 for 50 LOC
 
7:21 PM
@JerryCoffin As I always say, great minds are unique. It's mediocre minds that think alike.
 
@R.MartinhoFernandes Probably -- but bragging about how great you are is more fun than admitting to mediocrity.
 
My mediocrity is bigger than yours. SCNR.
 
No offense but when I see two gay men holding hands/kissing I feel uncomfortable likes it's unnatural.
Arrrggggghghgghgh
 
@EtiennedeMartel Likes?
 
@EtiennedeMartel Yeah, the grammar is all wrong. Cringeworthy.
 
7:27 PM
Yes. And also... FUCK.
 
@EtiennedeMartel Why are you getting so worked up about opinions on the web? I mean, I've seen plenty more outrageous and less subjective opinions vented
 
@sehe I don't know. I get worked up about lots of things.
 
Sounds like no fun to me. You could try getting some help with that. Or perhaps changing some things in your life that you're not happy about (disclaimer: arm chair pshychology here)
 
I think it's mostly my white knight side. I tend to get angry when I see people being discriminated against.
 
@EtiennedeMartel You mean light knight?
 
7:32 PM
@VinayakGarg I mean white.
 
@VinayakGarg The point. I think he missed it...
 
Also: "caucasian bishop", or just "fellow piece" :)
 
@sehe Ya he missed it. But you got it :D
 
Life is hard.
 
7:34 PM
And if it isn't: blue pills
 
@VinayakGarg C is usually done with a more functional mindset, whereas C++ is usually done with more of an OO mindset. C is not faster than C++, function tends to be faster than OO.
hmm, I replaced all tabs with four spaces in a large header and visual studio is now uphappy
 
@MooingDuck If, and only if, you define "OO" as "virtual".
 
@MooingDuck I'd say "procedural" or "imperative" instead of "functional" there -- at least to me, "functional" implies something like Haskell, which most C doesn't resemble at all.
 
@JerryCoffin procedural then
@EtiennedeMartel na, OO implies other overheads, related to invariants. Can write OO in C as well, without virtual functions.
 
@MooingDuck In that case, I tend to agree, for what little that may be worth.
 
7:39 PM
@MooingDuck What overhead? I mean, a C++ class vs a C struct + functions?
(Because sure, if you have no state, then why bother with OO anyway)
 
One other factor is that by providing nice collection classes and such, C++ makes it much easier to do things like "just read the whole file into memory". C's lack of such niceties tends to encourage such things as character by character processing whenever humanly possible.
 
@MooingDuck I am confused. What should a procedural code inside .cpp file be called? No classes. But STL used.
 
@EtiennedeMartel I mean the overhead of enforcing invariants at all times because you can't be certain of the calling code will do. Example: vector<int> zero initializes on resize. That's overhead if the calling code was about to assign them other values.
@VinayakGarg if it's procedural then it's procedural.
 
@MooingDuck That strikes me as a good thing.
 
@MooingDuck In which case the calling code could just use v.insert, v.assign, std::move(f,l,back_inserter), and/or the make_move_iterator facility
 
7:43 PM
You have to enforce invariants in C. Except you have to do it yourself there.
 
@EtiennedeMartel procedural code usually doesn't have that overhead, because there's no objects maintaining the invariants when it's not necessary.
@EtiennedeMartel then that's OO in C. Nothing wrong with that. It just tends to be slower than procedural.
 
Wait, wait.
 
@sehe back_inserter has overhead of messing with the end/size all the time.
@EtiennedeMartel some languages encourage OO, such as Java and C++. Every language allows OO.
 
sbi
@MooingDuck reserve()
 
@sbi that avoids messing with the capacity, but there's still the overhead of the "current size"
 
7:46 PM
@MooingDuck You're comparing apples and oranges. It seems to me like your definition of "overhead" is "anything that takes time".
 
@EtiennedeMartel anything that takes time when the program would be exactly the same without it. It's completely unnecessary (at run time).
 
@MooingDuck It wouldn't be the same.
 
@EtiennedeMartel then those cases aren't overhead.
 
You mean it's unnecessary for a vector to keep track of its size?
 
I think it can be summarized a little bit more simply: C++ places a stronger emphasis on writing general-purpose building blocks that can safely be used almost anywhere. Making them safer and more general-purpose almost always adds at least a little overhead. We usually use templates and do as much at compile time as possible to minimize the overhead, but there's still often at least a little left.
 
7:47 PM
@JerryCoffin ^that's good
 
sbi
@MooingDuck Sorry, but that's bovine excrements. It's one of the key features of C++ that it has shown that OO isn't inherently slower than procedural code. There actually have been studies finding out that using virtual functions not only isn't slower than C's switch statements, sometimes it's even faster.
 
@sbi He's comparing a class that maintains its invariants to a function that does nothing. Of course the latter is going to be faster.
 
How do you compare a class to a function.
 
(Hmm, that was some weird syntax I just wrote)
 
@EtiennedeMartel Turns out there is an opportunity for character building experience:
Can someone just please knock some common sense and reality into my head? #please
 
7:49 PM
@R.MartinhoFernandes Yeah, after pressing enter, I realized it did not make a lot of sense.
@sehe You know what I say? As long as there is beer, there is hope. And there is plenty of beer right now.
 
sbi
@R.MartinhoFernandes Apples, please meet Oranges. Oranges, Apples.
 
@sbi I messed up my explanation. Wait.
I should have said "class method" instead of just "class".
That would have been better.
 
sbi
@EtiennedeMartel I already waited, and it didn't get any better. :)
 
@R.MartinhoFernandes Using a a functor comparator polymorphic callable object, of course
 
@sbi You should have waited five more seconds.
 
sbi
7:50 PM
@EtiennedeMartel I just did. So?
 
39 secs ago, by Etienne de Martel
I should have said "class method" instead of just "class".
 
@sbi I think that falls into a "yes and no" area. On one hand, it's true that a virtual function call can be competitive with a switch. At the same time, people writing OO (especially beginners) often use virtual functions when they're unnecessary, just in case somebody might eventually want to override them. Even more advanced programmers often end up with some of the same -- virtual functions they plan to allow overriding, even though they rarely are (e.g., iostreams and locales).
 
@EtiennedeMartel the common example being C code that allocates an array of ints, then assigns each of them a value from rand(). If you try to do that with a C++ vector, it will always be slower, because of the safety mechanisms. But since there's no exceptions that can be thrown, that safety is useless in this scenario, and just takes extra time. That's the definition of overhead. (To be clear, I still use vector 100% of the time. That overhead is totally worth it)
 
sbi
@EtiennedeMartel Bah. A "class method" is just a function with an implicit argument anyway... :)
 
@MooingDuck I think this baby needs a proof. I don't think it is true. Let me check
 
7:51 PM
@sbi Oï.
 
@sehe A really good optimizer might be able to optimize it out. But the C version had nothing to optimize out
 
That pedantry, that nitpicking... @sbi, you would be a perfect addition to the room owners!
 
sbi
@MooingDuck Oh, now you're backing out, right?
 
@MooingDuck That's only because vector does not provide an interface for that operation.
 
sbi
I don't even saw that.
 
7:53 PM
@MooingDuck OTOH... Sounds like a challenge.
 
sbi
@JerryCoffin Don't get me started on the atrocities novice C programmer inflict on their code.
 
But, indeed, writing it yourself to be as close to the metal as possible is going to yield something that runs faster than the already available general solution... if you get it right.
 
Xeo
@MooingDuck Which overhead are you talking about specifically?
 
@JerryCoffin Seems like they don't know the YAGNI principle.
 
@MooingDuck What's that for benefit?
 
7:55 PM
@Xeo depends on the method. resize+assign has the unneeded initialization. reserve+push_back keeps updating the current size.
 
@Xeo Keeping the size up to date during hte whole operation.
@MooingDuck Yes, but that's only because you are using the wrong interface.
 
@sehe the theoretical case where the optimizer might not be able to optimize all of the overhead out
 
@sbi It's not lumber? You don't saw it :)
 
@R.MartinhoFernandes reserve+assign_with_iterators might be the same speed maybe.
 
@MooingDuck Oh great. I'd opt for correct any day
 
7:56 PM
The operation you want to do is "add a series of elements". The operation you are using is "add many elements one at a time".
 
@MooingDuck I remember saying this
 
Xeo
@MooingDuck auto gen = generator_range(0); vector<int> v(gen.begin(), gen.end());? :)
 
@MooingDuck Ok, so I don't need to write it.
 
@sehe oh, so would I. I never said otherwise. I love the invariants and such
 
You can claim that the interface is crappy (writing an iterator? Oh gawd, please...). But if you do the right operation, you get the right effects.
 
7:58 PM
@EtiennedeMartel I think YAGNI was largely a reaction to exactly the sort of thing I'm talking about. For that matter, it's still pretty common (for one obvious example) Java -- the giant class hierarchy that (for example) adds another layer of inheritance to add exactly one new virtual function (that nobody ever really uses) -- but the book spent so much time on exceptions like non-flying birds that they feel obliged to incorporate all such possibilities in their hierarchies too.
 
@R.MartinhoFernandes no, I claimed not all objects have the interface you want.
 
Xeo
@R.MartinhoFernandes Not that you totally need to write an iterator.
 
@R.MartinhoFernandes I also claimed there are hypothetical situations where the optimizer might not be able to optimize out the overhead.
 
@MooingDuck With an inlinable iterator, I doubt that will ever happen (the size adjustment is not anywhere in the code, so that's not what has to be optimized).
 

« first day (760 days earlier)      last day (4183 days later) »