Algorithms, performance with data structures

Dec. 5, 2015
( 11:50am - )
CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures"

https://www.youtube.com/watch?v=fHNmRkzxHWs

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)

    Julia worked on this algorithm problem - actually it is one of leetcode questions on June 10, 2015:

http://juliachencoding.blogspot.ca/search/label/Boyer-Moore%20algorithm (question 3)

https://github.com/jianminchen/stringDemo/blob/master/Program.cs  (June 10, 2015, strstr function) 

     std::vector using vector::reserve call first

     cache[key] – save a local variable to avoid duplicated calls 4 times

 41:10/1:13:40
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