News features in DataFrames.jl 1.3: part 4

By: Blog by Bogumił Kamiński

Re-posted from: https://bkamins.github.io/julialang/2021/12/31/leftjoin.html

Introduction

This post continues the presentation of new features added in DataFrames.jl 1.3. This time I will discuss the leftjoin! function.

The post was written under Julia 1.7.0 and DataFrames.jl 1.3.1.
For performance comparison I have used R 4.1.2 and data.table 0.14.2.
Both in R and Julia I run the computations on 4 threads.

An in place left join

Before release 1.3, DataFrames.jl already offered a rich set of efficient
join functions:
innerjoin, leftjoin, rightjoin, outerjoin, semijoin, antijoin,
and crossjoin.

However, they all have a common limitation: their result is a freshly allocated
data frame.

A common usage scenario in practice is that we would like to add some
new columns to an existing table in-place. This is more efficient and uses less
memory (which is relevant if we work with very large data frames).

Since DataFrames.jl 1.3 this option is available with the addition of the
leftjoin! function. if you run leftjoin!(df1, df2; on=...) then the contract
is that the df1 data frame is updated in-place with columns coming from df2
based on matching rows of both data frames using the columns passed in the on
keyword argument.

It is important to remember that the design of leftjoin! assumes that the
columns of df1 are left unchanged (this is crucial for performance of the
operation). However, this implies that each row in df1 must have at most one
match in df2. Otherwise, leftjoin! would not be able to execute the
operation in-place since new rows would need to be added to df1. If you have
matching duplicate rows in df2 then just use leftjoin.

Here are two minimal examples of leftjoin!.

julia> using DataFrames

julia> using Random

julia> df1 = DataFrame(a=1:6, b=1:6)
6×2 DataFrame
 Row │ a      b
     │ Int64  Int64
─────┼──────────────
   1 │     1      1
   2 │     2      2
   3 │     3      3
   4 │     4      4
   5 │     5      5
   6 │     6      6

julia> df2 = DataFrame(a=[2, 4, 6], c=1:3)
3×2 DataFrame
 Row │ a      c
     │ Int64  Int64
─────┼──────────────
   1 │     2      1
   2 │     4      2
   3 │     6      3

julia> leftjoin!(df1, df2, on=:a)
6×3 DataFrame
 Row │ a      b      c
     │ Int64  Int64  Int64?
─────┼───────────────────────
   1 │     1      1  missing
   2 │     2      2        1
   3 │     3      3  missing
   4 │     4      4        2
   5 │     5      5  missing
   6 │     6      6        3

julia> Random.seed!(1234);

julia> df1 = DataFrame(a=randperm(6), b=1:6)
6×2 DataFrame
 Row │ a      b
     │ Int64  Int64
─────┼──────────────
   1 │     3      1
   2 │     2      2
   3 │     6      3
   4 │     5      4
   5 │     1      5
   6 │     4      6

julia> df2 = DataFrame(a=shuffle!([2, 4, 6]), c=1:3)
3×2 DataFrame
 Row │ a      c
     │ Int64  Int64
─────┼──────────────
   1 │     4      1
   2 │     2      2
   3 │     6      3

julia> leftjoin!(df1, df2, on=:a)
6×3 DataFrame
 Row │ a      b      c
     │ Int64  Int64  Int64?
─────┼───────────────────────
   1 │     3      1  missing
   2 │     2      2        2
   3 │     6      3        3
   4 │     5      4  missing
   5 │     1      5  missing
   6 │     4      6        1

Performance benchmarks

Now let me run two performance benchmarks of DataFrames.jl against data.table.
In the benchmarks I use 32-bit integers to ensure comparability of memory
footprint of objects between R and Julia.

The first test is on sorted key column. We start with Julia:

julia> df1 = DataFrame(a=Int32.(1:10^8));

julia> df2 = DataFrame(a=Int32.(1:10^8), x = true);

julia> @time leftjoin!(df1, df2, on=:a);
  2.867632 seconds (221.45 k allocations: 2.433 GiB, 6.47% gc time, 3.98% compilation time)

julia> df1 = DataFrame(a=Int32.(1:10^8));

julia> @time leftjoin!(df1, df2, on=:a);
  2.934633 seconds (150 allocations: 2.421 GiB, 8.19% gc time)

And now the data.table:

> library(data.table)
> df1 = data.table(a=1:10^8)
> df2 = data.table(a=1:10^8, x=TRUE)
> system.time(df1[df2, on = 'a', x := i.x])
   user  system elapsed
  8.067   1.106   5.679
> df1 = data.table(a=1:10^8)
> system.time(df1[df2, on = 'a', x := i.x])
   user  system elapsed
  9.305   1.184   6.652

As you can see for sorted data DataFrames.jl timings are competitive. Let us
now check shuffled data.

We start with DataFrames.jl:

julia> df1 = DataFrame(a=shuffle!(Int32.(1:10^8)));

julia> df2 = DataFrame(a=shuffle!(Int32.(1:10^8)), x = true);

julia> @time leftjoin!(df1, df2, on=:a);
 23.881552 seconds (175 allocations: 3.167 GiB, 1.43% gc time)

julia> df1 = DataFrame(a=Int32.(1:10^8));

julia> @time leftjoin!(df1, df2, on=:a);
 18.909113 seconds (175 allocations: 3.167 GiB, 1.40% gc time)

and now the timing for data.table:

> df1 = data.table(a=sample(1:10^8))
> df2 = data.table(a=sample(1:10^8), x=TRUE)
> system.time(df1[df2, on = 'a', x := i.x])
   user  system elapsed
 30.778   1.791  23.153
> df1 = data.table(a=sample(1:10^8))
> system.time(df1[df2, on = 'a', x := i.x])
   user  system elapsed
 30.586   1.695  22.893

Again the timing of DataFrames.jl is competitive.

(let me stress here that this is just one set of examples and relative
performance of different packages can vary depending on the data and the
operating environment; the point of these tests is to show that currently
DataFrmes.jl is not much worse than data.table in execution of joins, as this
was a performance bottleneck of DataFrames.jl in the past)

Conclusions

This time in the post I have focused on a single function: the leftjoin!.
The reason is that I believe that addition of an in-place left join to
DataFrames.jl is quite significant since it is needed in many data processing
scenarios, especially when working with large tables.

Advent of Code 2021 – Day 21

By: Julia on Eric Burden

Re-posted from: https://ericburden.work/blog/2021/12/31/advent-of-code-2021-day-21/

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

Day 21 – Dirac Dice

Find the problem description HERE.

The Input – Two Lines, Please

The input for today is really simple, just two lines, each of which ends with a number representing the starting board space of a player, in order. The major thing here is having structs to hold and represent each Player and the Game overall, which is also pretty straightforward. There may be a more elegant way to represent the data models for today’s problem, but this seems like a really simple and understandable way to do it.

# Data Structures --------------------------------------------------------------

# Represents a player's current "state", their current board position and score
struct Player
	position::Int64
	points::Int64
end
Player(pos::Int64) = Player(pos, 0)

# Represents the current state of the game, both players' board position and
# current score
struct Game
	player1::Player
	player2::Player
end


# Helper Functions -------------------------------------------------------------

# Given a string, return a Player whose position is the number at the end of
# the string.
playerpos(s) = Player(parse(Int, s[end]))


# Ingest the Data -------------------------------------------------------------

# There's only two lines, the first line for player one and the second line for
# player two, both of which end with a single digit representing that
# player's starting space
function ingest(path)
    return open(path) do f
		player1 = playerpos(readline(f))
		player2 = playerpos(readline(f))
		Game(player1, player2)
    end
end

Part One – I Want to Play a Game

Ok, so no more games with giant squids, now we’re playing games with… the submarine. At this point, we’ve done so much work on this submarine’s systems, surely we can outsmart it, right? I certainly hope so, otherwise we may have a tough time with the remaining days’ puzzles. Actually, part one seems suspiciously straightforward. There’s a bit of implementation here, but it all boils down to looping over the die rolls (which we can calculate in advance), finding a winner, then returning some version of the final game state. We’ve got this!

# Helper Functions -------------------------------------------------------------

# Given a board position and a roll, return the next position that results from
# that roll. The only tricky bit here is that 10 + 1 wraps around to 1 instead
# of zero.
function nextposition(pos::Int64, roll::Int64)
    pos += roll
    pos > 10 && pos % 10 == 0 && return 10
    pos > 10 && return pos % 10
    return pos
end

# Given a player and a roll, return a `Player` at the next position that will 
# result from the given roll with their score updated to reflect the move.
function move(player::Player, roll::Int64)
    position = nextposition(player.position, roll)
    points = player.points + position
    return Player(position, points)
end

# Given a game board, a roll, and an optional boolean value indicating whether
# or not it is Player 1's turn, return a `Game` reflecting the state that would
# be achieved if the indicated player moves by the amount given by `roll`
function move(game::Game, roll::Int64, player1 = true)
    if player1
        player1 = move(game.player1, roll)
        return Game(player1, game.player2)
    else
        player2 = move(game.player2, roll)
        return Game(game.player1, player2)
    end
end

# Take a `Game` an return either the current high score or the current low score
highscore(game::Game) = max(game.player1.points, game.player2.points)
lowscore(game::Game)  = min(game.player1.points, game.player2.points)

# Some Useful Data Structures --------------------------------------------------

# Literally an empty struct for the purposes of creating an iterator over the
# possible die rolls
struct Die end

# On the first roll, the die returns `6` (1 + 2 + 3) and the next starting number
# of `4`. On subsequent rolls, return the sum of the next three numbers and the
# fourth number in sequence as a tuple, to keep the iterator going. The `if`
# statements are there for wrapping around 100 if need be (I don't think it
# actually happens).
Base.iterate(::Die) = (6, 4)
function Base.iterate(::Die, start::Int64)
    (nextvalue, nextstart) = if start < 98
        (sum(start:start+2), start + 3)
    elseif start == 98
        (297, 1)
    elseif start == 99
        (200, 2)
    elseif start == 100
        (103, 3)
    end

    return (nextvalue, nextstart)
end


# Solve Part One ---------------------------------------------------------------

# Play the game as described! Roll the die, move the players, check the score. 
# Whenever a winner is found, return the number of rolls (3 * the number of
# rounds) multiplied by the lowest player score
function part1(game)
    die = Die()
    player1turn = true
    round = 0
    for roll in die
        game = move(game, roll, player1turn)
        round += 1
        highscore(game) >= 1000 && break
        player1turn = !player1turn
    end
    rolls = round * 3
    return rolls * lowscore(game)
end

There wasn’t even any tricky input like yesterday. In fact, part one seemed almost… too easy…

Part Two – Wake Up

Oookay… Part two has us playing with the fabric of reality. Neat! Now, every time we roll the ‘special’ die, the universe splits into 27 new alternate realities, one where we rolled a total of 3, three where we rolled a 4, etc. So, we’re keeping up with the number of wins per player, for a given game state. Like, a frequency analysis? It’s lanternfish all the way down!

# Constants --------------------------------------------------------------------

# Of the 27 alternate realities created by three rolls of the 'Dirac Die', we
# already know in how many of those universes we rolled a total of `3` (1), a 
# total of `4` (3), and so on. Since these proportions don't change, we can
# define a constant.
const FREQUENCIES = Dict(3 => 1, 4 => 3, 5 => 6, 6 => 7, 7 => 6, 8 => 3, 9 => 1)


# Data Structures --------------------------------------------------------------

# Just a type alias for a Dict to keep track of the number of universes that
# current exist for each found game state.
const GameFreqMap = Dict{Game,Int64}


# Helper Functions -------------------------------------------------------------

# Shorthand function for convenience
function set!(dict, key, value)
    dict[key] = value
end

# For each round of the game, the active player "moves" 27 time in 27 alternate
# realities. We simulate this by keeping track of the number of games in each
# particular 'state' (a `Game` struct) and creating a new `GameFreqMap` where
# each previous game state is advanced by a roll of 3, 4, 5, 6, 7, 8, or 9 (the 
# possible values from three rolls from 1-3) the number of times those values
# can be made by rolling three three-sided dice. If, say, a particular game
# state existed in 10 alternate realities, then after moving there would exist
# 10 realities where that player rolled 3, 30 realities where that player rolled
# 4, 60 realities where that player rolled 5, etc.
function move(games::GameFreqMap, player1 = true)
    nextgames = GameFreqMap()
    victories = 0
    for (game, count) in games
        for (roll, frequency) in FREQUENCIES
            newstate = move(game, roll, player1)
            newcount = count * frequency
            if newstate.player1.points >= 21 || newstate.player2.points >= 21
                # If either player won, there's no need to continue this game
                # state forward, just count the number of realities where that
                # player won.
                victories += newcount
            else
                # Otherwise, check the next games frequency map for this new
                # state, initialize its count to 0 if it doesn't exist, then
                # add the number of new realities where this new state exists.
                newstate ∈ keys(nextgames) || set!(nextgames, newstate, 0)
                nextgames[newstate] += newcount
            end
        end
    end

    return (nextgames, victories)
end


# Solve Part Two ---------------------------------------------------------------

# Play the game, roll the crazy die, move the player, repeat until all the games
# have played themselves out. Each time a player wins a game (or more) in one of 
# the alternate realities, add it (them) to the ongoing sum.
function part2(input)
    games = GameFreqMap(input => 1)
    victoryarray = [0, 0]
    player1turn = true

    while !isempty(games)
        (games, victories) = move(games, player1turn)
        if player1turn
            victoryarray[1] += victories
        else
            victoryarray[2] += victories
        end
        player1turn = !player1turn
    end

    return maximum(victoryarray)
end

Yep. Seems like this year’s theme is frequency analysis. I wonder if this is the last problem of this type we’ll see this year, or of there’s one more waiting in the wings… (since this blog post is coming out after Christmas, I’ll know the answer to this question by the time I post it, but acknowledging that means I’d miss out on the suspense!)

Wrap Up

You know, one of the things I really do enjoy about AoC is how these approaches get re-used and tweaked over several days, which really helps drive home an understanding and recognition of this type of problem in many different circumstances. After this year, I should be a lot better at spotting opportunities for frequency analysis in real life, which can be a huge win in terms of algorithmic run times. This is a good argument in favor of practicing all kinds of algorithmic problems and approaches, since you can often find that at least part of a “real world” problem can be solved better, faster, more efficiently when you have a good grasp on some of these algorithmic building blocks. I’m definitely learning a lot this year, and for that, I am grateful.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!

Advent of Code 2021 – Day 21

By: Julia on Eric Burden

Re-posted from: https://www.ericburden.work/blog/2021/12/31/advent-of-code-2021-day-21/

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

Day 21 – Dirac Dice

Find the problem description HERE.

The Input – Two Lines, Please

The input for today is really simple, just two lines, each of which ends with a number representing the starting board space of a player, in order. The major thing here is having structs to hold and represent each Player and the Game overall, which is also pretty straightforward. There may be a more elegant way to represent the data models for today’s problem, but this seems like a really simple and understandable way to do it.

# Data Structures --------------------------------------------------------------

# Represents a player's current "state", their current board position and score
struct Player
	position::Int64
	points::Int64
end
Player(pos::Int64) = Player(pos, 0)

# Represents the current state of the game, both players' board position and
# current score
struct Game
	player1::Player
	player2::Player
end


# Helper Functions -------------------------------------------------------------

# Given a string, return a Player whose position is the number at the end of
# the string.
playerpos(s) = Player(parse(Int, s[end]))


# Ingest the Data -------------------------------------------------------------

# There's only two lines, the first line for player one and the second line for
# player two, both of which end with a single digit representing that
# player's starting space
function ingest(path)
    return open(path) do f
		player1 = playerpos(readline(f))
		player2 = playerpos(readline(f))
		Game(player1, player2)
    end
end

Part One – I Want to Play a Game

Ok, so no more games with giant squids, now we’re playing games with… the submarine. At this point, we’ve done so much work on this submarine’s systems, surely we can outsmart it, right? I certainly hope so, otherwise we may have a tough time with the remaining days’ puzzles. Actually, part one seems suspiciously straightforward. There’s a bit of implementation here, but it all boils down to looping over the die rolls (which we can calculate in advance), finding a winner, then returning some version of the final game state. We’ve got this!

# Helper Functions -------------------------------------------------------------

# Given a board position and a roll, return the next position that results from
# that roll. The only tricky bit here is that 10 + 1 wraps around to 1 instead
# of zero.
function nextposition(pos::Int64, roll::Int64)
    pos += roll
    pos > 10 && pos % 10 == 0 && return 10
    pos > 10 && return pos % 10
    return pos
end

# Given a player and a roll, return a `Player` at the next position that will 
# result from the given roll with their score updated to reflect the move.
function move(player::Player, roll::Int64)
    position = nextposition(player.position, roll)
    points = player.points + position
    return Player(position, points)
end

# Given a game board, a roll, and an optional boolean value indicating whether
# or not it is Player 1's turn, return a `Game` reflecting the state that would
# be achieved if the indicated player moves by the amount given by `roll`
function move(game::Game, roll::Int64, player1 = true)
    if player1
        player1 = move(game.player1, roll)
        return Game(player1, game.player2)
    else
        player2 = move(game.player2, roll)
        return Game(game.player1, player2)
    end
end

# Take a `Game` an return either the current high score or the current low score
highscore(game::Game) = max(game.player1.points, game.player2.points)
lowscore(game::Game)  = min(game.player1.points, game.player2.points)

# Some Useful Data Structures --------------------------------------------------

# Literally an empty struct for the purposes of creating an iterator over the
# possible die rolls
struct Die end

# On the first roll, the die returns `6` (1 + 2 + 3) and the next starting number
# of `4`. On subsequent rolls, return the sum of the next three numbers and the
# fourth number in sequence as a tuple, to keep the iterator going. The `if`
# statements are there for wrapping around 100 if need be (I don't think it
# actually happens).
Base.iterate(::Die) = (6, 4)
function Base.iterate(::Die, start::Int64)
    (nextvalue, nextstart) = if start < 98
        (sum(start:start+2), start + 3)
    elseif start == 98
        (297, 1)
    elseif start == 99
        (200, 2)
    elseif start == 100
        (103, 3)
    end

    return (nextvalue, nextstart)
end


# Solve Part One ---------------------------------------------------------------

# Play the game as described! Roll the die, move the players, check the score. 
# Whenever a winner is found, return the number of rolls (3 * the number of
# rounds) multiplied by the lowest player score
function part1(game)
    die = Die()
    player1turn = true
    round = 0
    for roll in die
        game = move(game, roll, player1turn)
        round += 1
        highscore(game) >= 1000 && break
        player1turn = !player1turn
    end
    rolls = round * 3
    return rolls * lowscore(game)
end

There wasn’t even any tricky input like yesterday. In fact, part one seemed almost… too easy…

Part Two – Wake Up

Oookay… Part two has us playing with the fabric of reality. Neat! Now, every time we roll the ‘special’ die, the universe splits into 27 new alternate realities, one where we rolled a total of 3, three where we rolled a 4, etc. So, we’re keeping up with the number of wins per player, for a given game state. Like, a frequency analysis? It’s lanternfish all the way down!

# Constants --------------------------------------------------------------------

# Of the 27 alternate realities created by three rolls of the 'Dirac Die', we
# already know in how many of those universes we rolled a total of `3` (1), a 
# total of `4` (3), and so on. Since these proportions don't change, we can
# define a constant.
const FREQUENCIES = Dict(3 => 1, 4 => 3, 5 => 6, 6 => 7, 7 => 6, 8 => 3, 9 => 1)


# Data Structures --------------------------------------------------------------

# Just a type alias for a Dict to keep track of the number of universes that
# current exist for each found game state.
const GameFreqMap = Dict{Game,Int64}


# Helper Functions -------------------------------------------------------------

# Shorthand function for convenience
function set!(dict, key, value)
    dict[key] = value
end

# For each round of the game, the active player "moves" 27 time in 27 alternate
# realities. We simulate this by keeping track of the number of games in each
# particular 'state' (a `Game` struct) and creating a new `GameFreqMap` where
# each previous game state is advanced by a roll of 3, 4, 5, 6, 7, 8, or 9 (the 
# possible values from three rolls from 1-3) the number of times those values
# can be made by rolling three three-sided dice. If, say, a particular game
# state existed in 10 alternate realities, then after moving there would exist
# 10 realities where that player rolled 3, 30 realities where that player rolled
# 4, 60 realities where that player rolled 5, etc.
function move(games::GameFreqMap, player1 = true)
    nextgames = GameFreqMap()
    victories = 0
    for (game, count) in games
        for (roll, frequency) in FREQUENCIES
            newstate = move(game, roll, player1)
            newcount = count * frequency
            if newstate.player1.points >= 21 || newstate.player2.points >= 21
                # If either player won, there's no need to continue this game
                # state forward, just count the number of realities where that
                # player won.
                victories += newcount
            else
                # Otherwise, check the next games frequency map for this new
                # state, initialize its count to 0 if it doesn't exist, then
                # add the number of new realities where this new state exists.
                newstate ∈ keys(nextgames) || set!(nextgames, newstate, 0)
                nextgames[newstate] += newcount
            end
        end
    end

    return (nextgames, victories)
end


# Solve Part Two ---------------------------------------------------------------

# Play the game, roll the crazy die, move the player, repeat until all the games
# have played themselves out. Each time a player wins a game (or more) in one of 
# the alternate realities, add it (them) to the ongoing sum.
function part2(input)
    games = GameFreqMap(input => 1)
    victoryarray = [0, 0]
    player1turn = true

    while !isempty(games)
        (games, victories) = move(games, player1turn)
        if player1turn
            victoryarray[1] += victories
        else
            victoryarray[2] += victories
        end
        player1turn = !player1turn
    end

    return maximum(victoryarray)
end

Yep. Seems like this year’s theme is frequency analysis. I wonder if this is the last problem of this type we’ll see this year, or of there’s one more waiting in the wings… (since this blog post is coming out after Christmas, I’ll know the answer to this question by the time I post it, but acknowledging that means I’d miss out on the suspense!)

Wrap Up

You know, one of the things I really do enjoy about AoC is how these approaches get re-used and tweaked over several days, which really helps drive home an understanding and recognition of this type of problem in many different circumstances. After this year, I should be a lot better at spotting opportunities for frequency analysis in real life, which can be a huge win in terms of algorithmic run times. This is a good argument in favor of practicing all kinds of algorithmic problems and approaches, since you can often find that at least part of a “real world” problem can be solved better, faster, more efficiently when you have a good grasp on some of these algorithmic building blocks. I’m definitely learning a lot this year, and for that, I am grateful.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!