Оптимизация ввода-вывода в C ++

Question

У меня проблемы с оптимизацией программы на C ++ для максимально быстрого выполнения.

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

./myprogram < unkownfilenamefullofdata

Имя файла неизвестно и содержит 2 числа в строке, разделенных пробелом.Существует неизвестное количество тестовых данных.Я создал 2 файла тестовых данных.Один имеет крайние случаи и имеет 5 пробежек.Что касается другого, я использовал программу на Java для генерации 2 000 000 случайных чисел и выводил их в файл с временным запуском - тесты объемом 18 МБ.Мне нужно сократить это до 1,1 секунды.

Это мой код:

int main() {
long int a, b;
while (scanf("%li %li",&a,&b)>-1){
  if(b>=a)
    printf("%li/n",(b-a));
  else
    printf("%li/n",(a-b));
  } //endwhile
return 0;
}//end main

Я запустил Valgrind в своей программе, и это показало, что большая задержка была вчитать и писать часть.Как бы я переписал print / scan в самую простую форму C ++, если бы знал, что получу только номер?Есть ли способ, которым я могу сканировать число в виде двоичного числа и манипулировать данными с помощью логических операций, чтобы вычислить разницу?Мне также сказали подумать о создании буфера, но после ~ 6 часов поиска в Интернете и попыток написания кода я потерпел неудачу.

Любая помощь будет принята с благодарностью.

Answer 1

Что вам нужно сделать, это загрузить всю строку в память и затем извлечь из нее числа, а не делать повторные вызовы ввода / вывода.Однако вы можете обнаружить, что загрузка 18 МБ с жесткого диска просто занимает много времени.

Answer 2

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

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

Вы говорите, что 2 000 000 номеров занимают 18 МБ = 9 байтов на число. Это включает пробелы и маркеры конца строки, поэтому звучит разумно.

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

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

Я предполагаю, что это чрезвычайно упрощенная модель обработки, которую вам нужно сделать. Если ваше описание - это все, что нужно, реальным решением будет вычитание в программе, которая записывает тестовые файлы!

Answer 3

Вы можете значительно улучшить Scanf, потому что вы можете гарантировать формат вашего файла.Поскольку вы точно знаете, что это за формат, вам не нужно столько проверок на ошибки.Кроме того, printf выполняет преобразование новой строки в соответствующий разрыв строки для вашей платформы.

Я использовал код, подобный тому, который можно найти в этом сообщении SPOJ на форуме (см. Половину сообщения nosy).вниз по странице), чтобы получить довольно большие ускорения в области чтения целых чисел.Вам нужно будет изменить его, чтобы иметь дело с отрицательными числами.Надеюсь, что это даст вам некоторые идеи о том, как написать более быструю функцию printf, но я бы начал с замены scanf и посмотрел, как далеко вы зашли.

Answer 4

Даже лучше, чем открыть файл в вашей программе и прочитать все сразу, было бы сопоставление памяти. ~ 18 МБ не проблема для адресного пространства ~ 2 ГБ, доступного вашей программе.

Затем используйте strtod, чтобы прочитать число и переместить указатель.

Я бы ожидал 5-10-кратное ускорение по сравнению с перенаправлением ввода и scanf.