How r-niemans/cds_ternarysearchtree works
Project type and purpose
• This is a library and benchmarking framework for various Ternary Search Tree (TST) implementations in Python.
• It explores multiple TST variants (object-oriented, iterative, sparse, recursive), compares them to a binary tree, and measures performance on small datasets locally and large datasets on HPC infrastructure.
File structure
• Top-level
• trees/ – all tree implementations: btree.py, ternary_tree.py, ternary_tree_B.py, ternary_tree_minimalistic.py, ternary_tree_recursive.py
• data/ – raw datasets (small and sample words files)
• test_tst.py – unit tests for correctness
• tst_implementations.ipynb – Jupyter notebook for local benchmarking
• HPC/ – scripts, job definitions, and outputs for large-scale tests
• HPC/ substructure
• jobscript.slurm, jobscript2.slurm – SLURM batch definitions
• *.py scripts – wrappers to load data, perform insert/search tests on HPC
• Outputs/slurm-out.zip – collected logs and metrics
• README files describe high-level flow and how to run tests.
Extract insights from the README
• Four distinct TST variants plus a modified binary tree
• Workflow: implement → unit test → local performance tests → large-scale HPC performance tests → documentation
• Data flow: ingest dataset → build tree → run searches → collect metrics
Main components
a. Code modules
• Tree library layer (trees/)
• Unit test harness (test_tst.py)
• Local performance bench (tst_implementations.ipynb)
• HPC performance bench scripts (HPC/*.py)
b. Data stores
• Local datasets (data/*.txt)
• External datasets (wikipedia, frequency words)
• HPC output storage (HPC/Outputs)
c. Execution environments
• Local workstation (running Python + Jupyter)
• HPC cluster (SLURM scheduler)
d. External services
• HPC scheduler (SLURM)
• Storage for big datasets (Hugging Face URLs)
Relationships and data flows
• Local workflow:
data/ → Python TST modules → unit tests → Jupyter notebook → metrics
• HPC workflow:
data/ (transferred) → HPC/*.py → SLURM jobscript → HPC compute nodes → Outputs
• The tree library is the core component invoked by both local bench and HPC scripts.
Architectural patterns and design principles
• Modular codebase: separate modules for each TST variant, clear API for insert/search.
• Test-driven approach: unit tests enforce correctness before performance tests.
• Benchmark layering: local quick tests vs. large-scale HPC runs share the same core library.
• Separation of concerns: data ingestion, algorithm implementation, test harness, result collection.
Technologies and frameworks
• Python 3.x
• Jupyter Notebook for local benchmarking
• SLURM for HPC batch scheduling
• Standard text files for datasets