DEV Community: shaolang

Storybook.JS with Shadow-CLJS

shaolang — Sun, 14 Feb 2021 01:44:43 +0000

Storybook.JS is a very interesting development tool from JavaScript ecosystem¹. This tutorial shows how we can use it with Shadow-CLJS. The code resides at storybook.js-with-shadow-cljs repo.

Prerequisites

The tutorial uses the following:

Java version 11
Node.js version 14.15.4
Reagent version 1.0.0
Shadow-CLJS version 2.11.8
Storybook.JS version 6.1.17

Make sure the first two are installed prior the tutorial. The others will be installed along the way.

Getting a simple React app running

Let's create the scaffold to kick-start:

$ mkdir acme
$ cd acme
$ npm init        # just keep pressing enter until the prompt ends
$ npm install --save-dev shadow-cljs

In the generated package.json, add a helper script to launch shadow-cljs and automatically compile when it detect changes:

"scripts": {
  "dev": "shadow-cljs watch frontend"
}

The script uses the :frontend profile defined in shadow-clj.edn for ClojureScript compiler. Run npx shadow-cljs init to generate the skeleton shadow-cljs.edn file and edit it as follows:

;; shadow-cljs configuration
{:source-paths
  ["src/dev"
   "src/main"
   "src/test"]

 :dependencies
 [[reagent "1.0.0"]]

 :builds
 {:frontend {:target  :browser
             :modules {:main {:init-fn acme.core/init}}}}}

Line 8 adds Reagent as a dependency; lines 11 and 12 create the profile :frontend (that matches the npm script's shadow-cljs watch command). This profile specifies that the build targets the browser and should generate the file main.js ('cos of the :main key) that will invoke acme.core/init function at initialization. Let's implement init that uses a simple Reagent component in src/main/acme/core.cljs:

(ns acme.core
  (:require [reagent.dom :refer [render]]))

(defn header [text]
  [:h1 text])

(defn init []
  (render [header "Hello, World!"]
          (js/document.getElementById "app")))

Simple enough: a custom header component that outputs the given text in an h1 element and the init function that renders the header. To see this glorious app render, create the public/index.html as follows:

<!doctype html>
<html>
  <head>
    <meta charset='utf-8'>
    <title>Acme</title>
  </head>
  <body>
    <div id='app'></div>
    <script src='js/main.js'></script>
  </body>
</html>

By default, Shadow-CLJS generates the output to public/js, hence the highlighted line (line 9). When the page is ready, init will run and renders the header component. Before running npm run dev, add dev-http to shadow-cljs.edn to configure the dev-server to listen to port 8080 and serve artifacts from public directory:

;; shadow-cljs configuration
{:source-paths
  ["src/dev"
   "src/main"
   "src/test"]

 :dev-http {8080 "public"}

 :dependencies
 [[reagent "1.0.0"]]

 :builds
 {:frontend {:target  :browser
             :modules {:main {:init-fn acme.core/init}}}}}

With all these set up, run npm run dev and load the page localhost:8080 in your favorite browser; you should see "Hello, World!":

Some cleanup

Before integrating with Storybook.JS, let's do some cleaning up: extract the custom header component to its own namespace and make acme.core/init use that extracted one instead. First, the extracted component at src/main/acme/components/header.cljs:

(ns acme.components.header)

(defn header [text]
  [:h1 text])

Then, in src/main/acme/core.cljs, delete header function and require the header component namespace (as shown in line 2 below):

(ns acme.core
  (:require [acme.components.header :refer [header]]
            [reagent.dom :refer [render]]))

(defn init []
  (render [header "Hello, World!"]
          (js/document.getElementById "app")))

Adding Storybook.JS to the mix

Time to add Storybook.JS to the project. Install it with npm install --save-dev @storybook/react; then create .storybook/main.js with the following contents to configure Storybook.JS to look for stories in public/js/stories directory:

module.exports = {
  stories: ['../public/js/stories/**/*_stories.js'],
};

Update shadow-cljs.edn to create a new profile specifically for stories that outputs the transpiled stories to public/js/stories too:

;; shadow-cljs configuration
{:source-paths
  ["src/dev"
   "src/main"
   "src/stories"
   "src/test"]

 :dev-http {8080 "public"}

 :dependencies
 [[reagent "1.0.0"]]

 :builds
 {:frontend {:target  :browser
             :modules {:main {:init-fn acme.core/init}}}
  :stories  {:target      :npm-module
             :entries     [acme.stories.header-stories]
             :output-dir  "public/js/stories"}}}

A few notable points on the new :stories profile:

:entries specifies the namespaces to transpile to stories; unlike :frontend profile that specifies the target filename to output to (main.js), Shadow-CLJS uses the namespace as the output filename, e.g., acme.stories.header_stories.js
:target states the build should target npm module which works for Storybook.JS²

Add two script commands to package.json to ease the auto-compilation of stories and to start Storybook.JS:

"scripts": {
  "dev": "shadow-cljs watch frontend",
  "dev-stories": "shadow-cljs watch stories",
  "storybook": "start-storybook"
}

And finally, the story. Let' create a very simple story at src\stories\acme\stories\header_stories.cljs that says "Hello, World!":

(ns acme.stories.header-stories
  (:require [acme.components.header :refer [header]]
            [reagent.core :as r]))

(def ^:export default
  #js {:title     "Header Component"
       :compoent  (r/reactify-component header)})

(defn ^:export HelloWorldHeader []
  (r/as-element [header "Hello, World!"]))

The snippet above uses Component Story Format, hence the need to add the metadata ^:export to default and HelloWorldHeader. Because Storybook.JS operates on React components, reactify-component at line 7 turns the Reagent component into a React one.³ With all these preparation, run npm run dev-stories in one console, and npm run storybook in another. You should see Storybook.JS render our first story:

For the fun of it, let' append another story to header-stories:

(defn ^:export GoodbyeSekaiHeader []
  (r/as-element [header "Goodbye, Sekai!"]))

Wrapping up

That concludes this tutorial on using Storybook.JS with Shadow-CLJS. In this case, we are using Reagent to create the components for Storybook.JS to render. It shouldn't be that difficult to adapt the setup to work with other ClojureScript rendering libraries, e.g., Helix.

ClojureScript world also has a similar devcards. ↩
Shadow-CLJS has a new :esm target that outputs to ES Modules, but as of this writing, it is cumbersome to use (the ^:export metadata hint isn't working, thus requiring the need to declare all exports in shadow-cljs.edn. ↩
Refer to Reagent's tutorial on Interop with React for more information. ↩

Getting Started With Chronicle Queue

shaolang — Sun, 26 Apr 2020 09:28:29 +0000

Chronicle Queue is low-latency, broker-less, durable message queue. Its closest cousin is probably 0MQ, except that 0MQ doesn't store the messages published and the open-source version of Chronicle Queue doesn't support cross-machine communication¹. Chronicle Queue's biggest claim to fame is that it generates no garbage as it uses RandomAccessFiles as off-heap storage.

Chronicle Queue is producer-centric, i.e., applications built on Chronicle Queue cannot tell the producer to slow down in putting messages onto the queue (no back-pressure mechanics). Such design is useful in cases where there is little to no control on the producer's throughput, e.g., FX price updates.

Terminology

Where most message queues use the terms Producer and Consumer, Chronicle Queue uses Appender and Tailer instead to make the distinction that it always appends messages to the queue and it never "destroys/drops" any message after the tailer (read: receiver) reads the message from the queue. And instead of Message, Chronicle Queue prefers the term Excerpt because the blob written to Chronicle Queue can range from byte arrays to strings to domain models.

Hello, World!

Let's use the traditional "Hello, World!" to demonstrate basic usage. Add the following to build.gradle.kts if you are using Gradle:

import org.jetbrains.kotlin.gradle.tasks.KotlinCompile        // line 1

plugins {
    id("org.jetbrains.kotlin.jvm") version "1.3.71"
    application
}

repositories {
    mavenCentral()
    mavenLocal()
}

dependencies {
    implementation("org.jetbrains.kotlin:kotlin-bom")
    implementation("org.jetbrains.kotlin:kotlin-stdlib-jdk8")

    implementation("net.openhft.chronicle:chronicle-queue:5.19.8")   // line 17
    implementation("org.apache.logging.log4j:log4j-sl4fj18-impl:2.13.1")
}

application {
    mainClass = "hello.AppKt"
}

tasks.withType<KotlinCompile> {
    kotlinOptions.jvmTarget = "1.8"       // line 26
}

Importing KotlinCompile (line 1) allows specifying Java 1.8 as the compilation target (lines 25-27)². Lines 17-18 shows the additional dependencies you'd need to get started with Chronicle Queue. Note that build.gradle.kts assumes the package to use is hello. Let's turn to the code demonstrating Chronicle Queue usage:

package hello

import net.openhft.chronicle.queue.ChronicleQueue

fun main(args: Array<String>) {
    val q: ChronicleQueue = ChronicleQueue.single("./build/hello-world")

    try {
        val appender: ExcerptAppender = q.acquireAppender()
        appender.writeText("Hello, World!")

        val tailer: ExcerptTailer = q.createTailer()
        println(tailer.readText())
    } finally {
      q.close()
    }
}

ChronicleQueue.single(<path>) returns a new ChronicleQueue that uses the given path for storing the excerpts. The rest of the code are pretty much self-explanatory: the acquired appender appends the excerpt "Hello, World!" to the queue; the tailer reads from the queue and prints the excerpt to standard output. The queue must always be closed at the end of the program.³

Remember that Chronicle Queues are durable? Comment out two appender lines and run the code again with gradle run. You'll see that the program outputs Hello, World! again in standard output: the tailer is reading from the queue that was written in the previous run. Such durability allows replaying incoming excerpts when tailers crash.

Detour: Excerpt types

Chronicle Queue only accepts the following types as excerpts:

Serializable objects: note that serializing such objects are inefficient due to reliance on reflection
Externalizable objects: if compatibility with Java is important but at the expense of handwritten logic
byte[]
String
net.openhft.chronicle.wire.Marshallable objects: high performance data exchange using binary formats
net.openhft.chronicle.bytes.BytesMarshallable objects: low-level binary or text encoding

As "Hello, World!" has already demonstrated strings, we detour a little and look at an example using Marshallable offered in Chronicle Wire library.

package types

import net.openhft.chronicle.wire.Marshallable
import net.openhft.chronicle.wire.SelfDescribingMarshallable

class Person(val name: String, val age: Int): SelfDescribingMarshallable()

fun main(args: Array<String>) {
    val person = Person("Shaolang", 3)
    val outputString = """
    !types.Person {
      name: Shaolang
      age: 3
    }

    """.trimIndent()

    println(person.toString() == outputString)

    val p = Marshallable.fromString<Person>(outputString)

    println(person == p)
    println(person.hashCode() == p.hashCode())
}

You'll see three true printed to standard output when you run the snippet above. SelfDescribingMarshallable makes it effortless to make a class Marshallable for persistence in Chronicle Queue.

Writing and Reading Domain Objects

With the knowledge from the small detour tucked under our belt, the following demonstrates the writing and reading of Marshallable objects to and from Chronicle Queue⁴:

package docs

import net.openhft.chronicle.queue.ChronicleQueue
import net.openhft.chronicle.wire.SelfDescribingMarshallable

class Person(var name: String? = null,
             var age: Int? = null): SelfDescribingMarshallable()

class Food(var name: String? = null): SelfDescribingMarshallable()

fun main(args: Array<String>) {
    ChronicleQueue.single("./build/documents").use { q ->
        val appender = q.acquireAppender()

        appender.writeDocument(Person("Shaolang", 3))
        appender.writeText("Hello, World!")
        appender.writeDocument(Food("Burger"))

        val tailer = q.createTailer()

        val person = Person()
        tailer.readDocument(person)
        println(person)

        println("${tailer.readText()}\n")

        val food = Food()
        tailer.readDocument(food)
        println(food)
    }
}

After running the above, you should see the following printed out:

!docs.Person {
  name: Shaolang,
  age: 3
}

Hello, World!

!docs.Food {
  name: Burger,
}

There's a few things to note:

Because Chronicle Queue aims to generate no garbage, it requires the domain model to be a mutable object; this is why the two classes uses var instead of val in their constructors.
Chronicle Queue allows appenders to write different things to the same queue.
Tailers need to know what it should be reading to get the proper result back.

If we were to change the last tailer.readDocument(food) to tailer.readDocument(person) and print out person instead, we'll see the following printed⁵:

!docs.Person {
  name: Burger,
  age: !!null ""
}

Because both Person and Food have an attribute with the same name, Chronicle Queue hydrates Person with whatever it could and leave the others blank.

That last point on tailers needing to know what they're reading is troubling: they are now ladened with the burden of filtering things they want to be notified from the avalanche of data the producer keep throwing at them. To keep our codebases sane, we need to use the observer pattern.

(Kinda) Listening Only to Things You're Interested in

Other than using the excerpt appender directly, another way is to make it reify the first class given to its methodWriter. The following snippet focuses on this reifying of the given listener:

package listener

import net.openhft.chronicle.queue.ChronicleQueue
import net.openhft.chronicle.queue.ChronicleReaderMain
import net.openhft.chronicle.wire.SelfDescribingMarshallable

class Person(var name: String? = null,
             var age: Int? = null): SelfDescribingMarshallable()

interface PersonListener {
    fun onPerson(person: Person)
}

fun main(args: Array<String>) {
    val directory = "./build/listener"

    ChronicleQueue.single(directory).use { q ->
        val observable: PersonListener = q.acquireAppender()   // line 18
              .methodWriter(PersonListener::class.java)
        observable.onPerson(Person("Shaolang", 3))
        observable.onPerson(Person("Elliot", 4))
    }

    ChronicleReaderMain.main(arrayOf("-d", directory))
}

Lines 18-19 invoke methodWriter with the given PersonListener on the acquired appender. Notice that the type assigned to observable is PersonListener, not ExcerptAppender. Now, any calls to the methods in PersonListener writes the given argument to the queue. However, there's a difference in writing to the queue using the appender directly and using a reified class. To see the difference, we'll use ChronicleReaderMain to examine the queue:

0x47c900000000:
onPerson {
  name: Shaolang,
  age: 3
}

0x47c900000001:
onPerson {
  name: Elliot,
  age: 4
}

Notice that instead of !listener.Person { ... }, reified classes write excerpts using onPerson {...} to the queue. This difference allows tailers that implement PersonListener to be notified of new Person objects written to the queue and ignore others that they aren't interested in.

Yup, you've read that right: tailers that implement PersonListener. Unfortunately, Chronicle Queue (kinda) conflates observables and observers, thus making it a little hard in distinguishing observables from observers. I think the easiest way to tell the difference is to use the heuristics as shown in the following snippet's comments:

interface PersonListener {
    onPerson(person: Person)
}

// this is an observer because it implements the listener interface
class PersonRegistry: PersonListener {
    override fun onPerson(person: Person) {
        // code omitted for brevity
    }
}

fun main(args: Array<String>) {
    // code omitted for brevity

    val observable: PersonListener = q.acquireAppender()    // this is an
            .methodWriter(PersonListener::class.java)       // observable

    // another way to differentiate: the observer will never call the
    // listener method, only observables do.
    observable.onPerson(Person("Shaolang", 3))

    // code omitted for brevity
}

Let's turn our focus to tailers. Even though Chronicle Queue ensures that every tailer sees every excerpt, tailers can filter only excerpts that they want to see by implementing the listener class/interface and creating a net.openhft.chronicle.bytes.MethodReader with the implemented listener:

package listener

import net.openhft.chronicle.bytes.MethodReader
import net.openhft.chronicle.queue.ChronicleQueue
import net.openhft.chronicle.wire.SelfDescribingMarshallable

class Person(var name: String? = null,
             var age: Int? = null): SelfDescribingMarshallable()

class Food(var name: String? = null): SelfDescribingMarshallable()

interface PersonListener {
    fun onPerson(person: Person)
}

class PersonRegistry: PersonListener {
    override fun onPerson(person: Person) {
        println("in registry: ${person.name}")
    }
}

fun main(args: Array<String>) {
    ChronicleQueue.single("./build/listener2").use { q ->
        val appender = q.acquireAppender()
        val writer: PersonListener = appender
                .methodWriter(PersonListener::class.java)

        writer.onPerson(Person("Shaolang", 3))
        appender.writeDocument(Food("Burger"))
        writer.onPerson(Person("Elliot", 4))

        val registry: PersonRegistry = PersonRegistry()
        val reader: MethodReader = q.createTailer().methodReader(registry)

        reader.readOne()
        reader.readOne()
        reader.readOne()
    }
}

What's largely new to this is the implementation of PersonRegistry that simply prints the name of the person it is given. Instead of reading off the queue using an ExcerptTailer directly, the snippet creates a MethodReader from the tailer with the given instantiated PersonRegistry. Unlike .methodWriter that accepts Class, .methodReader expects objects. The appender writes three excerpts to the queue: person (via call to onPerson), food (via .writeDocument), and person. Because tailers see every excerpts, the reader also make three calls to "read" all excerpts, but you'll see only two outputs:

in registry: Shaolang
in registry: Elliot

If only there were only two .readOne() calls instead of three, the output will not include in registry: Elliot.

`MethodReader` Uses Duck Typing

Remember the outputs from ChronicleReaderMain when we examined the queue that's populated by the reified PersonListener? Instead of a class name, the outputs are similar to onPerson { ... }. That suggests MethodReader filters excerpts that matches the method signature, i.e., it doesn't care about the interface/class that contains the method signature; or simply put, duck typing:

package duck

import net.openhft.chronicle.queue.ChronicleQueue
import net.openhft.chronicle.wire.SelfDescribingMarshallable

class Person(var name: String? = null,
             var age: Int? = null): SelfDescribingMarshallabl()

interface PersonListener {
    fun onPerson(person: Person)
}

interface VIPListener {
    fun onPerson(person: Person)
}

class VIPClub: VIPListener {
    override fun onPerson(person: Person) {
        println("Welcome to the club, ${person.name}!")
    }
}

fun main(args: Array<String>) {
    ChronicleQueue.single("./build/duck").use { q ->
        val writer = q.acquireAppender()
                      .methodWriter(PersonListener::class.java)
        writer.onPerson(Person("Shaolang", 3))

        val club = VIPClub()
        val reader = q.createTailer().methodReader(club)

        reader.readOne()
    }
}

Notice that VIPClub implements VIPListener that happens to have the same onPerson method signature as PersonListener. When you run the above, you'll see Welcome to the club, Shaolang! printed.

Named Tailers

In all demonstrations so far, we've been creating anonymous tailers. Because they are anonymous, every (re-)run results in reading all excerpts in the queue. Sometimes, such behavior is acceptable, or even desirable, but there are times it doesn't. To pick up reading where it last stopped is done simply by naming the tailer:

package restartable

import net.openhft.chronicle.queue.ChronicleQueue
import net.openhft.chronicle.queue.ExcerptTailer

fun readQueue(tailerName: String, times: Int) {
    ChronicleQueue.single("./build/restartable").use { q ->
        val tailer = q.createTailer(tailerName)       // tailer name given

        for (_n in 1..times) {
          println("$tailerName: ${tailer.readText()}")
        }

        println()       // to separate outputs for easier visualization
    }
}

fun main(args: Array<String>) {
    ChronicleQueue.single("./build/restartable").use { q ->
        val appender = q.acquireAppender()
        appender.writeText("Test Message 1")
        appender.writeText("Test Message 2")
        appender.writeText("Test Message 3")
        appender.writeText("Test Message 4")
    }

    readQueue("foo", 1)
    readQueue("bar", 2)
    readQueue("foo", 3)
    readQueue("bar", 1)
}

Notice that the tailer's name is given to createTailer method. The code above has two tailers--unimaginatively named foo and bar--reading off the queue and outputs the following when run:

foo: Test Message 1

bar: Test Message 1
bar: Test Message 2

foo: Test Message 2
foo: Test Message 3
foo: Test Message 4

bar: Test Message 3

Notice that the second time foo and bar read from the queue, they pick up from where they've left previously.

Roll 'Em

Chronicle Queue rolls the file it uses based on the roll cycle defined when the queue is created; by default, it rolls the file daily. To change the roll cycle, we cannot use the simple ChronicleQueue.single
method anymore:

package roll

import net.openhft.chronicle.queue.ChronicleQueue
import net.openhft.chronicle.queue.RollCycles
import net.openhft.chronicle.impl.single.SingleChronicleQueueBuilder

fun main(args: Array<String>) {
    var qbuilder: SingleChronicleQueueBuilder = ChronicleQueue
            .singleBuilder("./build/roll")

    qbuilder.rollCycle(RollCycles.HOURLY)
    val q: ChronicleQueue = qbuilder.build()

    // code omitted for brevity
}

First, we get an instance of SingleChronicleQueueBuilder and set the roll cycle with .rollCycle method. The snippet above configures the queue to roll the file hourly. When we are happy with the configuration, call .build() on the builder to get an instantiated ChronicleQueue. Note that both appender and tailer(s) must use the same roll cycle when accessing the same queue.

As SingleChronicleQueueBuilder supports fluent interface, the code could also be simplified as follows:

val q: ChronicleQueue = ChronicleQueue.singleBuilder("./build/roll")
                                      .rollCycle(RollCycles.HOURLY)
                                      .build()

What's Next

This post covers Chronicle Queue terminology and basics. The following sites have more information to dig from:

Have fun!

This post Getting Started With Chronicle Queue first appeared on Bit by Bit

I wonder whether it's possible and make sense to combine the two to get the best of both worlds. ↩
As of this writing, Kotlin JVM compiler produces Java 6 compatible bytecode, as stated in https://kotlinlang.org/docs/reference/faq.html#what-does-kotlin-compile-down-to ↩
The code could be simplified further by replacing try-finally construct with Kotlin's equivalent of Java's try-with-resource syntax. ↩
Although it'll make more sense to run the appender and tailer in different VM processes, keeping both in the same VM makes it much simpler to understand the discussion without having to sieve through non-related code. ↩
At least as of Chronicle Queue version 5.19.x, it doesn't crash/throw any exceptions. ↩

Genetic Algorithm Basics

shaolang — Tue, 26 Nov 2019 06:23:34 +0000

Genetic algorithm is another branch of artificial intelligence that takes inspirations from Darwin's theory of evolution. Genetic algorithm is useful in solving optimization problems where a good-enough solution is acceptable as opposed to best solution. Good-enough because getting the best solution can take a long time or a lot of resources to compute. For example, genetic algorithm is useful for solving timetable scheduling and bin packing problems. Not to be confused with the similarly named Genetic programming, genetic algorithm uses lists/arrays extensively; genetic programming uses trees instead.

Building blocks

Candidate solutions are encoded as chromosomes (also known as individuals); each chromosome is made up of multiple genes that encode the solution-space. Genetic algorithm "evolves" a population of individuals by crossing over and mutating them towards an acceptable solution, much like the natural, biological world. The pseudocode for a basic algorithm is as follows:

population = create_random_population
while continue_evolution?(population)
  population_crossed = crossover(population)
  population_mutated = mutate(population_crossed)
  evaluate(population_mutated)
  population = population_mutated
end

The pseudocode shows two genetic operators in use: crossover and mutation. Crossover is the process of producing a child solution from two or more parent solutions (think breeding/mating). By combining portions of good solutions, the algorithm is likely able to produce better and better child solutions as generations pass (genetic-algorithm-speak for iterations). Mutation randomly changes some genes within the chromosome, thus creating genetic diversity in the population. However, when crossover and mutation rates are too high, fitter individuals might be lost during evolution; when rates are too low, potentially strong individuals might never enter the gene pool. Introducing elitism mitigates some effects of crossover and mutations. Elitism keeps a handful of the fittest individuals in the current generation untouched for interacting with individuals in the next generation.

Crossover

Crossover, also known as recombination, can be implemented in
several ways:

Uniform crossover: each gene in selected parents has equal probability in being inherited by the offspring, e.g., when there are two parents, each gene in the offspring has a 50/50 chance of coming from either parents.
Single-point crossover: a common point on both parents is picked randomly and the offspring will inherit the first parent's genes up till that point and the second's genes from that point onward as its genes, e.g., if the chromosome length is 10, and the common point randomly chosen is 7, the offspring will inherit the first 7 genes from the first parent and the last 3 genes from the second.
Two-point crossover: two common points on both parents are picked randomly and the offspring will inherit the genes within the two points from the first parent and the rest from the second, e.g., if the chromosome length is 10, and the common points are 3 and 6, the offspring will inherit the first 2 genes from the second parent, the next 4 genes from the first, and the remainder from the second parent.

Mutation

Mutation can be implemented in one of the following ways:

Flip bit: invert the gene's value, if it is encoded as ones and zeroes
Boundary: replace the gene with a random value between the specified upper and lower bound
Swap: swap the gene selected for mutation with another in the same chromosome; this implementation is useful when the chromosome cannot allow duplicate values/genes
Uniform: create a new (valid) individual with randomly initialized chromosome, and mutate (randomly) selected genes of the individual (not the newly created one) by taking genes from the newly created individual, e.g., if genes 1, 3, and 5 from an individual (ID1) are to be mutated, uniform mutation will take genes from 1, 3, and 5 from the newly created individual and substitute them at genes 1, 3, and 5 of the mutated ID1; it feels a little like uniform crossover, except that the offspring will take genes from the randomly-created individual when mutation_rate > rand

Genes and chromosomes

Genes can be encoded in any way that makes sense for the problem on hand, although they commonly are encoded numerically. For example, a binary-encoded chromosome could be created as follows:

chromosome_length = 100
chromosome = chromosome_length.times.map { |_| rand 2 }

The Ruby code above creates an array of length 100 with randomly generated numbers between 0s and 1s.

Based on the chromosome, the genetic algorithm will calculate the fitness of the individual, usually normalized to values between 0 and 1. The higher the fitness score, the better the individual is/the closer the program is to solving the problem. Survival of the fittest, if you'd like.¹

Selection

Selection is the process of choosing individuals from the population for crossover. Although elites are favored, they shouldn't be the only ones made available for crossovers; sometimes, genes of two seemingly weak individuals can create surprisingly fit offsprings.

Selection can be implemented in one of the following ways:

Fitness proportionate: individuals with higher fitness scores are more likely to be selected, e.g., a population of 4 individuals with fitness scores as [1, 2, 3, 4, 5], the first individual will only have 1/15 of a chance in getting chosen, but the last will have a 1/3 chance. This method is also known as roulette wheel selection.
Tournament: k individuals are selected randomly from the population, and they compete with one another in several "tournaments;" in deterministic tournament, the best/fittest among the selected is always chosen.

First toy example: All-ones

This toy example is taken from the book Genetic Algorithms in Java Basics, but implemented in Ruby.² This example shows how the basic blocks can be put together to solve problems with genetic algorithm; its goal is to evolve the individuals and stop when one of them whose chromosome contains genes that are all ones. Such trivial example do not require any other support classes/functions to work; those support classes/functions will distract the goal of understanding genetic algorithm implementations unnecessarily.

class Individual
  def Individual.of_length(length)
    Individual.new(length.times.map { |_| rand 2 })
  end

  attr_reader :chromosome, :fitness


  def initialize(chromosome)
    @chromosome = chromosome
  end


  def calc_fitness!
    @fitness = @chromosome.sum / @chromosome.size.to_f
  end


  def mate(spouse)
    offspring = @chromosome.zip(spouse.chromosome).   # pair up parents' genes
      map { |genes| genes[rand 2] }                   # randomly choose either one
    Individual.new offspring
  end


  def mutate(mutation_rate)
    mutated = @chromosome.map do |gene|
      # when mutation should happen, then
      #   when gene = 1, (1 - 1).abs => 0; when 0, (0 - 1).abs => 1
      mutation_rate > rand ? (gene - 1).abs : gene
    end

    Individual.new mutated
  end


  def <=>(other)
    -1 * (@fitness <=> other.fitness)
  end


  def to_s
    "#{@chromosome.join ''} (fitness: #{@fitness})"
  end
end

Individual largely keeps track of the chromosome and its fitness. Specific to genetic algorithms are calc_fitness, mate, and mutate functions. calc_fitness simply 1 divide the sum of the chromosome, so nothing really to see here.

mate is the method used in crossovers; it accepts another Individual instance:

Pairs up the parents' genes (e.g., if parents' genes were [1, 2], and [3, 4], [1, 2].zip [3, 4] returns [[1, 3], [2, 4]]
Chooses randomly from the pairs of genes in the block given to map
Creates and returns the offspring with the new genes

mutate is given the mutation rate, and it simply run through the entire chromosome and flip bit the gene when mutation_rate > rand.

<=> overrides the comparison to allow sorting fitness in descending order.

class Population
  def Population.of_size(size, chromosome_length)
    Population.new(size.times.map { |_| Individual.of_length chromosome_length})
  end


  def initialize(individuals)
    @individuals = individuals
  end


  def eval_individuals!
    @individuals.each { |i| i.calc_fitness! }
    @individuals.sort!
    @population_fitness = @individuals.map { |i| i.fitness }.sum
  end


  def crossover_individuals(crossover_rate, elitism_count)
    elites = @individuals.take elitism_count                      # keep elites for next gen
    crossed = @individuals[elitism_count..].map do |individual|   # cross the rest
      if crossover_rate > rand
        spouse = select_parent    # helper method
        individual.mate spouse
      else
        individual
      end
    end

    Population.new(elites + crossed)
  end


  def mutate_individuals(mutation_rate, elitism_count)
    elites = @individuals.take elitism_count
    mutated = @individuals[elitism_count..].map do |individual|
      individual.mutate mutation_rate
    end

    Population.new(elites + mutated)
  end


  def fittest
    @individuals[0]
  end


  private
  def select_parent
    roulette_wheel_pos = rand * @population_fitness
    spin_wheel_pos = 0

    for individual in @individuals
      spin_wheel_pos += individual.fitness

      return individual if spin_wheel_pos >= roulette_wheel_pos
    end

    @individuals[-1]  # return last individual if for-loop completes its run
  end
end

Population is the "container" for individuals, that has a class method to create a population with randomly initialized individuals (delegating to Individual.of_length). Both crossover_individuals and mutate_individuals methods are given the elitism_count parameter, so as to ensure the preservation of elites for the next generation (refer back to Building blocks for info).

crossover_individuals calls the private select_parent when it needs to select a parent for crossover with the current individual it is looping over. select_parent uses the fitness proportionate selection method to select the parent. Notice that the individuals available for selection include the elites (as evident on line 100 for individual in @individuals in select_parent method).

mutate_individuals simply loops through @individuals and delegates the mutation to the individual's mutate method.

eval_individuals makes all individuals to calculate their own fitness, and it also calculates the population's overall fitness (tracked by @population_fitness instance variable). Normally, there isn't a need to keep track of the population's fitness; the need arises because fitness proportionate selection method used in select_parent needs to know the population's overall fitness to function.

if __FILE__ == $PROGRAM_NAME
  mutation_rate = 0.01
  crossover_rate = 0.95
  elitism_count = 3
  population_size = 100
  chromosome_length = 50

  population = Population.of_size population_size, chromosome_length
  population.eval_individuals!

  curr_generation = 1

  while population.fittest.fitness < 1.0
    puts "Generation #{curr_generation} fittest: #{population.fittest}"

    next_gen = population.crossover_individuals crossover_rate, elitism_count
    next_gen = next_gen.mutate_individuals mutation_rate, elitism_count
    next_gen.eval_individuals!

    population = next_gen
    curr_generation += 1
  end

  puts "Solution found in generation #{curr_generation}"
  puts population.fittest
end

The main program ties both Population and Individual up by implementing the pseudocode as outlined in Building blocks (except the addition of outputting the current fittest in the loop, and the fittest at the end of the program). With the given values to mutation_rate, crossover_rate and elitism_count, the program should arrive at the solution within 400 to 600 generations most of the time.

Real-world example: Class scheduling

Another example borrowed from the book but with a much simpler implementation: the algorithm attempts to generate a class schedule that meets the following hard criteria:

Room must be able to fit in all students from the student group (assuming full-attendance)
No room is double-booked for each timeslot
No professor is teaching in any two sessions at the same time

Soft criteria such as ensuring the professor should not teach more than 2 consecutive sessions a day are not covered to simplify the discussion. By not catering for soft criteria, the algorithm does not account for the quality of the solutions found.

ROOMS = {1 => {name: 'A1', capacity: 15},
         2 => {name: 'B1', capacity: 30},
         4 => {name: 'D1', capacity: 20},
         5 => {name: 'F1', capacity: 25}}

SLOTS = {1  => 'Mon 09:00 - 11:00',
         2  => 'Mon 11:00 - 13:00',
         3  => 'Mon 13:00 - 15:00',
         4  => 'Tue 09:00 - 11:00',
         5  => 'Tue 11:00 - 13:00',
         6  => 'Tue 13:00 - 15:00',
         7  => 'Wed 09:00 - 11:00',
         8  => 'Wed 11:00 - 13:00',
         9  => 'Wed 13:00 - 15:00',
         10 => 'Thu 09:00 - 11:00',
         11 => 'Thu 11:00 - 13:00',
         12 => 'Thu 13:00 - 15:00',
         13 => 'Fri 09:00 - 11:00',
         14 => 'Fri 11:00 - 13:00',
         15 => 'Fri 13:00 - 15:00'}

PROFESSORS = {1 => 'Dr P Smith',
              2 => 'Mrs E Mitchell',
              3 => 'Dr R Williams',
              4 => 'Mr A Thompson'}

MODULES = {1 => {name: 'Computer Science',  professors: [1, 2]},
           2 => {name: 'English',           professors: [1, 3]},
           3 => {name: 'Maths',             professors: [1, 2]},
           4 => {name: 'Physics',           professors: [3, 4]},
           5 => {name: 'History',           professors: [4]},
           6 => {name: 'Drama',             professors: [1, 4]}}

STUDENT_GROUPS = {1  => {size: 10, modules: [1, 3, 4]},
                  2  => {size: 30, modules: [2, 3, 5, 6]},
                  3  => {size: 18, modules: [3, 4, 5]},
                  4  => {size: 25, modules: [1, 4]},
                  5  => {size: 20, modules: [2, 3, 5]},
                  6  => {size: 22, modules: [1, 4, 5]},
                  7  => {size: 16, modules: [1, 3]},
                  8  => {size: 18, modules: [2, 6]},
                  9  => {size: 24, modules: [1, 6]},
                  10 => {size: 25, modules: [3, 4]}}

SESSIONS = STUDENT_GROUPS.map do |kv|
  sg_id = kv[0]
  size = kv[1][:size]
  kv[1][:modules].map { |m| {sg_id: sg_id, size: size, module: m} }
end.reduce(:+)

To keep things really simple, the data are hard-coded as maps. The last line calculates the total number of sessions the algorithm needs to work out. professors key in MODULES lists the professors (by ID) that can teach that module; similarly, modules key in STUDENT_GROUPS lists the modules that group is taking.

SESSIONS translates STUDENT_GROUPS into (class) sessions that needed to be conducted, e.g., the algorithm needs to schedule 3 sessions for student group 1: one for Computer Science, one for Maths, and one for Physics.

def random_room
  ROOMS.keys[rand ROOMS.size]
end


def random_slot
  SLOTS.keys[rand SLOTS.size]
end


def random_professor(sess_id)
  mod_id = SESSIONS[sess_id][:module]
  professors = MODULES[mod_id][:professors]
  professors[rand professors.size]
end

The above are helper functions for randomly choosing timeslot, and professor. When choosing a professor randomly, the function needs to know for which module's list of professors it need to look at.

class Individual
  GENE_GROUP_SIZE = 3
  ROOM_IX, SLOT_IX, PROF_IX = GENE_GROUP_SIZE.times.to_a

  def Individual.random_schedule
    Individual.new(SESSIONS.size.times.map do |sess_id|
      mod_id = SESSIONS[sess_id][:module]
      [random_room, random_slot, random_professor(mod_id)]
    end.reduce(:+))
  end


  attr_reader :chromosome, :fitness


  def initialize(chromosome)
    @chromosome = chromosome
  end


  def calc_fitness
    gene_groups = to_gene_groups(@chromosome)
    clashes = from_room_capacity_vs_group_size gene_groups
    clashes += from_room_availability gene_groups
    clashes += from_professor_availability gene_groups

    @fitness = 1.0 / (clashes + 1)
  end


  def mate(spouse)
    offspring = @chromosome.zip(spouse.chromosome).map do |genes|
      genes[rand 2]
    end

    Individual.new offspring
  end


  def mutate(mutation_rate)
    other = Individual.random_schedule
    mutated = @chromosome.zip(other.chromosome).map do |genes|
      genes[mutation_rate > rand ? 1 : 0]
    end

    Individual.new mutated
  end


  def to_s
    schedule = to_gene_groups(@chromosome).map do |v|
      sess, i = v
      room = "Room #{ROOMS[sess[ROOM_IX]][:name]}"
      slot = SLOTS[sess[SLOT_IX]]
      professor = PROFESSORS[sess[PROF_IX]]
      mod = MODULES[SESSIONS[i][:module]][:name]
      sg_id = SESSIONS[i][:sg_id]

      [sg_id, slot, mod, room, professor]
    end.sort.map do |s|
      s.join ','
    end.join "\n"

    "Schedule fitness #{@fitness}\n#{schedule}"
  end


  def <=>(other)
    -1 * (@fitness <=> other.fitness)
  end


  private
  def to_gene_groups(chromosome)
    chromosome.each_slice(GENE_GROUP_SIZE).zip SESSIONS.size.times.to_a
  end


  def from_room_capacity_vs_group_size(gene_groups)
    gene_groups.map do |gg|
      sess, i = gg
      room_capacity = ROOMS[sess[ROOM_IX]][:capacity]
      group_size = SESSIONS[i][:size]
      room_capacity < group_size ? 1: 0
    end.sum
  end


  def from_room_availability(gene_groups)
    gene_groups.map do |gg|
      target = [gg[ROOM_IX], gg[SLOT_IX]]

      # must divide by 2, 'cos the following will always count itself once
      gene_groups.map { |x| [x[ROOM_IX], x[SLOT_IX]] == target ? 1 : 0 }.sum / 2
    end.sum
  end


  def from_professor_availability(gene_groups)
    gene_groups.map do |gg|
      target = [gg[PROF_IX], gg[SLOT_IX]]

      # must divide by 2, 'cos the following will always count itself once
      gene_groups.map { |x| [x[PROF_IX], x[SLOT_IX]] == target ? 1 : 0 }.sum / 2
    end.sum
  end
end

Woah! This Individual implementation is huge! Let's break that down. The three biggest changes to Individual are how it creates a random individual, how it calculates its fitness, and how it mutates. Or put another way, only its mate method is identical to the toy example's.

Unlike the toy example, the chromosome cannot be examined in isolation: the entire chromosome needs to be examined in groups of 3 (evident at lines 2 and 3) where:

First gene in group represents the room ID
Second gene represents the timeslot ID
Third represents the professor ID

Each group corresponds to the (class) session in SESSIONS. For simplicity in discussion, we'll call each group a gene group.

Individual.random_schedule uses the helper functions to generate the chromosome, and those helper functions ensure that the genes are always correct. Individual.random_schedule can't just do a rand(n) + 1 for each gene, as IDs in the hard-coded data aren't always in running order, e.g., there is no room ID 3. Such rigorous control ensures that all chromosomes are valid (even if they contain clashes).

Because of the need to ensure the chromosomes are valid, mutate uses uniform mutation (refer to description covered in mutation); it creates a valid random individual and uses that individual's genes at place where mutation should occur.

calc_fitness (seemingly) has the most complicated change: by examining all gene groups in the chromosome, it determines the number of clashes (or if you'd like, breaks in hard constraints) by calling the private helper methods from_room_capacity_vs_group_size, from_room_availability, and from_professor_availability. As highlighted in the code comments on lines 165 and 174, clashes counted in the latter two methods must be divided by two, as the counts include the (target) session itself. The code makes use of Ruby's integral division round-down behavior: Ruby returns 0 for the expression 1 / 2, 1 for 2 / 2 and 3 / 2. When there are 2 or more counts of the same constraint, we don't really care whether there are 2 or 3 or more breaks, thus Ruby's round-down behavior is good enough to account for the breaks.

class Population
  def Population.random_schedules(pop_size)
    Population.new(pop_size.times.map { |_| Individual.random_schedule })
  end


  def initialize(individuals)
    @individuals = individuals
  end


  def eval_individuals!
    @individuals.each { |i| i.calc_fitness }
    @individuals = @individuals.sort
  end


  def crossover_individuals!(crossover_rate, elitism_count, tournament_size)
    elites = @individuals.take elitism_count
    crossed = @individuals[elitism_count..].map do |i|
      if crossover_rate > rand
        i.mate select_parent(tournament_size)
      else
        i
      end
    end

    Population.new(elites + crossed)
  end


  def mutate_individuals!(mutation_rate, elitism_count)
    elites = @individuals.take elitism_count
    mutated = @individuals[elitism_count..].map { |i| i.mutate mutation_rate }

    Population.new(elites + mutated)
  end


  def fittest
    @individuals[0]
  end


  private
  def select_parent(tournament_size)
    candidates = @individuals.shuffle.take tournament_size
    candidates.sort[0]
  end
end

The main difference in Population is select_parent employs deterministic tournament selection (refer to description in Selection).

if __FILE__ == $PROGRAM_NAME
  pop_size = 100
  mutation_rate = 0.01
  crossover_rate = 0.9
  elitism_count = 2
  tournament_size = 5
  max_generations = 1000
  curr_gen = 1

  population = Population.random_schedules pop_size
  population.eval_individuals!


  while curr_gen < max_generations && population.fittest.fitness < 1.0
    puts "Generation #{curr_gen} fittest: #{population.fittest.fitness}"

    next_gen = population.crossover_individuals!(crossover_rate, elitism_count,
                                                 tournament_size)
    population = next_gen.mutate_individuals! mutation_rate, elitism_count
    population.eval_individuals!

    curr_gen += 1
  end

  puts "Best solution found: #{population.fittest}"
end

The main program is largely the same, except the introduction of tournament_size that is used in selecting parents for crossovers. The following shows one possibility of the schedule (reformatted for the web):

 1, Fri 09:00 - 11:00, Maths,            Room B1, Dr R Williams
 1, Mon 13:00 - 15:00, Physics,          Room D1, Mrs E Mitchell
 1, Tue 09:00 - 11:00, Computer Science, Room D1, Dr P Smith
 2, Fri 09:00 - 11:00, History,          Room B1, Mr A Thompson
 2, Mon 11:00 - 13:00, English,          Room B1, Mr A Thompson
 2, Mon 13:00 - 15:00, Drama,            Room B1, Mr A Thompson
 2, Wed 11:00 - 13:00, Maths,            Room B1, Dr P Smith
 3, Mon 13:00 - 15:00, History,          Room D1, Mr A Thompson
 3, Tue 13:00 - 15:00, Maths,            Room B1, Dr P Smith
 3, Wed 09:00 - 11:00, Physics,          Room D1, Dr P Smith
 4, Tue 13:00 - 15:00, Computer Science, Room B1, Dr P Smith
 4, Wed 09:00 - 11:00, Physics,          Room F1, Dr P Smith
 5, Thu 11:00 - 13:00, History,          Room D1, Mr A Thompson
 5, Thu 11:00 - 13:00, Maths,            Room B1, Dr P Smith
 5, Wed 11:00 - 13:00, English,          Room D1, Mr A Thompson
 6, Thu 11:00 - 13:00, Computer Science, Room B1, Mrs E Mitchell
 6, Tue 09:00 - 11:00, History,          Room F1, Mr A Thompson
 6, Tue 09:00 - 11:00, Physics,          Room B1, Mrs E Mitchell
 7, Fri 13:00 - 15:00, Maths,            Room D1, Dr P Smith
 7, Tue 09:00 - 11:00, Computer Science, Room D1, Dr P Smith
 8, Thu 13:00 - 15:00, English,          Room F1, Mr A Thompson
 8, Tue 09:00 - 11:00, Drama,            Room D1, Mr A Thompson
 9, Mon 13:00 - 15:00, Drama,            Room B1, Mr A Thompson
 9, Tue 13:00 - 15:00, Computer Science, Room F1, Mrs E Mitchell
10, Fri 09:00 - 11:00, Maths,            Room F1, Dr R Williams
10, Thu 09:00 - 11:00, Physics,          Room B1, Mrs E Mitchell

As mentioned, soft criteria are not accounted for by this algorithm, but implementing requires a slight change in calculating the individual's fitness:

Breaks in hard criteria attract large negative scores, e.g., -100 for each break
Breaks in soft criteria attract small positive scores, e.g., +1 for each break

Care must be taken for such scoring method to ensure points from soft criteria do not cancel out points from hard ones, e.g., 1 hard break (-100 points) is not cancelled out by 100 soft breaks (+100 points). When soft criteria are included, the fitness score may not necessarily be 1 because the (fittest) solution may not meet all soft criteria, but solutions that consider soft criteria definitely differ from one other in terms of quality: a solution with fitness 0.5 (one soft break) is better than another with fitness 0.33 (two soft breaks).

Last note on crossovers

As the two examples above use uniform crossover, let's touch a bit on single-point crossover. What follows is equally applicable to two-point crossover.

The algorithm cannot simply choose any point in the chromosome for single-point crossover, as that may break the chromosome's validity. As seen in the class scheduling example, genes should be viewed in groups of three. Therefore, the following implementation is wrong:

def mate(spouse)
  common_point = rand @chromosome.size    # NO!
  offspring = @chromosome.take(common_point) + spouse.chromosome[common_point..]
  Individual.new offspring
end

Assuming rand @chromosome.size returns 1, this implementation of mate will likely invalidate the first three genes that should be viewed as a group.

The following shows the correct implementation that crosses over the genes in gene groups:

def mate(spouse)
  groups = @chromosome.size / GENE_GROUP_SIZE     # assuming GENE_GROUP_SIZE = 3
  common_point = rand(groups) * GENE_GROUP_SIZE
  offspring = @chromosome.take(common_point) + spouse.chromosome[common_point..]
  Individual.new offspring
end

Closing thoughts

Genetic algorithms aren't that difficult, considering that the class schedule example has only 255 LOC. Adding optimizations such as fitness calculation memoization, adaptive algorithms³ will probably add another 10 - 100 LOC, but even so, it's doing so much with so little code.

While genetic algorithm isn't as "sexy" as machine learning, it's definitely one useful tool for solving optimization problems.

This post Genetic Algorithms Basics first appeared first on Bit by Bit

Herbert Spencer coined this phrase after reading Charles Darwin's On the Origin of Species. This phrase is best understood as "survival of the form that will leave the most copies of itself in successive generations." On a side note, the other oft-heard phrase "[i]t is not the strongest of the species that survives, nor the most intelligent, but the one most adaptable to change" did not originate from Charles Darwin. A Louisiana State University business professor, Leon C. Megginson, first used that phrase--his idiosyncratic interpretation on Darwin's On the Origin of Species--at a convention in 1963. ↩
Because the overly verbose Java syntax masks the otherwise simple concepts of genetic algorithm. Other than the difference in language choice, the following also reorganizes the code to make it more cohesive and simpler to understand (the book's insistence in create a specific GeneticAlgorithm class hurts cohesiveness big time). ↩
Adaptive genetic algorithm tunes various parameters (mutation rate, crossover rate, etc) based on the state of the algorithm, e.g., it increases the mutation rate to encourage increasing the gene pool diversity when it detects very little difference between the individuals. ↩

Ranking Data in MSExcel

shaolang — Fri, 16 Aug 2019 16:56:40 +0000

MSExcel, despite its bad name for data analysis, can still be a very good tool to reach out to for one-off analysis jobs, especially when the output needs to be interactive. After all, nothing comes close to the reactivity -- as in reactive programming -- simple MSExcel formulae provide that do not require hardcore development skills.¹

Getting our hands dirty

Let's say the requirement is to rank the customers' YTD Trade Count and MTD Trade Count. One method is to do that by hand:

	A	B	C
1	Customer	YTD Trade Count	MTD Trade Count
2	ABC	190	7
3	DEF	288	38
4	GHI	69	32
5	JKL	168	38
6
7
8
9	Customer	YTD Rank	MTD Rank
10	ABC	2nd	4th
10	DEF	1st	1st
11	GHI	4th	3rd
12	JKL	3rd	1st

Yeah, it works! But if the number of customers is in the hundreds, doing it by hand is a huge waste of time. We can do better than that.

MSExcel has one handy function LARGE² which the official documentation says:

Returns the k-th largest value in a data set. You can use this function to select a value based on its relative standing. For example, you can use LARGE to return the highest, runner-up, or third-place score.

and its syntax:

LARGE(array, k)

The LARGE function syntax has the following arguments:

Array Required. The array or range of data for which you want to determine the k-th largest value.

K Required. The position (from the largest) in the array or cell range of data to return.

Great! Type out the formula =LARGE(B$2:B$5,ROW()-9), copy and paste it across the range B10:C13, and we'll get:

	A	B	C
1	Customer	YTD Trade Count	MTD Trade Count
2	ABC	190	7
3	DEF	288	38
4	GHI	69	32
5	JKL	168	38
6
7
8
9	Customer	YTD Rank	MTD Rank
10	ABC	2nd	4th
10	DEF	1st	1st
11	GHI	4th	3rd
12	JKL	3rd	1st
13
14
15
16		YTD Ordered	MTD Ordered
17		=LARGE(B$2:B$5,ROW()-16)	=LARGE(C$2:C$5,ROW()-16)
18		=LARGE(B$2:B$5,ROW()-16)	=LARGE(C$2:C$5,ROW()-16)
19		=LARGE(B$2:B$5,ROW()-16)	=LARGE(C$2:C$5,ROW()-16)
20		=LARGE(B$2:B$5,ROW()-16)	=LARGE(C$2:C$5,ROW()-16)

And that yields the following:

	A	B	C
1	Customer	YTD Trade Count	MTD Trade Count
2	ABC	190	7
3	DEF	288	38
4	GHI	69	32
5	JKL	168	38

	...	...	...

16		YTD Ordered	MTD Ordered
17		288	38
18		190	38
19		168	32
20		69	7

ROW() returns the row number of the cell the function is applied to, thus ROW()-16 at B17 signals to LARGE to return the first largest value; at B18 to return second largest...

Although that simply sorts the two columns in descending order, it beats the manual steps in the following ways:

Typing out the formula, copy and paste takes only 2 steps, but manual sorting takes 4:
1. Copy values from B2:B5 and paste them at B17:B20
2. Sort values in B17:B20
3. Copy values from C2:C5 and paste them at C17:C20
4. Sort values in C17:C20
MSExcel automatically apply the ordering when any values in B2:C5 change

Type out the rank at column D (actually, for ranks 4th and beyond, using the formula =ROW()-15&"th" can save some typing with some copy & paste laziness):

	B	C	D
16	YTD Ordered	MTD Ordered	Rank
17	288	38	1st
18	190	38	2nd
19	168	32	3rd
20	69	7	4th

Replace the hand-coded rank at cell B10 with the formula =VLOOKUP(B2,B$17:$D$17,5-COLUMN(),FALSE), then copy and paste the cell across B10:C12 yields the same result to the do-by-hand version but with an important advantage: any changes to the values in B2:C5 automatically refresh the ranks.

COLUMN returns the column number the function is applied to. The 5-COLUMN() fragment in the VLOOKUP formula is to determine automatically the lookup index. For example, at cell B10, 5-COLUMN() resolves to 3, at cell C10 resolves to 2.

Wrapping up

With no coding, some creative use of MSExcel functions, and lots of copy-and-paste, MSExcel's efficiency is unbeatable. Yes, using pandas or R makes the work reproducible, but sometimes not everything is a nail. MSExcel has its place in data analysis; knowing what tool to use appropriately is far more important and flexing the scripting muscles.

This post Ranking Data in MSExcel first appeared first on Bit by Bit

How many data analysts understand reactive programming? My unscientific survey says "not many." ↩
The counterpart to LARGE is SMALL ↩

Property-Based Testing: From Erlang/Elixir to Clojure

shaolang — Mon, 12 Aug 2019 02:33:20 +0000

Reading Property-Based Testing with PropEr, Erlang, and Elixir and following along the examples helped me in learning this exciting testing methodology; but it also left me wondering: have I really absorbed and internalized just by following along?

So, I reached out to Fred, got his approval, and started translating the code from Erlang/Elixir to Clojure with test.check. All the code done [so far] are hosted at https://github.com/shaolang/pbtic I'm using test.check as the property-based testing tool in Clojure.

Birthday Greeting Kata

The book breaks up the kata into 4 parts: CSV parsing, records filtering, employee module (bridging CSV parsing and records filtering), and email templating.

CSV Parsing

(ns pbtic.birthday.csv-test
  (:require [clojure.test :refer [deftest is]]
            [clojure.test.check.clojure-test :refer [defspec]]
            [clojure.test.check.generators :as gen]
            [clojure.test.check.properties :refer [for-all]]
            [pbtic.birthday.csv :as csv]))

;;;;;;;
;; defs

(def ^:private text-data
  (str "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
       ":;<=>?@ !#$%&'()*+-./[\\]^_`{|}~"))

;;;;;;;;;;;;;
;; generators

(defn- text [cs]
  (gen/let [xs (gen/list (gen/elements cs))]
    (apply str xs)))

(def unquoted-text (text text-data))
(def quotable-text (text (str text-data "\r\n\",")))


(def field (gen/one-of [unquoted-text, quotable-text]))


(def header (partial gen/vector field))
(def record (partial gen/vector field))


(defn entry [size ks]
  (gen/let [vs  (record size)]
    (zipmap ks vs)))


(def csv-source
  (gen/let [size    gen/pos-int
            ks      (header (inc size))]
    (gen/list (entry (inc size) ks))))

Unlike ?LET/let in PropEr/PropCheck,
clojure.test.check.generators/let can have multiple bindings where the binding after can reference the value of the one before, as shown at lines 39 and 40.

csv-source generates a list of maps, where each map is one record from the CSV source, and the keys of each map the header record. While it's idiomatic for Clojure maps to use keywords as keys to maps, the book recommends keeping the CSV parsing focused on encoding/decoding and not bring in any business requirements to keep the module/namespace maintainable.

;;;;;;;;;;;;;
;; properties

(defspec roundtrip-encoding-decoding
  (for-all [maps  csv-source]
    (= maps (csv/decode (csv/encode maps)))))

;;;;;;;;
;; tests

(deftest one-column-csv-files-are-inherently-ambiguous
  (is (= "\r\n\r\n\r\n"
         (csv/encode [{"" ""}, {"" ""}])))

  (is (= [{"" ""}]
         (csv/decode "\r\n\r\n"))))


(deftest one-record-per-line
  (is (= [{"aaa" "zzz", "bbb" "yyy", "ccc" "xxx"}]
         (csv/decode "aaa,bbb,ccc\r\nzzz,yyy,xxx\r\n"))))


(deftest optional-trailing-crlf
  (is (= [{"aaa" "zzz", "bbb" "yyy", "ccc" "xxx"}]
         (csv/decode "aaa,bbb,ccc\r\nzzz,yyy,xxx"))))


(deftest double-quotes
  (is (= [{"aaa" "zzz", "bbb" "yyy", "ccc" "xxx"}]
         (csv/decode "\"aaa\",\"bbb\",\"ccc\"\r\n\"zzz\",\"yyy\",\"xxx\""))))


(deftest escape-crlf
  (is (= [{"aaa" "zzz", "b\r\nbb" "yyy", "ccc" "xxx"}]
         (csv/decode "\"aaa\",\"b\r\nbb\",\"ccc\"\r\nzzz,yyy,xxx"))))


(deftest double-quotes-escaping
  (is (= [{"aaa" "", "b\"bb" "", "ccc" ""}]
         (csv/decode "\"aaa\",\"b\"\"bb\",\"ccc\"\r\n,,"))))


(deftest dupe-keys-unsupported
  (let [csv     (str "field_name,field_name,field_name\r\n"
                     "aaa,bbb,ccc\r\n"
                     "zzz,yyy,xxx\r\n")
        [m1 m2] (csv/decode csv)]
    (is (= ["field_name"] (keys m1)))
    (is (= ["field_name"] (keys m2)))))

The property and tests straight-up mirror the original code in the book. But the implementation? LOL, I took the shortcut by using data.csv instead, as my main intention is to learn how to write property tests, not implementing a CSV parser.

(ns pbtic.birthday.csv
  (:require [clojure.data.csv :as csv]
            [clojure.string :as str]))

(defn encode [ms]
  (let [ks    (-> ms first keys)
        vs    (map vals ms)
        out   (java.io.StringWriter.)]
    (csv/write-csv out (conj vs ks) :newline :cr+lf)
    (.toString out)))


(defn decode [s]
  (let [[header & body] (csv/read-csv (java.io.StringReader. s))]
    (map (partial zipmap header) body)))

Records Filtering

Records filtering module/namespace filters the employees whose birthdays fall on the given date. Although properties are the new-found power, employing them for this instance might not be suitable, as property tests are probabilistic at their core. "Traditional" unit tests can explore this problem space much better. Even so, Fred suggests running an exhaustive search to cover all possible cases, using generators in property-based tests as inspiration in "generating" the cases.

(ns pbtic.birthday.bday-filter-test
  (:require [pbtic.birthday.bday-filter :as filter :refer [month-day]]
            [clojure.set :as set]
            [clojure.test :refer [deftest is]])
  (:import [java.time DateTimeException LocalDate]))

;;;;;;;;;;
;; helpers

(defn find-birthdays-for-year [people yeardata]
  (when (seq yeardata)
    (let [[day & year]  yeardata
          found         (filter/birthday people day)]   ;; <- function being tested
      (assoc (find-birthdays-for-year people year) day found))))


(defn generate-year-data [start]
  (let [start-date  (LocalDate/of start 1 1)
        end-date    (LocalDate/of (inc start) 1 1)]
    (into [] (.. start-date (datesUntil end-date) toArray))))


(defn generate-years-data [start end]
  (mapv generate-year-data (range start (inc end))))


(defn rand-name []
  (apply str (repeatedly 30 #(rand-nth "abcdefghijklmnopqrstuvwxyz"))))


(defn people-for-date [date]
  (try
    (let [[month day] (month-day date)
          rand-year   (+ 1900 (rand-int 100))]
      {:name          (rand-name)
       :date-of-birth (LocalDate/of rand-year month day)})
    (catch Exception _ (people-for-date date))))


(defn people-for-year [year]
  (map people-for-date year))


(defn generate-people-for-year [n]
  (let [year-seed (generate-year-data 2016)]  ;; leap year so all days are covered
    (mapcat (fn [_] (people-for-year year-seed)) (range n))))

;;;;;;;;;;;;;
;; assertions

(defn every-birthday-once [people birthdays]
  (let [found       (mapcat second birthdays)
        not-found   (set/difference (set people) (set found))]
    (is (empty? not-found))
    (is (zero? (- (count found) (count (set found)))))))


(defn on-right-date [people birthdays]
  (doseq [[date found]            birthdays
          {:keys [date-of-birth]} found]
    (let [[dob-month dob-day] (month-day date-of-birth)]
      (try
        (LocalDate/of (.getYear date) dob-month dob-day)
        (is (= (month-day date)
               (month-day date-of-birth)))
        (catch DateTimeException _ true)))))

;;;;;;;
;; test

(deftest property-style-filtering
  (let [years   (generate-years-data 2018 2038)
        people  (generate-people-for-year 3)]
    (doseq [yeardata years]
      (let [birthdays (find-birthdays-for-year people yeardata)]
        (every-birthday-once people birthdays)
        (on-right-date people birthdays)))))

The differences between this and the original are:

generate-year-data (lines 17-20) is significantly shorter than the original, as it uses java.time.LocalDate#datesUntil method to generate the dates. The Elixir version in the book is long probably because Fred wanted to align it with the Erlang version; if he were to use Elixir's Date.range/2 function (no equivalent available in Erlang 😭), the code would be much shorter, as shown below:

defp generate_year_data(year) do
  {:ok, start_date} = Date.new(year, 1, 1)
  {:ok, end_date} = Date.new(year, 12, 31)

  Date.range(start_date, end_date)
  |> Enum.into([])
end

rand-name (lines 27-28) is a simple stand-in for Erlang's make-ref/0.
every-birthday-once (line 51-55) uses the set data structure to determine the set of people not found.
on-right-date (lines 58-66) catches invalid dates and returns true in the catch clause to signify "skipping," as Clojure does not use pattern-matching as much as Erlang/Elixir do.

The implementation of pbtic.birthday.bday-filter is as follows:

(ns pbtic.birthday.bday-filter)


(def month-day (juxt #(.getMonthValue %) #(.getDayOfMonth %)))


(defn birthday-no-leap-year-handling [people date]
  (let [md (month-day date)]
    (filter #(= (month-day (:date-of-birth %)) md) people)))


(defn  filter-dob [people month day]
  (filter #(= (month-day (:date-of-birth %)) [month day]) people))


(defn birthday [people date]
  (let [[month day] (month-day date)]
    (if (and (= [month day] [2 28]) (not (.isLeapYear date)))
      (concat (filter-dob people 2 28) (filter-dob people 2 29))
      (filter-dob people month day))))

birthday-no-leap-year-handling (lines 7-9) shows how the code looks like prior to handling of 29 Feb birthdays on non-leap year (the company shouldn't only wish them happy birthday once every four years, should they?).

Employee Module

The namespace to rule them all 💍; it brings pbtic.birthday.csv and pbtic.birthday.bday-filter together. Functions in this namespace implement business requirements that other namespace may not have already, e.g., the CSV parser in pbtic.birthday.csv.

(ns pbtic.birthday.employee-test
  (:require [clojure.string :as str]
            [clojure.test.check.clojure-test :refer [defspec]]
            [clojure.test.check.generators :as gen]
            [clojure.test.check.properties :refer [for-all]]
            [pbtic.birthday.csv-test :as csv-test]
            [pbtic.birthday.employee :as employee])
  (:import [java.time LocalDate]))

;;;;;;;
;; defs

(def start-date (LocalDate/of 1900 1 1))

(def max-days (.. start-date
                  (until (LocalDate/of 2021 1 1))
                  getDays))

;;;;;;;;;;;;;
;; generators

(def text-date
  (gen/let [days-to-add (gen/choose 0 max-days)]
    (let [date (.plusDays start-date days-to-add)]
      (format " %4d/%02d/%02d"
              (.getYear date)
              (.getMonthValue date)
              (.getDayOfMonth date)))))


(def whitespaced-text
  (gen/let [txt csv-test/field]
    (str " " txt)))


(def raw-employee-map
  (gen/let [val-list (gen/tuple csv-test/field
                                whitespaced-text
                                text-date
                                whitespaced-text)]
    (zipmap ["last_name", " first_name", " date_of_birth", " email"] val-list)))

;;;;;;;;;;;;;
;; properties

(defspec check-that-leading-space-is-fixed
  (for-all [m raw-employee-map]
    (let [emp (employee/adapt-csv-result m)]
      (every? #(not (str/starts-with? (name %) " "))
              (concat (keys emp)
                      (filter string? (vals emp)))))))


(defspec check-that-date-is-formatted-right
  (for-all [m raw-employee-map]
    (let [m (employee/adapt-csv-result m)]
      (= (type (get m :date-of-birth)) LocalDate))))

Taking Fred's advice on reworking a restriction into a transformation when creating custom generators (refer to Imposing Restrictions subsection under Basic Custom Generators in chapter 4 of the book), text-date (lines 22-28) ditches gen/such-that and goes for a transformation that adds days to a known start date (1900-01-01). Although this is not a pure code-porting, it shows how re-imagining the problem on-hand is not that all difficult.

(ns pbtic.birthday.employee
  (:require [clojure.string :as str]
            [pbtic.birthday.bday-filter :as bday-filter]
            [pbtic.birthday.csv :as csv])
  (:import [java.time LocalDate]
           [java.time.format DateTimeFormatter]))

;;;;;;;
;; defs

(def ^:private datetime-formatter (DateTimeFormatter/ofPattern "yyyy/MM/dd"))

;;;;;;;;;;;;;
;; public API

(defn adapt-csv-result [m]
  (let [ks  (sequence (comp (map str/triml)
                            (map #(str/replace % #"_" "-"))
                            (map keyword))
                      (keys m))
        m   (zipmap ks (map str/triml (vals m)))
        dob (:date-of-birth m)]
    (assoc m :date-of-birth (LocalDate/parse dob datetime-formatter))))


(defn from-csv [s]
  (map adapt-csv-result (csv/decode s)))


;; parameter order is different from the book's
(defn filter-birthday [date employees]
  (bday-filter/birthday employees date))

pbtic.birthday.employee namespace does not implement "accessors" because of the keyword-izing of keys at line 19 because of Clojure's idiom on using keywords to retrieve values from maps (line 22 shows one such example). The other change is the swapping of the parameters in filter-birthday (lines 31-32); this makes the function more easily usable with the ->> threading macro; Elixir |> expects collections to be the first argument, but Clojure ->> expects it to be the last). Such omission makes Clojure's implementation/port shorter.

Templating

pbtic.birthday.mail-tpl/body function creates the message for inserting into the email. It's relatively easy that could have been tested using traditional unit testing method...

(ns pbtic.birthday.mail-tpl-test
  (:require [clojure.string :as str]
            [clojure.test.check.clojure-test :refer [defspec]]
            [clojure.test.check.generators :as gen]
            [clojure.test.check.properties :refer [for-all]]
            [pbtic.birthday.csv-test :as csv-test]
            [pbtic.birthday.mail-tpl :as mail-tpl])
  (:import [java.time LocalDate]))

;;;;;;;;;;;;;
;; generators

(def date
  (gen/let [days-to-add gen/nat]
   (.plusDays (LocalDate/of 1900 1 1) days-to-add)))


(def employee-map
  (gen/let [vs (gen/tuple (gen/not-empty csv-test/field)
                          (gen/not-empty csv-test/field)
                          date
                          (gen/not-empty csv-test/field))]
    (zipmap [:last-name :first-name :date-of-birth :email] vs)))

;;;;;;;;;;;;;
;; properties

(defspec email-template-has-first-name
  (for-all [employee employee-map]
    (str/includes? (mail-tpl/body employee)
                   (:first-name employee))))

The implementation is trivial:

(ns pbtic.birthday.mail-tpl)

(defn body [{:keys [first-name]}]
  (format "Happy birthday, dear %s!" first-name))


(defn full [{:keys [email] :as employee}]
  [email, "Happy birthday!", (body employee)])

Plumbing It All Together

pbtic.birthday/run function ties all these up (without any integration tests written).

(ns pbtic.birthday
  (:require [pbtic.birthday.csv :as csv]
            [pbtic.birthday.employee :as employee]
            [pbtic.birthday.mail-tpl :as mail-tpl])
  (:import [java.time LocalDate]))

;;;;;;;;;
;; helper

(defn- send-email [[to, _topic, _body]]
  (println "sent birthday email to" to))

;;;;;;;;;;;;;
;; public api

(defn run [path & {:keys [curr-date] :or {curr-date (LocalDate/now)}}]
  (doseq [employee (->> (slurp path)
                        employee/from-csv
                        (employee/filter-birthday curr-date))]
    (send-email (mail-tpl/full employee))))

To test it, pass the file name of the employee record CSV and optionally the "current date" (defaults to today). For example, run the following at Clojure REPL:

user=> (require '[pbtic.birthday :as bday])
user=> (import '[java.time LocalDate])
user=> (bday/run "resources/birthday/employees.csv" :curr-date (LocalDate/of 2019 8 10))
sent birthday email to john.doe@foobar.com
nil

Summary

It's quite a blast in porting the code from Erlang/Elixir to Clojure. In the next post, I'll cover the code ported from chapter 6 "Properties-Driven Development."

This post Property-Based Testing: From Erlang/Elixir to Clojure first appeared first on Bit by Bit

DEV Community: shaolang

Storybook.JS with Shadow-CLJS

Prerequisites

Getting a simple React app running

Some cleanup

Adding Storybook.JS to the mix

Wrapping up

Getting Started With Chronicle Queue

Terminology

Hello, World!

Detour: Excerpt types

Writing and Reading Domain Objects

(Kinda) Listening Only to Things You're Interested in

MethodReader Uses Duck Typing

Named Tailers

Roll 'Em

What's Next

Genetic Algorithm Basics

Building blocks

Crossover

Mutation

Genes and chromosomes

Selection

First toy example: All-ones

Real-world example: Class scheduling

Last note on crossovers

Closing thoughts

Ranking Data in MSExcel

Getting our hands dirty

Wrapping up

Property-Based Testing: From Erlang/Elixir to Clojure

Birthday Greeting Kata

CSV Parsing

Records Filtering

Employee Module

Templating

Plumbing It All Together

Summary

`MethodReader` Uses Duck Typing