Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более |
Здравствуйте, гость ( Вход | Регистрация )
Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более |
ViGOur |
21.8.2010, 17:39
Сообщение
#1
|
Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40 |
Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей? |
|
|
cross |
27.1.2012, 11:46
Сообщение
#2
|
Новичок Группа: Новичок Сообщений: 2 Регистрация: 24.6.2010 Пользователь №: 1833 Спасибо сказали: 0 раз(а) Репутация: 0 |
Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации. Согласен (о чем и писал ранее в соседней теме про эту задачу). Единственный линейный алгоритм, который мне видится, это если значение элементов лежит в интервале от 0 до Х (где Х не велико и нам хватает памяти) заводим массив из Х элементов, в котором индекс - это величина элемента в исходном множестве, а значение - число появлений этого элемента в исходном множестве. За один проход пересчитываем все элементы и берем нужное количество минимальных. |
|
|
Текстовая версия | Сейчас: 29.3.2024, 1:03 |