3

Вообщем написаны 2 программы на Delphi и на C++ , провожу абсолютно однотипные операции( считываю массив длинною 10 ^ 7) но почему то Delphi это делает на целую секунду быстрее, кто может ответить в чем причина? и как можно ускорить в C++ ввод и вывод данных?? alt text

Вот программы, на Си и на Delphi

#include <cstdio>
#include <iostream>

int n;
short a[10000000];

int main()
{
    freopen("output.txt", "r", stdin);
    freopen("input.txt", "w", stdout);

    scanf("%d\n", &n);
    for (int i = 0; i < n; i++)
        scanf("%hd", &a[i]);   
    printf("1");

    return 0;   
}

var n, i : integer;
      a : array[1..10000000] of shortInt;

begin
    reset(input, 'output.txt');
    rewrite(output, 'input.txt');

    ReadLn(n);
    for i := 1 to n do
      Read(a[i]);
    WriteLn('1');

    close(input);
    close(output);
end.  

Испытание 2. теперь первым выполняется exe - шник на c++ и в дельфи for заменен на while! все остальное то же.

alt text

    var n, i : integer;
      a : array[1..10000000] of Integer;

begin
    reset(input, 'output.txt');
    rewrite(output, 'input.txt');

    ReadLn(n);
    i := 1;
    while ( i <= n ) do
    begin
      Read(a[i]);
      inc(i);
    end;
    WriteLn('1');

    close(input);
    close(output);
end.
9
  • 2
    Сделайте на чистом Си и посмотрите результат. Думаю, он удивит еще больше. К тому же нельзя проводить опыты так, т.к. скажется буферизация файла операционной системой. Если дельфовая программа стартовала вторая - вот вам и "ускорение"
    – gecube
    24 дек 2012 в 10:21
  • на Си откомпилировал работает еще дольше, почти 3 секунды, почему так? я ожидал что будет быстрее 24 дек 2012 в 10:43
  • Может разница в том что C++ (сужу по JS не уверен) при каждой интеграции цикла проверяет условие а в Delphi число интераций заранее определено. Попробуйте (не будете же вы в C++ в исходном файле прописывать 10^7 вызовов ф-ций) использовать в Delphi проверяемые циклы например repeat...until while...do и скажите результат (мне тоже интересно :) )
    – Rules
    24 дек 2012 в 12:22
  • 3
    @Евгений536 А вы правда получаете удовольствие от бенчмарков бессмысленных последовательностей операций? 24 дек 2012 в 13:15
  • 2
    нет, я просто недавно писал олимпиаду и столкнулся с тем, что задача не прошла, когда я считывал таким образом cin >> a[i], то миллион чисел считывались дольше 2 секунд...! когда я изменил это на scanf("%d" &a[i]); то программа еле уложилась в секунду...! что очень меня удивило. Теперь задался вопросом как можно и это ускорить, ведь Delphi может быстрее и намного быстрее 24 дек 2012 в 13:19

5 ответов 5

13

Все очень просто. В случае с делфи, компилятор знает, что вызов Read будет читать число. И только его. И может вставить правильный код сразу.

В случае с scanf ситуация не столь проста. Как минимум каждый раз будет делаться парсинг строки формата. А это как не оптимизируй - медленно.

Что же делать?

  • писать свой парсер. Но как то не то.
  • использовать готовые парсеры, например boost.spririt
  • также, по ссылкам ниже, народ пишет, что если читать строку, а потом преобразовывать с помощью atoi, то получается в 4 раза быстрее.

полезные ссылки

3
  • Всем огромное спасибо, особенно teanЫЧ, немного да разобрался с этой проблемой, но больше всех ответов мне понравился у KoVadim! 24 дек 2012 в 13:30
  • @Евгений536, ну вы меня прямо в краску вогнали
    – teanЫЧ
    24 дек 2012 в 13:33
  • @Евгений536, это правильный ответ. Я тоже попробовал ускорить, смю в ответе 0.48 сек.
    – avp
    24 дек 2012 в 13:54
8

Хотите быстро? Тогда забудьте об "удобных" функциях во внутреннем цикле.

Вот, например

#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#define fatal(msg) ({fprintf(stderr,"%s: %m",(msg)); exit(-1);})

int n;
short a[10000000];

int
main (int ac, char *av[])
{
  int in = open ("output.txt", O_RDONLY);
  if (in == -1)
    fatal("open output.txt");

  //  freopen("input.txt", "w", stdout);

  struct stat st;
  fstat (in,&st);
  printf ("len = %ld\n",(long)st.st_size);
  char *file = (char *)mmap(NULL,st.st_size,PROT_READ,MAP_PRIVATE,in,0),
    *p;
  if (!file)
    fatal("mmap");
  madvise(p,st.st_size,MADV_SEQUENTIAL);
  n = strtol(file,&p,10);
  printf ("n = %d\n",n);

  int i;
  for (i = 0; i < n; i++) {
    while (*p <= ' ')
      p++;
    a[i] = 0;
    while (*p >= '0') 
      a[i] = a[i]*10 + (*p++ - '0');
  }

  printf ("i = %d, a[%d] = %d\n",i,i-1,a[i-1]);
  exit(0);
}

avp@avp-xub11:~/hashcode$ gcc -O3 mapio.c -o mapio
avp@avp-xub11:~/hashcode$ tail -5 output.txt 
9999995
9999996
9999997
9999998
9999999
avp@avp-xub11:~/hashcode$ cat input.txt 
1 -27009
avp@avp-xub11:~/hashcode$ time ./mapio 
len = 78888899
n = 10000000
i = 10000000, a[9999999] = -27009

real    0m0.478s
user    0m0.180s
sys 0m0.228s
avp@avp-xub11:~/hashcode$

tail показывает конец входного файла, а в Вашу программу я вставил печать последнего элемента a[], введенного scanf(), чтобы убедиться в результате своей программки.

Сейчас попробую просто прочесть весь файл read-ом вместо mmap-а.

Дополнение

Код меняем так

#if 0
  char *file = (char *)mmap(NULL,st.st_size,PROT_READ,MAP_PRIVATE,in,0),
    *p;
  if (!file)
    fatal("mmap");
  madvise(p,st.st_size,MADV_SEQUENTIAL);
#else
  char *file = malloc(st.st_size), *p;
  if (read (in,file,st.st_size) != st.st_size)
    fatal("read");
#endif

Получаем

avp@avp-xub11:~/hashcode$ gcc -O3 mapio.c -o mapio
avp@avp-xub11:~/hashcode$ time ./mapio 
len = 78888899
n = 10000000
i = 10000000, a[9999999] = -27009

real    0m0.989s
user    0m0.144s
sys 0m0.728s
avp@avp-xub11:~/hashcode$
9
  • Дополнил сравнением с read вместо mmap
    – avp
    24 дек 2012 в 14:13
  • Ахиреть, интересно будет разобраться! я завтра просмотрю все это и отпишусь! сегодня просто времени нету...! спасибо за помощь 24 дек 2012 в 15:41
  • 2
    Ха-ха паренек по неопытности работает на домашней Windows машине со старичком Delphi, а вы ему впаяли пачку системных вызовы *nix ядра не имеющих прямых аналогов у Microsoft. Ставлю сотню нефти что он ни черта в этом не поймет. P.S. Плюсую за код.
    – igumnov
    24 дек 2012 в 19:56
  • 1
    @mega Вы не так меня поняли. Я имею в виду что аналоги то есть, но чтобы заставить код @avp работать в Windows нужно все равно вручную заменить mmap на соответствующий заголовок из WinAPI с чем ТС и столкнулся. >когда попробовал на C++ запустить то указывал на ошибку в mman! У него просто нету хедера mman.h По поводу AWE ничего сказать не могу так как никогда не работал с этим.
    – igumnov
    25 дек 2012 в 14:06
  • 1
    @avp: извините, что пришлось упомянуть ваш код в переписке с нашей «достопримечательностью».
    – VladD
    19 авг 2013 в 16:41
5

Подозреваю что си код

scanf("%hd", &a[i]);

делает больше чем паскаль код

Read(a[i]);

Думаю как минимум на разбор входной строки.

3

На StackOverflow есть совершенно замечательный (по объёму проведённой работы) вопрос на похожую тему: Why is reading lines from stdin much slower in C++ than Python?

Основная идея там в том, что cin и stdio в С++ по умолчанию синхронизированы и из-за этого отключается буферизация. Надо делать

cin.sync_with_stdio(false);

Подробно про это - там, в первом ответе. Попробуйте.

0

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

Когда-то (10 лет назад) тестировал компиляторы на разных тестах: Один из видов тестов

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.