| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > посчитать медиану не держа весь массив в памяти |
| Автор: mrgloom 3.9.2012, 17:08 |
| возможно ли посчитать медиану не держа весь массив в памяти? |
| Автор: Akina 3.9.2012, 17:19 |
| Только для сортированного массива |
| Автор: Фантом 3.9.2012, 17:20 | ||
Нет. Такие фокусы только с разными средними проходят. |
| Автор: maxdiver 3.9.2012, 17:41 | ||
Да, но ведь существуют алгоритмы внешней сортировки, для которых не требуется загружать весь массив в оперативную память (а выгружая ненужные части массива во внешнюю память - например, на жесткий диск). Следовательно, можно надеяться на то, что существуют аналогичные алгоритмы внешнего нахождения медианы. |
| Автор: Akina 3.9.2012, 17:57 |
| Если можно привлечь внешнюю сортировку - то собсно задача-то решена... |
| Автор: Фантом 3.9.2012, 20:12 | ||
Это-то да, но тогда это стрельба из пушки по воробьям. |
| Автор: Pavia 3.9.2012, 20:42 |
| Существует множество алгоритмов поиска медианы. В том числе и без сортировки. |
| Автор: Akina 3.9.2012, 20:46 |
| Эммм... почему, если не секрет? ведь по сравнению с реальной сортировкой алгоритм будет значительно упрощён - нам не требуется получить сортированный массив, требуется только найти средний элемент (или пару), следовательно, начальные и конечные элементы можно никуда не записывать, а только подсчитывать их количество. Зримое улучшение можно искать, если о массиве что-то заранее известно наверняка (например, что он ограничен сверху и снизу, что распределение элементов равномерное или нормальное и т.п.). Добавлено через 4 минуты и 58 секунд Pavia, но они многопроходны. И на больших массивах всё равно дают те же O(N*logN). Но обычно работают хуже при высокой неравномерности распределения значений по диапазону. |
| Автор: Pavia 3.9.2012, 22:24 |
| Akina, Есть алгоритмы за O(n), для любого массива. Книга "Алгоритмы. Построение и анализ. Издание 2-е" |
| Автор: maxdiver 17.9.2012, 18:42 |
| Вот хорошая статья на тему внешнего поиска медиан: "External Selection" (Jop F. Sibeyn): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.9168&rep=rep1&type=pdf. Описаны рандомизированный и детерминированный алгоритмы, самый быстрый из которых - работает за N+o(N) операций чтения и o(N) операций записи. |
