- We've won! - 1 Update
- Longest word in a dictionary problem -- which container - 1 Update
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Nov 23 03:12PM -0800 On 11/23/2018 2:14 AM, David Brown wrote: > operations on the same mutex. That is /all/. "acquires_count" should > be atomic, and use atomic operations. Without atomic, or volatile, the > compiler can do exactly the same sort of optimisations. [...] No. acquires_count does not have to be atomic at all. A C11 mtx_t provides a standard mutex. In C++11, its equivalent is std::mutex. C11 https://en.cppreference.com/w/c/thread/mtx_lock https://en.cppreference.com/w/c/thread C++11 https://en.cppreference.com/w/cpp/thread/mutex/lock You do not seem to understand how a C11 mutex works. It is part of the language now. Variables protected by the mutex do NOT need to be atomic at all, no volatile or any crap like that. No extra memory barriers are needed at all. ____________________ // vars protected by the critical section. int a = 0; short b = 1; double c = 0.5; if (mtx_trylock(&mutex) == thrd_success) { // we are in a locked region. a += b + 1; b += 2; c += 1.6; int status = mtx_unlock(&mutex); assert(status == thrd_success); } ____________________ a, b and c do not need to be atomic types at all. No extra memory barriers are needed. Period. |
| "Öö Tiib" <ootiib@hot.ee>: Nov 23 07:18AM -0800 On Monday, 19 November 2018 12:19:51 UTC+2, Paul wrote: > std::vector<int> charCounts(const std::string& arrayOfLetters) > { > std::vector<int>counts(256); That is pessimization of std::array<int,256> into std::vector<int>. > const std::vector<int>& characterCounts = charCounts(arrayOfLetters); > // Test the longest words first > auto cmp = [](const std::string& word1, const std::string& word2)->bool{return word1.size() > word2.size();}; There is point to sort outside when several arrays of letters need to be validated for same dictionary. It is likely wasteful to sort for one pass search. > const std::set<std::string, decltype(cmp)> sortedDictionary(Dictionary.begin(), Dictionary.end(), cmp); That std::set destroys your algorithm when there are multiple entries with same length in dictionary. Your test data below does not have multiple entries with same length but generally it is the case. Some std::multiset would work. > // A vector solution would have been as below. Should I have done this? > /*std::vector<std::string> sortedDictionary(Dictionary.begin(), Dictionary.end()); > std::sort(sortedDictionary.begin(), sortedDictionary.end(), cmp);*/ In sorted dictionary you should first skip "too long" entries with std::upper_bound. > wordWorks = false; > break; > } I did not understand what you meant by "using continue" in other post? The break makes perfect sense here. > std::unordered_set<std::string> words = {"acceca", "ace", "acce", "accce" }; > std::cout << LongestWord("acecad", words); > } Download some words from somewhere stuff: https://github.com/dwyl/english-words Then you can use subsets of those for whatever tests. If you try to maximize performance of your program then you may discover that there are more efficient algorithms than std::sort for sorting dictionary with lot of entries with equal length by length. These are likely not good idea to write in answer for a test assignment. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment