Skip to content

Instantly share code, notes, and snippets.

Avatar
🎯
Focusing

Max Voitko mvoitko

🎯
Focusing
View GitHub Profile
@mvoitko
mvoitko / heap.py
Last active Sep 26, 2020
Min heap Python implementation
View heap.py
from typing import List, Optional, Set, Tuple
class Heap:
def __init__(self, arr: Optional[List[int]] = None):
self._to_delete: Set[int] = set()
if arr:
self.__heapify(arr)
else:
self.__arr: List[int] = []
@mvoitko
mvoitko / insertionSort.cpp
Created Oct 11, 2019
Fast version of insertion sort algorithm
View insertionSort.cpp
static void insertionSort(int[] a) {
for(int i = 1; i < a.length; ++i) {
// invariant x[0:i-1] sorted
// shift i_th element to its proper place
for(int j = i; j > 0 && a[j-1] > a[j]; --j) {
swap(a, j-1, j);
}
}
}
View bin_search_complex_function.py
# f(x) = x*x*x + a*x + b; a, b > 0, x - integer
# find x0, such that f(x0) = c, c > 0
# Для начала найдем левую границу, выберем произвольную отрицательную точку (например -1).
# Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.
#
# Для того, чтобы найти правую границу, выберем произвольную положительную точку (например 1).
# Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.
def findLeftBoard(C):
View Time complexity in s.java
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
int n = 100 * 1000;
long res = compute(n);
long endTime = System.currentTimeMillis();
System.out.println(res);
// 2.2 GHz ~ 2.2 * 10^9 op/sec
View Time complexity double loops
Find the number of times f() is called as a function of the input size n.
a. for (i = n; i > 1; i /= 2)
f()
a. O(log n)
b. for (i = 0; i * i < n; i++)
f()
b. O(sqrt n)
@mvoitko
mvoitko / Latencies.md
Last active Sep 15, 2020
Every Programmer Should Know These Latency Numbers
View Latencies.md

Latency numbers every programmer should know

L1 cache reference ......................... 0.5 ns
Branch mispredict ............................ 5 ns
L2 cache reference ........................... 7 ns
Mutex lock/unlock ........................... 25 ns
Main memory reference ...................... 100 ns
Compress 1K bytes with Zippy ............. 3,000 ns = 3 µs
Send 2K bytes over 1 Gbps network ....... 20,000 ns = 20 µs
SSD random read ........................ 150,000 ns = 150 µs
Read 1 MB sequentially from memory ..... 250,000 ns = 250 µs
@mvoitko
mvoitko / NestedDict.py
Created Jul 31, 2019
NestedDict class
View NestedDict.py
"""
Module for managing nested dictionary collections.
"""
# nestdict.py by Adam Szieberth (2013)
# Python 3.3+
class NestedDict(dict):
"""
Class for managing nested dictionary structures. Normally, it works
@mvoitko
mvoitko / Dockerfile
Created Jul 23, 2019
The elegant method of activating virtualenv in Python container
View Dockerfile
FROM ubuntu:18.04
RUN apt-get update && apt-get install \
-y --no-install-recommends python3 python3-virtualenv
ENV VIRTUAL_ENV=/opt/venv
RUN python3 -m virtualenv --python=/usr/bin/python3 $VIRTUAL_ENV
ENV PATH="$VIRTUAL_ENV/bin:$PATH"
# Install dependencies:
COPY requirements.txt .
@mvoitko
mvoitko / Dockerfile
Created Jul 20, 2019
Docker image based on Alpine with Tensorflow
View Dockerfile
FROM python:3.6-alpine
ARG ENV
WORKDIR /app
RUN pip install -U pip
RUN pip install awscli
RUN mkdir train && \
aws s3 cp s3://{bucket}/{model_file}.model train/{model_file}.model
@mvoitko
mvoitko / Dockerfile
Created Jul 20, 2019
Apex deploy image
View Dockerfile
ARG PYTHON_VERSION
FROM {registry_url}/lambda-base-image:$PYTHON_VERSION-0.5.0
RUN curl https://raw.githubusercontent.com/apex/apex/master/install.sh | sh
ADD bin/download_terraform.sh /bin
RUN /bin/download_terraform.sh