Skip to content

Instantly share code, notes, and snippets.

View senderista's full-sized avatar

Tobin Baker senderista

27 followers · 12 following
View GitHub Profile
@senderista
senderista / plot_bintree_level_count.py
Created August 22, 2023 23:00
#!/usr/local/bin/python3
import sys
import numpy as np
import pandas as pd
import matplotlib as mpl
import matplotlib.pyplot as plt
import seaborn as sns
import warnings; warnings.filterwarnings(action='once')
@senderista
senderista / rand_bintree.py
Created August 22, 2023 22:59
#!/usr/bin/env python3
import sys
import numpy
import math
class ImplicitBinarySearchTree:
def __init__(self, size) -> None:
@senderista
senderista / inverse64.py
Created September 6, 2018 18:38
calculate multiplicative inverse of odd number mod 2^64 (in hex format)
import sys
# calculate multiplicative inverse of odd number mod 2^64
# from https://groups.google.com/forum/m/#!msg/sci.crypt/UI-UMbUnYGk/hX2-wQVyE3oJ
def inverse(a):
x = a
assert (x * a & 0x7) == 1
x += x - a * x * x
assert (x * a & 0x3F) == 1
x += x - a * x * x
@senderista
senderista / inverse32.py
Created September 6, 2018 18:37
calculate multiplicative inverse of odd number mod 2^32 (in hex format)
import sys
# calculate multiplicative inverse of odd number mod 2^32
# from https://groups.google.com/forum/m/#!msg/sci.crypt/UI-UMbUnYGk/hX2-wQVyE3oJ
def inverse(a):
x = a
assert (x * a & 0x7) == 1
x += x - a * x * x
assert (x * a & 0x3F) == 1
x += x - a * x * x
@senderista
senderista / BLPIntHashSet.java
Last active August 24, 2018 23:41
Bidirectional linear probing implementation (first draft)
import java.util.Arrays;
public class BLPIntHashSet {
private int[] arr;
private int size = 0;
public BLPIntHashSet(int maxEntries, double loadFactor) {
assert maxEntries > 0;
@senderista
senderista / linear_probing.py
Last active August 17, 2018 18:55
#!/usr/bin/env python
import sys
import logging
from speck import SpeckCipher
from runstats import Statistics
import numpy
from collections import Counter
@senderista
senderista / bidirectional_linear_probing.py
Last active August 17, 2018 18:55
implementation of Knuth's bidirectional linear probing algorithm (https://academic.oup.com/comjnl/article/17/2/135/525363)
#!/usr/bin/env python
import sys
import logging
from speck import SpeckCipher
import numpy
from runstats import Statistics
from collections import Counter
@senderista
senderista / best_spot_price.py
Created June 26, 2018 22:20
import boto3
def get_best_spot_price(instance_type, ec2_client=None):
client = ec2_client or boto3.client('ec2')
zones = [az['ZoneName'] for az in client.describe_availability_zones()['AvailabilityZones']]
best_price = None
best_zone = None
last_price = float('inf')
for zone in zones:
price = float(client.describe_spot_price_history(
@senderista
senderista / quasirandom_consistent_hashing.py
Created March 22, 2018 22:16
An experimental algorithm to use quasirandomness to assign nodes to positions on the consistent hashing ring (deterministically bounding skew to at most a factor of 2)
#!/usr/bin/env python
import sys
import math
from bisect import *
from collections import defaultdict
from collections import Counter
"""Find rightmost value less than or equal to x"""
@senderista
senderista / jump_consistent_hashing.py
Created March 22, 2018 22:11
A simple python impl of "jump consistent hashing" (https://arxiv.org/abs/1406.2294)
#!/usr/bin/env python
import sys
import math
import random
from collections import defaultdict
from collections import Counter
def consistent_hash(key, num_buckets):