Commits

Kenneth Jørgensen committed c8fa56f

Implemented weighted randomness and random array selection

  • Participants
  • Parent commits e4f7623

Comments (0)

Files changed (5)

File coffeelint.coffee

 	"no_throwing_strings":
 		"level": "error"
 	"cyclomatic_complexity":
-		"value": 1
+		"value": 4
 		"level": "error"
 	"no_backticks":
 		"level": "error"

File package.json

 {
 	"fullname": "RandomUtil",
 	"name": "random-util",
-	"version": "0.0.1",
+	"version": "0.0.2",
 	"description": "Randomness utility.",
 	"keywords": ["random", "prng"],
 	"homepage": "https://bitbucket.org/kennethjor/random-util",

File random-util.js

-/*! RandomUtil 0.0.1-dev - MIT license */
+/*! RandomUtil 0.0.2 - MIT license */
 (function() {
-  var RandomUtil, exports, floor, root;
+  var RandomUtil, exports, floor, root,
+    __hasProp = {}.hasOwnProperty;
 
   root = this;
 
   RandomUtil = {
-    version: "0.0.1-dev"
+    version: "0.0.2"
   };
 
   if (typeof exports !== "undefined") {
     return this.random() * (max - min) + min;
   };
 
+  RandomUtil.arrayElement = function(arr) {
+    var index;
+    index = this.randomInt(0, arr.length - 1);
+    return arr[index];
+  };
+
+  RandomUtil.weighted = function(obj) {
+    var current, i, pos, r, sum, v;
+    sum = 0;
+    for (i in obj) {
+      if (!__hasProp.call(obj, i)) continue;
+      v = obj[i];
+      sum += parseFloat(v);
+    }
+    r = this.random();
+    pos = r * sum;
+    current = 0;
+    for (i in obj) {
+      if (!__hasProp.call(obj, i)) continue;
+      v = obj[i];
+      current += parseFloat(v);
+      if (current > pos) {
+        return i;
+      }
+    }
+    throw new Error("This should never happen, r was " + r);
+  };
+
 }).call(this);

File spec/RandomUtilSpec.coffee

 describe "RandomUtil", ->
 	state = null
 	precision = null
+	increment = null
+
 	beforeEach ->
-		precision = 0.00000001
+		precision = 4
 		state = 0.0
+		increment = 0.1
 		RandomUtil.random = ->
 			r = state
-			state += 0.1
+			state += increment
+			if r <= 0.0 then return 0.0000001
+			if r >= 1.0 then return 0.9999999
 			return r
 
 	it "should generate predictable random numbers during tests", ->
+		expect(RandomUtil.random()).toBeCloseTo 0.0, precision
 		expect(RandomUtil.random()).toBeCloseTo 0.1, precision
 		expect(RandomUtil.random()).toBeCloseTo 0.2, precision
 		expect(RandomUtil.random()).toBeCloseTo 0.3, precision
-		expect(RandomUtil.random()).toBeCloseTo 0.4, precision
 
 	it "should generate random integers", ->
 		expect(RandomUtil.randomInt 3, 12).toEqual 3
 		expect(RandomUtil.randomInt 3, 12).toEqual 11
 		expect(RandomUtil.randomInt 3, 12).toEqual 12
 
+	it "should generate evenly distributed random integers", ->
+		RandomUtil.random = Math.random
+		generated = {}
+		n = 1000000
+		for i in [1..n]
+			v = RandomUtil.randomInt 5, 9
+			generated[v] or= 0
+			generated[v]++
+		for own i, v of generated
+			generated[i] = v/n
+		expect(generated[5]).toBeCloseTo 1/5, 2
+		expect(generated[6]).toBeCloseTo 1/5, 2
+		expect(generated[7]).toBeCloseTo 1/5, 2
+		expect(generated[8]).toBeCloseTo 1/5, 2
+		expect(generated[9]).toBeCloseTo 1/5, 2
+
 	it "should generate random numbers", ->
 		expect(RandomUtil.randomNumber 10, 15).toBeCloseTo 10.0, precision
 		expect(RandomUtil.randomNumber 10, 15).toBeCloseTo 10.5, precision
 		expect(RandomUtil.randomNumber 10, 15).toBeCloseTo 14.0, precision
 		expect(RandomUtil.randomNumber 10, 15).toBeCloseTo 14.5, precision
 		expect(RandomUtil.randomNumber 10, 15).toBeCloseTo 15.0, precision
+
+	it "should select random array elements", ->
+		increment = 0.25
+		arr = "abcd".split("")
+		expect(RandomUtil.arrayElement arr).toBe "a"
+		expect(RandomUtil.arrayElement arr).toBe "b"
+		expect(RandomUtil.arrayElement arr).toBe "c"
+		expect(RandomUtil.arrayElement arr).toBe "d"
+
+	it "should select from a weighted hash", ->
+		increment = 1/(6-1)
+		obj =
+			a: 0
+			b: 1
+			c: 2
+			d: 3
+		expect(RandomUtil.weighted obj).toBe "b"
+		expect(RandomUtil.weighted obj).toBe "c"
+		expect(RandomUtil.weighted obj).toBe "c"
+		expect(RandomUtil.weighted obj).toBe "d"
+		expect(RandomUtil.weighted obj).toBe "d"
+		expect(RandomUtil.weighted obj).toBe "d"

File src/RandomUtil.coffee

 # Returns a random number between `min` and `max`.
 RandomUtil.randomNumber = (min, max) ->
 	return @random() * (max - min) + min
+
+# Returns a random element from an array.
+RandomUtil.arrayElement = (arr) ->
+	index = @randomInt 0, arr.length - 1
+	return arr[index]
+
+# Given an object with string indexes and integer weights, will return a random index based on those weights.
+#
+#     var val = RandomUtil({
+#        "bird": 2
+#        "dog": 1
+#        "cat": 0
+#     });
+#
+# Bird is now twice as likely to be returned as dog, and cat will never be returned.
+RandomUtil.weighted = (obj) ->
+	sum = 0
+	for own i, v of obj
+		sum += parseFloat v
+	r = @random()
+	pos = r * sum
+	current = 0
+	for own i, v of obj
+		current += parseFloat v
+		if current > pos
+			return i
+	throw new Error "This should never happen, r was #{r}"