У меня есть программа, которая читает 2 входных файла. Первый файл содержит несколько случайных слов, которые помещаются в дерево BST и AVL. Затем программа ищет слова, перечисленные во втором прочитанном файле, и говорит, что они существуют в деревьях, а затем записывает выходной файл с собранной информацией. При этом программа выводит время, затраченное на поиск определенного предмета. Однако программа, похоже, не измеряет затраченное время.
BST* b = new BST();
AVLTree* t = new AVLTree();
string s;
ifstream in;
in.open(argv[1]);
while(!in.eof())
{
in >> s;
b->insert(s);
t->insert(s);
}
ifstream q;
q.open(argv[2]);
ofstream out;
out.open(argv[3]);
int bstItem = 0;
int avlItem = 0;
float diff1 = 0;
float diff2 = 0;
clock_t t1, t1e, t2, t2e;
while(!q.eof())
{
q >> s;
t1 = clock();
bstItem = b->findItem(s);
t1e = clock();
diff1 = (float)(t1e - t1)/CLOCKS_PER_SEC;
t2 = clock();
avlItem = t->findItem(s);
t2e = clock();
diff2 = (float)(t2e - t2)/CLOCKS_PER_SEC;
if(avlItem == 0 && bstItem == 0)
cout << "Query " << s << " not found in " << diff1 << " microseconds in BST, " << diff2 << " microseconds in AVL" << endl;
else
cout << "Query " << s << " found in " << diff1 << " microseconds in BST, " << diff2 << " microseconds in AVL" << endl;
out << bstItem << " " << avlItem << " " << s << "\n";
}
Значение clock (), которое я получаю непосредственно перед вводом while и сразу после окончания, точно такое же. Таким образом, создается впечатление, что программа вообще даже не запускает цикл while, поэтому выдает 0. Я знаю, что это не так, поскольку программе требуется около 10 секунд, чтобы завершить ее как следует. Также выходной файл содержит правильные результаты, поэтому вероятность наличия плохих функций findItem () также не соответствует действительности.
Я немного исследовал Stack Overflow и увидел, что многие люди сталкиваются с той же проблемой, что и я. Однако ни один из ответов, которые я прочитал, не решил это.
Я решил свою проблему, используя часы с более высоким разрешением, хотя разрешение часов не было моей проблемой. Я использовал clock_gettime () из time.h. Насколько я знаю, более высокое разрешение часов, чем clock (), зависит от платформы, и этот конкретный метод, который я использовал в своем коде, доступен только для Linux. Я до сих пор не понял, почему мне не удалось получить хорошие результаты от clock (), но я снова подозреваю зависимость от платформы.
Важное замечание: использование clock_gettime () требует, чтобы вы включали расширение POSIX в реальном времени при компиляции кода.
Так что вы должны сделать:
g++ a.cpp b.cpp c.cpp -lrt -o myProg
где -lrt — параметр для включения расширений POSIX.
Если (t1e — t1) < CLOCKS_PER_SEC ваш результат всегда будет 0, потому что целочисленное деление усекается. Приведите CLOCKS_PER_SEC к плаванию.
diff1 = (t1e — t1) / ((float) CLOCKS_PER_SEC);