Optimizing Virgo Using NArray

Virgo Example Output

Earlier this week, I had released Virgo, a Ruby CLI to generate wallpapers (including the one above). My goal was to be able to create beautiful OLED wallpapers for my phone, but unfortunately, the first version of Virgo would take about 15 seconds to generate a wallpaper the size of an iPhone 11. The first version of Virgo used ChunkyPNG::Image to place pixels on the background, and the author of ChunkyPNG alludes to this possible problem in his README:

Also, have a look at OilyPNG which is a mixin module that implements some of the ChunkyPNG algorithms in C, which provides a massive speed boost to encoding and decoding.

Improvement Goal

My goal was to reduce the time to generate an iPhone-sized wallpaper (about 1200 by 2200 pixels) in under one second. I chose this constraint so that I can eventually write a web frontend in Sinatra. Users won’t wait 15 seconds for an image to be generated, especially if the file is being provided by a server without any loading indication on the page.

Thinking of a Solution

When thinking of optimization ideas, two options stood out to me from Willem’s README:

  1. Can I adapt Virgo to use OilyPNG instead of ChunkyPNG?
  2. Is there another library that implements array manipulation in C?

After some research into OilyPNG, I found that the functions I used with ChunkyPNG weren’t implemented in OilyPNG1, so I was left to find another library that enabled a faster manipulation of integer arrays. I knew that in the Python world, NumPy would be the immediate answer. After some research for a Ruby alternative to NumPy, I came across NArray, which appeared to be a solution others had relied on in the past. I alluded to this possible approach in my original post:

ChunkyPNG was used to manage and save the wallpaper images, and Commander enabled terminal argument parsing and help documentation. For optimization, I plan to use NArray for creating the pixel locations in the wallpaper and writing a custom PNG encoder.

Fast Pixel Placement

After some profiling, the section of code that could be improved the most was overlaying pixels on the background image:

def place_pixel
  # Create a new canvas
  pixel = Image.new(@pixel_diameter, @pixel_diameter, @theme.foreground)

  # Replace the old image with the new canvas at the pixel coordinate
  @image = @image.replace(pixel, pixel_coordinate.x, pixel_coordinate.y)
end

Rather than creating new ChunkyPNG::Images and overlaying them on a master Image, I decided to use a new data structure for the image. Instead, Virgo now uses an NArray to represent the image, where each item is the Integer representation of the pixel ChunkyPNG::Color. For every pixel, a portion of the array is replaced with the integer color:

def create_map
  # Start with each pixel in the image as the background color
  map = NArray.int(@width, @height).fill!(@theme.background)

  # Place each pixel in the map
  count = number_pixels_to_place
  (1..count).each do
    # Determine pixel location
    x = @x_distribution.random_point
    x_max = x + @pixel_diameter
    y = @y_distribution.random_point
    y_max = y + @pixel_diameter

    # Replace the pixel in the map with a new (random) color
    map[x..x_max, y..y_max] = @theme.random_foreground
  end
end

Then, to create save a Wallpaper instance, a ChunkyPNG::Image is created by inserting rows of the NArray into the Image:

def image
  img = Image.new(@width, @height, Color::TRANSPARENT)

  # Put each row of @map into the image
  num_rows = @map.shape[1]
  (0...num_rows).each do |row_idx|
    # Replace the row in the image with the new colors
    img.replace_row!(row_idx, @map[true, row_idx])
  end

  img
end

int vs Integer

There was only one problem with this solution: the range of values for ChunkyPNG::Image would often exceed the range of the int type used by NArray. Therefore, most of the colors in the predefined themes could not be placed into the color map as-is.

I decided to implement a color hash (enum) for a Theme instance, where every key is a unique (low Integer value identifier), and each value is the (large Integer) ChunkyPNG::Image value. The background color (@background) will always have the identifier 0, and the foreground colors (@foregrounds) have identifiers from 1 to n. The color hash is created in Theme.initialize:

def initialize(background = BACKGROUNDS[:black],
               foregrounds = FOREGROUNDS[:ruby])
  @background = Color.from_hex(background)
  @foregrounds = foregrounds.map { |x| Color.from_hex(x) }

  # Because NArray can't handle the size of some ChunkyPNG::Color
  # values, create a Hash of the background and foreground colors,
  # where the key of the hash is an Integer, and the
  # value is the value of the color
  # Background has a key of 0, foregrounds have keys from 1..n
  colors = [@background] + @foregrounds
  colors_with_indices = colors.each_with_index.map do |color, idx|
    [idx, color]
  end
  @color_hash = Hash[colors_with_indices]
end

Let’s look at an example:

2.6.3 :001 > # Construct a theme using predefined color names
2.6.3 :002 > t = Theme.from_syms(:black, :ruby)
 => #<Theme:0x00007f861f8c2128
      @background=255,
      @foregrounds=[
        2367954943,
        2720605439,
        3073321215,
        3425971711,
        3561307903,
        3646510079,
        3731712255],
      @color_hash={
        0=>255,
        1=>2367954943,
        2=>2720605439,
        3=>3073321215,
        4=>3425971711,
        5=>3561307903,
        6=>3646510079,
        7=>3731712255}>

Note that the @background color 255 is in @color_hash as 0=>255, which means it has an identifier of 0. The second color in @foregrounds, 2720605439, is in @color_hash as 2=>2720605439, meaning that color has an identifier of 2.

Therefore, if the Wallpaper map has the following values:

[ [0, 0, 0],
  [0, 2, 0],
  [0, 0, 0] ]

Then the middle pixel is red (a value of 2720605439), and the border pixels are black (a value of 255).

Next, we add a few helper functions to Theme for retrieving a random foreground (pixel) color and color keys/values:

# Returns the key for the background color
def background_key
  # The background always has a key of 0
  0
end

# Returns a random @color_hash foreground key
def random_foreground_key
  # (Slightly) speed up getting a foreground by returning the first
  # item if only one exists
  color = if @foregrounds.length == 1
            @foregrounds[0]
          else
            @foregrounds.sample
          end

  key_from_color(color)
end

# Returns the ChunkyPNG::Color value for a color key
def color_from_key(key)
  @color_hash[key]
end

# Returns the key (in @color_hash) for a color value
def key_from_color(color)
  @color_hash.key(color)
end

And create_map is updated to use the color keys rather than the large values:

def create_map
  # Start with each pixel in the image as the background color
  map = NArray.int(@width, @height).fill!(@theme.background_key)

  # Place each pixel in the map
  count = number_pixels_to_place
  (1..count).each do
    # Determine pixel location
    x = @x_distribution.random_point
    x_max = x + @pixel_diameter
    y = @y_distribution.random_point
    y_max = y + @pixel_diameter

    # Replace the pixel in the map with a new (random) color
    map[x..x_max, y..y_max] = @theme.random_foreground_key
  end

  map
end

Now we can test whether using NArray vs ChunkyPNG::Image reduced the time to generate large wallpapers.

Results

Using NArray significantly improved Virgo’s speed:

Virgo Example Output

Note the exponential time complexity of the original implementation, and the linear time complexity.2 With 10 trials, NArray Virgo took 0.5 seconds on average to generate a 1000x1000 wallpaper, while the original implementation of Virgo takes 15.1 seconds on average. That’s a a 30x improvement! Even better, these updates will allow me to make a responsive Sinatra web frontend, without worrying about user retention or delays.

Future Improvements

I believe more improvements could be made to Virgo, especially since I plan on writing a web frontend. In particular, I’ve added a Distribution class to enable both normal and uniform pixel distributions, but I have not added it as a feature to the CLI. Further, there is a new version of NArray called Numo::NArray that supports UInt64 values, so there will no longer be a need to map each color in a Theme to unique identifiers.

Virgo is available on my GitHub profile, and it’s open to pull requests!

Virgo Example Output

  1. In fact, the library didn’t seem to have implemented much, if any, of the ChunkyPNG functionality. 

  2. Well, O(n) at least comparative to the ChunkyPNG implementation and tests I conducted up to an image size of 5000x5000. 

Virgo: Ruby Wallpaper Generator

There are many galaxies with strange, funny, or mysterious names, such as the Sombrero Galaxy or the Cartwheel Galaxy. Inspired by these galaxies I wanted to be able to make space-like wallpapers for my devices.

The Thousand Ruby Galaxy

As a result, I’ve written Virgo, a wallpaper generator CLI written in Ruby. Virgo is great for creating PNG OLED phone wallpapers with a true black background. Let’s create an iPhone 11 size wallpaper:

$ cd ~/virgo
$ ./virgo.rb --width 828 --height 1792

Virgo Example Output

Virgo has many options for creating wallpapers, including the image dimension, colors, and pixel properties:

./virgo.rb save PATH [options]

OPTIONS:
    --background BACKGROUND
        Wallpaper background as a hexcode. Use list-backgrounds to list predefined background names

    --foregrounds FOREGROUNDS
        Wallpaper foregrounds as hexcodes separated by commans. Use list-foregrounds to list predefined foreground names

    --width PIXELS
        Width of the wallpaper

    --height PIXELS
        Height of the wallpaper

    --density RATIO
        Ratio of pixels to size of the image, as a percent integer

    --diameter PIXELS
        Diameter of each pixel drawn on the wallpaper

There are also many predefined backgrounds and foregrounds for you to explore! Use the following commands to list some options:

$ ./virgo.rb list_backgrounds

black: #000000
white: #ffffff
dark_blue: #355c7d
chalkboard: #2a363b
peach: #ff8c94
gray: #363636
teal: #2f9599
orange: ff4e50
brown: #594f4f
gray_green: #83af9b
$ ./virgo.rb list_foregrounds

white: ["#ffffff"]
ruby: ["#8d241f", "#a22924", "#b72f28", "#cc342d", "#d4453e", "#d95953", "#de6d68"]
sunset: ["#f8b195", "#f67280", "#c06c84", "#6c5b7b"]
primaries: ["#99b898", "#feceab", "#ff847c", "#e84a5f"]
primaries_light: ["#a8e6ce", "#bcedc2", "#ffd3b5", "#ffaaa6"]
gothic: ["#a8a7a7", "#cc527a", "#e8175d", "#474747"]
solar: ["#a7226e", "#ec2049", "#f26b38", "#9dedad"]
yellows: ["#e1f5c4", "#ede574", "#f9d423", "#fc913a"]
earth: ["#e5fcc2", "#9de0ad", "#45ada8", "#547980"]
faded: ["#fe4365", "#fc9d9a", "#f9cdad", "#c8c8a9"]

ChunkyPNG was used to manage and save the wallpaper images, and Commander enabled terminal argument parsing and help documentation. For optimization, I plan to use NArray for creating the pixel locations in the wallpaper and writing a custom PNG encoder. Here are a few example wallpapers created by Virgo:

Virgo Example Output Virgo Example Output Virgo Example Output Virgo Example Output Virgo Example Output

You can find Virgo on GitHub here.

Fast Introduction to Node APIs

By the end of this post, we will have created an API using Node, express and body-parser. Our API will have two endpoints: /magic-8-ball will return a random Magic 8-Ball response, and /to-zalgo will convert given text into Zalgo text.

Setup

First, create a new folder named node-api and navigate to it. We need to create a new npm package that will hold our API app. Run the following command and fill out the information. Each part can be left the default, except the entry point should be app.js:

$ npm init

Next, let’s install express and body-parser, as we’ll need both later:

$ npm install express body-parser

In order to run our app, we’ll add a command inside package.json for npm start. Add this item to the "scripts" array:

  "scripts": {
    ...
    "start": "node app.js"
  },

Express Hello World

Now that we have our package set up, we can begin writing the web app. Let’s return “Hello world!” at the root of our app (/, or http://localhost:3200/):

// Load the modules we installed
const express = require('express')
const bodyparser = require('body-parser')

// Tell express to run the webserver on port 3200
const app = express();
const port = process.env.port || 3200

// Use body-parser for unencoding API request bodies - more on this later
app.use(bodyparser.json())
app.use(bodyparser.urlencoded({ extended: false }))

app.listen(port, () => {
    console.log(`running on port ${port}`)
})

// Return "Hello world" when you go to http://localhost:3200
app.get('/', (req, res) => res.send('Hello world!'))

To test our app, run npm start in one terminal window, then use curl in the other:

$ curl http://localhost:3200
Hello world!

Magic 8-Ball Responses

Our first API endpoint, /magic-8-ball, will return a JSON result in the form of {"prediction": "<8-ball response>"}. I wrote a helper function to return a random item from an array:

function randomItemFromArray(arr) {
    return arr[Math.floor(Math.random() * arr.length)]
}

Then all we need to do is have our server keep an array of possible responses, pick a random one, and return the response in JSON format:

// Return a random response for http://localhost:3200/magic-8-ball
// {"prediction": "<random_prediction>"}
app.get('/magic-8-ball', (req, res) => {
    const responses = [
        'It is certain.',
        'It is decidedly so.',
        'Without a doubt.',
        'Yes - definitely.',
        'You may rely on it.',
        'As I see it, yes.',
        'Most likely.',
        'Outlook good.',
        'Yes.',
        'Signs point to yes.',
        'Reply hazy, try again.',
        'Ask again later.',
        'Better not tell you now.',
        'Cannot predict now.',
        'Concentrate and ask again.',
        "Don't count on it.",
        'My reply is no.',
        'My sources say no.',
        'Outlook not so good.',
        'Very doubtful.'
    ]

    res.status(200).json({
        prediction: randomItemFromArray(responses)
    })
})

Run npm start, and we can test it a few times using curl:

$ curl http://localhost:3200/magic-8-ball
{"prediction":"Without a doubt."}

$ curl http://localhost:3200/magic-8-ball
{"prediction":"Yes - definitely."}

$ curl http://localhost:3200/magic-8-ball
{"prediction":"Signs point to yes."}

Zalgo Text

Our Zalgo endpoint (/to-zalgo) is a little more advanced. A user will send a POST request including a message in the form {"text": "your text here"}, and the endpoint will return a response in the form {"code": 200, "original": "your text here", "zalgo": "zalgo-ified text"}. The endpoint will also return a 400 HTTP Status Code error if the input data is incorrect:

// Return Zalgo-ified text for http://localhost:3200/to-zalgo
// Input:   {"text": "your text here"}
// Returns: {"code": 200, "original": "your text here", "zalgo": "zalgo-ified text"}
app.post('/to-zalgo', (req, res) => {
    // Return 400 if the input doesn't contain a "text" element
    if (req.body.text === undefined) {
        res.status(400).json({
            "code": 400,
            "message": "Missing 'text' argument"
        })
        return
    }

    original = req.body.text
    zalgo = toZalgo(original)

    res.status(200).json({
        "code": 200,
        "original": original,
        "zalgo": zalgo
    })
})

Let’s test it a few times with curl. To send data in a POST request, like our text in JSON format, use -d "data". Because we’re sending data in a JSON format, our requests via curl will need to include -H "Content-Type: application/json" as well.

(If you’re wondering why the text looks odd, I’d recommend checking out another Zalgo converter first)

$ curl -d '{"text":"Sphinx of black quartz, judge my vow"}' -H "Content-Type: application/json" http://localhost:3200/to-zalgo
{"code":200,"original":"Sphinx of black quartz, judge my vow","zalgo":"S̡̲̳͔̻ͤ̏ͦ̾̀͒̀p̰̯̐̃͒͂ͪͨͤ͘͠h̷̖̰̩̍ͯi̸̩̜͇̪͍͉̭ͨ͐̆͞ͅn̡̧̤̭͚̤̯̼̹ͪͫ́̌ͫ̇̑̋ͅx̧̻̤̄ͩ͋ͣ͂ ̥̤̩̳̠͖ͧ͡ͅö͍̮̅ͯ̋ͣf̠͎̗͕̯̈́̀͑̐͌͊̍͒́ͅ ̦̬̱͉̫͍̞ͤͯͦ͂͜b̡̼̱̊ͅl̵̻̹͇̘̒̌̊̄aͩ̏͛̋̇̅̇ͩ̀͏̘̳̲̫͕ͅc̢̛̗̱͗́̓̆̌k̡͉͉̼̾̍̒͌̀ ̡̳͈͓̞̦̞̱̥̒̌ͦ̅̃q̰̪̟̥̿̀͝ȕ̗a͓̟͍͐̓̂ͣ̀͜r̞̭̪̦̩̹̂̒̐͗̕t̺͎͛̿̽͒̑̓̆ͧz̸͖̟͓̪̻͓̝̦ͨ̕,̻͔͙̲̓̈ͮ̍ ͍̘̟̖̩͊̀̈́ͩͯ̑j̷͕̱̖̔ͧ͌u̗̱͈ͨ̄ͩͬd̜̖̖̦̺̟́̇͐͛̒̆͊ͦ͜g̎ͩͅe̪̟̦͓̥̘͙ͭ̊ͨ̓ ͔̳̒̔̈̈́̈͠ͅm̧̪̊̌y̧͂̑ͯͤ͏͔͔͓͕̮ ̸̛͎͚͇͔̭̱̱͐ͮ̐ͪ͐̊͌v̘̬̘͋̅̽̅̄̐̀o̵̤̝̯̞̪̍͞ͅw̶̠̝̦̹͔̍ͪ͐̂ͮͭ̌͟"}

{"code":200,"original":"the blood of the ancients resides within me","zalgo":"t͍̗͖͚͙͖͖̿ͪ̍h͍̘̩̤̼̞̫̜̒͟ȩ̛̺̫̖̝̰̥͋͛̎̎̈̈ ̢̼̫͈͓ͦ̿ͯb̺̖͚̤͓̲͓ͬ͊ͬ͑̅l̼̪̞̮͖̩̥͕̎ͧ̓̋̐̒ͧͯö̱̹͔̫͇́͌ͭͩ̉̆ͬ͆͠ͅô̸̶̲̫̞͔̻̝̰͓͋d̹̫̠͚͉͎ͨ͑ͯ̀ ̨̫͍̹̺̰̑͛̂̾͗ͪ̓ͅô͙̰͍͓̯͍̼̟ͭ́̽̑́͐̓f̯̥͙͈̺̮̙̙̅̌͂̓ͦ ̸͚̝̥̮̅̾t̨̟̗̟̼͔̑ͥ̊̾ͧͮ̿̿h̜̉͋ͮ͐e̪̳ͧ̾̏ ͬͤ̄̽̾̈̓͊͏̖̗̪͖͚a̢̩̖̯̹͗̊̽͢n̴̔ͥ̓͐͏̙̞̙̭̞͉c̖͕̘̗͉̠̬͂ͤͦ͋ì͕̥̱͍̗̐̅̆̓ͫe̮̩̩̮̬͕͈̾͂͒ͪ͛̇͞n̸̳̹̗͊ͦ̋ͅt͎̯̖̟̫ͯͪs͔̮͋ͧͩ͋̏ͯ̆͢ ̺̤̘̫̗̻̂r̡͚̮͇̘̻͔̉ͅĕ͔̪͖͓̯̙͙͗̂ͯ͛ͭs̵̝̘̺̠̘ͬͮi̴͖̤̟̭͚̞ͪͣd̶̛̪͈̉e͉̺̖̫ͥ̔̽̂̄͒́ͬ́́ͅṡ̵͕͟ͅ ̷̜̤̝̹̦̼͖̅ͭ̈͌͐̍ͦ͗ͅw̧̠͍̻̜͆̔ͣ͗͜i̵̶̙͉̺̦̲̅͋t̗̽͑͐ͣ̇ͣ͛ͧh̢̗͍͎̪̪̹̳̎͗̑̔̎̏͛͜i̶̱̪̺̖̻͓ͥ̿ͨ̇̅̔͗̎ͅņ̪ͬ̇ͭ̉ͬͩ͢ ̶̨̲̩̙ͦ̔̈́̄m̡̳̬̟͐e̱̩̠̙ͨ̓̇̽͑̋"}

Conclusion

Now our API has two endpoints, /magic-8-ball and /to-zalgo for you to use as a starting point for your own web app.

Here’s the full version of our app.js:

// Load the modules we installed
const express = require('express')
const bodyparser = require('body-parser')
var toZalgo = require('to-zalgo')

// Tell express to run the webserver on port 3200
const app = express();
const port = process.env.port || 3200

// Use body-parser for unencoding API request bodies - more on this later
app.use(bodyparser.json())
app.use(bodyparser.urlencoded({ extended: false }))

app.listen(port, () => {
    console.log(`running on port ${port}`)
})

// Return "Hello world" when you go to http://localhost:3200
app.get('/', (req, res) => res.send('Hello world!'))

// Return a random response for http://localhost:3200/magic-8-ball
// Returns: {"prediction": "<random_prediction>"}
app.get('/magic-8-ball', (req, res) => {
    const responses = [
        'It is certain.',
        'It is decidedly so.',
        'Without a doubt.',
        'Yes - definitely.',
        'You may rely on it.',
        'As I see it, yes.',
        'Most likely.',
        'Outlook good.',
        'Yes.',
        'Signs point to yes.',
        'Reply hazy, try again.',
        'Ask again later.',
        'Better not tell you now.',
        'Cannot predict now.',
        'Concentrate and ask again.',
        "Don't count on it.",
        'My reply is no.',
        'My sources say no.',
        'Outlook not so good.',
        'Very doubtful.'
    ]

    res.status(200).json({
        prediction: randomItemFromArray(responses)
    })
})

// Return Zalgo-ified text for http://localhost:3200/to-zalgo
// Input:   {"text": "your text here"}
// Returns: {"code": 200, "original": "your text here", "zalgo": "zalgo-ified text"}
app.post('/to-zalgo', (req, res) => {
    // Return 400 if the input doesn't contain a "text" element
    if (req.body.text === undefined) {
        res.status(400).json({
            "code": 400,
            "message": "Missing 'text' argument"
        })
        return
    }

    original = req.body.text
    zalgo = toZalgo(original)

    res.status(200).json({
        "code": 200,
        "original": original,
        "zalgo": zalgo
    })
})

function randomItemFromArray(arr) {
    return arr[Math.floor(Math.random() * arr.length)]
}

The entire example app can be found as a GitHub repo as well.

Calculating a Levenshtein Distance

Imagine you’re writing a mobile app, and your user searches for the word kitten. Unfortunately, the only search terms you expected them to enter were from the following:

smitten
mitten
kitty
fitting
written

How do we figure out which word the user meant to type?

Levenshtein Distances

A Levenshtein distance is a distance between two sequences a and b. If a and b are strings, the Levenshtein distance is the minimum amount of character edits needed to change one of the strings into the other. There are three types of edits allowed:

  • Insertion: a character is added to a
  • Deletion: a character is removed from b
  • Substitution: a character is replaced in a or b

For example, if the first string a = 'abc' and the second string is b = 'abc', the Levenshtein distance between the two strings is 0 because a and b are equal. If a = 'abcd' and b = 'a', the distance is 3. If a = 'abcd' and b = 'aacc', the distance is 2.

The definition of the Levenshtein distance for a string a with a length i and a string b with a length j is:

This definition is a recursive function. The first portion, max(i, j) if min(i, j) = 0, is the base cases where either the first string or the second string is empty.

The function 1_(ai != bi) at the end of the third minimum element is the cost. If a[i] != b[i], the cost is 1, otherwise the cost is 0. The first minimum element is a deletion from a, the second is an insertion, and the third is a substitution.

A Naive Implementation

First, let’s implement a straightforward implementation in Swift. We’ll create a function named levenshtein_distance and write the base cases to check whether either of the strings are empty:

func levenshtein_distance(a: String, b: String) -> Int {
    // If either array is empty, return the length of the other array
    if (a.count == 0) {
        return b.count
    }
    if (b.count == 0) {
        return a.count
    }
}

Then we add the recursive portion. We calculate the cost for the substitution, then find the minimum distance between the three different possible edits (deletion, insertion, or substitution):

func levenshtein_distance(a: String, b: String) -> Int {
    // ...

    // Check whether the last items are the same before testing the other items
    let cost = (a.last == b.last) ? 0 : 1

    let a_dropped = String(a.dropLast())
    let b_dropped = String(b.dropLast())

    return min(
        // Find the distance if an item in a is removed
        levenshtein_distance(a: a_dropped, b: b) + 1,
        // Find the distance if an item is removed from b (i.e. added to a)
        levenshtein_distance(a: a, b: b_dropped) + 1,
        // Find the distance if an item is removed from a and b (i.e. substituted)
        levenshtein_distance(a: a_dropped, b: b_dropped) + cost
    )
}

Let’s test our distance function with a simple test case:

print(opti_leven_distance(a: "123", b: "12"))
1

More example test cases can be found below in the final files. And now we can compare the distances of our words to the string kitten to figure out which word the user probably meant to type:

// Print out the distances for our test case
let first_word = "kitten"
let test_words = ["smitten", "mitten", "kitty", "fitting", "written"]

for word in test_words {
    let dist = opti_leven_distance(a: first_word, b: word)
    print("Distance between \(first_word) and \(word): \(dist)")
}
Distance between kitten and smitten: 2
Distance between kitten and mitten: 1
Distance between kitten and kitty: 2
Distance between kitten and fitting: 3
Distance between kitten and written: 2

The user probably meant to type mitten instead of kitten!

An Improved Implementation

The recursive implementation of the Levenshtein distance above won’t scale very well for larger strings. What if we needed to find the distance between a thousand strings, each with hundreds of characters?

One improved way to calculate a Levenshtein distance is to use a matrix of distances to “remember” previously calculated distances. First, the distance function should check for empty strings. Then, we’ll create a matrix to hold the distance calculations:

func opti_leven_distance(a: String, b: String) -> Int {
    // Check for empty strings first
    if (a.count == 0) {
        return b.count
    }
    if (b.count == 0) {
        return a.count
    }

    // Create an empty distance matrix with dimensions len(a)+1 x len(b)+1
    var dists = Array(repeating: Array(repeating: 0, count: b.count+1), count: a.count+1)
}

The first column and first row of the distance matrix are zeros as an initialization step. The next column goes from 1 to the length of a to represent removing each character to get to an empty string, and the next row goes from 1 to the length of b to represent adding (or inserting) each character to get to the value of b:

func opti_leven_distance(a: String, b: String) -> Int {
    //...

    // a's default distances are calculated by removing each character
    for i in 1...(a.count) {
        dists[i][0] = i
    }
    // b's default distances are calulated by adding each character
    for j in 1...(b.count) {
        dists[0][j] = j
    }
}

Similar to our naive implementation, we’ll check the remaining indices in the distance matrix. This time, however, we’ll use the previous values stored in the matrix to calculate the minimum distance rather than recursively calling the distance function. The final distance is the last element in the distance matrix (at the bottom right):

func opti_leven_distance(a: String, b: String) -> Int {
    //...

    // Find the remaining distances using previous distances
    for i in 1...(a.count) {
        for j in 1...(b.count) {
            // Calculate the substitution cost
            let cost = (a[i-1] == b[j-1]) ? 0 : 1

            dists[i][j] = min(
                // Removing a character from a
                dists[i-1][j] + 1,
                // Adding a character to b
                dists[i][j-1] + 1,
                // Substituting a character from a to b
                dists[i-1][j-1] + cost
            )
        }
    }

    return dists.last!.last!
}

We can use our test cases again to verify that our improved implementation is correct:

print(opti_leven_distance(a: "123", b: "12"))

// Print out the distances for our test case
let first_word = "kitten"
let test_words = ["smitten", "mitten", "kitty", "fitting", "written"]

for word in test_words {
    let dist = opti_leven_distance(a: first_word, b: word)
    print("Distance between \(first_word) and \(word): \(dist)")
}
1
Distance between kitten and smitten: 2
Distance between kitten and mitten: 1
Distance between kitten and kitty: 2
Distance between kitten and fitting: 3
Distance between kitten and written: 2

Swift and Python Implementations

Distance.playground:


import Foundation


/// Calculates the Levenshtein distance between two strings
/// - Parameter a: The first string
/// - Parameter b: The second string
func levenshtein_distance(a: String, b: String) -> Int {
    // If either array is empty, return the length of the other array
    if (a.count == 0) {
        return b.count
    }
    if (b.count == 0) {
        return a.count
    }

    // Check whether the last items are the same before testing the other items
    let cost = (a.last == b.last) ? 0 : 1

    let a_dropped = String(a.dropLast())
    let b_dropped = String(b.dropLast())

    return min(
        // Find the distance if an item in a is removed
        levenshtein_distance(a: a_dropped, b: b) + 1,
        // Find the distance if an item is removed from b (i.e. added to a)
        levenshtein_distance(a: a, b: b_dropped) + 1,
        // Find the distance if an item is removed from a and b (i.e. substituted)
        levenshtein_distance(a: a_dropped, b: b_dropped) + cost
    )
}

/// String extension to add substring by Int (such as a[i-1])
extension String {
    subscript (i: Int) -> Character {
      return self[index(startIndex, offsetBy: i)]
    }
}

/// A more optimized version of the Levenshtein distance function using an array of previously calculated distances
/// - Parameter a: The first string
/// - Parameter b: The second string
func opti_leven_distance(a: String, b: String) -> Int {
    // Check for empty strings first
    if (a.count == 0) {
        return b.count
    }
    if (b.count == 0) {
        return a.count
    }

    // Create an empty distance matrix with dimensions len(a)+1 x len(b)+1
    var dists = Array(repeating: Array(repeating: 0, count: b.count+1), count: a.count+1)

    // a's default distances are calculated by removing each character
    for i in 1...(a.count) {
        dists[i][0] = i
    }
    // b's default distances are calulated by adding each character
    for j in 1...(b.count) {
        dists[0][j] = j
    }

    // Find the remaining distances using previous distances
    for i in 1...(a.count) {
        for j in 1...(b.count) {
            // Calculate the substitution cost
            let cost = (a[i-1] == b[j-1]) ? 0 : 1

            dists[i][j] = min(
                // Removing a character from a
                dists[i-1][j] + 1,
                // Adding a character to b
                dists[i][j-1] + 1,
                // Substituting a character from a to b
                dists[i-1][j-1] + cost
            )
        }
    }

    return dists.last!.last!
}

/// Function to test whether the distance function is working correctly
/// - Parameter a: The first test string
/// - Parameter b: The second test string
/// - Parameter answer: The expected answer to be returned by the distance function
func test_distance(a: String, b: String, answer: Int) -> Bool {
    let d = opti_leven_distance(a: a, b: b)

    if (d != answer) {
        print("a: \(a)")
        print("b: \(b)")
        print("expected: \(answer)")
        print("distance: \(d)")
        return false
    } else {
        return true
    }
}

// Test the distance function with many different examples
test_distance(a: "", b: "", answer: 0)
test_distance(a: "1", b: "1", answer: 0)
test_distance(a: "1", b: "2", answer: 1)
test_distance(a: "12", b: "12", answer: 0)
test_distance(a: "123", b: "12", answer: 1)
test_distance(a: "1234", b: "1", answer: 3)
test_distance(a: "1234", b: "1233", answer: 1)
test_distance(a: "1248", b: "1349", answer: 2)
test_distance(a: "", b: "12345", answer: 5)
test_distance(a: "5677", b: "1234", answer: 4)
test_distance(a: "123456", b: "12345", answer: 1)
test_distance(a: "13579", b: "12345", answer: 4)
test_distance(a: "123", b: "", answer: 3)
test_distance(a: "kitten", b: "mittens", answer: 2)

print(opti_leven_distance(a: "123", b: "12"))

// Print out the distances for our test case
let first_word = "kitten"
let test_words = ["smitten", "mitten", "kitty", "fitting", "written"]

for word in test_words {
    let dist = opti_leven_distance(a: first_word, b: word)
    print("Distance between \(first_word) and \(word): \(dist)")
}

Here’s a Python implementation of the Swift code above as distance.py. The Python version also can handle any list as well as any str

# Calculates the Levenshtein distance between two strings
def levenshtein_distance(a, b):
    # If either array is empty, return the length of the other array
    if not len(a):
        return len(b)
    if not len(b):
        return len(a)

    # Check whether the last items are the same before testing the other items
    if a[-1] == b[-1]:
        cost = 0
    else:
        cost = 1

    return min(
        # Find the distance if an item in a is removed
        levenshtein_distance(a[:-1], b) + 1,
        # Find the distance if an item is removed from b (i.e. added to a)
        levenshtein_distance(a, b[:-1]) + 1,
        # Find the distance if an item is removed from a and b (i.e. substituted)
        levenshtein_distance(a[:-1], b[:-1]) + cost
    )

# A more optimized version of the Levenshtein distance function using an array of previously calculated distances
def opti_leven_distance(a, b):
    # Create an empty distance matrix with dimensions len(a)+1 x len(b)+1
    dists = [ [0 for _ in range(len(b)+1)] for _ in range(len(a)+1) ]

    # a's default distances are calculated by removing each character
    for i in range(1, len(a)+1):
        dists[i][0] = i
    # b's default distances are calulated by adding each character
    for j in range(1, len(b)+1):
        dists[0][j] = j

    # Find the remaining distances using previous distances
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            # Calculate the substitution cost
            if a[i-1] == b[j-1]:
                cost = 0
            else:
                cost = 1

            dists[i][j] = min(
                # Removing a character from a
                dists[i-1][j] + 1,
                # Adding a character to b
                dists[i][j-1] + 1,
                # Substituting a character from a to b
                dists[i-1][j-1] + cost
            )

    return dists[-1][-1]

# Function to test whether the distance function is working correctly
def test_distance(a, b, answer):
    dist = opti_leven_distance(a, b)

    if dist != answer:
        print('a:', a)
        print('b:', b)
        print('expected:', answer)
        print('distance:', dist)
        print()

if __name__ == '__main__':
    # Test the distance function with many different examples
    test_distance('', '', 0)
    test_distance('1', '1', 0)
    test_distance('1', '2', 1)
    test_distance('12', '12', 0)
    test_distance('123', '12', 1)
    test_distance('1234', '1', 3)
    test_distance('1234', '1233', 1)
    test_distance([1, 2, 4, 8], [1, 3, 4, 16], 2)
    test_distance('', '12345', 5)
    test_distance([5, 6, 7, 7], [1, 2, 3, 4], 4)
    test_distance([1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], 1)
    test_distance([1, 3, 5, 7, 9], [1, 2, 3, 4, 5], 4)
    test_distance([1, 2, 3], [], 3)
    test_distance('kitten', 'mittens', 2)



    first_word = 'kitten'
    test_words = ['smitten', 'mitten', 'kitty', 'fitting', 'written']
    for word in test_words:
        dist = opti_leven_distance(first_word, word)
        print(f'Distance between {first_word} and {word}: {dist}')

Announcing Darkscreen - A Dark App

I’m so excited to announce that my first iOS app, Darkscreen - A Dark App, has a public beta on Testflight! Ever since I was given my first iPod (all the way back in 7th grade!) I’ve dreamed of creating something that millions of people have the ability to enjoy, and I can’t express how excited I am. Here’s the official description:

Darkscreen allows you to use other iPad apps in Split View without any distractions, no hassle.

Darkscreen provides multiple themes, including:

  • Dark
  • Light
  • 80s
  • 90s
  • Outrun

Download using Testflight today!

Why Darkscreen?

I really love using Apollo for Reddit by Christian Selig, but he hasn’t gotten a chance to create a true iPad experience for his Reddit client yet. I use Darkscreen next to Apollo in Split View so that Apollo can be in an iPhone-sized container while keeping the rest of the screen black.

For example, posts shown in Apollo don’t quite look right when in full horizontal mode on iPad:

Apollo in full horizontal mode

Now with Darkscreen, I can browse Apollo in its intended view size without being distracted by other apps:

Apollo in Split View with Darkscreen

Switching to a new theme in Darkscreen automatically updates the table view as well as the root view underneath:

Darkscreen switching themes

My next goal, of course, is for Darkscreen to respond to the system-wide Dark Mode setting.

Why Open Source?

I found it an interesting challenge to modify the appearance of all of all views in the app immediately after a user selects a theme in a UITableView, and I hope this brief example can help other developers implement their own theme system.

Even though iOS 13 introduces system-wide Dark Mode, this example app can be helpful to support any custom themes that go beyond the default dark and light styles.

How to Update the Theme for a View

I’ve implemented the theme system using a Settings Bundle, so the BaseViewController can subscribe to settings (theme) changes:

func registerForSettingsChange() {
    NotificationCenter.default.addObserver(self,
                                            selector: #selector(BaseViewController.settingsChanged),
                                            name: UserDefaults.didChangeNotification,
                                            object: nil)
}

A Theme corresponds to UI styles and colors:

class Theme {

    // ...

    init(_ name: String, statusBar: UIStatusBarStyle, background: UIColor, primary: UIColor, secondary: UIColor) {
        self.name = name
        statusBarStyle = statusBar
        backgroundColor = background
        primaryColor = primary
        secondaryColor = secondary
    }
}

When a setting changes, BaseViewController updates its UI elements:

@objc func settingsChanged() {
    updateTheme()
}

func updateTheme() {
    // Status bar
    setNeedsStatusBarAppearanceUpdate()

    // Background color
    self.view.backgroundColor = Settings.shared.theme.backgroundColor

    // Navigation bar
    self.navigationController?.navigationBar.updateTheme()
}

And UINavigationBar is extended to support theme switching:

public extension UINavigationBar {
    func updateTheme() {
        // Background color
        barTintColor = Settings.shared.theme.backgroundColor

        // Bar item color
        tintColor = Settings.shared.theme.secondaryColor

        // Title text color
        titleTextAttributes = [NSAttributedString.Key.foregroundColor: Settings.shared.theme.secondaryColor]

        // Status bar style
        barStyle = Settings.shared.theme.navbarStyle

        // Tell the system to update it
        setNeedsDisplay()
    }
}

How to Build a Song Recommender Using Create ML MLRecommender

Beta Warning

This example was written using macOS Catalina Version 10.15 Beta and Xcode Version 11.0 beta 5. Changes may have been made to the MLRecommender constructor since this article was written (October 2019).

Objective

By the end of this post, we’ll learn how to use the Create ML MLRecommender to recommend a song to a user given their listening history. We’ll also learn how to parse and prepare an MLDataTable using Python and data from a third party.

Introduction to MLRecommender

A personalized recommendation system can be used in many different applications, such as a music player, video player, or social media site. A machine learning recommendation system compares a user’s past activity to a large library of activity from many other users. For example, if Spotify wanted to recommend you a new Daily Mix, their ML recommendation system might look at your listening history for the past few weeks and compare that history to your friends’ history. Our goal today is to create an MLRecommender to recommend songs to a user given their listening history.

The constructor for MLRecommender is:

init(trainingData: MLDataTable, userColumn: String, itemColumn: String, ratingColumn: String? = nil, parameters: MLRecommender.ModelParameters = ModelParameters()) throws

Creating the Data Tables

The first step is to create the trainingData in the form of an MLDataTable. In this case, our training data is the listening history of many different users from the Million Song Dataset, which holds the metadata for over a million songs and ratings provided by users.

We’ll use two files from the dataset. The first is 1000.txt, which contains the user id, song id, and listen time for 10000 records. We’ll call that history.txt from now on. The second is song_data.csv, which contains the song id, title, release date and artist name. We’ll call that songs.csv from now on. All of the complete files for this tutorial can be found at the end of the post.

Here’s what our input files look like. Notice that songs.csv has a header row while history.txt does not:

# history.txt

b80344d063b5ccb3212f76538f3d9e43d87dca9e	SOAKIMP12A8C130995	1
b80344d063b5ccb3212f76538f3d9e43d87dca9e	SOBBMDR12A8C13253B	2
b80344d063b5ccb3212f76538f3d9e43d87dca9e	SOBXHDL12A81C204C0	1
...
# songs.csv

song_id,title,release,artist_name,year
SOQMMHC12AB0180CB8,"Silent Night","Monster Ballads X-Mas","Faster Pussy cat",2003
SOVFVAK12A8C1350D9,"Tanssi vaan","Karkuteillä",Karkkiautomaatti,1995
SOGTUKN12AB017F4F1,"No One Could Ever",Butter,"Hudson Mohawke",2006
...

We’ll be using the pandas Python library to handle our CSV data. First, download the files above and name them history.txt and songs.csv, and we’ll load them:

import csv
import pandas as pd

history_file = 'history.txt' # 'https://static.turi.com/datasets/millionsong/10000.txt'
songs_metadata_file = 'songs.csv' # 'https://static.turi.com/datasets/millionsong/song_data.csv'

# Import the files
history_df = pd.read_table(history_file, header=None)
history_df.columns = ['user_id', 'song_id', 'listen_count']
metadata_df =  pd.read_csv(songs_metadata_file)

songs.csv already has the column headers in the file, so we didn’t need to add those like we did with history_df. This is what our dataframes now look like:

# history_df

                                    user_id             song_id  listen_count
0  b80344d063b5ccb3212f76538f3d9e43d87dca9e  SOAKIMP12A8C130995             1
1  b80344d063b5ccb3212f76538f3d9e43d87dca9e  SOBBMDR12A8C13253B             2
2  b80344d063b5ccb3212f76538f3d9e43d87dca9e  SOBXHDL12A81C204C0             1
...
# metadata_df
# (The '\' means that the row continues onto the next lines)

              song_id              title                release  \
0  SOQMMHC12AB0180CB8       Silent Night  Monster Ballads X-Mas
1  SOVFVAK12A8C1350D9        Tanssi vaan            Karkuteillä
2  SOGTUKN12AB017F4F1  No One Could Ever                 Butter

        artist_name  year
0  Faster Pussy cat  2003
1  Karkkiautomaatti  1995
2    Hudson Mohawke  2006
...

Next, to create a single listening history for all users, we want to merge the song data in the metadata_df to the listening history in the history_df and create a CSV to use in Swift. Let’s also add a column that combines the song title with the artist name so that we can see both in our MLRecommender:

# Merge the files into a single csv
song_df = pd.merge(history_df, metadata_df.drop_duplicates(['song_id']), on="song_id", how="left")
song_df.to_csv('merged_listen_data.csv', quoting=csv.QUOTE_NONNUMERIC)

# Add a "Title - Name" column for easier printing later
song_df['song'] = song_df['title'] + ' - ' + song_df['artist_name']

Here’s what our combined song dataframe now looks like:

# song_df

                                    user_id             song_id  listen_count  \
0  b80344d063b5ccb3212f76538f3d9e43d87dca9e  SOAKIMP12A8C130995             1
1  b80344d063b5ccb3212f76538f3d9e43d87dca9e  SOBBMDR12A8C13253B             2
2  b80344d063b5ccb3212f76538f3d9e43d87dca9e  SOBXHDL12A81C204C0             1

             title              release    artist_name  year  \
0         The Cove   Thicker Than Water   Jack Johnson     0
1  Entre Dos Aguas  Flamenco Para Niños  Paco De Lucia  1976
2         Stronger           Graduation     Kanye West  2007

                              song
0          The Cove - Jack Johnson
1  Entre Dos Aguas - Paco De Lucia
2            Stronger - Kanye West
...

As of the time of writing, MLRecommender requires that the item id column in trainingData go from 1 to the number of items. In other words, if our trainingData included only three songs, merged_listen_data.csv would have song ids like SOQMMHC12AB0180CB8, SOVFVAK12A8C1350D9, and SOGTUKN12AB017F4F1, but we need to have song ids of 0, 1, and 2. Let’s add a new column to the CSV that uses incremental song ids from 0 to N:

# Find the unique song ids
song_ids = metadata_df.song_id.unique()

# Create a new dataframe of the unique song ids and a new incremental
# id for each one
incremental_id_df = pd.DataFrame({'song_id': song_ids})
incremental_id_df['incremental_song_id'] = incremental_id_df.index

# Merge the original song metadata with the incremental ids
new_song_id_df = pd.merge(song_id_df, incremental_id_df, on='song_id', how='left')
new_song_id_df.to_csv('songs_incremental_id.csv', quoting=csv.QUOTE_NONNUMERIC)

# Create a new merged history and song metadata CSV with incremental ids
new_history_df = pd.merge(history_df, incremental_id_df, on='song_id', how='inner')
new_history_df.to_csv('merged_listen_data_incremental_song_id.csv', quoting=csv.QUOTE_NONNUMERIC)

Here’s what our new song CSV file looks like. Notice that there’s now an added column at the beginning with a song id from 0 to 999999:

# songs_incremental_id.csv

"","song_id","title","release","artist_name","year","incremental_song_id"
0,"SOQMMHC12AB0180CB8","Silent Night","Monster Ballads X-Mas","Faster Pussy cat",2003,0
1,"SOVFVAK12A8C1350D9","Tanssi vaan","Karkuteillä","Karkkiautomaatti",1995,1
2,"SOGTUKN12AB017F4F1","No One Could Ever","Butter","Hudson Mohawke",2006,2
...

And here’s what our final merged listening data looks like with the incremental ids, ready to be read by the MLRecommender:

# merged_listen_data_incremental_song_id.csv

"","Unnamed: 0","user_id","song_id","listen_count","title","release","artist_name","year","incremental_song_id"
0,0,"b80344d063b5ccb3212f76538f3d9e43d87dca9e","SOAKIMP12A8C130995",1,"The Cove","Thicker Than Water","Jack Johnson",0,397069
1,18887,"7c86176941718984fed11b7c0674ff04c029b480","SOAKIMP12A8C130995",1,"The Cove","Thicker Than Water","Jack Johnson",0,397069
2,21627,"76235885b32c4e8c82760c340dc54f9b608d7d7e","SOAKIMP12A8C130995",3,"The Cove","Thicker Than Water","Jack Johnson",0,397069
...

Now we’re ready to load it into the recommender!

Using MLRecommender

Create a new Swift Playground, and add the two CSVs merged_listen_data_incremental_song_id.csv and songs_incremental_id.csv as resources to your Playground. For help on adding resources to a Swift Playground, check out this post. Make sure your Swift Playground is a blank macOS Playground and not an iOS Playground. Because our MLRecommender will only give us the user id and incremental song id when generating recommendations, we’ll use the second CSV to view the song titles.

First, let’s load the merged listening history with incremental ids:

import Foundation
import CreateML

// Create an MLDataTable from the merged CSV data
let history_csv = Bundle.main.url(forResource: "merged_listen_data_incremental_song_id", withExtension: "csv")!
let history_table = try MLDataTable(contentsOf: history_csv)
print(history_table)
Columns:
    X1	string
    Unnamed: 0	integer
    user_id	string
    song_id	string
    listen_count	integer
    title	string
    release	string
    artist_name	string
    year	integer
    incremental_song_id	integer
Rows: 2000000
Data:
+----------------+----------------+----------------+----------------+----------------+
| X1             | Unnamed: 0     | user_id        | song_id        | listen_count   |
+----------------+----------------+----------------+----------------+----------------+
| 0              | 0              | b80344d063b5...| SOAKIMP12A8C...| 1              |
| 1              | 18887          | 7c8617694171...| SOAKIMP12A8C...| 1              |
| 2              | 21627          | 76235885b32c...| SOAKIMP12A8C...| 3              |
| 3              | 27714          | 250c0fa2a77b...| SOAKIMP12A8C...| 1              |
| 4              | 34428          | 3f73f44560e8...| SOAKIMP12A8C...| 6              |
| 5              | 34715          | 7a4b8e7d2905...| SOAKIMP12A8C...| 6              |
| 6              | 55885          | b4a678fb729b...| SOAKIMP12A8C...| 2              |
| 7              | 65683          | 33280fc74b16...| SOAKIMP12A8C...| 1              |
| 8              | 75029          | be21ec120193...| SOAKIMP12A8C...| 1              |
| 9              | 105313         | 6fbb9ff93663...| SOAKIMP12A8C...| 2              |
+----------------+----------------+----------------+----------------+----------------+
+----------------+----------------+----------------+----------------+---------------------+
| title          | release        | artist_name    | year           | incremental_song_id |
+----------------+----------------+----------------+----------------+---------------------+
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
| The Cove       | Thicker Than...| Jack Johnson   | 0              | 397069              |
+----------------+----------------+----------------+----------------+---------------------+
[2000000 rows x 10 columns]

From there, we can create an MLRecommender. Our trainingData is the data table format of the merged listening history CSV, the userColumn is the user_id column name and the itemColumn is the incremental_song_id column name. The user_id of b80344d063b5ccb3212f76538f3d9e43d87dca9e was randomly picked from the merged CSV data:=.

// Generate recommendations
let recommender = try MLRecommender(trainingData: history_table, userColumn: "user_id", itemColumn: "incremental_song_id")
let recs = try recommender.recommendations(fromUsers: ["b80344d063b5ccb3212f76538f3d9e43d87dca9e"])
print(recs)
Columns:
    user_id	string
    incremental_song_id	integer
    score	float
    rank	integer
Rows: 10
Data:
+----------------+---------------------+----------------+----------------+
| user_id        | incremental_song_id | score          | rank           |
+----------------+---------------------+----------------+----------------+
| b80344d063b5...| 114557              | 0.0461493      | 1              |
| b80344d063b5...| 834311              | 0.0436045      | 2              |
| b80344d063b5...| 939015              | 0.043068       | 3              |
| b80344d063b5...| 955047              | 0.0427589      | 4              |
| b80344d063b5...| 563380              | 0.0426116      | 5              |
| b80344d063b5...| 677759              | 0.0423951      | 6              |
| b80344d063b5...| 689170              | 0.0418951      | 7              |
| b80344d063b5...| 333053              | 0.041788       | 8              |
| b80344d063b5...| 381319              | 0.0403042      | 9              |
| b80344d063b5...| 117491              | 0.0400819      | 10             |
+----------------+---------------------+----------------+----------------+
[10 rows x 4 columns]

But we want to know the song metadata associated with each recommended incremental_song_id. Let’s load the song metadata table and join the recommendations with the song metadata using the incremental id:

// Use the songs data CSV to print the recommended song titles
let songs_csv = Bundle.main.url(forResource: "songs_incremental_id", withExtension: "csv")!
let songs_table = try MLDataTable(contentsOf: songs_csv)
print(songs_table)

let song_title_recs = recs.join(with: songs_table, on: "incremental_song_id")
print(song_title_recs)
Columns:
    X1	string
    song_id	string
    title	undefined
    release	string
    artist_name	string
    year	integer
    incremental_song_id	integer
Rows: 1000000
Data:
+----------------+----------------+----------------+----------------+----------------+
| X1             | song_id        | title          | release        | artist_name    |
+----------------+----------------+----------------+----------------+----------------+
| 0              | SOQMMHC12AB0...| Silent Night   | Monster Ball...| Faster Pussy...|
| 1              | SOVFVAK12A8C...| Tanssi vaan    | Karkuteillä   | Karkkiautoma...|
| 2              | SOGTUKN12AB0...| No One Could...| Butter         | Hudson Mohawke |
| 3              | SOBNYVR12A8C...| Si Vos Querés | De Culo        | Yerba Brava    |
| 4              | SOHSBXH12A8C...| Tangle Of As...| Rene Ablaze ...| Der Mystic     |
| 5              | SOZVAPQ12A8C...| Symphony No....| Berwald: Sym...| David Montgo...|
| 6              | SOQVRHI12A6D...| We Have Got ...| Strictly The...| Sasha / Turb...|
| 7              | SOEYRFT12AB0...| 2 Da Beat Ch...| Da Bomb        | Kris Kross     |
| 8              | SOPMIYT12A6D...| Goodbye        | Danny Boy      | Joseph Locke   |
| 9              | SOJCFMH12A8C...| Mama_ mama c...| March to cad...| The Sun Harb...|
+----------------+----------------+----------------+----------------+----------------+
+----------------+---------------------+
| year           | incremental_song_id |
+----------------+---------------------+
| 2003           | 0                   |
| 1995           | 1                   |
| 2006           | 2                   |
| 2003           | 3                   |
| 0              | 4                   |
| 0              | 5                   |
| 0              | 6                   |
| 1993           | 7                   |
| 0              | 8                   |
| 0              | 9                   |
+----------------+---------------------+
[1000000 rows x 7 columns]


Columns:
    user_id	string
    incremental_song_id	integer
    score	float
    rank	integer
    X1	string
    song_id	string
    title	undefined
    release	string
    artist_name	string
    year	integer
Rows: 11
Data:
+----------------+---------------------+----------------+----------------+----------------+
| user_id        | incremental_song_id | score          | rank           | X1             |
+----------------+---------------------+----------------+----------------+----------------+
| b80344d063b5...| 114557              | 0.0461493      | 1              | 114578         |
| b80344d063b5...| 117491              | 0.0400819      | 10             | 117512         |
| b80344d063b5...| 333053              | 0.041788       | 8              | 333174         |
| b80344d063b5...| 381319              | 0.0403042      | 9              | 381465         |
| b80344d063b5...| 381319              | 0.0403042      | 9              | 444615         |
| b80344d063b5...| 563380              | 0.0426116      | 5              | 563705         |
| b80344d063b5...| 677759              | 0.0423951      | 6              | 678222         |
| b80344d063b5...| 689170              | 0.0418951      | 7              | 689654         |
| b80344d063b5...| 834311              | 0.0436045      | 2              | 834983         |
| b80344d063b5...| 939015              | 0.043068       | 3              | 939863         |
+----------------+---------------------+----------------+----------------+----------------+
+----------------+----------------+----------------+----------------+----------------+
| song_id        | title          | release        | artist_name    | year           |
+----------------+----------------+----------------+----------------+----------------+
| SOHENSJ12AAF...| Great Indoors  | Room For Squ...| John Mayer     | 0              |
| SOOGZYY12A67...| Crying Shame   | In Between D...| Jack Johnson   | 2005           |
| SOGFKJE12A8C...| Sun It Rises   | Fleet Foxes    | Fleet Foxes    | 2008           |
| SOECLAD12AAF...| St. Patrick'...| Room For Squ...| John Mayer     | 0              |
| SOECLAD12AAF...| St. Patrick'...| Room For Squ...| John Mayer     | 0              |
| SOAYTRA12A8C...| All At Once    | Sleep Throug...| Jack Johnson   | 2008           |
| SOKLVUI12A67...| If I Could     | In Between D...| Jack Johnson   | 2005           |
| SOYIJIL12A67...| Posters        | Brushfire Fa...| Jack Johnson   | 2000           |
| SORKFWO12A8C...| Quiet Houses   | Fleet Foxes    | Fleet Foxes    | 2008           |
| SOJAMXH12A8C...| Meadowlarks    | Fleet Foxes    | Fleet Foxes    | 2008           |
+----------------+----------------+----------------+----------------+----------------+
[11 rows x 10 columns]

The last table printed has our recommended songs, and the first one is “Great Indoors”! We can now use our MLRecommender for other user ids.

Wrap Up

First, we took a look at the MLRecommender constructor. Then, we gathered song data from the Million Song Dataset. We modified the dataset to increase legibility and added incremental ids for the song metadata. We loaded the song metadata and listening history into a Swift Playground, created an MLRecommender from the listening history and generated recommended songs. Then, we used the song metadata to join the recommended songs to their titles and artists.

Source Files

Each of the files mentioned in this tutorial can be found here, including:

  • songs.csv: Metadata for one million songs
  • history.txt: Song listening history for multiple users
  • data-parser.py: Python code to manipulate the Million Song Dataset
  • merged_listed_data.csv: Merged dataset of song metadata and listening history
  • merged_listed_data_incremental_song_id.csv: merged_listed_data.csv with incremental ids added
  • songs_incremental_id.csv: songs.csv with incremental ids added
  • MusicRecommender.playground: Swift Playground for creating the MLRecommender

How to Change the Status Bar Style in iOS 12

For some iOS apps, it may be helpful to change the color of the status bar at the top of the screen. For example, if I have a dark background, the default status bar style is hard to read:

Dark iPhone app

To change the appearance of the status bar within a view controller, first add “View controller-based status bar appearance” as an item to your Info.plist with a value of YES:

Info.plist

Then in any view controller, you override the preferredStatusBarStyle property:

override var preferredStatusBarStyle: UIStatusBarStyle {
    return .lightContent
}

And if you ever need to update the status bar color, call setNeedsStatusBarAppearanceUpdate(). Now the full view controller looks like this:

import UIKit

class ViewController: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        // Do any additional setup after loading the view,
        // typically from a nib.
        setNeedsStatusBarAppearanceUpdate()
    }

    override var preferredStatusBarStyle: UIStatusBarStyle {
        return .lightContent
    }
}

Running this view controller, we get a light status bar!

Dark iPhone app with light status bar

Compiling Cub for Shortcuts

Earlier this week I heard about Shortcuts JS, which uses JavaScript to generate Shortcuts. Here’s an example from their homepage:

// We'll use this later to reference the output of a calculation
let calcVar = actionOutput();

// Define a list of actions
const actions = [
  comment({
    text: 'Hello, world!',
  }),
  number({
    number: 42,
  }),
  calculate({
    operand: 3,
    operation: '/',
  }, calcVar),
  showResult({
    // Use the Magic Variable
    text: withVariables`Total is ${calcVar}!`,
  }),
];

While this is a good first step to writing “real code” to make Shortcuts, specifying the operands and others in this fashion is clunky. I wondered how easy it would be to use the syntax tree instead to create the Shortcut, and Will Richardson has done that exact thing for Cub in a blog post:

All I have to do was traverse the syntax tree and generate a Shortcuts file. In terms of code this is fairly straightforward - just add an extension to each AST node that generates the corresponding code.

I’m not familiar enough with iOS app development or Swift to do it myself, but it would be really interesting to write an app that can use something like swift-ast to generate Shortcuts. Who knows what power iOS users could get if they could program advanced Shortcuts using Swift?

Find more posts in the archive.