David Owen’s blog
https://blog.fugue88.ws/
Forward motionenhttps://blog.fugue88.ws/templates/2k11/img/s9y_banner_small.pngRSS: David Owen’s blog - Forward motion
https://blog.fugue88.ws/
10021In-order responses for asynchronous work
https://blog.fugue88.ws/archives/2023-02/In-order-responses-for-asynchronous-work
<p>Sometimes we end up executing some asynchronous function several times in a row, but we need only the results of the last call. The difficulty is that some earlier invocations may finish after the latest. I encounter this most often in Javascript, when I call an API in response to ongoing user input, like for looking up an address. While debouncing can help reduce this problem (and should be done anyway to lighten the load), it does not eliminate the problem.</p>
<p>A simple way to do this is to use a counter to keep track of each request, and only process a response if it's newer than any other processed so far.</p>
<a class="block_level" href="https://blog.fugue88.ws/archives/2023-02/In-order-responses-for-asynchronous-work#extended">Continue reading "In-order responses for asynchronous work"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2023-02-08T14:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=650https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=65Pipelines in Lisp
https://blog.fugue88.ws/archives/2022-03/Pipelines-in-Lisp
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2022-03-07T14:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=640https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=64Better averages for online machine-learning
https://blog.fugue88.ws/archives/2022-03/Better-averages-for-online-machine-learning
<p>Averages are used, in some form or other, and many machine-learning algorithms. Stochastic gradient descent is a great example of an average in disguise, thin though it may be.</p>
<p>Picking the right kind of average can be critical. As learning algorithms explore sub-optimal choices, the resulting negative impact on backed-up state values can persist over epochs, hampering performance. Alternatively, some kinds of average don't converge, preventing the algorithm from settling into optimal outcomes.</p>
<p>Here, I officially release a paper on a particular kind of average that's adaptable like an exponential moving average, but has guaranteed convergence like a simple average.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2022-03/Better-averages-for-online-machine-learning#extended">Continue reading "Better averages for online machine-learning"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2022-03-04T20:42:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=630https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=63Action-selection and learning-rates in Q-learning
https://blog.fugue88.ws/archives/2021-04/Action-selection-and-learning-rates-in-Q-learning
<p>Implementing a Q-table reinforcement-learner is in many ways simple and straight-forward and also somewhat tricky. The basic concept is easy to grasp; but, as many have mentioned, reinforcement-learners almost <em>want</em> to work, despite whatever bugs or sub-optimal math might be in the implementation.</p>
<p>Here are some quick notes about the approach I've come to use, specifically about action-selection (e.g. epsilon-greedy versus UCB) and managing learning-rates. They've helped my learners converge to good strategies faster and more reliably. Hopefully they can help you, too!</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2021-04/Action-selection-and-learning-rates-in-Q-learning#extended">Continue reading "Action-selection and learning-rates in Q-learning"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2021-04-13T13:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=620https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=62Simulating deck-shuffling
https://blog.fugue88.ws/archives/2020-12/Simulating-deck-shuffling
<p>I recently worked on a small project simulating random events that were far too numerous to enumerate. In such cases, every bit of speed matters.</p>
<p>The project in this case was similar to determining likelihood of five-card Poker hands in seven-card draws.</p>
<p>Simulation of shuffling the deck and drawing cards can take a large part of the runtime if not done well, but there's a trick that makes it almost trivial.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2020-12/Simulating-deck-shuffling#extended">Continue reading "Simulating deck-shuffling"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2020-12-30T14:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=610https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=61Exact random sums
https://blog.fugue88.ws/archives/2020-06/Exact-random-sums
<p>Sometimes, you need a list of random numbers that sum to a known constant. There's a known algorithm to provide this list of numbers with the proper distribution, but a straight-forward implementation may give a list that doesn't sum exactly to the desired constant because of rounding error.</p>
<p>This article describes the basic algorithm, why the rounding error happens, and the solution.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2020-06/Exact-random-sums#extended">Continue reading "Exact random sums"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2020-06-16T13:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=600https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=60Precision of random numbers
https://blog.fugue88.ws/archives/2020-06/Precision-of-random-numbers
<p>In some sense, random numbers uniformly-distributed in the range \([0, 1)\) are the easiest class of random number to generate.</p>
<p>Because of the internal representation of floating-point numbers, all you need to do is fill the significand with random bits, set the exponent to -1, and the sign bit to positive.</p>
<p>Some language run-times do this better than others.</p>
<p>This article shows how to check your run-time, and how to fix it.</p>
<a class="block_level" href="https://blog.fugue88.ws/archives/2020-06/Precision-of-random-numbers#extended">Continue reading "Precision of random numbers"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2020-06-02T13:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=590https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=59certbot and tinydns
https://blog.fugue88.ws/archives/2019-03/certbot-and-tinydns
<p>Let's Encrypt now supports wildcard certificates. To confirm DNS control,
they support several different DNS providers and dynamic DNS protocols, but
they don't yet have a plugin for tinydns by DJ Bernstein.</p>
<p>Luckily, the excellent designs of both certbot and tinydns make it very easy
to support on your own.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2019-03/certbot-and-tinydns#extended">Continue reading "certbot and tinydns"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2019-03-12T13:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=580https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=58von Neumann's 4-player {1/3, 1/3, -1/3, -1/3} imputation
https://blog.fugue88.ws/archives/2017-09/von-Neumanns-4-player-13,-13,-13,-13-imputation
<p>In <a href="https://archive.org/details/theoryofgamesand030098mbp">Theory of Games and Economic Behavior</a>, von Neumann discusses solutions to some kinds of zero-sum four-person games. See section 37.4.2, page 317. There, he finds that one set of imputations is incomplete, and must have at least another imputation added to it. He writes that <q>[it] seems very difficult to find a heuristic motivation for the steps which are now necessary</q> before giving the imputation as:</p>
\begin{equation} \vec a^{IV} = \left\{1/3, 1/3, -1/3, -1/3\right\} \end{equation}
<p>The situation is unusual in that the first three players have formed a coalition against the fourth. So, why does the third player have the same loss as the fourth? This is the heuristic that von Neumann didn’t provide, and he concludes by saying only that <q>[if] a common-sense interpretation of this solution… is wanted, … it seems to be some kind of compromise between a part (two members) of a possible victorious coalition and the other two players.</q></p>
<p>However, there’s an intriguing possibility.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2017-09/von-Neumanns-4-player-13,-13,-13,-13-imputation#extended">Continue reading "von Neumann's 4-player {1/3, 1/3, -1/3, -1/3} imputation"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2017-09-22T01:23:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=570https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=57Exponential Moving Average (EMA) Rates, part 3
https://blog.fugue88.ws/archives/2017-04/Exponential-Moving-Average-EMA-Rates,-part-3
<p>In the last post, we created an online implementation of an EMA to measure the rate of a Poisson event. However, it has the “warm-up” period seen in most EMA implementations.</p>
<p>This time, we’ll correct that. The technique is similar to what I wrote in <a href="https://blog.fugue88.ws/archives/2017-01/The-correct-way-to-start-an-Exponential-Moving-Average-EMA">The correct way to start an Exponential Moving Average (EMA)</a>.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2017-04/Exponential-Moving-Average-EMA-Rates,-part-3#extended">Continue reading "Exponential Moving Average (EMA) Rates, part 3"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2017-04-11T13:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=550https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=55Exponential Moving Average (EMA) Rates, part 2
https://blog.fugue88.ws/archives/2017-03/Exponential-Moving-Average-EMA-Rates,-part-2
<p>In the <a href="https://blog.fugue88.ws/archives/2017-03/Exponential-Moving-Average-EMA-Rates,-part-1">last post</a>, we simulated some Poisson data and then verified it by looking at its histogram and some descriptive statistics. We also built a basic sliding-window implementation and graphed its output.</p>
<p>To continue on, we’ll need to build a more realistic implementation, along with a method to feed it the simulated events. With that in hand, we’ll build an EMA function specialized for Poisson events.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2017-03/Exponential-Moving-Average-EMA-Rates,-part-2#extended">Continue reading "Exponential Moving Average (EMA) Rates, part 2"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2017-03-28T13:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=540https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=54Exponential Moving Average (EMA) Rates, part 1
https://blog.fugue88.ws/archives/2017-03/Exponential-Moving-Average-EMA-Rates,-part-1
<p>I had been thinking about determining the average rate of occurrences over time of some observation. For example, you might like to measure how much traffic flows through a street throughout the day. Reporting the time that every single car goes by is very accurate, but not very useful. You might bin traffic into hours starting on every hour, but if there is a spike or sudden increase in the middle of an hour you might miss its significance. So, you'd like to see a graph that's smooth like an average but with more detail in time.</p>
<p>One approach is similar to the binning approach, but slide the hour-long window across the data by minutes. Doing this requires keeping the data around, and using each data point repeatedly. If you have a surge of one million cars in a few minutes, you need to use those million points in your calculations 60 times.</p>
<p>This behavior is similar to the Simple Moving Average (SMA). A SMA can easily be transformed into an Exponential Moving Average, which requires only the previous EMA and the new data point to calculate the new EMA. So, I decided to create an Exponential Moving Average Rate (EMAR).</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2017-03/Exponential-Moving-Average-EMA-Rates,-part-1#extended">Continue reading "Exponential Moving Average (EMA) Rates, part 1"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2017-03-14T13:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=530https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=53The correct way to start an Exponential Moving Average (EMA)
https://blog.fugue88.ws/archives/2017-01/The-correct-way-to-start-an-Exponential-Moving-Average-EMA
<p>The EMA is a very handy tool. It lets us calculate an average over recent data. But, unlike a Simple Moving Average, we don't have to keep a window of samples around—we can update an EMA "online," one sample at a time.</p>
<p>But the perennial question is: how do you <i>start</i> an EMA?</p>
<p>First, here are a couple of wrong ways.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2017-01/The-correct-way-to-start-an-Exponential-Moving-Average-EMA#extended">Continue reading "The correct way to start an Exponential Moving Average (EMA)"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2017-01-31T14:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=520https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=52Deciding once
https://blog.fugue88.ws/archives/2017-01/Deciding-once
<p>In <a href="https://blog.fugue88.ws/archives/2017-01/Fixing-dispatch">Fixing dispatch</a>, we refactored some code that dispatched things from a <code>switch</code>-statement or cascading <code>if</code>-statements to dispatching by polymorphism.</p>
<p>This time, we'll refactor a different piece of dispatch in a completely different way, and cover another design principle.</p>
<a class="block_level" href="https://blog.fugue88.ws/archives/2017-01/Deciding-once#extended">Continue reading "Deciding once"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Software engineering, 2017-01-24T14:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=510https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=51Effective practice
https://blog.fugue88.ws/archives/2017-01/Effective-practice
<p>As a musician, I began to watch the different ways that people practice music. I noticed a pattern there, and started seeing the same pattern whenever people practice.</p>
<p>Our psychology makes it very easy to slip into practice ineffectively. On the other hand, simply understanding what and why makes it easy for you to have really effective practice.</p>
<p>It's the difference between mastering something versus just wasting your time. And you can boil it down to just one simple rule.</p> <a class="block_level" href="https://blog.fugue88.ws/archives/2017-01/Effective-practice#extended">Continue reading "Effective practice"</a>
David Owen’s blogdsowen@fugue88.ws (David Owen)
Personal effectiveness, 2017-01-17T14:00:00Zhttps://blog.fugue88.ws/wfwcomment.php?cid=500https://blog.fugue88.ws/rss.php?version=1.0&type=comments&cid=50