I'm doing a data structure programming assignment about stack in C++.
In this assignment, I should read lots of integers(in the worst case I should read 1,600,000 integers) and finally output some strings.
As a student, I submit my cpp source file and the website judges and scores my source code. I got 100% but I want to do better. The time restriction of this assignment is 2 seconds and the execution time of my source code is 128 milliseconds. However, the top student only used 52 milliseconds to complete the task. So I want to know how to make my code faster.
My source code mainly contains three parts:
- use cin to read lots of integers from the OnlineJudge system(up to 1,600,000 integers).
- try to find the solution and store it in a char array.
- use cout to output the char array.
OnlineJudge tells me the execution time of my code. The 1st part takes 100 milliseconds, the 2nd part takes 20 milliseconds, and the 3rd part takes 12 milliseconds. So if I want to make my code faster, I should improve input speed.
Input of OnlineJudge is like this:
5 2
1 2 3 5 4
The 1st line is two integers n and m, the 2nd line is n integers separated by spaces. Restrictions are: 1<=n<=1,600,000 and 0<=m<=1,600,000. In order to read more than 1 million integers, my code is like this:
#include <iostream>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
int *exit = new int[1600000];
cin>>n>>m;
for (int i=0;i<n;++i)
cin>>exit[i];
return 0;
}
If n is small, OnlineJudge says execution time is 0 milliseconds. if n is very large,e.g. 1,600,000. OnlineJudge says this code takes 100 milliseconds. If I delete
std::ios::sync_with_stdio(false);
cin.tie(NULL);
Then the code takes 424 milliseconds. However, reading integers is necessary in this assignment, so I'm really curious about how the top student can finish "cin,find the solution,cout" within only 52 milliseconds.
Do you have any ideas on improving input speed?
2019.4.17：Someone suggests using vector or std::from_chars, but in this assignment these are banned. If I write
#include <vector>
or
#include <charconv>
or
#include <array>
then OnlineJudge says "Compilation error".
Someone suggests using scanf, my code is like this:
for (int i=0;i<n;++i)
scanf("%d", &exit[i]);
But the execution time is 120 milliseconds.By the way, I don't think scanf is faster than cin, Using scanf() in C++ programs is faster than using cin?
Someone suggests using getline.I seldom uses this fuction,my code is like this:
stringstream ss;
string temp;
getline(cin, temp);
ss<<temp;ss>>n;ss>>m;
ss.clear();temp.clear();
getline(cin, temp);ss<<temp;
for (int i=0;i<n;++i)
ss>>exit[i];
Execution time is also 120 milliseconds.
Someone suggests using mmap. I've never heard this function before. It seems this function is only available in Unix? But I'm using Visual Studio 2010. My code is like this:
#include <unistd.h>
#include <sys/mman.h>
//to load 1,600,000 integers
int *exit = static_cast<int*>(mmap(NULL,1600*getpagesize(),PROT_READ,MAP_ANON|MAP_SHARED,0,0));
for (int i=0;i<n;++i)
cin>>*(exit+i);
OnlineJudge says "Runtime error (signal 11)" instead of "Compilation error", signal 11 means "Invalid memory reference", this signalis is sent to a process when it makes an invalid virtual memory reference, or segmentation fault, i.e. when it performs a segmentation violation. I don't know if there's anything wrong with my mmap.Hope you can tell me.
2019.4.22：Thanks for all your help.Now I solve this problem successfully.The key function is mmap.The code is like this:
#include <sys/mman.h>
cin.tie(NULL);
std::ios::sync_with_stdio(false);
string temp;
int n,m;
int *exit = new int[1600000];
const int input_size = 13000000;
void *mmap_void = mmap(0,input_size,PROT_READ,MAP_PRIVATE,0,0);
char *mmap_input = (char *)mmap_void;
int r=0,s=0;
while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
while (mmap_input[s]>='0' && mmap_input[s]<='9')
{ r=r*10+(mmap_input[s]-'0');++s; }
n=r;r=0;
while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
while (mmap_input[s]>='0' && mmap_input[s]<='9')
{ r=r*10+(mmap_input[s]-'0');++s; }
m=r;r=0;
while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
for (int i=0;i<n;++i)
{
while (mmap_input[s]>='0' && mmap_input[s]<='9')
{ r=r*10+(mmap_input[s]-'0');++s; }
++s;
exit[i]=r;r=0;
}
Execution time of mmap and convert chars to integers take 8 milliseconds. Now the total execution time of this homework take 40 milliseconds, faster than 52 milliseconds.
