Sp21 CS F002C 02W Adv Data Struct/Algrm In C++ ⻚⾯ Linear Search! Search... 查看所有⻚⾯ Immersive Reader Linear Search Linear Search Linear Search Why searching is useful Searching shows up a lot in the real world: search engines, online dic!onaries, databases, contacts apps, and at least N other things for all N > 0. In most searching problems you have some key, such as a word, that you already have and you want to find some value, like the defini!on. In other searching problems you just have a key, such as a word, and you want to know if that key is in some big list of keys, like if you wanted to know if a word is an English word or if the word is in a list of banned words on a family friendly site. To keep things simple, we'll just look at searching for a string in a vector
. The idea If you have a vector with a list of words in it, think of the simplest way you'd search through it; that's linear search. Just look at each word, one at a !me, and check that if that word is equal to the word you're looking for. Implementa!on bool contains_word_linear(const vector& words, const string& word) { for (const auto& w : words) { if (w == word) { return true; } } return false; } std::find , defined in the header is a more general version of linear search than contains_word_linear . How fast is it? linear_search_!med.cpp #include #include #include #include #include #include #include using std::cout; using std::endl; using std::ifstream; using std::string; using std::vector; vector read_lines(const string& filepath, const long max_lines=-1) { ifstream f(filepath); vector lines; for(string line; getline(f, line); ) { lines.push_back(line); if (max_lines > 0 && lines.size() >= max_lines) { break; } } return lines; } vector get_random_words(const vector& words, const int sample_size) { std::default_random_engine dre; std::uniform_int_distribution uniform_dist(0, words.size() - 1); vector random_words; for (int i = 0; i < sample_size; ++i) { random_words.push_back(words[uniform_dist(dre)]); } return random_words; } bool contains_word_linear(const vector& words, const string& word) { for (const auto& w : words) { if (w == word) { return true; } } return false; } // Returns the number of seconds to search for all `sample_words` in `words`. double time_contains_word_linear(const vector& words, const vector& sample_words) { auto start_time = std::chrono::steady_clock::now(); for (const string& w : sample_words) { contains_word_linear(words, w); } auto end_time = std::chrono::steady_clock::now(); std::chrono::duration elapsed_seconds = end_time - start_time; return elapsed_seconds.count(); } // Returns the number of seconds to search for all `sample_words` in `words`. double time_std_find(const vector& words, const vector& sample_words) { auto start_time = std::chrono::steady_clock::now(); for (const string& w : sample_words) { std::find(words.begin(), words.end(), w); } auto end_time = std::chrono::steady_clock::now(); std::chrono::duration elapsed_seconds = end_time - start_time; return elapsed_seconds.count(); } int main(int argc, const char* argv[]) { const int sample_size = 10000; // Output a CSV that can be graphed. cout << "\"Number of words\",contains_word_linear,std::find\n"; for (int n = 1; n < 1000000; n *= 2) { vector words = read_lines("words.txt", n); vector random_words = get_random_words(words, sample_size); cout << words.size() << "," << time_contains_word_linear(words, random_words) << "," << time_std_find(words, random_words) << '\n'; } return 0; } $ clang -pedantic -Wall -lm -lstdc++ -std=c++20 -o linear_search_timed binary_search/linear_search_timed.cpp $ ./linear_search_timed "Number of words",contains_word_linear,std::find 1,0.000425767,0.000664701 2,0.000736728,0.000959686 4,0.000728683,0.000850574 8,0.00112652,0.00143054 16,0.00176876,0.00219417 32,0.00344323,0.00385945 64,0.00656622,0.00718101 128,0.010704,0.0112444 256,0.0207429,0.022693 512,0.0395032,0.0442921 1024,0.0806212,0.0873203 2048,0.161903,0.172438 4096,0.325172,0.354117 8192,0.646353,0.703643 16384,1.29168,1.39929 32768,2.55309,2.14397 65536,5.02365,4.26402 124536,9.52836,8.0898 124536,9.45949,8.03647 124536,9.45964,8.01999 And now you know why we call it "linear" search! It's linear in two ways: it searches through the elements one at a !me (in a straight line, so-to-speak) and if you double the size of the input, it takes about twice as long. "上⼀⻚ 下⼀⻚# Spring 2021 主⻚ 公告 作业 讨论 评分 ⼈员 ⻚⾯ ⽂件 ⼤纲 测验 单元 会议 协作 Chat Library Evalua!onKIT Course Labster Dashboard Foothill Tutoring Tech Ambassador Search 帐户 控制⾯板 课程 ⽇历 收件箱 历史记录 Studio 帮助 Student Support Portal Pronto 欢迎咨询51作业君
