Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более |
Здравствуйте, гость ( Вход | Регистрация )
Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более |
AD |
26.8.2010, 11:58
Сообщение
#51
|
Профессионал Группа: Участник Сообщений: 2003 Регистрация: 4.2.2008 Из: S-Petersburg Пользователь №: 84 Спасибо сказали: 70 раз(а) Репутация: 17 |
|
|
|
DEADHUNT |
26.8.2010, 12:02
Сообщение
#52
|
Активный участник Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: 2 |
Ну это уже оффтоп будет, но не является неотъемлемой частью! Не зря ведь это отдельной библиотекой поставляется! в C++0x стандарте описание языка C++ занимает 400 страниц, далее идёт описание стандартной библиотеки(STL) на 700+ страниц. Сообщение отредактировал DEADHUNT - 26.8.2010, 12:02 |
|
|
kwisp |
28.8.2010, 14:25
Сообщение
#53
|
астарожна ынтжинэр Группа: Участник Сообщений: 1404 Регистрация: 26.11.2008 Из: ТаганрогРодинаЧехова Пользователь №: 435 Спасибо сказали: 113 раз(а) Репутация: 23 |
nth_element() - не катит?
|
|
|
DEADHUNT |
28.8.2010, 16:00
Сообщение
#54
|
Активный участник Группа: Участник Сообщений: 430 Регистрация: 15.4.2009 Пользователь №: 686 Спасибо сказали: 26 раз(а) Репутация: 2 |
nth_element() - не катит? да кстати, всё реализовано в stl, сложность - линейная. и весь код тогда будет занимать одну строчку:
|
|
|
Алексей1153 |
28.8.2010, 16:16
Сообщение
#55
|
фрилансер Группа: Участник Сообщений: 2941 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: 34 |
Цитата сложность - линейная Цитата The nth_element algorithm partitions the sequence [First..Last) on the value referenced by Nth. All the elements less than or equal to the value are placed before value and all elements greater than value are placed after value in the sequence. The nonpredicate version of nth_element uses operator< for comparisons. а про сортировку ни слова Может, поэтому Сообщение отредактировал Алексей1153 - 28.8.2010, 16:18 |
|
|
ViGOur |
25.1.2012, 10:59
Сообщение
#56
|
Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40 |
Как и обещал, код:
Конструктивная критика приветствуется! |
|
|
panter_dsd |
25.1.2012, 11:41
Сообщение
#57
|
Жаждущий знаний Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: 3 |
1. rValue = ++n; - зачем в 2 строки делать?
2. std::vector<int> collMin( coll.begin(), coll.begin() + n); все же лучше. |
|
|
ViGOur |
25.1.2012, 11:46
Сообщение
#58
|
Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40 |
1. Кому как нравится.
2. Чем лучше? |
|
|
panter_dsd |
25.1.2012, 12:04
Сообщение
#59
|
Жаждущий знаний Группа: Участник Сообщений: 254 Регистрация: 1.1.2009 Из: Санкт-Петербург Пользователь №: 474 Спасибо сказали: 32 раз(а) Репутация: 3 |
1. Если хочется в 2 строки, то хотя бы префиксную версию инкремента юзай.
2. Избавляемся от лишнего заполнения нулями, плюс от else, который только путает. Сообщение отредактировал panter_dsd - 25.1.2012, 12:05 |
|
|
ViGOur |
25.1.2012, 12:42
Сообщение
#60
|
Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40 |
1. в данном случае точно разницы нет постфиксный инкремент или префиксный!
2. То, что избавляет от лишнего заполнения нолями, согласен. Но ИМХО мой вариант наглядней будет. Всё равно, можно сказать, что ты выиграл M процессорных тактов на заполнении нолями и столько же можно убрать из цикла! Но с другой стороны, это ведь подготовительная часть, и она нужна, чтобы не реализовывать ручками выделение памяти и её заполнение. Тоесть только для наглядности! |
|
|
Текстовая версия | Сейчас: 1.12.2024, 5:54 |