this link पर निर्दिष्ट कोडिंग प्रतियोगिता में एक ऐसा कार्य है जहां आपको stdin पर अधिक डेटा पढ़ने की आवश्यकता है, कुछ गणना करें और stdout पर एक बहुत सारे डेटा प्रस्तुत करें।सी में फास्ट I/O, stdin/out
मेरी बेंचमार्किंग में यह लगभग केवल I/o है जो समय लगता है हालांकि मैंने जितना संभव हो इसे अनुकूलित करने का प्रयास किया है।
आपके पास इनपुट के रूप में क्या है एक स्ट्रिंग (1 <= len <= 100'000) और int की जोड़ी की क्यू पंक्तियां जहां q भी 1 <= q <= 100'000 है।
मैं एक 100 गुना बड़ा डाटासेट पर अपने कोड बेंचमार्क (लेन = 10M, q = 10M) और इस परिणाम है:
Activity time accumulated
Read text: 0.004 0.004
Read numbers: 0.146 0.150
Parse numbers: 0.200 0.350
Calc answers: 0.001 0.351
Format output: 0.037 0.388
Print output: 0.143 0.531
मेरे अपने formating और संख्या को पार्स इनलाइन को लागू करने से मैं पाने में कामयाब रहे printf और scanf का उपयोग करते समय समय के 1/3 तक समय।
हालांकि जब मैंने प्रतियोगिताओं के वेबपृष्ठ पर अपना समाधान अपलोड किया तो मेरे समाधान में 1.88 सेकंड (मुझे लगता है कि 22 डेटासेट्स का कुल समय है)। जब मैं उच्च स्कोर में देखता हूं तो कई कार्यान्वयन (सी ++ में) होते हैं जो 0.05 सेकेंड में समाप्त होते हैं, मेरी तुलना में लगभग 40 गुना तेज! वो कैसे संभव है?
मुझे लगता है कि मैं इसे 2 धागे का उपयोग करके थोड़ा सा गति दे सकता हूं, फिर भी मैं stdin से पढ़ते समय गणना और लिखना शुरू कर सकता हूं। हालांकि यह मेरे बड़े डेटासेट पर सैद्धांतिक सर्वोत्तम मामले में min(0.150, 0.143) के समय को कम करेगा। मैं अभी भी हाईस्कॉर के करीब कहीं नहीं हूं ..
नीचे दी गई छवि में आप उपभोग किए गए समय के आंकड़े देख सकते हैं।
कार्यक्रम इस विकल्प के साथ वेबसाइट द्वारा संकलित हो जाता है:
gcc -g -O2 -std=gnu99 -static my_file.c -lm
और इस तरह समय समाप्त हो गया:
time ./a.out <sample.in> sample.out
मेरे कोड इस तरह दिखता है:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN (100000 + 1)
#define ROW_LEN (6 + 1)
#define DOUBLE_ROW_LEN (2*ROW_LEN)
int main(int argc, char *argv[])
{
int ret = 1;
// Set custom buffers for stdin and out
char stdout_buf[16384];
setvbuf(stdout, stdout_buf, _IOFBF, 16384);
char stdin_buf[16384];
setvbuf(stdin, stdin_buf, _IOFBF, 16384);
// Read stdin to buffer
char *buf = malloc(MAX_LEN);
if (!buf) {
printf("Failed to allocate buffer");
return 1;
}
if (!fgets(buf, MAX_LEN, stdin))
goto EXIT_A;
// Get the num tests
int m ;
scanf("%d\n", &m);
char *num_buf = malloc(DOUBLE_ROW_LEN);
if (!num_buf) {
printf("Failed to allocate num_buffer");
goto EXIT_A;
}
int *nn;
int *start = calloc(m, sizeof(int));
int *stop = calloc(m, sizeof(int));
int *staptr = start;
int *stpptr = stop;
char *cptr;
for(int i=0; i<m; i++) {
fgets(num_buf, DOUBLE_ROW_LEN, stdin);
nn = staptr++;
cptr = num_buf-1;
while(*(++cptr) > '\n') {
if (*cptr == ' ')
nn = stpptr++;
else
*nn = *nn*10 + *cptr-'0';
}
}
// Count for each test
char *buf_end = strchr(buf, '\0');
int len, shift;
char outbuf[ROW_LEN];
char *ptr_l, *ptr_r, *out;
for(int i=0; i<m; i++) {
ptr_l = buf + start[i];
ptr_r = buf + stop[i];
while(ptr_r < buf_end && *ptr_l == *ptr_r) {
++ptr_l;
++ptr_r;
}
// Print length of same sequence
shift = len = (int)(ptr_l - (buf + start[i]));
out = outbuf;
do {
out++;
shift /= 10;
} while (shift);
*out = '\0';
do {
*(--out) = ""[len%10];
len /= 10;
} while(len);
puts(outbuf);
}
ret = 0;
free(start);
free(stop);
EXIT_A:
free(buf);
return ret;
}
आप अलग-अलग चींटियों के लिए स्मृति आवंटित क्यों कर रहे हैं? आप किस प्रणाली पर हैं? लिनक्स पर, विंडोज़ पर स्टडीओ तेजी से (और विंडोज़ पर आईस्ट्रीम की तुलना में तेज) है, विंडोज़ पर, आईओस्ट्रीम stdio outpeforms। आईओ फंक्शंस के अनलॉक वेरिएंट्स (puts_unlocked के बजाय puts ,unlocked) का उपयोग करके stdio को कुछ हद तक तेज बनाया जा सकता है क्योंकि POSIX को कॉल के लिए रिकर्सिव लॉक का उपयोग करने के लिए stdio की आवश्यकता होती है, जबकि iostream (AFAIK) के लिए ऐसी कोई आवश्यकता मौजूद नहीं है। – PSkocik
ऐसा लगता है कि आप प्रत्येक बार लूप के माध्यम से आउटपुट कर रहे हैं। क्या आपने गति के लिए स्मृति का व्यापार किया है, एक बड़ा बफर आवंटित किया है, और फिर पूरे आउटपुट को एक बार में मुद्रित किया है? या, यदि इसके लिए व्यवहार्य होने के लिए बहुत अधिक उत्पादन है, तो आप अभी भी बफरिंग के माध्यम से आउटपुट को समेकित कर सकते हैं। यदि समस्या 'वास्तव में * आपकी बाधा है तो यह समस्या हल करेगी। मुझे यकीन नहीं है कि आप उन समय पहुंचने के लिए कैसे माप रहे हैं। कहें, "प्रिंट आउटपुट" माप में सभी परिचालन शामिल हैं? –
माइनर: 'cptr = num_buf-1; 'अपरिभाषित व्यवहार है - हालांकि यह वांछित के रूप में" काम करता है "। – chux