Skip to main content

TsingPig_Lab is a package for algorithm.

Project description

TsingPig - Lab

image.png

[TOC]

1. Introduction

This is a python package for simple algorithms and data structures which is developed by tsingpig.

Author: TsingPig

Repo: https://gitlab.com/tsingpig-code/tsingpig_lab

You can connect me by email: 1114196607@qq.com

Thanks for your support!

2. Features

2.1. DataStructures

2.1.1 Sparse Table (ST)

A data structure ST table (Sparse Table) that supports interval contribution problem queries.

Usage

Method Time Complexity Description
__init__(nums: List, opt = lambda a, b: max(a, b)) $O(n \log n)$ Initialize the Sparse Table (ST) data structure with the given list of numbers and an optional comparison function.
qry(L: int, R: int) $O(1)$ Query the opt value within the range [L, R].

**Example **

from tsingpig_lab.DataStructures import ST as ST
st = ST([1, 9, 0, 2, 4, 5])
print(st.qry(1, 3))	# 9

You can also customize comparison methods by passing function parameters. In default condition, the maximum value will be returned.

from tsingpig_lab.DataStructures import ST as ST
st = ST([1, 9, -99, 2, 4, 5], lambda a, b: min(a, b))
print(st.qry(1, 4)) # -99

Please note that the issue of contribution needs to be met. It means $Opt (x, x)=x$

2.1.2 Fenwick Tree

A data structure Fenwick Tree that supports range queries efficiently.

Usage

Method Time Complexity Description
__init__(n: int, discretize: bool = False, nums: List[int] = None) $O(n \log n)$ Initialize the Fenwick Tree data structure with the given array length n and optionally with discretized values.
update(x: int, val: int = 1) $O(\log n)$ Update the value at index x by adding val.
query(lx: int, rx: int = None) $O(\log n)$ If only lx is provided, query the number of elements less than or equal to lx. If both lx and rx are provided, query the number of elements between lx and rx inclusive.

**Example **

Example without discretization

from tsingpig_lab.DataStructures import FenwickTree as FenwickTree
tr = FenwickTree(10)
tr.update(1, 1)
tr.update(2, 2)
tr.update(3, 5)
tr.update(1, 3)
# [0, 4, 2, 5, 0, 0, 0, 0, 0, 0]
print(tr.query(1, 10))	# 11

Example with discretization锛宨t allows the input array nums has repeated elements.

from tsingpig_lab.DataStructures import FenwickTree as FenwickTree
nums = [1, 9, -99, 2, 4, 5, -99]
ft = FenwickTree(len(nums), discretize=True, nums=nums)
ft.update(2, 4)
ft.update(-99, 3)
# [0, 0, 3, 4, 0, 0]
print(ft.query(-99, 9)) # 7

2.1.3 SegmentTree

This type of segment tree is static, which means you need to predetermine the size of the input arrays. And during the whole usage of this tree, the size is fixed and can not be change.

This static nature can offer performance benefits in scenarios where the size of the dataset is known and fixed, avoiding the overhead associated with dynamic resizing.

Usage

Method Time Complexity Description
__init__(nums, ops='sum') $O(n)$ Initialize the Segment Tree data structure with the given array nums and operation type ops, defaulting to sum operation.
build(idx=1, l=1, r=None) $O(n)$ Build the Segment Tree.
update(ul, ur, val, idx=1, l=1, r=None) $O(\log n)$ Update the range [ul, ur] with the given value val.
query(ql, qr, idx=1, l=1, r=None) $O(\log n)$ Query the result value within the range [ql, qr].

Sample

from tsingpig_lab.DataStructures import SegmentTree as SegmentTree

tr = SegmentTree([1, 2, 3, 4, 5], 'sum')
tr.build()
print(tr.query(1, 5))  # 15
print(tr.query(2, 5))  # 14
tr.update(2, 4, 2)  # 1 4 5 6 5
print(tr.query(2, 5))  # 20

tr = SegmentTree([8, 4, 5, 7, 9], 'min')
tr.build()
print(tr.query(1, 4)) # 4
tr.update(1, 4, 5) # [5, 4, 5, 5, 9]
print(tr.query(4, 5)) # 5
tr.update(3, 5, -10) # [5, 4, -10, -10, -10]
print(tr.query(1, 3)) # -10

Note: The index is start with 1.

2.1.4 SegmentTreeDynamic

This type of segment tree is dynamic, which means it supports dynamic allocation of nodes and efficient updates and queries on potentially very large ranges. This is beneficial when the range of possible indices is large, but the number of actual updates or queries is sparse.

The dynamic nature of this segment tree allows it to handle large datasets efficiently without requiring a fixed size at initialization, making it suitable for scenarios with unknown or very large ranges.

Usage

Method Time Complexity Description
__init__(ops='sum', max_val=1e9) $O(1)$ Initialize the Segment Tree data structure with the operation type ops, defaulting to sum operation, and a maximum value for the range.
update(ul, ur, val, node=None, l=1, r=None) $O(\log n)$ Update the range [ul, ur] with the given value val.
query(ql, qr, node=None, l=1, r=None) $O(\log n)$ Query the result value within the range [ql, qr].

Sample

Import the SegmentTreeDynamic class
from your_module import SegmentTreeDynamic

# Initialize the segment tree for sum operation with a maximum value of 1e15
tr = SegmentTreeDynamic('sum', int(1e15))
tr.update(1, 5, 99)
tr.update(1, 5, 1)
print(tr.query(1, 1))  # 100
print(tr.query(1, 5))  # 500

# Initialize the segment tree for min operation
tr = SegmentTreeDynamic(ops='min')
tr.update(1, 5, 10)
print(tr.query(1, 4)) # 10
tr.update(2, 4, 5) # [10, 5, 5, 5, 10]
print(tr.query(4, 5)) # 5
tr.update(3, 5, -10) # [10, 5, -10, -10, -10]
print(tr.query(1, 3)) # -10

Note: The index starts at 1.

2.2. Algorithms

2.2.1 BaseConverter

Using for convert input number with base-a to result number with base-b.

Usage

Method Time Complexity Description
__init__(a: int, b: int) N/A Initialize the BaseConverter with base a to convert numbers to base b. The bases must be within the range [2, 16].
convert(num: str) -> str $O(\log n)$ Convert a number in base a (given as a string) to its representation in base b.

**Example **

As shown below, you create a base converter from base-10 to base-2.

from tsingpig_lab.Algorithms import BaseConverter
baseCon = BaseConverter(10, 2)
print(baseCon.convert("123"))  # 1111011

As shown below, you create a base converter from base-16 to base-10.

All of the input and output string should not contain any prefix string or suffix string, for example you should not input like '1BF52H' or '0x1BF52', which may bring wrong results or errors.

from tsingpig_lab.Algorithms import BaseConverter
baseCon = BaseConverter(16, 10)
print(baseCon.convert("1BF52"))  # 114514

2.2.2 Bin

Usage

Method Time Complexity Description
__init__(num: str, b: int = 2) N/A Initialize the Bin object with a number string num in base b (default is binary). If b is not 2, it converts the number from base b to base 2.
grey_to_bin() -> str $O(n)$ Converts the stored binary string, treated as a Gray code, to its corresponding binary code. $n$ is the length of the binary representation of $num$ .
bin_to_grey() -> str $O(n)$ Converts the stored binary string, treated as a binary code, to its corresponding Gray code.

**Example **

As shown below, you initialize a binary object base on 2.

from tsingpig_lab.Algorithms import Bin
b = Bin('1111')

You can also initialize a binary object base on any number.

from tsingpig_lab.Algorithms import Bin
b = Bin("11", 10) # 1011

Calculate the binary num string which is treated as a normal binary code to Gray Code as below.

from tsingpig_lab.Algorithms import Bin

b = Bin("11", 10) # 1011
print(b.grey_to_bin())  # 1101

Calculate the binary num string which is treated as Gray Code code to normal binary code as below.

from tsingpig_lab.Algorithms import Bin

b = Bin("1100")
print(b.bin_to_grey())  # 1010

3. Note for Pypi

How to upload your own package

Firstly, open your package folder and type this command in its' corresponding cmd:

python setup.py sdist

Then:

twine upload dist/*

And then it works, users can download your package by this line in conda:

pip install TsingPig-Lab==0.1.7 -i https://www.pypi.org/simple/

API

pypi-AgEIcHlwaS5vcmcCJGYxZWEwMjY0LWJmMGUtNGMwMS1hMjM4LTVhZTA2N2EwMDA3MAACKlszLCI3NDRkODY1Ni02ODE3LTRiNjEtYTliMi1kZThmOTI0YjQ5ZWEiXQAABiC-6w2Qs90CFAe8UE5e9oYxb5RbBaRY0KXngikzxWfPcQ

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

TsingPig_Lab-0.2.1.tar.gz (9.0 kB view details)

Uploaded Source

File details

Details for the file TsingPig_Lab-0.2.1.tar.gz.

File metadata

  • Download URL: TsingPig_Lab-0.2.1.tar.gz
  • Upload date:
  • Size: 9.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.0.0 CPython/3.8.6

File hashes

Hashes for TsingPig_Lab-0.2.1.tar.gz
Algorithm Hash digest
SHA256 0fbda8337629ce42735b671f5532e98f7d7598d1a7de90c92b15b83c38dac9ca
MD5 69aa7e3c16dbc2aa38ba0c349389fc01
BLAKE2b-256 3346e1187eb28f223bd696a312d0f1cf16c8e806495b2897c08b19e770e10500

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page