Skip to content

Instantly share code, notes, and snippets.

@airekans
airekans / reduce.py
Created October 16, 2020 07:14
A recursion version of parallel reduce similar to the iterative version
def reduce(arr):
def impl(i, s):
if i >= len(arr):
return 0
elif i + s >= len(arr):
return arr[i]
a = impl(i, s * 2) # spawn
b = impl(i + s, s * 2)
return a + b
@airekans
airekans / gist:4bda05ad46a0a2733c5c0c4278431500
Created June 27, 2019 18:58 — forked from trongthanh/gist:2779392
How to move a folder from one repo to another and keep its commit history
# source: http://st-on-it.blogspot.com/2010/01/how-to-move-folders-between-git.html
# First of all you need to have a clean clone of the source repository so we didn't screw the things up.
git clone git://server.com/my-repo1.git
# After that you need to do some preparations on the source repository, nuking all the entries except the folder you need to move. Use the following command
git filter-branch --subdirectory-filter your_dir -- -- all
# This will nuke all the other entries and their history, creating a clean git repository that contains only data and history from the directory you need. If you need to move several folders, you have to collect them in a single directory using the git mv command.
@airekans
airekans / transform.py
Created January 31, 2018 22:48
A = [1, [2, 3], [4, 5, 6], 7] B = [2, 3, 4, 5, 6, 7, 8] How to transform B into the same structure as A? E.g. B' = [2, [3, 4], [5, 6, 7], 8]
def func(l1, l2):
def traverse(l1, l2, i):
res = []
for e in l1:
if isinstance(e, list):
res.append(traverse(e, l2, i))
else:
res.append(l2[i[0]])
i[0] += 1
return res
// O(n^3)
double brute_force_max_subarray(const double* array, unsigned int size)
{
double max_sum = 0.0;
for (unsigned int i = 0; i < size; ++i) {
for (unsigned int j = i; j < size; ++j) {
double tmp_sum = 0.0;
for (unsigned int k = i; k <= j; ++k) {
tmp_sum += array[k];
if (tmp_sum > max_sum) {
@airekans
airekans / initialize_array.cpp
Last active September 19, 2017 00:17
A technique to initialize array data when accessing it at the first time. This is presented in Programming Pearls' exercises. Here's a very nice explanation of what the following code does: https://research.swtch.com/sparse
template<unsigned int N>
struct Array
{
Array() : top(0) {}
// Invariant: if a data has been initialized, it will have the following properties:
// 1. index_key[i] < top
// 2. indexes[index_key[i]] == i
int Get(unsigned int i) {
if (index_key[i] < top && indexes[index_key[i]] == i) {
@airekans
airekans / test_half_close.py
Created October 21, 2015 04:52
Half close connection handling in TCP
# several behavior in TCP when handling half close connection:
# 1. if one end "close()" socket, while the other does not read from the socket,
# the other end will not be able to detect connection close.
# If at this moment, this end send some data to the close end, close end has been closed write and read,
# so it will not be able to recv data from this connection, and it will send an "RST" in this case
# to tell its peer about this.
# When the peer recv "RST", it will just set this connection as close, so next time when it tries to write
# data on this socket, it will have the broken pipe error.
# But it can still recv data on this socket. After all data in the TCP recv buffer has been read, it will return EOF.
# 2. If one end "shutdown(W)" the socket, this will be the read half close case. So the peer can send data if he wants.
@airekans
airekans / variadic_template.cpp
Created October 10, 2015 08:13
Closure implementation with c++11 variadic template.
// Test in gcc 4.8.1.
#include <tuple>
#include <iostream>
template<typename T> struct ParamTrait { typedef T& ForwardType; typedef T StoreType; };
template<> struct ParamTrait<int> { typedef int ForwardType; typedef int StoreType; };
class Closure
{
@airekans
airekans / binary_tree_serialization.cpp
Created July 15, 2015 05:00
binary tree serialization, check here for the format explanation: https://leetcode.com/problems/binary-tree-inorder-traversal/
#include <queue>
#include <string>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
struct Node
{
int data;
Node* left;
NOde* right;
};
void invert_binary_tree(Node* root)
{
if (root == NULL)
@airekans
airekans / string_rotate_left.cpp
Created May 15, 2015 02:56
Code snippet that help me understand std::rotate
// A reference to the idea is here: http://en.cppreference.com/w/cpp/algorithm/rotate
// Actually its idea is recursion, as shown as follow:
void str_rotate(char* first, char* middle, char* last)
{
char* next = middle;
while (first != middle && next != last)
{
std::iter_swap(first++, next++);
}
if (first == middle && next == last)