
CompSci
Provided are some toy implementations for some basic computer science problems.
Node
A Node provides a tree structure by assigning other Nodes to @children
.
-
Node
@value
@children
#[]
- child node at index
#[]=
- set child node at index
display
- display full tree with all descendents
-
examples/tree.rb
-
test/node.rb
KeyNode
A KeyNode adds @key
and allows a comparison based search on the key.
Binary search trees
are supported, and the @duplicated
flag determines whether duplicate keys
are allowed to be inserted. Any duplicates will not be returned from
#search
. A Ternary search tree is also supported, and it inherently allows
duplicates keys. #search
returns an array of KeyNode
, possibly empty.
ChildNode
A ChildNode adds reference to its @parent
.
Efficient Array implementation of a complete tree uses arithmetic to
determine parent/child relationships.
CompleteTree implementation. Both minheaps and maxheaps are
supported. Any number of children may be provided via child_slots
.
The primary operations are Heap#push
and Heap#pop
. My basic Vagrant VM
gets over 500k pushes per second, constant up past
1M pushes.
-
Fibonacci.classic(n)
- naive, recursive
-
Fibonacci.cache_recursive(n)
- as above, caching already computed results
-
Fibonacci.cache_iterative(n)
- as above but iterative
-
Fibonacci.dynamic(n)
- as above but without a cache structure
-
Fibonacci.matrix(n)
- matrix is magic; beats dynamic around n=500
-
test/fibonacci.rb
-
test/bench/fibonacci.rb
require 'compsci/timer'
include CompSci
overall_start = Timer.now
start = Timer.now
print "running sleep 0.01 (50x): "
_answer, each_et = Timer.loop_avg(count: 50) {
print '.'
sleep 0.01
}
puts
puts "each: %0.3f" % each_et
puts "elapsed: %0.3f" % Timer.since(start)
puts "cumulative: %0.3f" % Timer.since(overall_start)
puts
start = Timer.now
print "running sleep 0.02 (0.3 s): "
_answer, each_et = Timer.loop_avg(seconds: 0.3) {
print '.'
sleep 0.02
}
puts
puts "each: %0.3f" % each_et
puts "elapsed: %0.3f" % Timer.since(start)
puts "cumulative: %0.3f" % Timer.since(overall_start)
puts
running sleep 0.01 (50x): ..................................................
each: 0.010
elapsed: 0.524
cumulative: 0.524
running sleep 0.02 (0.3 s): ...............
each: 0.020
elapsed: 0.304
cumulative: 0.828
Fit
module
-
Fit.sigma
- sums the result of a block applied to array values
-
Fit.error
- returns a generic r^2 value, the coefficient of determination
-
Fit.constant
- fits y = a + 0x
; returns the mean and variance
-
Fit.logarithmic
- fits y = a + b*ln(x)
; returns a, b, r^2
-
Fit.linear
- fits y = a + bx
; returns a, b, r^2
-
Fit.exponential
- fits y = ae^(bx)
; returns a, b, r^2
-
Fit.power
- fits y = ax^b
; returns a, b, r^2
-
Fit.best
- applies known fits; returns the fit with highest r^2
-
test/bench/complete_tree.rb
-
test/fit.rb
This helps map a range of small integers to friendly names, typically in
alphabetical order.
UPPER
LOWER
SYMBOLS
CHAR_MAP
LATIN_SYMBOLS
SYMBOLS26
Names::Greek.upper
Names::Greek.lower
Names::Greek.sym
Names::Pokemon.array
Names::Pokemon.hash
Names::Pokemon.grep
Names::Pokemon.sample
WORK IN PROGRESS; DO NOT USE
The Simplex algorithm
is a technique for
Linear programming.
Typically the problem is to maximize some linear expression of variables
given some constraints on those variables in terms of linear inequalities.
-
Parse.tokenize
- convert a string to an array of tokens
-
Parse.term
- parse certain tokens into [coefficient, varname]
-
Parse.expression
- parse a string representing a sum of terms
-
Parse.inequality
- parse a string like "#{expression} <= #{const}"
-
test/simplex_parse.rb
With Simplex::Parse
, one can obtain solutions via:
Simplex.maximize
- takes an expression to maximize followed by a variable
number of constraints / inequalities; returns a solution
Simplex.problem
- a more general form of Simplex.maximize
; returns a
Simplex object
require 'compsci/simplex/parse'
include CompSci
Simplex.maximize('x + y',
'2x + y <= 4',
'x + 2y <= 3')
s = Simplex.problem(maximize: 'x + y',
constraints: ['2x + y <= 4',
'x + 2y <= 3'])
s.solution