gfx_sort1 takes way too long on big matrices

[vifino]

It should probably try to finish in a fixed time - or at least similar times - when running on a different matrix size.

On my X200's display, it takes a long time, probably over a minute.

[vifino]

Actually, it's not consistent there either, now it's been running for ~5 minutes.

[cyriax0]

That is to be expected.

The time for completion is highly dependent on display size. This is an inherent property of sorting algorithms.

Complexity of the algorithm

Bubblesort has a runtime of O(n^2) (see https://en.wikipedia.org/wiki/Bubble_sort#Performance). The runtime of that algorithm should be similar, although the complexity analysis is somewhat more complex as the data depenencies are spread over the 2D space.

For the simple variant where only diagonals are sorted the complexity on an AxB LED Matrix should be O(max(A,B)^2). The Complex variant might have longer path lengths between the starting position of a pixel and the final position, but the complexity class should still be similar.

The expected number of frames should should be different as O(AB) locations are considered per step. This should/could be measured but I expect something like omega(max(A,B)) and o(max(A,B)^2). frames. This is dependent on the maximal path length and stuff. Measuring should be doable as there exists already a framecounter.

Speedup Ideas

• Eliminate the random selection of places to invert. Currently only randomly selected 25% of the locations are touched. This would change the look of the effect a bit.
• Calculate multiple steps per frame. This assumes big displays are connected to big computers. If you're hitting a processing wall, this isn't an option.
• Deactive module for big outputs Some variations are deactivated for big outputs. Alternatively everything is deactivated when the output matrix is ''too big''.

Conclusion

Getting on or near a target number of frames isn't feasible right now as the runtime depends on sorting mode and I'm too lazy to measure for future predictions. You might manually adjust the framerate or deactivate the module.

[cyriax0]

It's not a bug. It's a feature/inherent property of the algorithm.

[vifino]

Sorry that I marked it as a bug, not an enhancement, my bad.

Yeah, I get it, I was thinking something like a frame limit, so it doesn't run for ages on big matrices and gives other modules a chance to run as well.

[orithena]

Another speedup idea: Scale a "sorting pixel" to multiple LEDs on higher resolutions; or, in other words, lower the resolution of the sorting matrix. E.g. 2x2 LEDs per "sorting pixel" on a 64x64 LED matrix, 3x3 on 96x96, 4x4 on 128x128 etc...