bk99.de entertain the web since 1997

bk99.de
HN · AlgorithmsCurated

Big O as a reference for data structures

Summary

Eric Rowell compares the running time and memory requirements of common data structures and sorting algorithms in a compact overview. The overview contains search, insertion and deletion costs. Several sorting algorithms are compared graphically.

Ideas

  • Big O describes growth as the input size increases.
  • Arrays and lists trade access speed for flexible changes.
  • Hash tables offer expected constant-time access under good assumptions.
  • Sorting methods differ in time, memory and stability.

Insights

  • Asymptotics compares growth, not real running time for small inputs.
  • Averages can hide dangerous worst cases.
  • The choice of data structure follows the actual operations rather than habit.

Facts

  • Space complexity is also shown.

Recommendations

  • Measure the input sizes and mix of operations of the real system.
  • Check the assumptions behind average running times.

References

Read the original article

Search the Web Archive

HN · 2012

Bandit algorithms instead of rigid A/B tests

Steve Hanov shows how a Bayesian bandit continuously directs traffic to promising variants. The example algorithm needs only a few lines of code. Beta distributions model binary success probabilities.

HN · 2013

Data structures and algorithms in the Linux kernel

A curated overview shows where the Linux kernel uses trees, hash lists, heaps, compression and scheduling algorithms in practice. The kernel provides generic list and tree helpers. CFS uses a red-black tree.

HN · 2015

Unix Toolbox as a compact admin reference

Colin Barschel collects practical commands for processes, networks, SSH, disks, file systems, cryptography and shell work. The collection covers Linux, BSD, Solaris and macOS. It is available as HTML and PDF.