Быстрый ввод-вывод в c, stdin/out
В конкурсе кодирования, указанном в эта ссылка, есть задача, в которой вам нужно прочитать много данных на stdin, выполните некоторые вычисления и представите множество данных на stdout.
В моем бенчмаркинге это почти только i/o, который требует времени, хотя я попытался оптимизировать его как можно больше.
В качестве ввода вы вводите строку (1 <= len <= 100'000) и q строк пары int, где q также является 1 <= q <= 100'000.
Я сравнил свой код с 100-кратным набором данных (len = 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
При внедрении моего собственного форматирования и синтаксического анализа строк inline мне удалось сократить время до 1/3 времени при использовании printf и scanf.
Однако, когда я загрузил свое решение на веб-страницу конкурсов, мое решение заняло 1,88 секунды (я думаю, что это общее время более чем 22 наборов данных). Когда я смотрю в высоком баллате, есть несколько реализаций (в С++), которые закончились за 0,05 секунды, почти в 40 раз быстрее, чем у меня! Как это возможно?
Я предполагаю, что я мог бы немного ускорить его, используя 2 потока, затем я могу начать вычислять и писать в stdout, все еще читая 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) = "0123456789"[len%10];
len /= 10;
} while(len);
puts(outbuf);
}
ret = 0;
free(start);
free(stop);
EXIT_A:
free(buf);
return ret;
}
Ответы
Ответ 1
Благодаря вашему вопросу, я сам решил и решил проблему. Ваше время лучше, чем мое, но я все еще использую некоторые функции stdio.
Я просто не думаю, что высокий балл 0,05 секунды является добросовестным. Я подозреваю, что это продукт высокоавтоматизированной системы, которая вернула результат в ошибке и что никто ее не проверял.
Как защитить это утверждение? Там нет реальной алгоритмической сложности: проблема O (n). "Трюк" состоит в том, чтобы писать специализированные синтаксические анализаторы для каждого аспекта ввода (и избегать работы, выполняемой только в режиме отладки). Общее время для 22 испытаний составляет 50 миллисекунд, что означает, что каждое испытание составляет в среднем 2,25 мс? Мы приближаемся к пределу измеримости.
Соревнования, такие как проблема, к которой вы обращались, являются неудачными, в некотором роде. Они усиливают наивную идею о том, что производительность является конечной мерой программы (для ясности нет оценки). Хуже того, они поощряют обойти такие вещи, как scanf "для производительности", в то время как в реальной жизни, чтобы программа работала правильно и быстро, в принципе никогда не влечет за собой избежания или даже настройки stdio. В сложной системе производительность исходит из таких вещей, как отказ от ввода-вывода, передача данных только один раз и минимизация копий. Использование СУБД эффективно часто является ключевым (как бы), но такие вещи никогда не появляются в задачах программирования.
Разбор и форматирование чисел в тексте требует времени, и в редких случаях это может быть узким местом. Но ответа вряд ли стоит переписать парсер. Скорее, ответ состоит в том, чтобы проанализировать текст в удобной двоичной форме и использовать его. Короче: компиляция.
Тем не менее, несколько наблюдений могут помочь.
Вам не нужна динамическая память для этой проблемы, и это не помогает. В заявлении о проблеме говорится, что входной массив может составлять до 100 000 элементов, а количество испытаний может достигать 100 000. Каждое испытание представляет собой две целые строки длиной до 6 цифр, каждая из которых разделена пробелом и завершается символом новой строки: 6 + 1 + 6 + 1 = 14. Общий ввод, максимум 100 000 + 1 + 6 + 1 + 100 000 * 14: под 16 КБ. Вам разрешено использовать 1 ГБ памяти.
Я просто выделил один буфер размером 16 КБ и сразу прочитал его с помощью read (2). Затем я сделал один проход над этим входом.
У вас есть предложения по использованию асинхронных операций ввода-вывода и потоков. В заявлении о проблеме говорится, что вы измеряете время процессора, поэтому ни одна из них не помогает. Самое короткое расстояние между двумя точками - это прямая линия; одно считывание в статически выделенную память не переносит никакого движения.
Один нелепый аспект того, как они измеряют производительность, заключается в том, что они используют gcc -g. Это означает, что assert (3) вызывается в коде, который измеряется для производительности! Я не мог получить менее 4 секунд на тесте 22, пока не удалю мои утверждения.
В общем, вы неплохо справились, и я подозреваю, что победителем вы озадачены phantom. Ваш код немного задевает, и вы можете обойтись без динамической памяти и настройки stdio. Готов поспорить, ваше время можно урезать, упростив его. В той мере, в какой это имеет значение, что я буду направлять ваше внимание.
Ответ 2
Вы должны распределять все свои буферы непрерывно.
Выделите буфер, который является размером всех ваших буферов (num_buff, start, stop), затем перестройте точки на соответствующие смещения по их размеру.
Это может уменьшить ваши ошибки промаха в кеше\страницы.
Поскольку операция чтения и записи, похоже, требует много времени, вы должны рассмотреть возможность добавления потоков. Один поток должен иметь дело с I\O, а другой должен иметь дело с вычислением. (Стоит проверить, может ли другой поток для печати также ускорить процесс). Убедитесь, что вы не используете блокировки при этом.
Ответ 3
Ответ на этот вопрос сложный, потому что оптимизация в значительной степени зависит от вашей проблемы.
Одна из идей - посмотреть содержимое файла, который вы пытаетесь прочитать, и посмотреть, есть ли у вас шаблоны или вещи, которые вы можете использовать в свою пользу.
Код, который вы написали, является "общим" решением для чтения из файла, выполнения чего-то, а затем записи в файл. Но если вы не произвольно генерируете файл каждый раз, а контент всегда один и тот же, почему бы не попытаться написать решение для этого файла?
С другой стороны, вы можете попытаться использовать низкоуровневые системные функции. Один из моих соображений - mmap, который позволяет отображать файл непосредственно в память и получать доступ к этой памяти вместо использования scanf и fgets.
Еще одна вещь, которую я нашел, которая может помочь, заключается в том, что у вас есть два цикла while, почему бы не попробовать и использовать только один? Другое дело было бы сделать некоторое чтение асинхронного ввода-вывода, поэтому вместо того, чтобы читать весь файл в цикле, а затем делать вычисления в другом цикле, вы можете попробовать и прочитать часть в начале, начать обрабатывать ее async и продолжить чтение.
Эта ссылка может помочь для асинхронной части
