Since she doesn't use anything clever to find the index of the rightmost-not-at-end, she could use doubly-linked list which would give O(1) reversal of sublist.
Also, she doesn't really need to keep all consecutive items of the same color, only the number of them, so she could merge consecutive items of same color and add their multiplicities.
Cool, as a further research, I think it may be good for GPU/SIMD. Because as a human you quickly see where is the boundary between groups, where to split. But our eyes are parallel to some degree, while computer needs to scan items one-by-one to find the boundary. But GPU is faster may do it in one call.
Glancing at the code it has three nested loops (two "while"s, and one "reverse" call), which makes it O(N^3) before optimizations.
She makes a very good point that an algorithm that has bad big-O behavior can be better for humans than an algorithm with better.
For instance, I found insertion sort to be the most effective at sorting papers when I was grading. . . at least, as long as the students bothered writing their names on their homework.
Since she doesn't use anything clever to find the index of the rightmost-not-at-end, she could use doubly-linked list which would give O(1) reversal of sublist.
Also, she doesn't really need to keep all consecutive items of the same color, only the number of them, so she could merge consecutive items of same color and add their multiplicities.
At least it's not O(n³).
Cool, as a further research, I think it may be good for GPU/SIMD. Because as a human you quickly see where is the boundary between groups, where to split. But our eyes are parallel to some degree, while computer needs to scan items one-by-one to find the boundary. But GPU is faster may do it in one call.
Glancing at the code it has three nested loops (two "while"s, and one "reverse" call), which makes it O(N^3) before optimizations.
She makes a very good point that an algorithm that has bad big-O behavior can be better for humans than an algorithm with better.
For instance, I found insertion sort to be the most effective at sorting papers when I was grading. . . at least, as long as the students bothered writing their names on their homework.
[dead]