Run length encoding

Wh开发者_C百科at is the best we can do with run length encoding.

This page suggests the time complexity is O(m*n) where m is the number of time the number repeats..

Is the a more efficient algorithm to do RLE?

I think you maybe mis-understood the runtime. The algorithm on the wikipedia page is O(n) (where n is the length of the input). Notice how the index is the same for both loops, and increasing.

As already stated the time complexity is O(n). More efficient algorithms use SIMD or CUDA to process more than one element at a time.

You might have a look at an efficient and fast implementation: TurboRLE:Run Length Encoding including SIMD. A benchmark program is also provided.