<?xml version="1.0" encoding="UTF-8"?>
<opml version="1.0">
  <head>
    <title>cmdln.net_2008-05-07</title>
    <expansionState>1,3,5,7,8,16,24,31,39,40,53,55,64,75,88,92,101,102,110</expansionState>
  </head>
  <body>
    <outline text="Intro" Offset="00:17"/>
    <outline text="Listener Feedback" Offset="02:51">
      <outline text="Chris on discovery"/>
    </outline>
    <outline text="Word of the Week: de-rezz" Offset="03:59">
      <outline text="http://catb.org/jargon/html/D/de-rezz.html"/>
    </outline>
    <outline text="Hacking 101: Complexity" Offset="05:13">
      <outline text="I've talked about complexity many times, haven't really defined"/>
      <outline text="A few relevant definitions">
        <outline text="Cyclomatic complexity">
          <outline text="http://en.wikipedia.org/wiki/Cyclomatic_complexity"/>
          <outline text="Based on decision points in program"/>
          <outline text="Draw a graph, each decision is a node"/>
          <outline text="Each edge is the flow of execution to the next decision"/>
          <outline text="Cyclomatic complexity is a way of computing a measurement"/>
          <outline text="Roughly is the density of nodes to edges"/>
          <outline text="Means a program is making a lot or a few decisions relative to just doing work"/>
        </outline>
        <outline text="Computational complexity">
          <outline text="http://en.wikipedia.org/wiki/Computational_complexity_theory"/>
          <outline text="Deals with the amount of resources needed to compute an algorithm"/>
          <outline text="Also with the difficulty in identifying efficient algorithms"/>
          <outline text="A typical question is what is the relationship to compute time to data input size?"/>
          <outline text="This leads to talking about Big O notation"/>
          <outline text="This is typically something like O(n) or order of n"/>
          <outline text="Simplest case means resources, O, are a simple scalar function of data input, n"/>
          <outline text="Leads to mathematical descriptsion">
            <outline text="Linear or scalar, means direct relation"/>
            <outline text="Logarithmic is a shallow but increasing curve"/>
            <outline text="Polynomial is a rapid, deep curve, like exponential or worse"/>
            <outline text="Exponential is something like resources required is the input times itself"/>
          </outline>
          <outline text="Theory also deals with figuring out if a program finishes"/>
          <outline text="This leads also into just figuring out if a more efficient algorithm exists"/>
        </outline>
        <outline text="Complexity as an emergent phenomenon">
          <outline text="Start with simple rules, like the syntax of a programming language"/>
          <outline text="Building a system out of those rules quickly becomes non-simple"/>
          <outline text="Should be able to predict all outcomes from simple start"/>
          <outline text="May be able to do so, but not faster than just running the systems"/>
          <outline text="An emergent system reveals unexpected surprises"/>
          <outline text="Defies a human's limited ability to model and predict"/>
          <outline text="Other examples include markets, physics, animal swarms"/>
        </outline>
      </outline>
      <outline text="Why is it important?">
        <outline text="Cyclomatic complexity">
          <outline text="Easiest to understand measure of complexity"/>
          <outline text="Doesn't necessarily relate directly to performance"/>
          <outline text="In my experience, has more to do with readability"/>
          <outline text="Humans are bad at keeping long chains of decisions straight"/>
          <outline text="Using this measure helps keep code readable"/>
          <outline text="Means maintainer can keep manageable amount of code clear in their head"/>
          <outline text="Improves odds of them spotting, fixing problems"/>
          <outline text="Learn to leverage language tricks like functions, classes, polymorphism, other ways to reduce costs of decisions"/>
          <outline text="When source grows to a certain size, provides a good heuristic for breaking up"/>
          <outline text="Also can guide functional decomposition"/>
          <outline text="If a function has more than about a dozen decision points, want to think about decomposing further"/>
          <outline text="Since it is formally computable with a decent parse tree, there are tools for measuring"/>
        </outline>
        <outline text="Computational complexity gives a vocabulary">
          <outline text="Can speak about relative efficiencies of algorithms"/>
          <outline text="Also provides a vast pre-existing body of expertise of good vs. bad algorithms">
            <outline text="For example, bubble sort vs. quick sort"/>
            <outline text="Bubble involves repeatedly iterating data and comparing two successive elements, swapping if they are out of order"/>
            <outline text="Easiest to arrive at on your own"/>
            <outline text="A quick search for bubble sort reveals its complexity is O(n^2) worst case"/>
            <outline text="Doing some search on efficient sorts leads to quick sort"/>
            <outline text="Relatively efficient, O(n * log(n))"/>
          </outline>
          <outline text="On your own, if test data is small, may not realize how poor bubble sort does"/>
          <outline text="Conversely, if you can control input, understanding computational complexity allows you to make qualified trade offs"/>
        </outline>
        <outline text="Emergence applies as you scale up">
          <outline text="Simplest programs are relatively predictable"/>
          <outline text="Given such and such input, does something expected"/>
          <outline text="For very large systems, input sets are huge"/>
          <outline text="May be combinatorial, that is involve many variables whose combinations describe a vast set"/>
          <outline text="Again, runs up against limits of human mind to retain, parse through"/>
          <outline text="Being able to address system at different scales helps"/>
          <outline text="Whole system, versus modules, versus classes, versus functions"/>
          <outline text="Reader is better able to ignore things that are not pertinent to a given scope"/>
          <outline text="Does mean you need a more sophisticated language"/>
          <outline text="Explains why OO is popular, regardless of other questions like dynamic vs. static"/>
        </outline>
      </outline>
      <outline text="I like to think of complexity as a budget">
        <outline text="Spending complexity is unavoidable"/>
        <outline text="Programs need to make decisions to do work"/>
        <outline text="However, if you thinking about it as something you spend or accrue, gives you context for implementation decisions"/>
        <outline text="This often flows up to user interface, features"/>
        <outline text="Have to bear in mind that a system's complexity is also limited by the user's ability to deal with complexity"/>
        <outline text="It is often hard to remove complexity at all levels once it is in"/>
        <outline text="Complexity is often a consequence of design decisions, amplified by the implementation decisions that follow"/>
        <outline text="Use the least complex design, there is room to add complexity later"/>
        <outline text="Start with a complex design, adding more complexity can make a system unmaintainable"/>
        <outline text="For example, a customer wants a granular permission system"/>
        <outline text="If you choose a simpler, say role based design, easier to implement and understand"/>
        <outline text="Can defined, add new roles later"/>
        <outline text="If you choose to expose fine grained, per use privileges">
          <outline text="Harder to implement, more complex UI"/>
          <outline text="Calculating who can do what also becomes harder to understand and implement"/>
          <outline text="Each addition of a new privilege is a combinatorial addition"/>
        </outline>
      </outline>
      <outline text="Complexity is single biggest factor at odds with our limits as humans">
        <outline text="Machines don't care about complexity"/>
        <outline text="If you have an infinitely complex program, one that never stops"/>
        <outline text="Computer will keep grinding until the heat death of the universe"/>
        <outline text="When trying to find, fix a bug, complexity is the most direct driver of cost"/>
        <outline text="Simple systems are easiest to understand"/>
        <outline text="That makes them easiest to fix"/>
        <outline text="Complexity is guaranteed to rise over time in successful programs"/>
        <outline text="If you are conservative, you keep your code as maintainable as possible, as long as possible"/>
      </outline>
    </outline>
    <outline text="Outro" Offset="28:14">
      <outline text="Contact me">
        <outline text="Email to feedback@thecommandline.net"/>
        <outline text="Web site at http://thecommandline.net/"/>
        <outline text="IM to command.line@skype"/>
        <outline text="Listener comment line is 240-949-2638"/>
        <outline text="del.icio.us tag is &quot;for:cmdln&quot;"/>
        <outline text="http://twitter.com/cmdln"/>
      </outline>
      <outline text="I'd like to thank libsyn.com for AAC hosting and Wouter de Bie for MP3 hosting"/>
      <outline text="These notes and the show audio and music are covered by a Creative Commons license">
        <outline text="http://creativecommons.org/licenses/by-nc-sa/3.0/us/"/>
        <outline text="Attribution, non-commercial, share alike"/>
      </outline>
    </outline>
  </body>
</opml>
