Project

compsci

0.0
No release in over a year
Trees, Heaps, Timers, Error fitting, etc
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
 Dependencies

Development

~> 3.0
~> 0
~> 0
>= 5.0
>= 12.3.3
~> 0
 Project Readme

CI Status Gem Version

CompSci

Provided are some toy implementations for some basic computer science problems.

Node classes

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.

CompleteTree classes

Efficient Array implementation of a complete tree uses arithmetic to determine parent/child relationships.

  • CompleteTree

    • CompleteTree.parent_idx
    • CompleteTree.children_idx
    • CompleteTree.gen
    • @array
    • @child_slots
    • #push
    • #pop
    • #size
    • #last_idx
    • #display - alias #to_s
  • CompleteBinaryTree < CompleteTree

    • @child_slots = 2
  • CompleteTernaryTree < CompleteTree

    • @child_slots = 3
  • CompleteQuaternaryTree < CompleteTree

    • @child_slots = 4
  • examples/complete_tree.rb

  • test/complete_tree.rb

  • test/bench/complete_tree.rb

Heap class

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 module

  • 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

Timer module

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

Names module

This helps map a range of small integers to friendly names, typically in alphabetical order.

Names::Greek module

  • UPPER LOWER SYMBOLS CHAR_MAP LATIN_SYMBOLS SYMBOLS26
  • Names::Greek.upper
  • Names::Greek.lower
  • Names::Greek.sym

Names::Pokemon module

  • Names::Pokemon.array
  • Names::Pokemon.hash
  • Names::Pokemon.grep
  • Names::Pokemon.sample

Simplex class

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.

Simplex::Parse module

  • 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')

# => [1.6666666666666667, 0.6666666666666666]



s = Simplex.problem(maximize: 'x + y',
                    constraints: ['2x + y <= 4',
                                  'x + 2y <= 3'])

# => #<CompSci::Simplex:0x0055b2deadbeef
#      @max_pivots=10000,
#      @num_non_slack_vars=2,
#      @num_constraints=2,
#      @num_vars=4,
#      @c=[-1.0, -1.0, 0, 0],
#      @a=[[2.0, 1.0, 1, 0], [1.0, 2.0, 0, 1]],
#      @b=[4.0, 3.0],
#      @basic_vars=[2, 3],
#      @x=[0, 0, 4.0, 3.0]>

s.solution

# => [1.6666666666666667, 0.6666666666666666]