Intereting Posts
Как работает макрос Q_FOREACH (= foreach) и почему он является сложным? Как я могу эмулировать деструктурирование в C ++? Какие библиотеки мне нужно связать, чтобы создать пример googlemock? Найти строку внутри самой внешней скобки Коллекция объектов более чем одного типа Как отключить ASSERT (x) в C ++? Как я могу различать «Закрыть все windows» и «Закрыть» отдельные windows в MFC с Windows 7? Почему случайный заголовок не импортируется Как диспетчер кучи в java или C ++ отслеживает все ячейки памяти, используемые streamами или процессами? Почему установка vcredist_x86.exe не исправляет ошибку SideBySide, когда я разрабатываю EXE на одной машине и запускаю ее на другой? В чем разница между std :: string :: c_str и std :: string :: data? Разница между неинициализированными и неопределенными два экземпляра статического члена, как это могло быть? Можете ли вы начать имя classа с цифровой цифрой? VS2012: ошибка с модульным тестом: Assert :: AreEqual (объект, объект) не работает

Почему я получаю константу вместо логарифмической кривой для теста времени вставки на основе C ++ std :: set на основе RB-дерева?

Я сравнивал BST с кучей в: Heap vs Binary Search Tree (BST), но когда я попытался сравнить и сравнить результаты, я не мог интерпретировать данные для BST.

Во-первых, я подтвердил, что стандартная библиотека использует дерево Red-black: Какова базовая структура данных STL-набора в C ++?

Затем я провел этот тест.

main.cpp

#include  #include  #include  #include  int main(int argc, char **argv) { size_t i, n; std::set bst; std::random_device dev; unsigned int seed = dev(); std::mt19937 prng(seed); std::uniform_int_distribution dist; if (argc > 1) { n = std::stoi(argv[1]); } else { n = 1000000; } for (i = 0; i < n; ++i) { auto random_value = dist(prng); auto start = std::chrono::steady_clock::now(); bst.insert(random_value); auto end = std::chrono::steady_clock::now(); auto dt_bst = end - start; std::cout << random_value << " " << std::chrono::duration_cast(dt_bst).count() << std::endl; } } 

plot.gnuplot:

 #!/usr/bin/env gnuplot set terminal png size 1024, 1024 set output "bst_vs_heap.png" set title "BST insert time" set xlabel "size" set ylabel "nanoseconds" plot "main.dat" using 2 notitle 

Скомпилируйте, запустите и запишите:

 g++ -ggdb3 -O3 -std=c++17 -Wall -Wextra -pedantic-errors -o main.out main.cpp ./main.out 10000000 > main.dat ./plot.gnuplot 

Результат:

введите описание изображения здесь

Почему бы мне не увидеть хорошую логарифмическую кривую, как в теоретической структуре данных, а несколько постоянную линию с некоторыми выбросами?

Ubuntu 18.04, GCC 7.3, процессор Intel i7-7820HQ, оперативная память DDR4 2400 МГц, Lenovo Thinkpad P51.

Часы, скорее всего, недостаточно точны, как упоминалось в комментариях, поэтому я попытался сгруппировать кучу вставок и время их улучшения сигнала на шум, и это сработало, теперь я вижу логарифм:

 #include  #include  #include  #include  int main(int argc, char **argv) { size_t i, j, n, granule; std::set bst; std::random_device dev; unsigned int seed = dev(); std::mt19937 prng(seed); std::uniform_int_distribution<> dist; int *randoms; if (argc > 1) { n = std::stoi(argv[1]); } else { n = 1000000; } if (argc > 2) { granule = std::stoi(argv[2]); } else { granule = 10; } randoms = new int[granule]; for (i = 0; i < n / granule; ++i) { for (j = 0; j < granule; ++j) { randoms[j] = dist(prng); } auto start = std::chrono::high_resolution_clock::now(); for (j = 0; j < granule; ++j) { bst.insert(randoms[j]); } auto end = std::chrono::high_resolution_clock::now(); auto dt_bst = end - start; std::cout << std::chrono::duration_cast(dt_bst).count() << std::endl; } delete[] randoms; } 

Команда:

 ./main.out 100000000 10000 

График:

введите описание изображения здесь