Ответ 1

Я проверил следующие строки ввода 28311552. Это в 10 раз быстрее, чем ваш код. То, что он делает, читает большой блок сразу, затем заканчивается до следующей новой строки. Цель здесь заключается в сокращении затрат ввода-вывода, поскольку scanf() считывает символ за раз. Даже при использовании stdio буфер, вероятно, слишком мал.

Как только блок готов, я анализирую числа непосредственно в памяти.

Это не самый элегантный из кодов, и у меня могут быть некоторые крайние случаи, но это достаточно для того, чтобы вы начали с более быстрого подхода.

Вот тайминги (без оптимизатора мое решение только примерно в 6-7 раз быстрее, чем исходная ссылка)

[xavier:~/tmp] dalke% g++ -O3 my_solution.cpp
[xavier:~/tmp] dalke% time ./a.out < c.dat
15728647
0.284u 0.057s 0:00.39 84.6% 0+0k 0+1io 0pf+0w
[xavier:~/tmp] dalke% g++ -O3 your_solution.cpp
[xavier:~/tmp] dalke% time ./a.out < c.dat
15728647
3.585u 0.087s 0:03.72 98.3% 0+0k 0+0io 0pf+0w

Здесь код.

#include <iostream>
#include <stdio.h>
using namespace std;

const int BUFFER_SIZE=400000;
const int EXTRA=30;  // well over the size of an integer 

void read_to_newline(char *buffer) {
  int c;
  while (1) {
    c = getc_unlocked(stdin);
    if (c == '\n' || c == EOF) {
      *buffer = '\0';
      return;
    }
    *buffer++ = c;
  }
} 

int main() {
  char buffer[BUFFER_SIZE+EXTRA];
  char *end_buffer;
  char *startptr, *endptr;

  //n is number of integers to perform calculation on
  //k is the divisor
  //inputnum is the number to be divided by k
  //total is the total number of inputnums divisible by k

  int n,k,inputnum,total,nbytes;

  //initialize total to zero
  total=0;

  //read in n and k from stdin
  read_to_newline(buffer);
  sscanf(buffer, "%i%i",&n,&k);

  while (1) {
    // Read a large block of values
    // There should be one integer per line, with nothing else.
    // This might truncate an integer!
    nbytes = fread(buffer, 1, BUFFER_SIZE, stdin);
    if (nbytes == 0) {
      cerr << "Reached end of file too early" << endl;
      break;
    }
    // Make sure I read to the next newline.
    read_to_newline(buffer+nbytes);

    startptr = buffer;
    while (n>0) {
      inputnum = 0;
      // I had used strtol but that was too slow
      //   inputnum = strtol(startptr, &endptr, 10);
      // Instead, parse the integers myself.
      endptr = startptr;
      while (*endptr >= '0') {
        inputnum = inputnum * 10 + *endptr - '0';
        endptr++;
      }
      // *endptr might be a '\n' or '\0'

      // Might occur with the last field
      if (startptr == endptr) {
        break;
      }
      // skip the newline; go to the
      // first digit of the next number.
      if (*endptr == '\n') {
        endptr++;
      }
      // Test if this is a factor
      if (inputnum % k==0) total += 1;

      // Advance to the next number
      startptr = endptr;

      // Reduce the count by one
      n--;
    }
    // Either we are done, or we need new data
    if (n==0) {
      break;
    }
  }

 // output value of total
 printf("%i\n",total);
 return 0;
}

О, и он очень полагает, что входные данные находятся в правильном формате.

Ответ 2

Скорость не определяется вычислением - большая часть времени, затрачиваемого программой на выполнение, потребляется i/o.

Добавьте setvbuf вызовы перед первым scanf для значительного улучшения:

setvbuf(stdin, NULL, _IOFBF, 32768);
setvbuf(stdout, NULL, _IOFBF, 32768);

- изменить -

Предполагаемые магические числа - это новый размер буфера. По умолчанию FILE использует буфер размером 512 байт. Увеличение этого размера уменьшает количество раз, которое библиотека времени выполнения С++ должна выдавать вызов для чтения или записи в операционную систему, что, безусловно, является самой дорогостоящей операцией в вашем алгоритме.

Сохраняя размер буфера кратным 512, это устраняет фрагментацию буфера. Независимо от того, должен ли быть размер 1024*10 или 1024*1024, зависит от системы, для которой он предназначен. Для 16-разрядных систем размер буфера, превышающий 32 КБ или 64 КБ, обычно создает трудности при распределении буфера и, возможно, его управлении. Для любой более крупной системы сделайте ее максимально полезной - в зависимости от доступной памяти и от чего еще она будет конкурировать.

Отсутствие какой-либо известной конкуренции в области памяти, выберите размеры буферов примерно в размере связанных файлов. То есть, если входной файл равен 250 КБ, используйте его как размер буфера. При увеличении размера буфера уменьшается убывание. Для примера 250K буфер 100K потребует трех чтений, в то время как по умолчанию 512-байтовый буфер требует 500 считываний. Дальнейшее увеличение размера буфера, поэтому требуется только одно чтение, вряд ли сделает значительное улучшение производительности более чем на три чтения.

Ответ 3

попробуйте заменить if с помощью count += ((n%k)==0);. что может немного помочь.

но я думаю, вам действительно нужно буферизовать ваш вход во временный массив. чтение одного целого из ввода за раз дорого. если вы можете разделить сбор данных и обработку данных, компилятор может генерировать оптимизированный код для математических операций.

Ответ 4

Операции ввода-вывода являются узким местом. Попытайтесь ограничить их, когда сможете, например, загрузите все данные в буфер или массив с буферизованным потоком за один шаг.

Хотя ваш пример настолько прост, что я почти не вижу того, что вы можете устранить, считая его частью вопроса для последующего чтения из stdin.

Несколько комментариев к коду: ваш пример не использует никаких потоков - не нужно включать заголовок iostream. Вы уже загружаете элементы библиотеки C в глобальное пространство имен, включая stdio.h вместо С++ версии заголовка cstdio, поэтому использование пространства имен не требуется.

Ответ 5

Вы можете прочитать каждую строку с помощью gets() и самостоятельно проанализировать строки без scanf(). (Обычно я бы не рекомендовал get(), но в этом случае ввод корректно задан.)

Пример программы C для решения этой проблемы:

#include <stdio.h>
int main() {
   int n,k,in,tot=0,i;
   char s[1024];
   gets(s);
   sscanf(s,"%d %d",&n,&k);
   while(n--) {
      gets(s);
      in=s[0]-'0';
      for(i=1; s[i]!=0; i++) {
        in=in*10 + s[i]-'0';   /* For each digit read, multiply the previous 
                                  value of in with 10 and add the current digit */
      }
      tot += in%k==0;          /* returns 1 if in%k is 0, 0 otherwise */
   }
   printf("%d\n",tot);
   return 0;
}

Эта программа примерно в 2,6 раза быстрее, чем решение, которое вы указали выше (на моей машине).

Ответ 6

Вы можете попытаться прочитать ввод строки за строкой и использовать atoi() для каждой строки ввода. Это должно быть немного быстрее, чем scanf, поскольку вы удаляете служебные данные "сканировать" в строке формата.

Ответ 7

Я думаю, что код в порядке. Я запустил его на своем компьютере менее чем за 0,3 секунды Я даже запускал его на гораздо больших входах менее чем за секунду.

Как вы его определяете?

Одна маленькая вещь, которую вы могли бы сделать, - удалить инструкцию if. начните с total = n, а затем внутри цикла:

total - = int ((input% k)/k + 1)//0, если делится, 1, если не

Ответ 8

Хотя я сомневаюсь, что CodeChef его примет, одна из возможностей - использовать несколько потоков, один для обработки ввода-вывода и другой для обработки данных. Это особенно эффективно для многоядерного процессора, но может помочь даже с одним ядром. Например, в Windows вы кодируете код, подобный этому (никакой реальной попытки соответствовать требованиям CodeChef - я сомневаюсь, что они согласятся с данными синхронизации на выходе):

#include <windows.h>
#include <process.h>
#include <iostream>
#include <time.h>
#include "queue.hpp"

namespace jvc = JVC_thread_queue;

struct buffer { 
    static const int initial_size = 1024 * 1024;
    char buf[initial_size];
    size_t size;

    buffer() : size(initial_size) {}
};

jvc::queue<buffer *> outputs;

void read(HANDLE file) {
    // read data from specified file, put into buffers for processing.
    //
    char temp[32];
    int temp_len = 0;
    int i;

    buffer *b;
    DWORD read;

    do { 
        b = new buffer;

        // If we have a partial line from the previous buffer, copy it into this one.
        if (temp_len != 0)
            memcpy(b->buf, temp, temp_len);

        // Then fill the buffer with data.
        ReadFile(file, b->buf+temp_len, b->size-temp_len, &read, NULL);

        // Look for partial line at end of buffer.
        for (i=read; b->buf[i] != '\n'; --i)
            ;

        // copy partial line to holding area.
        memcpy(temp, b->buf+i, temp_len=read-i);

        // adjust size.
        b->size = i;

        // put buffer into queue for processing thread.
        // transfers ownership.
        outputs.add(b);
    } while (read != 0);
}

// A simplified istrstream that can only read int's.
class num_reader { 
    buffer &b;
    char *pos;
    char *end;
public:
    num_reader(buffer *buf) : b(*buf), pos(b.buf), end(pos+b.size) {}

    num_reader &operator>>(int &value){ 
        int v = 0;

        // skip leading "stuff" up to the first digit.
        while ((pos < end) && !isdigit(*pos))
            ++pos;

        // read digits, create value from them.
        while ((pos < end) && isdigit(*pos)) {
            v = 10 * v + *pos-'0';
            ++pos;
        }
        value = v;
        return *this;
    }

    // return stream status -- only whether we're at end
    operator bool() { return pos < end; }
};

int result;

unsigned __stdcall processing_thread(void *) {
    int value;
    int n, k;
    int count = 0;

    // Read first buffer: n & k followed by values.
    buffer *b = outputs.pop();
    num_reader input(b);
    input >> n;
    input >> k;
    while (input >> value && ++count < n) 
        result += ((value %k ) == 0);

    // Ownership was transferred -- delete buffer when finished.
    delete b;

    // Then read subsequent buffers:
    while ((b=outputs.pop()) && (b->size != 0)) {
        num_reader input(b);
        while (input >> value && ++count < n)
            result += ((value %k) == 0);

        // Ownership was transferred -- delete buffer when finished.
        delete b;
    }
    return 0;
}

int main() { 
    HANDLE standard_input = GetStdHandle(STD_INPUT_HANDLE);
    HANDLE processor = (HANDLE)_beginthreadex(NULL, 0, processing_thread, NULL, 0, NULL);

    clock_t start = clock();
    read(standard_input);
    WaitForSingleObject(processor, INFINITE);
    clock_t finish = clock();

    std::cout << (float)(finish-start)/CLOCKS_PER_SEC << " Seconds.\n";
    std::cout << result;
    return 0;
}

В этом случае используется класс потокобезопасной очереди, который я написал несколько лет назад:

#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

namespace JVC_thread_queue { 
template<class T, unsigned max = 256>
class queue { 
    HANDLE space_avail; // at least one slot empty
    HANDLE data_avail;  // at least one slot full
    CRITICAL_SECTION mutex; // protect buffer, in_pos, out_pos

    T buffer[max];
    long in_pos, out_pos;
public:
    queue() : in_pos(0), out_pos(0) { 
        space_avail = CreateSemaphore(NULL, max, max, NULL);
        data_avail = CreateSemaphore(NULL, 0, max, NULL);
        InitializeCriticalSection(&mutex);
    }

    void add(T data) { 
        WaitForSingleObject(space_avail, INFINITE);       
        EnterCriticalSection(&mutex);
        buffer[in_pos] = data;
        in_pos = (in_pos + 1) % max;
        LeaveCriticalSection(&mutex);
        ReleaseSemaphore(data_avail, 1, NULL);
    }

    T pop() { 
        WaitForSingleObject(data_avail,INFINITE);
        EnterCriticalSection(&mutex);
        T retval = buffer[out_pos];
        out_pos = (out_pos + 1) % max;
        LeaveCriticalSection(&mutex);
        ReleaseSemaphore(space_avail, 1, NULL);
        return retval;
    }

    ~queue() { 
        DeleteCriticalSection(&mutex);
        CloseHandle(data_avail);
        CloseHandle(space_avail);
    }
};
}

#endif

Точно, сколько вы выиграете от этого, зависит от количества времени, затраченного на чтение, и количества времени, затраченного на другую обработку. В этом случае другая обработка достаточно тривиальна, что, вероятно, не сильно выигрывает. Если больше времени потрачено на обработку данных, многопоточность, вероятно, увеличится.

Ответ 9

2,5 МБ/с - 400 нс/байт.

Существует два больших процесса в байтах, ввод файлов и разбор.

Для ввода файла я просто загрузил его в большой буфер памяти. fread должен иметь возможность прочитать это при примерно полной ширине диска.

Для синтаксического анализа sscanf создается для общности, а не для скорости. atoi должен быть довольно быстрым. Моя привычка, к лучшему или худшему, состоит в том, чтобы сделать это сама, как в:

#define DIGIT(c)((c)>='0' && (c) <= '9')
bool parsInt(char* &p, int& num){
  while(*p && *p <= ' ') p++; // scan over whitespace
  if (!DIGIT(*p)) return false;
  num = 0;
  while(DIGIT(*p)){
    num = num * 10 + (*p++ - '0');
  }
  return true;
}

Петли, сначала над ведущими пробелами, затем над цифрами, должны быть почти такими же быстрыми, как машина может идти, конечно, намного меньше 400 нс/байт.

Ответ 10

Деление двух больших чисел тяжело. Возможно, улучшение должно было бы сначала охарактеризовать k немного, посмотрев на некоторые из меньших простых чисел. Скажем, 2, 3 и 5. Если k делится на любой из них, то inputnum также должен быть или inputnum не делится на k. Конечно, есть больше трюков для игры (вы можете использовать побитовое и inputnum для 1, чтобы определить, делитесь ли вы на 2), но я думаю, что просто удаление низких простых возможностей даст разумное повышение скорости (в любом случае это стоит того).