vector-backed-sorted-map

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

vector-backed-sorted-map

(★ 42)

A sorted map implementation designed for ultra-fast initialization and merge operations.

vector-backed-sorted-map Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# vector-backed-sorted-map
[![Clojars Project](https://img.shields.io/clojars/v/com.rpl/vector-backed-sorted-map.svg)](https://clojars.org/com.rpl/vector-backed-sorted-map)

A sorted map implementation designed for ultra-fast initialization and merge operations.

Maps returned by this library behave like those returned by Clojure `sorted-map` (PersistentTreeMap), but they have O(1) instantiation time instead of O(N log N). Instantiating a vector-backed sorted map (VBSM) will be dramatically faster than `sorted-map` for more than a small number of elements. The only catch is that your k/v pairs must already be sorted. It's not hard to structure your application such that the data will always be sorted in a previous step or read from disk in sorted order.

## Why do I want this?

The whole point is to be able to provide `sorted-map`-like access pattern over data that isn't currently in a `sorted-map`.

Let's say you're writing a flat-file database of sorted k/v pairs (something like RocksDB). The files are already sorted in the regular course of operation, but when you load a "file" or a "block" from disk to service a read, that data isn't currently in a `sorted-map`. If you put it into one, you'll pay O(N log N) to do so, which is a pretty bad deal if you're only going to look up a single k/v pair. Even if you'll do something smart like cache the resulting `sorted-map` for future read operations, you had a pay a greater-than-linear cost to get that map into your cache!

There are a number of existing sorted map libraries that support faster initialization when the input is explicitly sorted, but sadly Clojure doesn't have one, and none of the exiting data structures are compatible with external options like Java's TreeMap.

## Usage

Add a dependency on the [Clojars package](https://clojars.org/com.rpl/vector-backed-sorted-map)

In your code:

`(require 'com.rpl.vector-backed-sorted-map :as vbsm)`

To use, provide a vector of k/v tuples, and optionally a key comparator:

`(let [m (vbsm/vector-backed-sorted-map [[0 0] [1 1] [2 2]])])`

The vector tuples will never be mutated or modified in any way and can safely be reused elsewhere.

The tuples *must* be in already-sorted order! VBSM makes no effort to sort your input, but if assertions are enabled, it will verify that they're in sorted order. This verification behavior is really handy when you're just setting up a system that uses VBSMs, but it is also very, very expensive, so it's a good idea to disable assertions if you're aiming for high performance.

## Backing vector access

If you are using VBSMs explicitly in performance-critical code, it's often handy to be able to set aside the map wrapper all together and just access the backing vector. `vec` and similar core library fns would end up making a copy of the backing vector, and that's no good; so we provide a special helper fn called `vectorize`. `vectorize` exposes the direct backing vector in O(1) time, unless you call it on a VBSM that has overlaid modifications, in which case it will be O(N). (See read-only discussion below for more information).

## Fast merge support

Because of their flat structure, VBSMs are very amenable to high-performance merge operations. The library provides a handy `merge-sorted-optimal` function that implements a size-aware merging strategy, swapping between "one by one" and "bulk" modes based on relative sizes of the VBSMs being merged. Using this function tends to beat Clojure `merge` very handily.

## Read-only vs "updatable" VBSMs

When you instantiate a VBSM via `vector-backed-sorted-map`, you get back an "updatable" VBSM, that is, one that can be modified normally by `assoc`, `dissoc`, etc. This updatability is provided via an internal hidden overlay map, which is just a regular Clojure sorted-map. This approach avoids uncesssary vector surgery and makes random updates fairly cheap, particularly when the total number of updates is relatively small. However, there is an added cost at iteration or `vectorize` time, as the overlay has to be flattened into the backing vector to produce a new backing vector, making the operation take O(N).

It can be difficult to reason about whether a given map ever gets updated, so we provide the option to get a "read-only" VBSM by calling `read-only-vector-backed-sorted-map`. `assoc`, `dissoc`, etc will throw exceptions when invoked on a read-only VBSM. Using a read-only VBSM allows you to ensure that merge and `vectorize` operations down the road will always be consistently O(1), which can be important for performance-critical code.

## License

Distributed under the Apache Software License version 2.0

vector-backed-sorted-map

vector-backed-sorted-map Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

vector-backed-sorted-map

vector-backed-sorted-map Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README