Skip to content

Instantly share code, notes, and snippets.


Justin Meiners justinmeiners

View GitHub Profile
(defun compact-duplicates (vector cmp)
(prog ((i 1)
(j 1)
(N (length vector))
(x (aref vector 0)))
(if (not (funcall cmp (aref vector i) x))
(setf x (aref vector i))
; my own sin and cos functions using taylor seris
(defun eval-poly (coef x)
; horners method
(prog* ((i (- (length coef) 1))
(acc (aref coef i)))
(decf i)
(if (< i 0) (return acc))
(setf acc (+ (aref coef i) (* x acc)))
; code translated from
; note that theirs actually has an off by one error
(defun integer-sqrt (n)
(prog ((shift 2) (result 0))
(declare (fixnum n shift result))
(if (< n 2) (return n))
(if (not (= (ash n (- shift)) 0))
(defun group-adjacent (list &key (test #'eql))
(lambda (group x)
(if (or (funcall test (car group) x) (funcall test x (car group)))
(push group result)
(list x))
(cons x group)))
(cdr list)
View energy_minimize.js
// node kernel.js > out.txt; gnuplot -p -e 'plot "out.txt" using 1:2 with points pt 7'
function minimizeEnergy(samples, sampleCount, steps) {
// energy conservation
for (var step = 0; step < steps; ++step) {
for (var i = 0; i < sampleCount; ++i) {
var x = samples[i * 2];
(defun vec-zero (n &key (element-type 'float))
(make-array n
:element-type element-type
:initial-element (coerce 0 element-type)))
(defun vec-basis (n i &key (element-type 'float))
(let ((r (vec-zero n :element-type element-type)))
(setf (aref r i) (coerce 1 element-type))
View xlib_image.c
// gcc -I/usr/X11/include -L/usr/X11/lib -lX11 xlib_image.c
// bsd: gcc -I/usr/X11R6/include -L/usr/X11R6/lib -lX11 xlib_image.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <X11/Xlib.h>
#include <X11/Xutil.h>
void draw(char *rgb_out, int w, int h)
; either input works in SBCL
;(load "~/quicklisp/setup.lisp")
;(ql:quickload "asdf")
(require "asdf")
;(print (asdf:asdf-version))
; of course "cat" is superfulous here,
; but I just wanted to try out piping data.
(defparameter cat
justinmeiners /
Last active Oct 30, 2020
Why is std::map typically implemented as a red-black tree?

Why is std::map typically implemented as a red-black tree?

Why not a hash table?

A type only requires < operator (comparison) to be used as a key in a tree. However, hash tables require that each key type has a hash function defined. Keeping type requirements to a minimum is very important for generic programming so you can use it with a wide variety of types and algorithms.

Designing a good hash table requires intimate knowledge of the context it which it will be used. Should it use open addressing, or linked chaining? What levels of load should it accept before resizing? Should it use an expensive hash that avoids collisions, or one that is rough and fast?

Since the STL can't anticipate which is the best choice for your application, the default needs to be more flexible. Trees "just work" and scale nicely.

View nsopenpanel.m
NSOpenPanel *panel;
NSArray* fileTypes = [NSArray arrayWithObjects:@"pdf", @"PDF", nil];
panel = [NSOpenPanel openPanel];
[panel setFloatingPanel:YES];
[panel setCanChooseDirectories:NO];
[panel setCanChooseFiles:YES];
[panel setAllowsMultipleSelection:YES];
[panel setAllowedFileTypes:fileTypes];
int i = [panel runModal];
if (i == NSOKButton){
You can’t perform that action at this time.