Skip to content

A Ruby gem to sort large amounts of data using a predictable amount of memory.

License

Notifications You must be signed in to change notification settings

panorama-ed/offline-sort

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

26 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

offline-sort

Sort arbitrarily large collections of data with limited memory usage. Given an enumerable and a sort_by proc, this gem will break the input data into sorted chunks, persist the chunks, and return an Enumerator. Data read from this enumerator will be in its final sorted order.

The size of the chunks and the strategy for serializing and deserializing the data are configurable. The gem comes with builtin strategies for Marshal, MessagePack and YAML.

The development of this gem is documented in this post from the Salsify Engineering Blog.

Installation

Add this line to your application's Gemfile:

gem 'offline-sort'

And then execute:

$ bundle

Or install it yourself as:

$ gem install offline-sort

Usage

  arrays = [ [4,5,6], [7,8,9], [1,2,3] ]
  
  # Create a sorted enumerator
  sorted = OfflineSort.sort(arrays, chunk_size: 1) do |array|
    array.first
  end
  
  # Stream results in sorted order
  sorted.each do |entry|
    # e.g. write to a file
  end

The example above will create 3 files with 1 array each, then output them in sorted order. You should try different values of chunk_size to find the best speed/memory combination for your use case. In general larger chunk sizes will use more memory but run faster.

Sorting is not limited to arrays. You can use anything that can be expressed in a Enumerable#sort_by block.

Using MessagePack

Message pack serialization is faster than the default Ruby Marshal strategy. To enable message pack serialization follow these steps.

gem install msgpack

require 'msgpack'

Requiring MessagePack before you require offline_sort will automatically enable MessagePack serialization in the gem.

Limitations

The MessagePack serialize/deserialize process stringifies hash keys so it is important to write your sort_by in terms of string keys.

Contributing

  1. Fork it
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create new Pull Request

About

A Ruby gem to sort large amounts of data using a predictable amount of memory.

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • Ruby 100.0%