Skip to content

Instantly share code, notes, and snippets.

Tim McCormack timmc

View GitHub Profile
@timmc
timmc / weighted-shuffle-sampling.clj
Created Mar 25, 2019
A sampling-based version of weighted-shuffle (better to use the exponential random solution)
View weighted-shuffle-sampling.clj
;; This is asymptotically slower (n^2) than the exponential random sort
;; one (n log n) shown in https://gist.github.com/timmc/1211c1ac8ae96c2b42c94124005b5414
;; but it is preserved here for possible later interest
(defn weighted-random-sample
"Given a coll of weights, pick one according to a weighted-random
selection, and return its index. Weights must be non-negative."
[weights]
(when (empty? weights)
(throw (IllegalArgumentException. "Cannot sample from empty list")))
View weighted-shuffle-fancy.clj
(defn weighted-shuffle
"Perform a weighted shuffle on a collection. weight-fn is called at
most once for every element in the collection."
[weight-fn coll]
(->> coll
(shuffle) ;; tie-break any zero weights
(map (fn [el]
;; Bound the weight to positive values
(let [weight (Math/max Double/MIN_VALUE (double (weight-fn el)))
;; Weighted Random Sampling (2005; Efraimidis, Spirakis)
@timmc
timmc / spclsfc.md
Last active Mar 19, 2019
Success-prioritized, concurrency-limited stochastic fallback cascade
View spclsfc.md

Algorithm:

  • State
    • For each node, store:
      • Rolling window of 6 historical stat buckets
      • One additional "sticky" bucket
    • Write stats to newest bucket
    • Age out the oldest bucket every 5 seconds, and add a new one
      • If the oldest bucket had data, copy it over the "sticky" bucket
    • Recorded stats: Number of finished requests, number that
View urldecode.sh
#!/bin/bash
while read line; do
url_encoded="${line//+/ }"
printf '%b\n' "${url_encoded//%/\\x}"
done
@timmc
timmc / state-machine.java
Created Jan 22, 2019
Custom query term splitter, as state machine (demonstration only; a regex with possessive quantifiers slightly out-performs this)
View state-machine.java
public static List<String> splitTermsStateMachine(String query) {
// Horizontal or vertical whitespace
Pattern isWhitespace = Pattern.compile("[\\h\\v]");
//== Manually managed state bits ==//
// If non-null, we're in a term, and this contains the term so far
StringBuilder currentTerm = null;
// True iff inside a quoted run
boolean inQuotes = false;
View MapEntry.kt
data class MapEntry<K: Any?, V: Any?>(
override val key: K,
override val value: V
): Map.Entry<K, V>
@timmc
timmc / layout.kt
Created Nov 18, 2018
Wanted: Fluent interface for specifying filesystem layout
View layout.kt
class Repo : Layout() {
val config by leaf("config.json")
val myKeyring by leaf("self.keyring")
val posts by dir("posts", ::PostsDir)
}
class PostsDir : Layout() {
val post by multiple().dir(name = """[0-9]+""".toRegex(), ::OnePost)
}
@timmc
timmc / gist:d95b90336dfc63881a4034fef436c6e1
Created May 3, 2018
Passphrase compound collision - case analysis
View gist:d95b90336dfc63881a4034fef436c6e1
- 3 word passphrases
- 1000 word list, with one collision: dog, under, underdog
Compounding:
under dog x: 1000
x under dog: 1000
Total loss: 2 * 1000 out of 1000^3
View gist:55c8e488533e04f34efea3ef8de1f00c
-XX:-OmitStackTraceInFastThrow
-Dfile.encoding=UTF-8
@timmc
timmc / crash-imagemagick.svg
Last active May 6, 2017
segfaults imagemagick when `convert crash.svg out.jpg`
View crash-imagemagick.svg
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
You can’t perform that action at this time.