Efficient moving window for high-speed data processing.

Related tags

Images tools window
Overview

Moving Window Data Structure

Copyright (c) 2012. Jake Brukhman. ([email protected]). All rights reserved. See the LICENSE file for BSD-style license.


Installation

You need at least the following weekly version of Go:

go version weekly.2012-02-07 +52ba9506bd99

You can then use the 'go' command to obtain the package:

$ go get github.com/jbrukh/window
$ go install -v github.com/jbrukh/window

To run the benchmarks:

$ go test -test.bench=".*"

Documentation

A moving window is a FIFO data structure with a fixed maximum size and the property that if the size has been reached and an element is pushed into the window, then the head of the window is pushed out to accomodate it.

Typically, two operations are of importance whilst working with moving windows in a high-performance context. First, pushes are expected to happen often as lots of data comes in. Secondly, the window is typically converted to a simple array for interfacing with secondary processes, such as graphing.

The MovingWindow object implemented in this package optimizes both of these operations by trading off with space complexity. Given two parameters -- size S and space parameter M -- the window will allocate a single backing array of length SM and complexity of background copy operations will be proportional to 1/M.

As demonstrated in the benchmarks below, a MovingWindow can operate approximately 20x faster than a list-backed implementation and 3-4x faster than a ring-backed implementation. However, it is 5000x more efficient at generating array output because it can take slices of the backing array. It is also worth noting that most of the performance gain is reached quickly with relatively small M: for instance, setting M := S/100 is a good starting point.

Benchmarks

Here are some benchmarks:

 BenchmarkListS1000             10         188497800 ns/op
 BenchmarkRingS1000             50          35760520 ns/op
 BenchmarkS1000M1                1        2817453000 ns/op
 BenchmarkS1000M10             200           9012795 ns/op
 BenchmarkS1000M100            200           8807370 ns/op
 BenchmarkS1000M500            200           8471190 ns/op
 BenchmarkSlicifyList        50000             41656 ns/op
 BenchmarkSlicifyRing        50000             48598 ns/op
 BenchmarkSlicifyWindow  200000000              9.30 ns/op

The first set of benchmarks measures the time it takes for 1,000,000 points to go through a size 1000 list-based moving window, ring-based moving window, and a MovingWindow under different values of its space parameter M. The later test measures how long it takes to convert the moving windows into a slice, a common operation.

Owner
Jake Brukhman
Jake Brukhman
Go package for fast high-level image processing powered by libvips C library

bimg Small Go package for fast high-level image processing using libvips via C bindings, providing a simple programmatic API. bimg was designed to be

Tom 2k Aug 16, 2022
Fast, simple, scalable, Docker-ready HTTP microservice for high-level image processing

imaginary Fast HTTP microservice written in Go for high-level image processing backed by bimg and libvips. imaginary can be used as private or public

Tom 4.5k Aug 17, 2022
Image processing algorithms in pure Go

bild A collection of parallel image processing algorithms in pure Go. The aim of this project is simplicity in use and development over absolute high

Anthony N. Simon 3.6k Aug 9, 2022
Image processing library and rendering toolkit for Go.

blend Image processing library and rendering toolkit for Go. (WIP) Installation: This library is compatible with Go1. go get github.com/phrozen/blend

Guillermo Estrada 60 Aug 14, 2022
A lightning fast image processing and resizing library for Go

govips A lightning fast image processing and resizing library for Go This package wraps the core functionality of libvips image processing library by

David Byttow 731 Aug 8, 2022
Imaging is a simple image processing package for Go

Imaging Package imaging provides basic image processing functions (resize, rotate, crop, brightness/contrast adjustments, etc.). All the image process

Grigory Dryapak 4.3k Aug 18, 2022
Storage and image processing server written in Go

Mort An S3-compatible image processing server written in Go. Still in active development. Features HTTP server Resize, Rotate, SmartCrop Convert (JPEG

Marcin Kaciuba 459 Aug 12, 2022
A library for basic image processing in Go.

Imaging Package imaging provides basic image processing functions (resize, rotate, crop, brightness/contrast adjustments, etc.). All the image process

null 0 Nov 26, 2021
A library for basic image processing in Go.

Imaging Package imaging provides basic image processing functions (resize, rotate, crop, brightness/contrast adjustments, etc.). All the image process

null 0 Nov 26, 2021
Pixelizer is an efficient image pixelizer written in go

Pixelizer is an image pixelizer written in go. It allows very simple and intuitive CLI pixelization. Installation To install Pixelizer, you

Rewan_ 104 Jul 2, 2022
A simple, efficient spring animation library for smooth, natural motion🎼

Harmonica A simple, efficient spring animation library for smooth, natural motion. It even works well on the command line.

Charm 558 Aug 13, 2022
Publish Your GIS Data(Vector Data) to PostGIS and Geoserver

GISManager Publish Your GIS Data(Vector Data) to PostGIS and Geoserver How to install: go get -v github.com/hishamkaram/gismanager Usage: testdata fol

Hisham waleed karam 47 Aug 13, 2022
Go bindings for libVLC and high-level media player interface

Go bindings for libVLC 2.X/3.X/4.X and high-level media player interface. The package can be useful for adding multimedia capabilities to applications

Adrian-George Bostan 310 Jul 28, 2022
⚡High Performance DICOM Medical Image Parser in Go.

dicom High Performance Golang DICOM Medical Image Parser ?? v1.0 just released! This is a library and command-line tool to read, write, and generally

Suyash Kumar 753 Jul 28, 2022
An iterative algorithm to generate high quality triangulated images.

Triangula uses a modified genetic algorithm to triangulate images. It works best with images smaller than 3000px and with fewer than 3000 points, typically producing an optimal result within a couple of minutes.

null 3.7k Aug 12, 2022
Generate high-quality triangulated art from images.

An iterative algorithm to generate high quality triangulated images.

null 53 May 26, 2021
General purpose library for reading, writing and working with OpenStreetMap data

osm This package is a general purpose library for reading, writing and working with OpenStreetMap data in Go (golang). It has the ability to read OSM

Paul Mach 223 Aug 13, 2022
Decode embedded EXIF meta data from image files.

goexif Provides decoding of basic exif and tiff encoded data. Still in alpha - no guarantees. Suggestions and pull requests are welcome. Functionality

Robert Carlsen 526 Aug 7, 2022
A repository for plotting and visualizing data

Gonum Plot gonum/plot is the new, official fork of code.google.com/p/plotinum. It provides an API for building and drawing plots in Go. Note that this

null 2.2k Aug 11, 2022