Julia's coding blog - Practice makes perfect: Algorithms, performance with data structures
CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures"
code examples:
substring() - O(N^2) algorithm, to better algorithm – look for needle in hay algorithm – Next, Knuth-Morris-Pratt (a table to skip) – Finally, Boyer-Moore (use the end of the needle) (video time: 19:25/1:13:40)
substring() - O(N^2) algorithm, to better algorithm – look for needle in hay algorithm – Next, Knuth-Morris-Pratt (a table to skip) – Finally, Boyer-Moore (use the end of the needle) (video time: 19:25/1:13:40)
std::vector using vector::reserve call first
cache[key] – save a local variable to avoid duplicated calls 4 times
STD:::LIST
doubly-linked list
Each node separately allocated
All traversal operations chase pointers to totally new memory
In most cases, every step is a cache miss
Only use this when you rarely traverse the list, but very frequently update the list
Read full article from Julia's coding blog - Practice makes perfect: Algorithms, performance with data structures
No comments:
Post a Comment