[FoRK] Data Structures Question
Albert S.
<albert.scherbinsky at rogers.com> on
Wed Apr 4 07:22:18 PDT 2007
Let's be blunt here. The original question was vague.
If ya wants the right answer, ya gots to aks the right
question. If you want the right datastructure then you
need a clear description of the context in which that
datastructure lives. Inputs, Outputs, performance
constraints. None of these was clear from the original
question.
Albert
--- "Stephen D. Williams" <sdw at lig.net> wrote:
> The original question was trying to optimize when
> there were _any_
> number of variables. I took any to be very large
> (thousands or 10's of
> thousands), so O(n Log(n)) isn't very good compared
> to what can probably
> be done. In many cases, these kinds of problems
> will have mostly false
> variables or rules with limited interdependency
> which can be optimized for.
>
> sdw
>
> Nalin Savara wrote:
> >> No, that doesn't do the job. I'm not looking to
> rewrite a boolean
> >> calculator. I'm looking for a structure, such as
> a tree, that has inherent
> >> properties that provide loading of an expression
> with and's and or's, but
> >> enables to you go to a specific node, or use an
> algorithmic method of
> >> navigation through the nodes, so that getting the
> subexpressions costs, at
> >> the worst case, n * log(n)
> >>
> >>
> > Reza; Andy; Joe ;
> >
> > To add to Joe Barrera's very commendable and
> applicable answer:--
> > (and I say this as someone who was once co-author
> of a algorithm design book
> > that had a whole chapter on this):-- (Joe, Andy et
> al, feel free to comment)
> >
> > you can do the following:-- (the below are the
> exact steps--- hopefully
> > this'll help you get it to code and skip the
> complicated proofs in Dragon
> > book):--
> >
> > (1) First input the boolean expression in infix
> notation
> > (2) Convert above boolean expression to postfix
> notation-- use the
> > stack-based infix to postfix conversion algo found
> in any elementary
> > data-structures book.
> > Note: this algo is very efficient; because it
> involves peeking at the
> > stack-top-- which is the equivalent of LALR(1)
> parsing-- because peeking at
> > stack top is peeking ahead one symbol ahead.
> >
> > (3) Take the postfix expression and generate a
> tree out of it--> involves
> > walking through the expression pushing nodes with
> each node having a single
> > operand from the expression onto the stack until
> you 'see' a operator--> and
> > at that point, you pop two nodes with operands,
> and replace those with a
> > parent node with one operator and two terminal
> nodes which contain the
> > operands (or a single child node with a single
> operand incase of a unary
> > operator).
> >
> > (4) When there are no more operators or operands
> left in the expression; at
> > that point the stack will automatically contain
> just one pushed node--> and
> > that will be the root node of the expression tree
> representing the
> > expression.
> >
> > The order of the above expression tree generation
> will be O(n Log(n) ) -->
> > and assuming that nodes have pointers to parent
> nodes; and also references
> > to symbols in original expression, you can go from
> any node to any other
> > node as desired by you.
> >
> > If you want I can dig around for my old code-- see
> if i can find
> > somethingthat does almost exactly what you want.
> >
> > Hope that helps...
> >
> > Nalin
> >
> >
> > ----- Original Message -----
> > From: "Andy Armstrong" <andy at hexten.net>
> > To: <reza at voicegenesis.com>; "Friends of Rohit
> Khare" <fork at xent.com>
> > Sent: Tuesday, April 03, 2007 4:20 PM
> > Subject: Re: [FoRK] Data Structures Question
> >
> >
> >
> >> On 3 Apr 2007, at 05:33, Reza B'Far wrote:
> >>
> >>> However, I purposefully am trying not to treat
> it as a "logic"
> >>> question. I
> >>> want to load n expressions into a structure,
> such as a tree, that
> >>> has the
> >>> properties that support the decomposition that I
> want.
> >>> Essentially, what I
> >>> want is to explode the boolean (Andy refers to
> this) but with some
> >>> added
> >>> constraints... Get all the "anded" terms
> together in one single
> >>> expression.
> >>> So, the subexpressions should only have AND's.
> >>>
> >> That /is/ a sum of products then... If you
> rewrite your original
> >> expression in SoP form you get
> >>
> >> (e1 && e2 && e5) || (e3 && e5) || (e4 && e5)
> >>
> >> which is just your three AND terms ORed together.
> >>
> >>
> >>> So, to summarize, I'm trying to find a structure
> that has this
> >>> inherently
> >>> built in... which by several degrees of
> indirection means
> >>> significantly
> >>> improved performance if you have n expressions
> and need to find the
> >>> subexpressions and the path that was necessary
> to navigate to each
> >>> randomly... basically, looking for the canonical
> solution... don't
> >>> know if
> >>> one exists or not.
> >>>
> >> I'm obviously having YASD[1] but I'm still not
> really clear what you
> >> mean. For your example does the tree look like
> this?
> >>
> >> ( or )
> >> / | \
> >> / | \
> >> / (and) \
> >> / / \ \
> >> (and) e3 e5 (and)
> >> / | \ / \
> >> e1 e2 e5 e4 e5
> >>
> >> It might be worth looking at this:
> >>
> >> http://www.dei.isep.ipp.pt/~acc/bfunc/
> >>
> >> Unfortunately it's binary-only but, if nothing
> else, some of the
> >> links might be useful. I recently used it in
> conjunction with a
> >> little Perl wrapper to semi-automatically
> refactor a bunch of complex
> >> business rules.
> >>
> >> [1] Yet Another Stupid Day
> >>
> >> --
> >> Andy Armstrong, hexten.net
> >>
> >> _______________________________________________
> >> FoRK mailing list
> >> http://xent.com/mailman/listinfo/fork
> >>
> >
> > _______________________________________________
> > FoRK mailing list
> > http://xent.com/mailman/listinfo/fork
> >
>
> _______________________________________________
> FoRK mailing list
> http://xent.com/mailman/listinfo/fork
>
More information about the FoRK
mailing list