Блог

Я делаю проект, который включает в себя сравнение языков программирования. Я вычисляю функцию Аккермана. Я тестировал Java, Python и Ruby и получал ответы от 10 до 30 миллисекунд. Но C , похоже, занимает 125 миллисекунд. Это нормально, или это проблема с gettimeofday() ? Gettimeofday() находится в time.h.

Я тестирую на (виртуальном) Ubuntu Natty Narwhal 32-разрядный. Мне не хватает вычислительной мощности (четырехъядерный процессор Intel Xeon с частотой 2,13 ГГц).

Мой код здесь:

 #include <iostream>
#include <sys/time.h>
using namespace std;
int a(int m,int n) {
    if (m == 0) {
    return n   1;
    } else if (m > 0 and n == 0) {
    return a(m-1,1);
    } else if (m > 0 and n > 0) {
    return a(m-1,a(m,n-1));
    }
}

int main() {
    timeval tim;
    gettimeofday(amp;tim,NULL);
    double t1 = tim.tv_usec;
    int v = a(3,4);           
    gettimeofday(amp;tim,NULL);
    double t2 = tim.tv_usec;
    cout << v << endl << t2-t1;
    return 0;
}       
  

Предполагая, что вы говорите о разрешении возвращаемых данных, спецификация POSIX для gettimeofday состояний:

Разрешение системных часов не указано.

Это связано с тем, что системы могут иметь сильно различающиеся возможности для отслеживания небольших периодов времени. Даже стандартная clock() функция ISO содержит подобные оговорки.

Если вы говорите о том, сколько времени требуется для его вызова, стандарт не дает никаких гарантий относительно производительности в этом направлении. Реализация совершенно бесплатна, чтобы подождать 125 минут, прежде чем дать вам время, хотя я сомневаюсь, что такая реализация будет иметь большой успех на рынке 🙂

В качестве примера ограниченного разрешения я ввел следующий код, чтобы проверить его в своей системе:

 #include <stdio.h>
#include <sys/time.h>

#define NUMBER 30

int main (void) {
    struct timeval tv[NUMBER];
    int count[NUMBER], i, diff;

    gettimeofday (amp;tv[0], NULL);

    for (i = 1; i < NUMBER; i  ) {
        gettimeofday (amp;tv[i], NULL);
        count[i] = 1;
        while ((tv[i].tv_sec == tv[i-1].tv_sec) amp;amp;
            (tv[i].tv_usec == tv[i-1].tv_usec))
        {
            count[i]  ;
            gettimeofday (amp;tv[i], NULL);
        }
    }

    printf ("-: secs = %d, usecs = mn", 0, tv[0].tv_sec, tv[0].tv_usec);
    for (i = 1; i < NUMBER; i  ) {
        diff = (tv[i].tv_sec - tv[i-1].tv_sec) * 1000000;
        diff  = tv[i].tv_usec - tv[i-1].tv_usec;

        printf ("-: secs = %d, usecs = m, count = ], diff = %dn",
            i, tv[i].tv_sec, tv[i].tv_usec, count[i], diff);
    }

    return 0;
}
  

Код в основном записывает изменения в базовом времени, подсчитывая, сколько вызовов потребовалось gettimeofday() для фактического изменения времени. Это на достаточно мощной машине, поэтому у нее не хватает вычислительной мощности (счетчик показывает, как часто он мог вызывать gettimeofday() каждый квант времени, около отметки 5800, игнорируя первый, поскольку мы не знаем, когда в этом кванте мы начали измерения).

Вывод был:

  0: secs = 1318554836, usecs = 990820
 1: secs = 1318554836, usecs = 991820, count =  5129, diff = 1000
 2: secs = 1318554836, usecs = 992820, count =  5807, diff = 1000
 3: secs = 1318554836, usecs = 993820, count =  5901, diff = 1000
 4: secs = 1318554836, usecs = 994820, count =  5916, diff = 1000
 5: secs = 1318554836, usecs = 995820, count =  5925, diff = 1000
 6: secs = 1318554836, usecs = 996820, count =  5814, diff = 1000
 7: secs = 1318554836, usecs = 997820, count =  5814, diff = 1000
 8: secs = 1318554836, usecs = 998820, count =  5819, diff = 1000
 9: secs = 1318554836, usecs = 999820, count =  5901, diff = 1000
10: secs = 1318554837, usecs =    820, count =  5815, diff = 1000
11: secs = 1318554837, usecs =   1820, count =  5866, diff = 1000
12: secs = 1318554837, usecs =   2820, count =  5849, diff = 1000
13: secs = 1318554837, usecs =   3820, count =  5857, diff = 1000
14: secs = 1318554837, usecs =   4820, count =  5867, diff = 1000
15: secs = 1318554837, usecs =   5820, count =  5852, diff = 1000
16: secs = 1318554837, usecs =   6820, count =  5865, diff = 1000
17: secs = 1318554837, usecs =   7820, count =  5867, diff = 1000
18: secs = 1318554837, usecs =   8820, count =  5885, diff = 1000
19: secs = 1318554837, usecs =   9820, count =  5864, diff = 1000
20: secs = 1318554837, usecs =  10820, count =  5918, diff = 1000
21: secs = 1318554837, usecs =  11820, count =  5869, diff = 1000
22: secs = 1318554837, usecs =  12820, count =  5866, diff = 1000
23: secs = 1318554837, usecs =  13820, count =  5875, diff = 1000
24: secs = 1318554837, usecs =  14820, count =  5925, diff = 1000
25: secs = 1318554837, usecs =  15820, count =  5870, diff = 1000
26: secs = 1318554837, usecs =  16820, count =  5877, diff = 1000
27: secs = 1318554837, usecs =  17820, count =  5868, diff = 1000
28: secs = 1318554837, usecs =  18820, count =  5874, diff = 1000
29: secs = 1318554837, usecs =  19820, count =  5862, diff = 1000
  

показано, что разрешение, по-видимому, ограничено не более чем одной тысячей микросекунд. Конечно, ваша система может отличаться от этой, суть в том, что это зависит от вашей реализации и / или среды.

Один из способов обойти этот тип ограничений — не делать что-то один раз, а делать это N несколько раз, а затем разделить прошедшее время на N .

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

Если это окажется 125 секунд, то да, это, вероятно, медленно. Однако, если это займет всего 27 секунд, это будет означать, что разрешение вашего таймера является причиной кажущегося большого времени, поскольку это будет равно 27 миллисекундам на итерацию, наравне с тем, что вы видите из других результатов.

Изменение вашего кода с учетом этого будет выглядеть следующим образом:

 int main() {
    const int count = 1000;
    timeval tim;

    gettimeofday(amp;tim, NULL);
    double t1 = 1.0e6 * tim.tv_sec   tim.tv_usec;

    int v;
    for (int i = 0; i < count;   i)
        v = a(3, 4);           

    gettimeofday(amp;tim, NULL);
    double t2 = 1.0e6 * tim.tv_sec   tim.tv_usec;

    cout << v << 'n' << ((t2 - t1) / count) << 'n';

    return 0;
}