Skip to content

Card details: technical

dxnn edited this page Dec 23, 2014 · 1 revision

All cards:

  • data structure title
  • historical tidbit
  • graphical representation
  • power-up signatures

Abstract cards:

  • required operations + time expectation
  • optional operations + time expectation

Above possibly notated by a list of all possible operations, with one edge-printed color for required and another for optional, and all other operations listed but greyed out and neutrally labeled. Time expectation might turn out to always be consistent per-operation, rather than per-card, in which case it could be denoted elsewhere -- for example, an info sheet providing an explanation of the operations.

Concrete cards:

  • fulfilled operations + time required + modifiers (mutation, amortization, etc)
  • time required for fulfilled operations should be edge-printed in an appropriate color, like green for cards that meet the timing, yellow for ones that almost meet it (within a log factor) or are amortized, and red for ones that don't even come close. yellow might be too harsh here, since it's usually as good as green. leave it blank for operations with > n^2 higher than expected cost, or simple impossible.
  • list of all modifiers on the left, with edge-printed colors for each possessed and greyed out versions for those not. these might be cumulative over all the operations. or they might not. this might be tricky.

Keep the operations in the same order for all cards, and the modifiers in the same order for all concrete cards, so you can just look at the side of the stack to pick the one you want.

Modifiers are things like:

  • amortized / worst-case
  • catenable / non-catenable
  • persistent / ephemeral
  • fully persistent
  • confluently persistent
  • mutates / immutable (almost exactly like persistent / ephemeral ...)
  • spatial concerns
  • best case different, or like some kind of Q-factor for how tight the bounds are
  • unusually large constant factors
  • locality concerns
  • parallelism concerns

Operations are things like:

  • push
  • pop
  • shift
  • unshift
  • peek first
  • peek last
  • count
  • insert
  • update
  • lookup
  • subvec
  • memberof
Clone this wiki locally