Всем привет :) Ребята, нужна помощь. В задаче количество чисел, которые нужно считать, неизвестно, потому считывать надо до конца входного потока. Есть метод следующий: while (cin >> n) { ... } Но при количестве чисел 10^9 такое считывание, конечно, не есть оптимальным. Нужно что-то со "scanf()" или в этом роде, что является более быстрым. Есть идеи?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
14:26:03
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
14:26:03
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 03:08:57 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
while(scanf("%d",&x) != -1)большое спасибо ;)
while (scanf("%d",&n) != EOF){ ... } является более быстрым. Но при количестве чисел 10^9 ???
sync_with_stdio(false)
10^9 чисел считать вы за сколько времени хотите? Как я знаю, за секунду можно считать только около 10^7 чисел.
лично я хочу их считать как-то приблизительно за 4 секунды.
Вам вряд ли минуты хватит.
**UPD.** Только что поэкспериментировал, через printf и scanf на моем ноуте 107 чисел вывело за 7.41 сек, ввело за 5.6
Сейчас готовлюсь к университетской олимпиаде, в задаче нужно считать в худшем случае 10^9 элементов и вывести отсортированную последовательность, числа в диапазоне int'a. Вложился в 5 позволенных секунд. Не пойму, почему у Вас так долго ).
То есть там нужно ввести 109 чисел, отсортировать их и вывести? Вы там на суперкомпьютерах работаете что-ли?) За 5 секунд это невозможно в принципе. 109 девятизначных чисел — 9 Гб на каждый тест. Видимо вы неправильно оценили худший случай.
Во-первых, мне просто нужно считать числа с потока. И там не может быть 9-значных чисел, все они в диапазоне типа int. Если не верите - http://olymp.franko.lviv.ua/cgi-bin/new-register?contest_id=8&locale_id=0 задача А.
А кто сказал, что девятизначные числа не влазят в int? В большинстве компиляторов int 32-битный.
А по ссылке ничего нету, надо регистрироваться. Киньте лучше само условие.
Зарегистрироваться там можно быстре, чем где-нибудь ))). Но раз уж Вы так просите — пожалуйста ) A. Впорядкування
Time limit: 5 s Memory limit: 256 M Задано цілі числа a, b, c1, c2, ..., ck. Відомо, що всі a <= ci <= b, b-a < 500, 0 < k < 1000000001. Впорядкуйте послідовність {ci} за зростанням і виведіть її через пропуск, по двадцять чисел у рядку.
Приклад вхідних даних 0 300 297 95 136 59 98 6 276 172 127 110 182 113 275 133 125 289 183 80 277 160
Результат 6 59 80 95 98 110 113 125 127 133 136 160 172 182 183 275 276 277 289 297 Жаль, но не могу посмотреть время, за которое работала моя программа.
Больше похоже на опечатку в условии. Попробуйте сами, например, просто вывести в файл 109 единичек через пробел. А потом засеките, за сколько программа всю эту радость считает оттуда. Или даже не через файл, а
for (int i=0;i<1000000000;++i) sscanf("1","%d",&x);Какой-нибудь fread будет работать быстрее, чем scanf, но 9 Гб он за 5 секунд тоже не прочитает.
Да, Вы правы. Это очень долго. В принципе я и сам думал, что уж если процессор исполняет приблизительно 10^9 операций за секунду, то моя программа действительно будет работать дольше. Наверное, виной всему опечатка в условии).
Попробуйте буфер размера >50-100 Мб и вручную парсить числа. Но 10^9 чисел — это все-таки много, минимум секунд 20 читать надо.
а что значит "парсить вручную"?
Считываешь fread'ом блок из потока, дальше из строки руками получаешь числа. Что-то похожее на это: http://pastie.org/3774850
Но это всё равно нереально. 10^9 чисел = почти 9 гигов данных. Даже если у вас есть идеальный жёсткий диск, подключенный по SATA 3.0, это же всего 6 гигабит, то есть 9*8/6 = 12 секунд минимум.
Плюс мы только один фактор учли, в реальной жизни это будет ещё хуже. Плюс это почти 10^10 сложений, что тоже никак в 5 секунд не уложится. Шляпа :)
Возможно, Вы правы. Только что сам попробовал просто вывести 10^9 единичек в файл, работало больше, чем минута. Соглашусь, если просто опечатка в условии.