Алгоритмы и понятия, которые важно знать программисту или почему меня этому не учили в универе?
Понятия
Сложность
Вычислительная сложность: сколько времени займёт вычисление в зависимости от входных данных. Указывается в форме “О большое от …” (т.е. реальное значение всегда ограничено сверху константой умноженной на значение параметра). Например, последовательное суммирование N чисел имеет сложность O(N).
Сложность по памяти: аналогично, но оцениваем объём памяти. Например, последовательное суммирование N чисел имеет сложность по памяти O(1).
Цикломатическая сложность: насколько сложен код. Сначала код представляется в виде графа, где линейные участки - вершины, а передача управления - дуги. Формула расчёта - E − N + 2P, (E = число дуг, N = число узлов, P = число компонент связности). Есть другие варианты расчёта. Считается, что сложность одной единицы кода (метод, модуль) не должна превышать 10 (иногда 15).
Алгоритмы
сортировки - TODO (но это все знают) хеширование - TODO (тоже все знают) два указателя - TODO
Числа, которые должен знать каждый (с) Google
| Operation | Time in ns | Time in ms (1ms = 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