🚪 revdoor

revdoor is a single-file C++ library for visiting revolving door combinations.

The combinations without replacement generator implements Algorithm R from TAOCP 7.2.1.3 [1]. The combinations with replacement generator implements the same algorithm, modified to support replacement.

The algorithms visit combinations by indicating at most two pairs of items to swap in and out on each iteration.

The source code is available on GitHub:
https://github.com/dstein64/revdoor

Continue reading

Tagged , , , , | Leave a comment

⏲️ vim-startuptime and 🖼️ vim-win

I recently implemented two Vim plugins (they also work on Neovim).

vim-startuptime

vim-startuptime is a plugin for viewing Vim startup event timing—reported in milliseconds. This can be helpful when trying to modify your configuration to improve Vim’s startup time.

  • Launch vim-startuptime with :StartupTime.
  • Press <space> on events to get additional information.
  • Press <enter> on sourcing events to load the corresponding file in a new split.
  • Access documentation with :help vim-startuptime.

The source code—along with installation instructions—is available on GitHub:
https://github.com/dstein64/vim-startuptime

vim-win

vim-win is a plugin for managing windows, including 1) selecting windows, 2) swapping window buffers, and 3) resizing windows. Full functionality requires vim>=8.2 or nvim>=0.4.0.

  • Enter vim-win with <leader>w or :Win.
  • Arrows or hjkl keys are used for movement.
  • Change windows with movement keys or numbers.
  • Hold <shift> and use movement keys to resize the active window.
  • Press s or S followed by a movement key or window number, to swap buffers.
  • Press ? to show a help message.
  • Press <esc> to leave vim-win.
  • Access documentation with :help vim-win.

The source code—along with installation instructions—is available on GitHub:
https://github.com/dstein64/vim-win

Tagged , , , | Leave a comment

🎨 gifcast Color Profiles

gifcast—discussed in a prior post—now supports color profile selection.

The following animated GIFs—generated with gifcast—show a sample of available profiles.

Here is the asciinema cast file used to generate the animated GIFs: profile_demo.cast

Tagged , , | Leave a comment

▶️ gifcast

I implemented gifcast, a web page for converting asciinema casts to animated GIFs. Here’s the link:
https://dstein64.github.io/gifcast/

The JavaScript source code is available on GitHub:
https://github.com/dstein64/gifcast

The example below was generated with gifcast.

Here is the asciinema cast file used to generate the animated GIF: gifcast.cast

Tagged , , , , | Leave a comment

Compressing VGG for Style Transfer

32-bit float (no quantization) 8-bit 7-bit
6-bit 5-bit 4-bit
3-bit 2-bit 1-bit

I recently implemented pastiche—discussed in a prior post—for applying neural style transfer. I encountered a size limit when uploading the library to PyPI, as a package cannot exceed 60MB. The 32-bit floating point weights for the underlying VGG model [1] were contained in an 80MB file. My package was subsequently approved for a size limit increase that could accommodate the VGG weights as-is, but I was still interested in compressing the model.

Various techniques have been proposed for compressing neural networks—including distillation [2] and quantization [3,4]—which have been shown to work well in the context of classification. My problem was in the context of style transfer, so I was not sure how model compression would impact the results.

Experiments

I decided to experiment with weight quantization, using a scheme where I could store the quantized weights on disk, and then uncompress the weights to full 32-bit floats at runtime. This quantization scheme would allow me to continue using my existing code after the model is loaded. I am not targeting environments where memory is a constraint, so I was not particularly interested in approaches that would also reduce the model footprint at runtime. I used kmeans1d—discussed in a prior post—for quantizing each layer’s weights.

Continue reading

Tagged , , , , | Leave a comment

SMAWK in C++

I recently implemented kmeans1d—discussed in a prior post—for efficiently performing globally optimal 1D k-means clustering. The implementation utilizes the SMAWK algorithm (Aggarwal et al., 1987), which calculates argmin(i) for each row i of an arbitrary n × m totally monotone matrix, in O(m(1 + lg(n/m))).

I’ve factored out my SMAWK C++ code into the example below. In general, SMAWK works with an implicitly defined matrix, utilizing a function that returns a value corresponding to an arbitrary position in the matrix. An explicitly defined matrix is used in the example for the purpose of illustration.

The program prints the column indices corresponding to the minimum element of each row in a totally monotone matrix. The matrix is from monge.pdf—a course document that I found online.

Continue reading

Tagged , , | Leave a comment

kmeans1d: Globally Optimal Efficient 1D k-means Clustering

I implemented kmeans1d, a Python library for performing k-means clustering on 1D data, based on the algorithm in (Xiaolin 1991), as presented in section 2.2 of (Grønlund et al., 2017).

Globally optimal k-means clustering is NP-hard for multi-dimensional data. LLoyd’s algorithm is a popular approach for finding a locally optimal solution. For 1-dimensional data, there are polynomial time algorithms.

kmeans1d contains an O(kn + n log n) dynamic programming algorithm for finding the globally optimal k clusters for n 1D data points. The code is written in C++—for faster execution than a pure Python implementation—and wrapped in Python.

The source code is available on GitHub:
https://github.com/dstein64/kmeans1d

Continue reading

Tagged , , , | Leave a comment

Style Transfer Medley

I used the pastiche style transfer program—discussed in a prior post—to create the video shown above. The content image is a photo I took in Boston in 2015, and the style images were randomly sampled from the test images of the Painter by Numbers Kaggle competition.

The frames used in the video were retained during gradient descent by using pastiche‘s --workspace option.

The Python script for generating the video is on GitHub:
https://gist.github.com/dstein64/5dcc67fa43cc0d13d6d4d544095a1382

Tagged , , , | Leave a comment

🎨 pastiche

pastiche A literary, artistic, musical, or architectural work that imitates the style of previous work.

―Merriam-Webster dictionary

I recently implemented pastiche, a PyTorch-based Python program for applying neural style transfer [1]. Given a content image C and a style image S, neural style transfer (NST) synthesizes a new image I that retains the content from C and style from S. This is achieved by iteratively updating I so that relevant properties of its representation within the VGG neural network [3] approach the corresponding properties for C and S.

The library is available on PyPI and can be installed with pip.

$ pip3 install pastiche

The example image above was synthesized by applying the style from Vincent van Gogh’s The Starry Night to a photo I took in Boston in 2015.

Continue reading

Tagged , , , , | Leave a comment

Debugging in Vim

Vim 8.1 was released in May 2018. The “main new feature” was official support for running a terminal within vim. Along with this came a built-in debugger plugin, termdebug, which provides a visual interface for interacting with gdb. This post walks through an example session using termdebug.

Continue reading

Tagged , , | 21 Comments