2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Быстрый поиск порядковой статистики
Сообщение15.07.2018, 06:24 
Здравствуйте. Возникла такая задача: из массива N действительных чисел найти k-е число упорядоченной последовательности.
Пока я применил брутальное решение, основанное на предварительной сортировке:
код: [ скачать ] [ спрятать ]
Используется синтаксис C
// ys - сортируемый массив
.....................................
const int Lag[9]={1, 4, 10, 23, 57, 132, 301, 701, 1750};
    int N=8, j, Lim;
    double val;
   
    if (nObs==1) return 0;
   
    while (Lag[N] >= nObs) N--;
       
    for (int ii=N; ii>=0; ii--)
    { Lim=Lag[ii];
      for (int pos=Lim; pos < nObs; pos++)
      {
        val=*(ys+pos);
        for (j=pos; j>=Lim; j-=Lim)
            if (val<*(ys+j-Lim))
                *(ys+j)=*(ys+j-Lim);
            else
                break;
           
        *(ys+j)=val;
      }
    }

val=*(ys+k);
........................
 


Однако есть подозрение, что можно сделать эффективнее, т.к. сортировка всех элементов массива не требуется.
Видел соответствующие адаптации алгоритма quksort, но они меня не очень впечатлили, т.к. в том виде, как они есть - весьма неустойчивы и могут деградировать до $O(N^2)$.
Хотелось бы обсудить, как это можно реализовать лучше, проще и эффективнее.

 
 
 
 Re: Быстрый поиск порядковой статистики
Сообщение15.07.2018, 07:48 
Может, пирамидальную? Первую стадию провести, вторую частично.
Если $k$ сравнительно маленькое, можно завести массив из $k$ элементов и одним проходом найти $k$ первых.

 
 
 
 Re: Быстрый поиск порядковой статистики
Сообщение15.07.2018, 16:35 
Например:
K’th Smallest/Largest Element in Unsorted Array
(На странице есть ссылки на предыдущие статьи серии.)

 
 
 
 Re: Быстрый поиск порядковой статистики
Сообщение15.07.2018, 16:37 
В STL есть готовая функция:
https://en.cppreference.com/w/cpp/algorithm/nth_element

 
 
 
 Re: Быстрый поиск порядковой статистики
Сообщение15.07.2018, 18:33 
Спасибо Yuri Gendelman, кажется хорошая штука! Сейчас буду разбираться.

 
 
 
 Re: Быстрый поиск порядковой статистики
Сообщение15.07.2018, 21:24 
Ознакомился, и чуда не произошло. Там описан алгоритм, работающий за линейное время. Но, как часто бывает, константа слишком велика, что делает его на практике неэффективным. Опять же резюмируют, что лучший вариант - quksort с рандомизацией.
Но рандомизация мне вообще говоря не нравится. Плюсы от её применения, на мой взгляд, иллюзорны. Ведь нет ни какой гарантии, что после её применения элементы массива не распределяться ещё хуже.

 
 
 
 Re: Быстрый поиск порядковой статистики
Сообщение15.07.2018, 22:20 
Гарантии нет, но они если и станут хуже, то скорее всего незначительно. Зато аномально часто встречающийся худший случай превратится в произвольный (не самый худший), что и даст в среднем выигрыш. Если все входные комбинации равновероятны, то рандомизация лишняя.
Для гарантий применяйте методы класса $O(n \log n)$ в худшем случае.

 
 
 
 Re: Быстрый поиск порядковой статистики
Сообщение15.07.2018, 22:26 
Вообще, хотелось бы просто улучшить мою исходную сортировку Шелла, она хоть и не $n\cdot log(n)$, но всё равно прилично. Смущает тот факт, что она полностью сортирует весь массив ...

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group