Parser algorithm test for bosphorus.

parser_test.py

import random
import timeit
from collections import deque

from brial import declare_ring, Block

"""
Short script to test different parser algorithms for ANF's. Intended to show a possible improvement to the parser in Bosphorus.

Expects a python interpreter with access to sage, and specifically BRiAl.

Hopefully is representative of what I consider to be the bosphorus parser algorithm, and my new algorithm.
"""

d = {}
declare_ring([Block("b", 10000)], d)
x = d["b"]
BRIAL_ONE = d["r"].one()
BRIAL_ZERO = d["r"].zero()

CONS_ZERO = -1
CONS_ONE = -2
CONS_INIT = -3


def gen_poly(n_terms=50, n_mono=50, term_chance=0.25):
    """
    Returns an array of array of terms with differing lengths and monomials. Represents a single polynomial.
    """
    return sorted(
        [
            sorted([i+1 for i in range(n_terms) if random.random() < term_chance])
            for _ in range(n_mono)
        ]
    )


def parser_bosphorus(poly):
    out = BRIAL_ZERO

    for i, mono in enumerate(poly):
        monom = BRIAL_ONE
        if len(mono) == 0:
            continue
        elif monom == [CONS_ONE]:
            out += 1
        else:
            for term in mono:
                monom *= x(term)
            out += monom
    return out


def parser_reverse(xoa, node_val=CONS_INIT):
    """
    Build a ZDD structure from a XOA tuple structure.

    We represent the polynomial as a 2-dimensional matrix of terms, sorted by term-value (variable order).

    Naive, greedy, algorithms go through this basically row by row.
    This algorithm goes through it column-wise, in reverse order to the terms. This should minimize the work done navigating through the underlying ZDD structure.

    @param xoa: the 'xors of ands' tuple structure to build ZDD from
    @param node_val: the node value (integer) we are working on, may be negative for constants
    @return: the ZDD
    """
    if node_val == CONS_ONE:
        return BRIAL_ONE
    elif node_val == CONS_ZERO:
        return BRIAL_ZERO

    current_el = CONS_INIT
    zdd = BRIAL_ZERO
    dq = deque()

    for xors in reversed(xoa):
        if len(xors) == 0:
            continue
        elif xors[0] == current_el:
            dq.append(xors[1:])
        else:
            if current_el != CONS_INIT:
                zdd += parser_reverse(dq, current_el)

            current_el = xors[0]
            dq = deque()
            dq.append(xors[1:])

    zdd += parser_reverse(dq, current_el)

    if node_val == CONS_INIT:
        return zdd
    else:
        return x(node_val) * zdd


if __name__ == "__main__":
    n_terms, n_mono, term_chance = 500, 500, 0.50
    n = 1

    poly = gen_poly(n_terms, n_mono, term_chance)

    t0 = timeit.timeit(lambda: parser_bosphorus(poly), number=n)
    poly = [
        p + [CONS_ONE] for p in poly
    ]  # preparation needed for the reverse-order/column-wise algo, this would normally be added by the tokenizer at nearly no cost, so should be kept out of the timer loop
    t1 = timeit.timeit(lambda: parser_reverse(poly), number=n)
    print("Original parser: %.2f\nNew parser: %.2f\nSpeed-up: %.2f" % (t0, t1, t0 / t1))