Madoka: Memory-efficient CountMin Sketch

0.7.2.1 · active · verified Thu Apr 16

Madoka is a Python library that provides a memory-efficient implementation of the CountMin Sketch probabilistic data structure, based on the Madoka C++ library. It's designed for estimating frequencies of items in a data stream with limited memory. The current version is 0.7.2.1, and releases occur infrequently, primarily for maintenance or updates to the underlying C++ library.

Common errors

```
TypeError: a bytes-like object is required, not 'str'
```
cause Attempted to add or query a key using a Python string instead of a byte string.

fix Convert the string key to bytes before passing it to Madoka methods. Example: `sketch.add(my_string.encode('utf-8'))` or `sketch.query(b'my_literal_key')`.
```
ModuleNotFoundError: No module named 'madoka'
```
cause The Madoka library is not installed in your current Python environment.

fix Install the library using pip: `pip install madoka`. If in a virtual environment, ensure it's activated.
```
error: command 'gcc' failed with exit status 1 (or similar compilation error with MSVC/Clang)
```
cause During installation, pip attempted to compile Madoka from source, but a C++ compiler was not found or configured correctly on your system.

fix Install the necessary C++ build tools for your operating system. For Linux (Debian/Ubuntu), run `sudo apt-get install build-essential`. For macOS, install Xcode Command Line Tools (`xcode-select --install`). For Windows, install Microsoft Visual C++ Build Tools.

Warnings

gotcha Madoka requires keys to be `bytes` objects, not strings. Passing a string will result in a `TypeError`.
Fix: Ensure all keys passed to `add()` or `query()` are byte strings. For example, use `b'your_key'` or `key.encode('utf-8')`.
gotcha Installation may fail if a C++ compiler is not available on your system, especially if pre-built wheels are not provided for your specific OS and Python version.
Fix: Install build tools (e.g., `build-essential` on Debian/Ubuntu, Xcode Command Line Tools on macOS, Visual C++ Build Tools on Windows) before running `pip install madoka`.
gotcha The `width` parameter (or implied by `epsilon`) directly impacts memory usage. A very large `width` can lead to significant memory consumption, potentially exceeding available RAM.
Fix: Carefully choose `width` (or `epsilon`) based on your memory constraints and desired accuracy. Monitor memory usage in production environments.

Install

pip install madoka Install latest version

Imports

CountMinSketch
wrong:
```
import madoka.CountMinSketch
```
correct:
```
from madoka import CountMinSketch
```
While 'import madoka' and then 'madoka.CountMinSketch' also works, direct import is often preferred.

Quickstart

Initializes a CountMin Sketch, adds byte-encoded items, queries their approximate frequencies, and demonstrates resetting the sketch.

import madoka

# Create a CountMin Sketch with desired depth and width (or epsilon/delta)
sketch = madoka.CountMinSketch(depth=4, width=2**20)

# Add items (must be bytes)
sketch.add(b"user_id_1")
sketch.add(b"product_page_A")
sketch.add(b"user_id_1")

# Query approximate counts
count_user1 = sketch.query(b"user_id_1")
count_pageA = sketch.query(b"product_page_A")
count_unknown = sketch.query(b"non_existent_item")

print(f"Approximate count for 'user_id_1': {count_user1}")
print(f"Approximate count for 'product_page_A': {count_pageA}")
print(f"Approximate count for 'non_existent_item': {count_unknown}")

# Reset the sketch
sketch.reset()

view raw JSON →