Skip to content

Instantly share code, notes, and snippets.

Tim McCormack timmc

Block or report user

Report or block timmc

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
@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.