Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Built with g++ -O2 -std=c++11 -Wall -Wpedantic
- * produces results like:
- Linear Scan: 5 ms
- Hashmap: 14 ms
- * Probably due to the higher cost of computing the hash than to
- * comparing the strings.
- */
- #include <string>
- #include <vector>
- #include <unordered_map>
- #include <algorithm>
- #include <ctime>
- #include <iostream>
- #include <stdexcept>
- typedef unsigned char day_t;
- // vector is an array, so equivilent to Java's ArrayList
- std::vector<std::string> days_vector {
- "Monday",
- "Tuesday",
- "Wednesday",
- "Thursday",
- "Friday",
- "Saturday",
- "Sunday"
- };
- // unorderd map is a hash map implementation.
- std::unordered_map<std::string, day_t> days_map {
- {"Monday", 0},
- {"Tuesday", 1},
- {"Wednesday", 2},
- {"Thursday", 3},
- {"Friday", 4},
- {"Saturday", 5},
- {"Sunday", 6}
- };
- // use a separate vector to avoid pointer equality.
- std::vector<std::string> days_vector2 {
- "Monday",
- "Tuesday",
- "Wednesday",
- "Thursday",
- "Friday",
- "Saturday",
- "Sunday"
- };
- bool GetDayOfWeekFromString_LinearScan(const std::string& text, day_t& day) {
- auto r = std::find(days_vector.begin(), days_vector.end(), text);
- if (r != days_vector.end()) {
- day = (day_t)( r - days_vector.begin() );
- return true;
- }
- else {
- return false;
- }
- }
- bool GetDayOfWeekFromString_HashMap(const std::string& text, day_t& day) {
- auto r = days_map.find(text);
- if (r != days_map.end()) {
- day = r->second;
- return true;
- } else {
- return false;
- }
- }
- typedef bool foo_t(const std::string& text, day_t& day);
- double test(const foo_t& alg, int iterations) {
- std::clock_t start_time = std::clock();
- for (int i = 0; i < iterations; ++i) {
- int idx = std::rand() % 7;
- std::string& dayString = days_vector2[idx];
- day_t foundDay;
- bool ok = alg(dayString, foundDay);
- if (!ok || (foundDay != idx)) throw std::runtime_error("fail");
- }
- std::clock_t end_time = std::clock();
- double duration = (end_time - start_time) / (double) CLOCKS_PER_SEC;
- return duration * 1000.0; // ms
- }
- int main(void) {
- const int iterations = 100000;
- try {
- std::cout << "Linear Scan: "
- << test(GetDayOfWeekFromString_LinearScan, iterations)
- << " ms" << std::endl;
- std::cout << "Hashmap: "
- << test(GetDayOfWeekFromString_HashMap, iterations)
- << " ms" << std::endl;
- } catch (const std::exception& e) {
- std::cerr << e.what() << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment