weekly_20190107_20190113

时间: 20190107 ~ 20190113

新闻

• New year, new GitHub: Announcing unlimited free private repos and unified Enterprise offering

  GitHub 个人账号可以免费创建无限多个 private repo 了, 这是微软收购 GitHub 后给大家带来的一个福利

• VLC 下载量超过 30 亿

• Observations of fast radio bursts at frequencies down to 400 megahertz

  有人认为这是外星人发出的信号

• 在空中给无人机充电

• 英特尔的 10nm Ice Lake CPU

  
  

资源推荐

• C++ string::find complexity

  Q: Why the c++’s implemented string::find() doesn’t use the KMP algorithm (and doesn’t run in O(N + M)) and runs in O(N * M)?

  A: The C++ standard doesn’t specify implementation details, and only specifies complexity requirements in some cases. The only complexity requirements on std::string operations are that size(), max_size(), operator[], swap(), c_str() and data() are all constant time. The complexity of anything else depends on the choices made by whoever implemented the library you’re using.

  The most likely reason for choosing a simple search over something like KMP is to avoid needing extra storage. Unless the string to be found is very long, and the string to search contains a lot of partial matches, the time taken to allocate and free that would likely be much more than the cost of the extra complexity.

  Q: If the complexity of current substr is not O(N * M), what is that?

  A: That’s the worst-case complexity, when the string to search contains a lot of long partial matches. If the characters have a reasonably uniform distribution, then the average complexity would be closer to O(N). So by choosing an algorithm with better worst-case complexity, you may well make more typical cases much slower.

• Visualizations of Data Structure and Algorithm

  来自 Department of Computer Science of USFCA, 展示了常见数据结构和算法的可视化过程

  比如 Red/Black Tree, Splay Tree 的结点的插入删除等等

• online gif editor

  在查看 office 的这篇文档时发现的一个在线编辑和制作 gif 动画的工具

• Trie by 花花

  对应 LeetCode P208 Implement Trie (Prefix Tree)

• suffix array by WilliamFiset

  
  

其他

本文地址：https://jjayyyyyyy.github.io/2019/01/13/weekly_20190107_20190113.html

(END)

---

相关阅读