logv

wow, that's way off!

for n = 2, n^n^n^n returns 65536. for n = 3, javascript thinks its infinity.

i guess BOAT should start using decimal values for n so we can detect this problem.

logv

7년 전discuss

Yes, this is likely true - I really need to think about it more, though. I don't know how to do static or runtime analysis, so I can't say much about it

logv

7년 전discuss

Yes, it analyzes a formula or recurrence relation - sorry to get your hopes up :-D I wish it could analyze source code, but the halting problem says that would be a bit difficult.

I think one could execute source code with varying size inputs to get an idea of a function's growth (assuming the function does halt), but I haven't thought about what that entails

PS: maybe I should have named it BOFAT (Big O Formula Analyzer Tool)

logv

7년 전discuss

Thanks for the feedback and good catch!

The list of big O classes is the following:

   var classes = [
      define_func("0"),
      define_func("1"),
      define_func("lg(n)"),
      define_func("sqrt(n)"),
      define_func("n"),
      define_func("n * lg(lg((n)))"),
      define_func("n * lg(n)"),
      define_func("n * sqrt(n)"),
      define_func("n**2"),
      define_func("n**3"),
      define_func("n**4"),
      define_func("2**n"),
      define_func("n**n"),
      define_func("factorial(n)"),
      define_func("2**(2**n)"),
      define_func("n**(n**n)"),
    ];

lg(lg(N)) is very small, for 1e30, the value is approximately ~6 and at 1e60 it is ~7.6, at which point lg(lg(N)) is pretty much a constant value (or trivial), but yes - it is technically included in the growth rate, but for practical purposes can probably be ignored

logv

7년 전discuss

BOAT is a quick tool I made for analyzing and comparing the Big O growth rate of mathematical functions. I built it to help students get a sense of Big O notation, as its a common class exercise to have to rank several math functions in terms of their Big O. BOAT works by trying to find an upper and lower bound of a given math function by comparing the function against a set of known functions. If it can't find a tight bound, it tries to find an upper bound.

If it's given two functions, it will try to locate their crossover point (if any) using a binary search, as well as compare their growth rates to determine which will eventually grow faster. It might get some wrong (I'm curious which) as it only has a handful of function classes.

The last feature it has is an automated master/muster theorem solver. It's pretty simple - you give it the values of a recurrence relation and it tells you the big O.

Thanks for looking!

logv

9년 전discuss

good point! i'm not against a DSL. as I was working on plait.py, one thought going through my head was: "am i re-writing haskell or lisp but worse"? my experience with python and DSL is that I need to use YACC / PLY to create a grammar and so on. maybe a lot of work. i take it that its easier in ruby?

yaml was a format I chose because it is easy to write (close to human), but can not express full programming concepts (but yes to some metaprogramming). i did not want the templates to be full powered as they are meant to be able to express relationships between variables, but not much more (especially not side effects). they also support lazy evaluation - statements do not need to be in order. this is closer to a "mathematical language" for me.

the choice for yaml was also based on the premise that if performance becomes an issue, can hopefully move to another language but retain templates (will have to re-implement python's "random" compat, though)

logv

9년 전discuss

it's a drop in replacement for stympy/faker, but not joke2k faker

joke2k/faker is python and the data is stored in code (all or most of the random values are in .py files around the codebase), perhaps leading to its slowness.

stympy/faker is ruby and its random values are in yaml files, with some fields defined as ruby functions (those are not supported by plait.py).

can use 'plait -l' and 'plait -ll name' and 'plait -ll name.name' (more info in the README) to get a list of fake fields available.

logv

9년 전discuss

part of what prompted the work on plait.py was that joke2k/faker was reasonably slow to generate 10K fake names for me: https://paste.ubuntu.com/26354987/

PS. that's a really cool python tip!

logv

9년 전discuss

if you already have a way of printing XML, you can add a "printer" field (that is a python function) to your template, like so:http://github.com/plaitpy/plaitpy/blob/master/templates/test...

if that function uses an import, you might also need to add an "imports" field, like in this example: https://github.com/plaitpy/plaitpy/blob/master/templates/web...

otherwise, that's a feature that can be added here: https://github.com/plaitpy/plaitpy/blob/master/src/fields.py..., if it works for you (and is added as a flag), i'd be happy to take patches.

logv

9년 전discuss

if you create a template and keep calling .gen_record(), i think it will do what you want. Template() does not implement python's __next__ or __iter__ at the moment, but that's a good idea - i'm very open to diffs :-D

Submissions

Logs vs. Metrics – A False Dichotomy

Show HN: Boat – Big O analysis tool

Show HN: Plait.py – a fake data modeler

comments