« first day (558 days earlier)      last day (4391 days later) » 

9:00 PM
Does anyone have any examples of algorithms that are asymptotically optimal (or best) but that aren't used in practice because of the large constants? I only know of the Coppersmith-Winograd matrix multiplication algorithm.
 
@GManNickG I know one that is rarely used, lemme find it
 
lol, our algorithm is the fastest but not if run on modern hardware.
 
What about matrix chain multiplication?
Matrix chain multiplication is an optimization problem that can be solved using dynamic programming. Given a sequence of matrices, we want to find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications. We have many options because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have: :(ABC)D = (AB)(CD) = A(BCD) = A(BC)D...
 
Fürer's algorithm is an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity. It was created in 2007 by Swiss mathematician Martin Fürer of Pennsylvania State University as an asymptotically faster (when analysed on a multitape Turing machine) algorithm than its predecessor, the Schönhage–Strassen algorithm published in 1971. The predecessor to the Fürer algorithm, the Schönhage-Strassen algorithm, used fast Fourier transforms to compute integer products in time O(n \log n \log \log n) in big O notation and its authors, Arnold Schönhage and ...
 
@DeadMG make_unique<vector<int>>( { 1, 2, 3 } ) wouldn't forward properly.
 
9:05 PM
@GManNickG Schönhage–Strassen is only used when multiplying numbers with more than ~10000 decimal digits
 
that algorithm name reminded me of en.wikipedia.org/wiki/Adolf_Hitler
 
(Yes, I know make_unique vector is stupid, but replace that for any other init-list constructible type)
 
@MooingDuck Sweet, thanks.
 
@RMartinhoFernandes Only because some moron invented initializer_list instead of using the existing Standard type representing a statically-sized bunch of T.
 
9:07 PM
@GManNickG And the Fürer's I linked isn't used at all, because it's constant is even bigger, but it has a smaller complexity than Schonhage-Strassen even.
@GManNickG Karatsuba multiplication fits between "long" multiplication and Schonhage-Strassen.
 
@MooingDuck Ya. It's actually extremely close to being theoretically optimal too, that's cool.
 
@DeadMG I was going to say that array is not movable, but then remembered that initializer_list sucks, so I'll just shut up.
 
@RMartinhoFernandes don't see why array shouldn't be movable
 
@DeadMG it doesn't make sense.
 
Because it stores the data inline.
Otherwise it would require allocations, no?
 
9:10 PM
so what?
std::array<std::string, 5>.
doesn't store the important data inline at all.
 
Did you mean cheaply movable?
 
If it allocates, it's redundant: just use vector.
@LucDanton Yeah, that.
 
there is no reason that an array move cannot be the move of each constituent element
 
Still cheaper than copying.
Conceptually. Ends up the same at worst of course.
 
more importantly
allows you to store move-only types in a std::array
and actually be able to use them
 
9:12 PM
@DeadMG Oh, but a vector is still better.
 
@RMartinhoFernandes Why?
 
@DeadMG I thought they'd fixed that, guess I was wrong.
 
a vector allocates on the heap. What does wanting to put a move-only type in have to do with where I choose to allocate that type?
 
@RMartinhoFernandes what it you want those objects on the stack?
 
there is no relation whatsoever to wanting to move the contents of an array, and where I choose to put that array.
 
9:14 PM
@MooingDuck It works fine.
 
@LucDanton you can return an array of ostream objects from a function?
 
Yep.
 
@LucDanton deadMG and MSDN disagree. Testing IDEOne
 
it's probably just MSVC being out of date
 
MSDN is not a standard.
 
9:16 PM
Clang and GCC disagree.
#include <array>
#include <memory>
#include <utility>

typedef std::unique_ptr<int> ptr;

std::array<ptr, 2> a = {{ ptr { new int{} }, ptr { new int{} } }};

int main() {
    auto b = std::move(a);
}
Compiles fine.
 
If DeadMG is a standard, he never said.
 
@CatPlusPlus Only for Wide :P
 
Copying an initializer_list is cheaper than moving an array.
 
Ideone has GCC 4.5, which is ancient by now.
The point is Haskell is awesome.
 
@RMartinhoFernandes Any situation where you can copy the initializer_list, you only need a reference to the array.
 
9:19 PM
@CatPlusPlus That's why I didn't say he was wrong. MSDN is always my first check, since it's usually close, and easy to access/use.
 
@MooingDuck: Another algorithm/structure that's theoretically best but practically ugly:
In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: O(1) for insertion, find-minimum, meld (merge two queues) and decrease-key and O(\mathrm{log}(n)) for delete-minimum and general deletion; they are the first heap variant with these bounds. Brodal queues are named after their inventor Gerth Stølting Brodal. While having better asymptotic bounds than other priority queue structures, they are, in the words of Brodal himself, "quite complicated" and "[not] applicable in practice." References
 
Woot, I updated GCC and it is now building clang again!
 
I had a roommate who claimed there was no good use for std::list. Took me years to find a counterexample. And it comes up so rarely I usually just agree with his sentiment.
 
Well, it works nicely for stacks and queues, if your implementation has borked deque.
 
Anywhere I would have used a std::list I used an intrusive linked-list instead.
 
9:22 PM
@MooingDuck I used one for an LRU cache.
Oh, scratch that, I used an intrusive one, not the standard.
 
@MooingDuck What was the counterexample? Feel free to add it to my old question on the subject.
 
@GManNickG I've used intrusive lists I suppose.
@JerryCoffin splice (And even then rarely)
 
Didn't C++11 make splice, the only useful thing about a linked-list, useless? (By making it O(n).)
 
@MooingDuck splice is a cool thing, but what was the actual use?
 
Shit, my Keepass is borken too! Why the heck did I upgrade everything. I'm so stupid.
3
 
9:24 PM
Suffer as I suffer.
 
@JerryCoffin If you already had iterators and needed to cut bits out of the middle frequently.
 
I was warned and fucked it anyway.
 
@RMartinhoFernandes Pwned. Windows users are the winners here, nubs! mwahahaha
 
KeePassX should hurry up and finish kdbx support.
 
@DeadMG Meh, I can just rollback to the previous version. I have a package manager.
 
9:25 PM
@GManNickG no -- it's O(1) in the cases it can be, and O(n) in only one case. For that case, you have a choice: you can make either splice O(1) and size() O(N), or vice versa, and they chose to make size()` O(1).
 
@JerryCoffin Jason Williams's answer basically
 
@JerryCoffin Oh, good. :)
 
@JerryCoffin Isn't that the less flexible alternative?
 
@JerryCoffin That case is the most powerful one though, isn't it?
 
@RMartinhoFernandes Hard to say. Apparently they thought size() was used more often than splice...
Oops -- gotta go pick up kids. Back in a while.
 
9:29 PM
@JerryCoffin Since splice is the list's biggest pro, seems wierd they'd make it O(N)
 
@DeadMG There, keepass fixed.
So, anyone been to the movies lately?
 
I admit to nothing. On a totally unrelated note, time to sleep.
 
lol
I was hoping to get a good suggestion for Saturday. You guys suck.
 
You're the one 'going' to the movies. Not that I admit to anything.
 
I need to ask. Are you making fun of something I did wrong?
 
9:37 PM
@RMartinhoFernandes I saw Hunger Games and a friend saw Cabin in the Woods. We recommended it, I thought the Hunger Games was enjoyable but not mind-shattering. Haven't seen Cabin in the Woods myself, yet.
 
@RMartinhoFernandes No.
 
Just plain silliness then. Ok.
 
@RMartinhoFernandes I saw Hunger Games.
 
@DeadMG do I need to remind you of your unfortunate run ins with Microsofts sweet management of software dependencies?
 
@sehe no
 
9:39 PM
lol
 
@DeadMG Good
 
@DeadMG What'd you think of it?
 
I thought it was reasonably fun.
not as good as it could have been, but worth the entry cost
 
Ha, in the finest tradition of Lounge<C++>, a message with "I'm so stupid" was starred.
It's probably the easiest way to get stars here.
 
I hadn't noticed that, but thanks for pointing it out so that I could also star it.
 
9:44 PM
@sehe gah, I keep thinking you're a newb since I don't immediately recognise the pic :/
 
Meh, seems like we're going to watch The Avengers. Most of use have seen Hunger Games already, and I'm the only one not very interested in the Avengers :S
 
@MooingDuck What, he isn't?
 
Thanks for the suggestion anyway.
@DeadMG Ow.
 
@MooingDuck ♫ I'm a newbie and I'm ok ♫
 
@sehe people shouldn't be allowed to change their avatars
 
9:49 PM
@MooingDuck Weehoo!
Jan 10 at 19:31, by sehe
I liked Mooing Duck. It had character. It's like Neil Butterworth - he had something else before that - very recognizable. Ambeco sounds like an insurance company :) (I hope I don't insult you if that's your real name haha)
I remeber that ^
 
@MooingDuck Well, it does let them require size() to have constant complexity. In the '03 standard there was just a note to say "should be constant", but no statement about where/when/why it was/wasn't required. In the end, I tend to agree though -- it would probably have been better to specify it as linear for list and forward_list, and constant for all others.
 
@sehe shush, I'm pretending that never happened
 
Honestly, I think people should be allowed to do whatever they please, but in that instance I thought it was a shame of the good screenname. In my case, I went from 'dull default mandala' to 'somewhat less generic and less nondescript slightly funny thematic pic'
 
I'm fine with my avatar, which I've had since I got here
 
Are there any real advantages of singly linked lists against doubly linked lists ? I've pretty much always used the bidirectional ones.
 
9:53 PM
woof woof, bitches
 
I like to think it was a change for the better. I'm gonna roll with it for a while :)
 
@ScarletAmaranth less memory, at the cost of some speed
 
I've actually changed mine.
 
I remember
 
@ScarletAmaranth Half as much wasted space, depending on viewpoint and usage, manipulations can be simpler.
 
9:54 PM
vaguely
 
I originally used a picture of Alice slaying the Jabberwock, and then changed to Robbie.
 
Is this one showing more leg?
 
Well, you could always just XOR the pointers into one DWORD if you really need that extra memory.
 
Hmm...Maybe I should change mine and see how many people I can confuse.
 
@ScarletAmaranth theres some sort of rule thing making that a bad idea in C++11 I think. Under certain circumstances
 
9:55 PM
@ScarletAmaranth That does severely limit your options though.
 
Partially, yeah, although i have yet to encounter a situation in which i can conclude that a singly linked list would be of greater benefit than doubly.
 
@MooingDuck reinterpret_cast to uintptr_t, XOR away with it, and store. reinterpret_cast the stored integer back to pointers when needed.
 
@MooingDuck I believe it's now officially UB. The intent is to allow GC, which wouldn't recognize them as pointers any more, so it would collect the nodes with no recognizable pointers to them.
 
Oh, that thing.
 
@RMartinhoFernandes right
 
9:57 PM
You can explicitly mark them as reachable.
 
§ 3.7.4.3 [basic.stc.dynamic.safety]
 
void declare_reachable(void *p);
A tad more complex? Yes. Impossible? Don't think so.
 
undeclare_reachable? Why not declare_unreachable? Nevermind, got it
 
@RMartinhoFernandes ...at which point the GC stores the extra pointers instead, and your overall memory usage is back about where you started.
 
9:59 PM
Why should something like GC make the assumption that i "lost" access to some memory ?
 
@JerryCoffin Sssh.
 
What are we in Java ?
 
@ScarletAmaranth getting closer, that's the idea
 
@ScarletAmaranth Because you have no pointers to it? That's how a GC works, no?
 
Yeah it does, I just think it's partially silly, that it basically concludes that you're stupid :)
 
10:00 PM
@ScarletAmaranth The basic idea of what GC is/does is figure out when memory is no longer accessible (and then make it available for other purposes).
 
@JerryCoffin Possibly, but what if i want to store my memory addresses as strings and then reconstruct them and then access them like a mentally-ill individual ? :P
 
@ScarletAmaranth While I think it's possible to largely ameliorate the problems, experience indicates that quite a few programmers are stupid (based on that criterion).
 
@ScarletAmaranth those aren't "safely derived pointers" and you'll have to use the aforementioned functions to register them.
 
@ScarletAmaranth Then you're into UB. unless you register them as already mentioned.
 
10:03 PM
Yeah you're quite right, yet i still don't want / need GC. (He says and leaks some memory :))
2
 
Anyway, you can't start traversing a XOR list from the middle, and that makes it even less useful that std::list.
 
I was addressing the "gigantic memory loss issue" :)
But it sure does Garfunkle some other stuffs ;)
 
So, don't expect to have the bonuses like fast random removal or insertion.
 
@RMartinhoFernandes If you have a pointer to the middle, you certainly can (and I'm not sure how you'd even hope to without a pointer to the middle).
 
At that point, an unrolled list (i.e. like deque) starts to sound better.
@JerryCoffin How would you find your neighbors with just a pointer to some node?
 
10:09 PM
Or i could simply used the generic doubly-linked list. Eventho i reckon people tend to overused linked lists.
 
You need one neighbor's address to find the other.
 
@RMartinhoFernandes I'm not sure you can quite call deque an unrolled list
 
@MooingDuck It's close.
 
@RMartinhoFernandes except for that O(N) removal from the middle
 
@MooingDuck Which is exactly the same as a XORed list.
 
10:10 PM
@RMartinhoFernandes not if you have an iterator that has pointers to two adjacent nodes, which is the only real way to implement an iterator for that anyway.
 
@RMartinhoFernandes Well, you do need to store kind of a "fat" pointer -- one that points not only to the node you care about, but to its predecessor or successor (in whichever direction you care about traversing). Given the number of those you normally store, it's still generally a win though.
 
"fat pointer", PRICELESS! :)
 
Oh, that was really obvious.
I guess I need sleep.
 
@RMartinhoFernandes especially since that's how deque solved that problem
 
I was going to say "I am stupid" again, but one on the starboard is enough.
Woot, clang finished building.
 
10:13 PM
It can do that ?
 
@ScarletAmaranth I've heard rumors
 
@JerryCoffin Actually, the direction you care about traversing is irrelevant. With any two adjacent pointers you can go in any direction.
Ok, time to smoke test this baby.
> fatal error: constexpr function's return type '::std::chrono::nanoseconds' (aka 'duration<long long, nano>') is not a literal type
Damn.
 
Made marginal progress, but still need help on: stackoverflow.com/questions/10329147/…
 
@RMartinhoFernandes Sorry, poor wording on my part -- I just meant you need to adjacent ones, and the extra will be either the predecessor or successor, depending on which way you want to go.
 
if anyone knows anything about RSA... C# is giving me the same signature every time, which is what I want, but what I tried with Python and PHP has been giving me a different each time. Can I prevent that and just get what I've been getting with C#?
 
10:22 PM
@Walkerneo: This is the C++ room. :P
 
Yeah, but I was hoping someone could shed some light on RSA
I mean, why is C# producing the same thing, but not the Python or PHP libraries?
 
@Walkerneo ...because you should obviously be using C++ throughout!
 
I don't have c++ on my webhost :(
 
7 mins ago, by GManNickG
@Walkerneo: This is the C++ room. :P
I like how @Walkerneo's direct response to that includes RSA, C#, Python and PHP :)
 
hahahahahah
 
10:34 PM
Anyone want to give my noble work a pageview? I'm afraid noone will ever even see my answer, and I tried to be helpful (explaining how to analyze the causes).
 
@sehe I've noticed Boost. Spirit questions are often ignored.
 
@GManNickG I'm a perv. I'm subsribed to the RSS feed :)
 
@sehe :o!
 
Arrgh, Clang Y U STILL NO COMPILE MY CODE.
Here I go for another bug report.
 
Hello people!
 
10:38 PM
Really quite pathetic. 57 upvotes in 39 answers :(
 
@unNaturhal Hello.
@sehe :(
 
@RMartinhoFernandes So they fixed your bug (report), but not quite enough
 
I heard once that someone made a quicksort that used O(1) extra space. Anyone know where I can find more info on that?
 
That's kinda how quicksort works ?
 
@MooingDuck They probably were ignoring stack space for recursion.
 
10:40 PM
@MooingDuck I think it was radix-sort with limited range (so, indeed the XOR trick could be done on the elements)? Very badly remembered.
 
@ScarletAmaranth quicksort normally takes log(n) stack space
 
oh, youre right
sry
 
@ScarletAmaranth No, it would take log(n) space
 
yeah i was being silly
 
10:41 PM
Maybe someone know if exist a tool to auto-indent an HTML file?
 
@GManNickG 'without a stack' -- has me worried they just use an array and iterate :)
 
Published in 1986, so you can probably find it free somewhere, but maybe not.
 
@GManNickG hmm, that's exactly what I asked for, if not quite what I wanted :(
 
@unNaturhal tidy (aka htmltidy)
 
Hmm, maybe not clang. Seems like it's a libc++ bug.
 
10:42 PM
@unNaturhal also, vim seems to do a pretty good job normally
 
@sehe I tried the HTML Tidy plug-in of notepad++... it doesn't work...
 
@unNaturhal It sits on the couch all day. The lazy bastard!
 
@sehe Really? Ok, I'm downloading Vim xD
 
You don't have vim installed? Sacrilege!
 
@sehe Eeeeh? WTF? xD
 
10:44 PM
He meant blasphemy!
 
@RMartinhoFernandes :| Sorry, I'm an eretic, I know...
 
@unNaturhal It's an old stock response to the meaningless "doesn't work" reflex
 
@sehe LOL But it really doesn't work xD
 
@unNaturhal missing the aspirated h, makes me wonder whether Italian has aspirated h?
 
Mwhahahaha. It works. Time to submit a patch!
 
10:47 PM
@unNaturhal But that really doesn't mean anything. I mean, it does something, even if it doesn't do anything. Tell us the symptoms. Is there an error message? Is the window refreshed? Is there a bleep, is there something in the status bar? Is there a log file? Is the file status 'modified' after you call it? Is the file named .html? What version of Notepad++? Is the plugin installed, enabled, configured? Can you update Notepad++ or the plugin?
Do you need externally installed htmltidy for that plugin to work?
I could go on
 
@RMartinhoFernandes en.wikipedia.org/wiki/Quicksort#Space_complexity "Another, less common, not-in-place, version of quicksort uses O(n) space for working storage and can implement a stable sort." Maybe that was it
 
But that's worse (though with stronger postconditions).
 
@MooingDuck But that is worse resource complexity, for more features (stability).
 
@sehe Mmmmh... I think so... To say "Io ho" you have to throw off the air, and so with many other "h" words...
 
Not quite O(1)
 
10:48 PM
@sehe not quite
 
@sehe Ok, wait. Overload x(
 
@MooingDuck I do remember seeing something like that but I'm not even sure it was Radix Sort.
@unNaturhal Don't bother for me, I don't have windows nor Notepad++ installed. I use vim :)
I was just making a point about the uselessness of reporting that a program "Sits on the couch all day".
 
@sehe xD So, can you link me a GUI version of Vim? I hate command-line-editors :/
 
First link there on the download page
@KonradRudolph markdown fail
 
10:51 PM
@sehe meesa tired
 
@sehe Thanks :D
 
Gosh, not that accent please.
 
@KonradRudolph Since you are bored, could you review my answer here?
@RMartinhoFernandes Does that count as an accent? What planet was that from again
 
@sehe Misunderstanding: I am going to bed now
 
@sehe Naboo.
 
10:52 PM
@RMartinhoFernandes I knew you'd know that :)
So youse gonna hava lotta fun witha accentsz! (add songful intonation)
 
@sehe However I have understood what you meant. Just the uselessness to say that something doesn't work without specyfing why :P
 
@KonradRudolph That's bad bed
 
I think I only answered one question on Science Fiction and Fantasy. I'm not really a Star Wars know-it-all.
And my answer was a joke.
38
A: Was the thermal exhaust port on the Death Star really a design flaw?

R. Martinho FernandesThere are several theories. David Morgan-Mar of Irregular Webcomic! has two. One of them puts the blame on a social issue. It says that the Death Star was probably built to impress chicks, and withstanding a space battle was a secondary concern: Another one blames physics. It says that it was...

 
@unNaturhal Or even, what.
 
Vim is installing :O
 
10:55 PM
Had to downvote because, while the comic is funny, this isn't a very good answer to the question. — DampeS8N May 2 '11 at 13:52
 
"Happy Vimming!" LOL
 
@RMartinhoFernandes I think the physics reasoning is fundamentally unsound
 
^ someone is clearly on the wrong site. Shall I point him to 'meta.stackoverflow.com'?
 
the excess heat is vented … into the planet that is destroyed
that’s the whole point, no?
 
@KonradRudolph Yeah, I do mention that it's most likely that they were built to impress chicks.
 
10:56 PM
if there would be an excess of 10^35 Joules then they could just generate less force to begin with …
yup
 
Thanks guys, I feel appreciated now my answer has been read by at least 2 people :) (@KonradRudolph, @GManNickG)
 
Mmmmh... where is the function to auto-indent? xD
 
And on that note, I'm off to bed.
@unNaturhal gg=G (basically, = in normal or ex mode)
 
farewell
 
@sehe Oh yeah, clear... xD
 
10:58 PM
So you can select a region and press =, or you can enter command line and indent all: :%=
 
Hmm, either my concepts are broken or clang doesn't like Boost.Concept.
 
good night y’all
 
Sleep well
 
Good night.
 
@sehe All it's lost...
 
11:00 PM
@unNaturhal undo is u (or :undo, or :e! or :earlier 1 minute (which is roughly 10g-) etc)
 
> fatal error: unable to execute command: Segmentation fault
Damn.
 
@RMartinhoFernandes I've seen that earlier today. What code?
 
Different code.
 
@sehe Mmmmh... I haven't understood how to use a command... Like a shortcut?
 
@RMartinhoFernandes I figured. But what?
@unNaturhal Like a keyboard key. Always keyboard. Vim loves keys.
 
11:02 PM
@sehe Tests for a generic overloaded function object.
 
@RMartinhoFernandes strace -f clang++ test.cpp -v worked quite nicely to see what clang++ was up to right before segfaulting (e.g. you could see what the lexer/parser just read)
 
@sehe I have an italian keyboard, maybe it's the problem?
 
@unNaturhal Depends on what the symptoms are... (<whistle/>)
Do you have any experience with vi/vim?
 
@sehe I'll try that later. Right now I just #ifdefed that out. I want to see how much of the code is unpleasant to clang. If it's too much, I'll file bugs and stick to GCC some more.
 
I mean, if you're going to use it as a newbie just for 'easy indenting' I'm quite positive that you'll find command line invocation of htmltidy a lot easier to get started
@RMartinhoFernandes makes sense.
 
11:04 PM
@sehe Of course no...
 
7 mins ago, by sehe
And on that note, I'm off to bed.
See you
@unNaturhal See above. Perhaps give yourself a fair shot with vimtutor
2
Q: How to run vimtutor on windows?

Eric WilsonI'm running vim on Windows 7. It works, but when I type vimtutor on the command line, a window opens and closes immediately, and nothing else happens. Is there a way to run vimtutor with Vim for Windows?

 
BAM, another segfault.
 
Ok, tutor works xD
 
11:13 PM
@unNaturhal Happy vimming!
Night
 
11:38 PM
I've been on tropes for 20 minutes, I can blame that one someone here right?
ah, it was @RMartinhoFernandes's answer that linked me to it.
 
@sehe Thanks xD
Good night people!
 
Night.
 
@MooingDuck What? No, my answer only links to Irregular Webcomic!
 
@RMartinhoFernandes hmm, I clicked buttons. I followed your answer to scifi.stackexchange.com/questions/1458/…, which has a comment that links to tropes. I still blame you.
I'm trying to think of how far I have to modify/rework a quick-sort to be able to do it iteratively, in O(1) space
 
11:49 PM
Argh, clang still not usable. GCC it is.
 

« first day (558 days earlier)      last day (4391 days later) »