Tuple-sum-filter - Library to play with filtering numeric sequences by sums of their pairs, triplets, etc. With a bonus CLI demo

Overview

Tuple Sum Filter

A library to play with filtering numeric sequences by sums of their pairs, triplets, etc.

Comes with a bonus CLI to demo the functionality.

Requires (and CI tests on) python 3.8 to 3.10. If you need to use python 3.7 then try replacing math.prod(some_iterable) with functools.reduce(lambda x, y: x * y, some_iterable)

Approach

We're thinking of this mostly as a library with the CLI as only for demo purposes. Ways you can see this in the code:

  • logging should really handled by the consumer,
    • our get_logger should be something that is passed into the lib
  • the CLI is pretty light on automated tests
  • we use pretty loose production dependency pinning
    • rather than pip freeze > requirements.txt of a deployed app
    • we want to keep things loose so that consumers can keep installing us alongside other things
    • we should probably set up tox/nox test runs against v.latest of our dependencies

Running the demo

in a fresh virtualenv (python>=3.8)

# install project and deps
pip install git+https://github.com/lbillingham/tuple-sum-filter.git

# create a suitable input file
echo "1721\n979\n366\n299\n675\n1456\n" > example.txt

# run the demo
filter_demo --input_file=example.txt --sum_target=2020 --dimension=2

you should see output like

checking for pairs of numbers that sum to 2020 in example.txt
Results pair (1721, 299) match: sum to 2020 and multiply to 514579

Consuming the library

The main filtering functions are pairs_that_sum_to and triplets_that_sum_to. They both have signatures (numbers: Sequence[int|float], sum_target: int|float) -> things_that_passed_the_filter list[tuple].

There is also a file-reading helper numbers_in_file exported at the top level.

Developing

Run the following to install the project (and dev dependencies) into your active virtualenv:

make dev_install

day-to-day development tasks can be orchestrated via make

  • dependency management
  • test/lint/typecheck running
  • coverage reporting
  • run make without any arguments to see a list

There is a CI suite which runs lint and test on several python versions. We don't run typechecking as a gate in CI because we think that turns a sometimes-useful tool into a Goodhart target.

Performance

We have not been optimizing for performance and it kind of shows.

When we run the benchmarking suite we see ~0.4 seconds fairly consistently for the triplet/3D problem.

We have at least 3 ideas of how to speed things up: several of them include dropping floating-point support.

$ make benchmark

tests/performance_check.py ..                                                                                                                                [100%]


------------------------------------------------------------------------------------- benchmark: 2 tests ------------------------------------------------------------------------------------
Name (time in ms)             Min                 Max                Mean            StdDev              Median               IQR            Outliers       OPS            Rounds  Iterations
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_input1_pairs          5.4665 (1.0)        6.2297 (1.0)        5.6687 (1.0)      0.1018 (1.0)        5.6575 (1.0)      0.1289 (1.0)          47;3  176.4077 (1.0)         172           1
test_input1_triplets     384.6154 (70.36)    386.5000 (62.04)    385.4776 (68.00)    0.8287 (8.14)     385.4333 (68.13)    1.5047 (11.67)         2;0    2.5942 (0.01)          5           1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

--

🍪 ✂️ cookiecut from lbillingham's python-cli-template

You might also like...
Linux GUI app to codon optimize many single-fasta files with coding sequences , using many taxonomy ids
Linux GUI app to codon optimize many single-fasta files with coding sequences , using many taxonomy ids

codon_optimize_cds_with_many_taxids_singlefasta Linux GUI app to codon optimize many single-fasta files with coding sequences, using many taxonomy ids

Ingestinator is my personal VFX pipeline tool for ingesting folders containing frame sequences that have been pulled and downloaded to a local folder

Ingestinator Ingestinator is my personal VFX pipeline tool for ingesting folders containing frame sequences that have been pulled and downloaded to a

Python Common things by Problem Fighter Library, (Exception, Debug Log, etc.)

In the name of God, the Most Gracious, the Most Merciful. PF-PY-Common Documentation Install and update using pip: pip install -U xxxx Please find the

Devil - Very Semple Auto Filter V1 Bot
Devil - Very Semple Auto Filter V1 Bot

Devil Very Semple Auto Filter V1 Bot

Cairo-bloom - A naive bloom filter implementation in Cairo

🥀 cairo-bloom A naive bloom filter implementation in Cairo. A Bloom filter is a

Snakemake worflow to process and filter long read data from Oxford Nanopore Technologies.
Snakemake worflow to process and filter long read data from Oxford Nanopore Technologies.

Nanopore-Workflow Snakemake workflow to process and filter long read data from Oxford Nanopore Technologies. It is designed to compare whole human gen

Runnable Python demo of ArtLine

artline-demo How to run? pip3 install -r requirements.txt python3 app.py How to use? Run the Flask app Open localhost:5000 in browser Select an image(

Tiny demo site for exploring SameSite=Lax

samesite-lax-demo Background on my blog: Exploring the SameSite cookie attribute for preventing CSRF This repo holds some tools for exploring the impl

An extended version of the hotkeys demo code using action classes

An extended version of the hotkeys application using action classes. In adafruit's Hotkeys code, a macro is using a series of integers, assumed to be

Comments
  • Perf: :zap:  merge if you want to go faster but don't need float support

    Perf: :zap: merge if you want to go faster but don't need float support

    This moves away from the shared itertools implimentations for finding pairs, triplets of the input numbers that sum to a given target.

    Instead, we

    • 1st expose the underlying $~O^{dimensions}$ nested loops
    • trade some extra memory and some $O^{1}$ lookups to give us $~O^{dimensions-1}$
    • get a >= 170x speedup in our benchmarks

    However, we:

    • loose the ability to properly work with floating point input
      • the fast lookup uses hasing and hashing floats gets weird due to floating point equality
    • can't trivially extend to higher-dimension problems: 4-element-tuples etc.

    I've moved the float input tests out the their own file and away from the CI test path

    Performance benchmarks

    with these changes:

    $ make benchmark
    tests/performance_check.py ..                                                                                                                             [100%]
    
    -------------------------------------------------------------------------------------------- benchmark: 2 tests --------------------------------------------------------------------------------------------
    Name (time in us)               Min                   Max                  Mean              StdDev                Median                 IQR            Outliers          OPS            Rounds  Iterations
    ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    test_input1_pairs           22.1660 (1.0)        166.3790 (1.0)         23.6089 (1.0)        5.0170 (1.0)         23.0000 (1.0)        0.5123 (1.0)        87;521  42,356.8183 (1.0)        7677           1
    test_input1_triplets     1,994.8000 (89.99)    3,561.1120 (21.40)    2,152.1272 (91.16)    204.1428 (40.69)    2,033.1040 (88.40)    299.1878 (584.07)       41;4     464.6565 (0.01)        341           1
    ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    

    itertools, but non-float supporting version

    $ make benchmark
    tests/performance_check.py ..                                                                                                      [100%]
    
    ------------------------------------------------------------------------------------- benchmark: 2 tests ------------------------------------------------------------------------------------
    Name (time in ms)             Min                 Max                Mean            StdDev              Median               IQR            Outliers       OPS            Rounds  Iterations
    ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    test_input1_pairs          2.8727 (1.0)        4.2386 (1.0)        3.1265 (1.0)      0.1638 (1.0)        3.1067 (1.0)      0.1888 (1.0)          78;9  319.8414 (1.0)         326           1
    test_input1_triplets     211.6325 (73.67)    213.3950 (50.35)    212.4042 (67.94)    0.6555 (4.00)     212.2717 (68.33)    0.8081 (4.28)          2;0    4.7080 (0.01)          5           1
    ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    =========================================================== 2 passed in 3.59s ============================================================
    

    Note the change in units this branch is in microseconds, the itertools version is in milliseconds

    opened by lbillingham 0
Releases(v0.0.1)
  • v0.0.1(Feb 17, 2022)

    Initial release. Lib allows filtering by sum over pairs and triplets of numbers loaded from a local file. Plus a bonus CLI app that can be used for demoing the lib.

    Solution is itertools-y and rather slow (probably $O^{n}$ where pairs->n=2 and triplets->n=3).

    This is the version shown to MM

    Source code(tar.gz)
    Source code(zip)
Owner
Laurence Billingham
+ sustainable software + data science
Laurence Billingham
BinCat is an innovative login system, with which the account you register will be more secure.

BinCat is an innovative login system, with which the account you register will be more secure. This project is inspired by a conventional token system.

Hipotesi 2 May 22, 2022
A companion web application to connect stash to deovr

stash-vr-companion This is a companion web application to connect stash to deovr. Stash is a self hosted web application to manage your porn collectio

19 Sep 29, 2022
This is a Python program I wrote to simulate the solar system with 79 lines of code.

Solar System With Python This is a Python program I wrote to simulate the solar system with 79 lines of code. Required modules tkinter, math, time Why

Mehmet Aydoğmuş 1 Oct 26, 2021
A silly RPG(Not MMO) made in python

Project_PyMMo A silly RPG(Not MMO) made in python, FOR WINDOWS 10 ONLY! Hello tester, to install pymmo follow the steps bellow: 1.First install python

0 Feb 08, 2022
JupyterLite as a Datasette plugin

datasette-jupyterlite JupyterLite as a Datasette plugin Installation Install this plugin in the same environment as Datasette. $ datasette install dat

Simon Willison 11 Sep 19, 2022
In this project, we are going to display the battery notification and the time left for the battery to drain out using the battery capacity value.

In this project, we are going to display the battery notification and the time left for the battery to drain out using the battery capacity value.

Ritoban Biswas 1 Dec 20, 2021
Store Simulation

Almacenes Para clonar el Repositorio: Vaya a la terminal de Linux o Mac, o a la cmd en Windows y ejecute:

Johan Posada 1 Nov 12, 2021
Collection of functions for working with interlaced content in VapourSynth.

vsfieldkit Collection of functions for working with interlaced content in VapourSynth. It does not have any hard dependencies outside of VapourSynth.

Justin Turner Arthur 11 May 27, 2022
🛠️ Plugin to integrate Chuy with Poetry

Archived This is bundled with Chuy since v1.3.0. Poetry Chuy Plugin This plugin integrates Chuy with Poetry. Note: This only works in Poetry 1.2.0 or

Eliaz Bobadilla 4 Sep 24, 2021
Add any Program in any language you like or add a hello world Program ❣️ if you like give us :star:

Welcome to the Hacktoberfest 2018 Hello-world 📋 This Project aims to help you to get started with using Github. You can find a tutorial here What is

Aniket Sharma 1.5k Nov 16, 2022
It is convenient to quickly import Python packages from the network.

It is convenient to quickly import Python packages from the network.

zmaplex 1 Jan 18, 2022
DC619/DC858 Mainframe Environment/Lab

DC619 Training LPAR The file DC619 - Mainframe Overflows Hands On.pdf contains the labs and walks through how to perform them. Use docker You can use

Soldier of FORTRAN 9 Jun 27, 2022
A python script for osu!lazer rulesets auto update.

osu-lazer-rulesets-autoupdater A python script for osu!lazer rulesets auto update. How to use: 如何使用: You can refer to the python script. The begining

3 Jul 26, 2022
Waydroid is a container-based approach to boot a full Android system on a regular GNU/Linux system like Ubuntu.

Waydroid is a container-based approach to boot a full Android system on a regular GNU/Linux system like Ubuntu.

WayDroid 4.7k Jan 08, 2023
Create a program for generator Truth Table

Python-Truth-Table-Ver-1.0 Create a program for generator Truth Table in here you have to install truth-table-generator module for python modules inst

JehanKandy 10 Jul 13, 2022
The Google Assistant on a rotary phone

Google Assistant Rotary Phone Shoutout to my dad who had this idea a year ago and I'm only now getting around to doing it. Notes This is the code used

rydercalmdown 10 Nov 04, 2022
Introduction to Databases Coursework 2 (SQL) - dataset generator

Introduction to Databases Coursework 2 (SQL) - dataset generator This is python script generates a text file with insert queries for the schema.sql fi

Javier Bosch 1 Nov 08, 2021
A(Sync) Interface for internal Audible API written in pure Python.

Audible Audible is a Python low-level interface to communicate with the non-publicly Audible API. It enables Python developers to create there own Aud

mkb79 192 Jan 03, 2023
This library attempts to abstract the handling of Sigma rules in Python

This library attempts to abstract the handling of Sigma rules in Python. The rules are parsed using a schema defined with pydantic, and can be easily loaded from YAML files into a structured Python o

Caleb Stewart 44 Oct 29, 2022
Tindicators is a Python library to calculate the values of various technical indicators

Tindicators is a Python library to calculate the values of various technical indicators

omar 3 Mar 03, 2022