История изменений
Исправление shkolnick-kun, (текущая версия) :
Ты про кольцевой буфер забыл. С фиксированным размером еще попадаешь на копирование.
В таком случае можно попробовать:
Torben's method
This method was pointed it out to me by Torben Mogensen.
It is certainly not the fastest way of finding a median, but it has the very interesting property that it does not modify the input array when looking for the median. It becomes extremely powerful when the number of elements to consider starts to be large, and copying the input array may cause enormous overheads. For read-only input sets of several hundred megabytes in size, it is the solution of choice, also because it accesses elements sequentially and not randomly. Beware that it needs to read the array several times though: a first pass is only looking for min and max values, further passes go through the array and come out with the median in little more time that the pixel_qsort() method. The number of iterations is probably O(log(n)), although I have no demonstration of that fact.
Исправление shkolnick-kun, :
Ты про кольцевой буфер забыл. С фиксированным размером еще попадаешь на копирование.
В таком случае можно попробовать:
Torben's method
This method was pointed it out to me by Torben Mogensen.
It is certainly not the fastest way of finding a median, but it has the very interesting property that it does not modify the input array when looking for the median. It becomes extremely powerful when the number of elements to consider starts to be large, and copying the input array may cause enormous overheads. For read-only input sets of several hundred megabytes in size, it is the solution of choice, also because it accesses elements sequentially and not randomly. Beware that it needs to read the array several times though: a first pass is only looking for min and max values, further passes go through the array and come out with the median in little more time that the pixel_qsort() method. The number of iterations is probably O(log(n)), although I have no demonstration of that fact.
Исходная версия shkolnick-kun, :
Ты про кольцевой буфер забыл. С фиксированным размером еще попадаешь на копирование.