4 ms·
So, in effect, with word-wrapping on in the terminal, this scenario effectively produces a "Shlemiel the painter's algorithm" [0] in that for every character ou
by stygiansonic 10y ago
So, in effect, with word-wrapping on in the terminal, this scenario effectively produces a "Shlemiel the painter's algorithm" [0] in that for every character output on the same line (when it exceeds the line length), you have go backtracking in vain to find a place to break - where this is none - so outputting N characters on a line is basically an O(N^2) operation.
0. http://www.joelonsoftware.com/articles/fog0000000319.html http://www.joelonsoftware.com/articles/fog0000000319.html
- heywire 10y agoI wonder if this is also why the default terminal in Ubuntu slows to a crawl if you write a ~4kb long line (I was working on a program which was processing some SDR data, outputting 0/1 to the screen without any line breaks).
- mjevans 10y agoProbably that or some other case of selecting an algorithm without consideration of the /worst possible/ performance cases. It may be better to try a generally good algorithm first, then if it fails after X iterations to fall back to an algorithm with a better bound on the worst case.