Algorithms and basics, programmer should know, or why I hadn'd been learnt this in the University?
Concepts
Complexity
Computational complexity: how long it will take to compute in relation to the input size. It is expressed in the form “big O of…” (i.e., the actual value is always bounded from above by a constant multiplied by the value of the parameter). For example, sequentially summing N numbers has a complexity of O(N).
Space complexity: similar to the above, but for memory. For example, sequentially summing N numbers has a space complexity of O(1).
Cycle complexity: how complex the code is. First, the code is represented as a graph (a cycle graph), and then we analyze it. in the form of a graph, where linear segments represent vertices and control transfer - edges. The formula for calculation is E - N + 2P, (E = number of edges, N = number of nodes, P = number of connectivity components). There are other calculation methods. It is considered that the complexity of one unit of code (method, module) should not exceed 10 (sometimes 15).
Algorithms
Sorting algorithms - TODO (but this is all known) Hashing - TODO (also known to all) Two-pointer technique - TODO
Numbers that every (s) Google should know
| Operation | Time in ns | Time in ms (1 ms = 1,000,000 ns) | ||||
|---|---|---|---|---|---|---|
| L1 cache reference | 1 | |||||
| Branch misprediction | 3 | |||||
| L2 cache reference | 4 | |||||
| Mutex lock/unlock | 17 | |||||
| Main memory reference | 100 | Compress 1 kB with Zippy | 2,000 | 0.002 | ||
| Read 1 MB sequentially from memory | 10,000 | 0.010 | ||||
| Send 2 kB over 10 Gbps network | 1,600 | 0.0016 | ||||
| SSD 4kB Random Read | 20,000 | 0.020 | ||||
| Read 1 MB sequentially from SSD | 1,000,000 | 1 | ||||
| Round trip within same datacenter | 500,000 | 0.5 | ||||
| Read 1 MB sequentially from disk | 5,000,000 | 5 | ||||
| Read 1 MB sequentially from 1Gbps network | 10,000,000 | 10 | ||||
| Disk seek | 10,000,000 | 10 | ||||
| TCP packet round trip between continents | 150,000,000 | 150 |
Therefore, it is possible to read:
- sequentially from HDD at a rate of ~200MB per second
- sequentially from SSD at a rate of ~1 GB per second
- sequentially from main memory at a rate of ~100GB per second (burst rate)
- sequentially from 10Gbps Ethernet at a rate of ~1000MB per second