Skip to content

Instantly share code, notes, and snippets.

K. kaja47

Block or report user

Report or block kaja47

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
@kaja47
kaja47 / RadixQuicksort.scala
Created Apr 4, 2016
Three-way radix quicksort
View RadixQuicksort.scala
import java.util.Arrays
// Three-way radix quicksort aka Multi-key quicksort
//
// Fast Algorithms for Sorting and Searching Strings
// http://www.cs.princeton.edu/~rs/strings/paper.pdf
object RadixQuicksort {
def sort(arr: Array[String]) =
@kaja47
kaja47 / burst.scala
Created Apr 2, 2016
quick and dirty sketch of burstsort
View burst.scala
import java.util.Arrays
// BurstSort
// Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries
// http://goanna.cs.rmit.edu.au/~jz/fulltext/alenex03.pdf
class BurstLeaf(initSize: Int) {
var size: Int = 0
@kaja47
kaja47 / jacc.c
Created Oct 5, 2015
jaccard similarity using AVX2 SIMD
View jacc.c
#include <stdio.h>
#include <immintrin.h>
#include <stdint.h>
int intersectionSize(int* a, const int alen, int* b, const int blen) {
int ai = 0, bi = 0, size = 0;
while (ai < alen && bi < blen) {
int av = a[ai];
int bv = b[bi];
size += ((av == bv) ? 1 : 0);
View bin-search.scala
// size = (1 << 25), time = 800 ms
// size = (1 << 25) - 1999, time = 400 ms ???
// size = (1 << 24), time = 700 ms
val size = 1 << 25
val randos = new util.Random()
val arr = Array.fill(size)(randos.nextInt)
java.util.Arrays.sort(arr)
View StringIntDictionary.scala
/** Idiosyncratic dictionary mapping strings to ints specialized for english
* words and other short alphanumeric strings. Long strigns are packed into
* one continuous char array, short alphanumeric strings are inlined into the
* structure that normally points into the array of long strings. This has the
* effect that strings shorter than 9 characters need only 12 bytes per mapping
* and lookup causes only one cache miss.
*
* Warning: Might contains subtle and not-so-soubtle errors.
*/
class StringIntDictionary {
@kaja47
kaja47 / 1nn.c
Last active Aug 29, 2015
nearest neighbor
View 1nn.c
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>
#include <immintrin.h>
#include "sys/param.h"
@kaja47
kaja47 / lol.php
Last active Aug 29, 2015
PHP polymorphic inline caches
View lol.php
<?php
class A {
public $somePropertyWithReasonablyLongName = 1;
}
class B {
public $somePropertyWithReasonablyLongName = 1;
}
View sepukku.scala
val boardStr = """
53 7 |
6 195 |
98 6 |
8 6 3|
4 8 3 1|
7 2 6|
6 28 |
419 5|
8 79|
View gist:fd426c8c21ddb07bb617
$size = 512*1024;
$keys = range(1, $size);
//shuffle($keys);
$arr = [];
foreach ($keys as $k) {
$arr[$k] = $k;
}
$s = microtime(1);
View gist:8951883af057590bc28b
try {
throw new Exception("E2")
} catch {
case ex: Exception if ex.getMessage == "E1" =>
println("caught E1")
case ex: Exception if ex.getMessage == "E2" =>
println("caught E2")
}
You can’t perform that action at this time.