Эффективный расчет медианы для небольшого набора данных в переполнении стека
У меня есть много (сотни тысяч, м) наборов парных чисел d, ~ 5-10 (n, постоянный маленький) долго. Эти двойники в основном случайным образом распределены. Мне нужно получить медиану каждого набора: поскольку m очень велико, нам нужно довольно быстро рассчитать медиану … хотя эти наборы довольно малы, поэтому я думаю, что это сыграет важную роль в выборе того, как делать медиана Я знаю, что могу использовать nth_element получить медиану в O (n) с помощью алгоритма выбора, который, я знаю, я не собираюсь бить по сложности. Однако из-за небольшой константы n я, вероятно, ищу метод, который просто имеет наименьшие издержки.
Я нашел кучу разных способов сделать медиану (ниже), но я просто любопытен, если кто-нибудь знает «правильный» метод для использования здесь.
Мин макс кучи (O (n) время сборки, постоянный доступ, вероятно, слишком много накладных расходов)
Этот вопрос с 2010 года Что может быть устаревшим (новый код STL / Boost, возможно, уже реализует этот материал), также фокусируется больше на сложности времени, чем на накладных расходах.
Решение
Это может не соответствовать вашим размерам данных, но это фрагмент кода, который я нашел (не могу вспомнить где) и использую в своих функциях обработки изображений, чтобы получить медиану из 9 знаков без знака.
// optimised median search on 9 values
#define PIX_SWAP(a, b) { unsigned char uTemp = (a); (a) = (b); (b) = uTemp; }
#define PIX_SORT(a, b) { if ((a) > (b)) PIX_SWAP((a), (b)); }
unsigned char GetMedian9(unsigned char *pNine)
{
// nb - this is theoretically the fastest way to get the median of 9 values
PIX_SORT(pNine[1], pNine[2]); PIX_SORT(pNine[4], pNine[5]); PIX_SORT(pNine[7], pNine[8]);
PIX_SORT(pNine[0], pNine[1]); PIX_SORT(pNine[3], pNine[4]); PIX_SORT(pNine[6], pNine[7]);
PIX_SORT(pNine[1], pNine[2]); PIX_SORT(pNine[4], pNine[5]); PIX_SORT(pNine[7], pNine[8]);
PIX_SORT(pNine[0], pNine[3]); PIX_SORT(pNine[5], pNine[8]); PIX_SORT(pNine[4], pNine[7]);
PIX_SORT(pNine[3], pNine[6]); PIX_SORT(pNine[1], pNine[4]); PIX_SORT(pNine[2], pNine[5]);
PIX_SORT(pNine[4], pNine[7]); PIX_SORT(pNine[4], pNine[2]); PIX_SORT(pNine[6], pNine[4]);
PIX_SORT(pNine[4], pNine[2]); return(pNine[4]);
}
#undef PIX_SWAP
#undef PIX_SORT
РЕДАКТИРОВАТЬ — Хорошо, это также упоминается и в этом ответе
Другие решения
если это std :: set (вы не ответили на BoBTFish), то он уже отсортирован. Следовательно, вы получите медиану путем итерации до n / 2, которая всегда лучше или равна O (n), обычно это должно быть O (ld n). n-й элемент тут не поможет.