Блог пользователя Squire

Автор Squire, 12 лет назад, По-русски

Всем привет :) Ребята, нужна помощь. В задаче количество чисел, которые нужно считать, неизвестно, потому считывать надо до конца входного потока. Есть метод следующий: while (cin >> n) { ... } Но при количестве чисел 10^9 такое считывание, конечно, не есть оптимальным. Нужно что-то со "scanf()" или в этом роде, что является более быстрым. Есть идеи?

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

while(scanf("%d",&x) != -1)

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

while (scanf("%d",&n) != EOF){ ... } является более быстрым. Но при количестве чисел 10^9 ???

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

sync_with_stdio(false)

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

10^9 чисел считать вы за сколько времени хотите? Как я знаю, за секунду можно считать только около 10^7 чисел.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    лично я хочу их считать как-то приблизительно за 4 секунды.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Вам вряд ли минуты хватит.
      **UPD.** Только что поэкспериментировал, через printf и scanf на моем ноуте 107 чисел вывело за 7.41 сек, ввело за 5.6

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Сейчас готовлюсь к университетской олимпиаде, в задаче нужно считать в худшем случае 10^9 элементов и вывести отсортированную последовательность, числа в диапазоне int'a. Вложился в 5 позволенных секунд. Не пойму, почему у Вас так долго ).

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +7 Проголосовать: не нравится

          То есть там нужно ввести 109 чисел, отсортировать их и вывести? Вы там на суперкомпьютерах работаете что-ли?) За 5 секунд это невозможно в принципе. 109 девятизначных чисел — 9 Гб на каждый тест. Видимо вы неправильно оценили худший случай.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится -6 Проголосовать: не нравится

            Во-первых, мне просто нужно считать числа с потока. И там не может быть 9-значных чисел, все они в диапазоне типа int. Если не верите - http://olymp.franko.lviv.ua/cgi-bin/new-register?contest_id=8&locale_id=0 задача А.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +11 Проголосовать: не нравится

              А кто сказал, что девятизначные числа не влазят в int? В большинстве компиляторов int 32-битный.
              А по ссылке ничего нету, надо регистрироваться. Киньте лучше само условие.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Зарегистрироваться там можно быстре, чем где-нибудь ))). Но раз уж Вы так просите — пожалуйста ) 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 Жаль, но не могу посмотреть время, за которое работала моя программа.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

                  Больше похоже на опечатку в условии. Попробуйте сами, например, просто вывести в файл 109 единичек через пробел. А потом засеките, за сколько программа всю эту радость считает оттуда. Или даже не через файл, а for (int i=0;i<1000000000;++i) sscanf("1","%d",&x);
                  Какой-нибудь fread будет работать быстрее, чем scanf, но 9 Гб он за 5 секунд тоже не прочитает.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится

                  Да, Вы правы. Это очень долго. В принципе я и сам думал, что уж если процессор исполняет приблизительно 10^9 операций за секунду, то моя программа действительно будет работать дольше. Наверное, виной всему опечатка в условии).

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Попробуйте буфер размера >50-100 Мб и вручную парсить числа. Но 10^9 чисел — это все-таки много, минимум секунд 20 читать надо.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    а что значит "парсить вручную"?

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      Считываешь fread'ом блок из потока, дальше из строки руками получаешь числа. Что-то похожее на это: http://pastie.org/3774850

      Но это всё равно нереально. 10^9 чисел = почти 9 гигов данных. Даже если у вас есть идеальный жёсткий диск, подключенный по SATA 3.0, это же всего 6 гигабит, то есть 9*8/6 = 12 секунд минимум.

      Плюс мы только один фактор учли, в реальной жизни это будет ещё хуже. Плюс это почти 10^10 сложений, что тоже никак в 5 секунд не уложится. Шляпа :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Возможно, Вы правы. Только что сам попробовал просто вывести 10^9 единичек в файл, работало больше, чем минута. Соглашусь, если просто опечатка в условии.