{"id":7389,"library":"madoka","title":"Madoka: Memory-efficient CountMin Sketch","description":"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.","status":"active","version":"0.7.2.1","language":"en","source_language":"en","source_url":"https://github.com/ikegami-yukino/madoka-python","tags":["data-structures","countmin-sketch","probabilistic-data-structures","memory-efficient","streaming"],"install":[{"cmd":"pip install madoka","lang":"bash","label":"Install latest version"}],"dependencies":[],"imports":[{"note":"While 'import madoka' and then 'madoka.CountMinSketch' also works, direct import is often preferred.","wrong":"import madoka.CountMinSketch","symbol":"CountMinSketch","correct":"from madoka import CountMinSketch"}],"quickstart":{"code":"import madoka\n\n# Create a CountMin Sketch with desired depth and width (or epsilon/delta)\nsketch = madoka.CountMinSketch(depth=4, width=2**20)\n\n# Add items (must be bytes)\nsketch.add(b\"user_id_1\")\nsketch.add(b\"product_page_A\")\nsketch.add(b\"user_id_1\")\n\n# Query approximate counts\ncount_user1 = sketch.query(b\"user_id_1\")\ncount_pageA = sketch.query(b\"product_page_A\")\ncount_unknown = sketch.query(b\"non_existent_item\")\n\nprint(f\"Approximate count for 'user_id_1': {count_user1}\")\nprint(f\"Approximate count for 'product_page_A': {count_pageA}\")\nprint(f\"Approximate count for 'non_existent_item': {count_unknown}\")\n\n# Reset the sketch\nsketch.reset()","lang":"python","description":"Initializes a CountMin Sketch, adds byte-encoded items, queries their approximate frequencies, and demonstrates resetting the sketch."},"warnings":[{"fix":"Ensure all keys passed to `add()` or `query()` are byte strings. For example, use `b'your_key'` or `key.encode('utf-8')`.","message":"Madoka requires keys to be `bytes` objects, not strings. Passing a string will result in a `TypeError`.","severity":"gotcha","affected_versions":"All versions"},{"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`.","message":"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.","severity":"gotcha","affected_versions":"All versions"},{"fix":"Carefully choose `width` (or `epsilon`) based on your memory constraints and desired accuracy. Monitor memory usage in production environments.","message":"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.","severity":"gotcha","affected_versions":"All versions"}],"env_vars":null,"last_verified":"2026-04-16T00:00:00.000Z","next_check":"2026-07-15T00:00:00.000Z","problems":[{"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')`.","cause":"Attempted to add or query a key using a Python string instead of a byte string.","error":"TypeError: a bytes-like object is required, not 'str'"},{"fix":"Install the library using pip: `pip install madoka`. If in a virtual environment, ensure it's activated.","cause":"The Madoka library is not installed in your current Python environment.","error":"ModuleNotFoundError: No module named 'madoka'"},{"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.","cause":"During installation, pip attempted to compile Madoka from source, but a C++ compiler was not found or configured correctly on your system.","error":"error: command 'gcc' failed with exit status 1 (or similar compilation error with MSVC/Clang)"}]}