Loading ...
Sorry, an error occurred while loading the content.

Re: Combining two criticisms (was: Re: [hackers-il] Question to graph theorists - non-recursive binary tree traversal algorithm?)

Expand Messages
  • Omer Zak
    ... If the tree nodes have links to their siblings and parents, and if the memory occupied by the links is not counted as extra memory (reasonable when the
    Message 1 of 12 , Aug 25, 2005
    • 0 Attachment
      On Thu, 2005-08-25 at 16:33 +0300, guy keren wrote:
      > On Thu, 25 Aug 2005, Arik Baratz wrote:
      >
      > > On 25/08/05, Omer Zak <omerz@...> wrote:
      > > > - Processes need to access the tree in different orders (prefix vs.
      > > > postfix traversal, for example)?
      > > > - Processes need to skip different parts of the tree while traversing
      > > > it.
      > > > - The tree is dynamically modified by another process (stipulating that
      > > > there are locking mechanisms such that processes in middle of tree
      > > > traversal are not confused by the change) and it is expensive to unroll
      > > > the tree after each modification.
      > >
      > > Hm.. I just came back from my thinking place, and it seems to me like
      > > Guy may be right after all. Your NextSibling() node method needs to
      > > know what you mean by 'next', so it has to somehow remember where in
      > > relation to other siblings you are now. It has to go to the parent,
      > > and look for the 'next' sibling. You need to keep information
      > > regarding which is the next sibling somewhere, and that somewhere is
      > > different for each process...
      >
      > ofcourse i was right. omer had tried to show that some basic issues of
      > computation theory are wrong, or some very hard problems are actually
      > easy to solve. what are the chances of him being right about this?
      >
      > you cannot traverse a tree using an O(1) ammount of extra memory - i think
      > if omer looks properly, he'll find proofs for this theorem.

      If the tree nodes have links to their siblings and parents, and if the
      memory occupied by the links is not counted as extra memory (reasonable
      when the trees are read-only accessed by several processes, each of
      which needs to maintain its own traversal state) - then you can consider
      the tree as a maze (each vertex is a corridor and each node is a meeting
      place of few corridors). You then follow the maze using the right hand
      law. When using the right hand law, you do not need more than O(1)
      read-write memory.

      Of course, when only a single process needs to traverse the tree at the
      same time, it is more economical to maintain the O(log N) read-write
      memory than to spend space on redundant links in the tree.

      > as i said, omer's in a very strange mood today - it's not like him to come
      > up with so many fataly flawed ideas. could it be that someone took over
      > omer's email account and is trying to ruin his reputation? :0

      Thanks for the belated compliment on my past ideas.
      If you feel bored by my flawed but nevertheless interesting (at least to
      my ego) ideas, which were publicized in an attempt to wake up the
      Hackers-IL mailing list, can you post your own speculative (translation:
      flawed) but interesting ideas?
      --- Omer
      --
      Jara Cimrman! He is one of the unsung geniuses--scientist, engineer,
      inventor and literary critic.
      My own blog is at http://www.livejournal.com/users/tddpirate/

      My opinions, as expressed in this E-mail message, are mine alone.
      They do not represent the official policy of any organization with which
      I may be affiliated in any way.
      WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
    • Omer Zak
      [... snipped ...] If the tree nodes have links to their siblings and parents, and if the memory occupied by the links is not counted as extra memory
      Message 2 of 12 , Aug 25, 2005
      • 0 Attachment
        [... snipped ...]
        If the tree nodes have links to their siblings and parents, and if the
        memory occupied by the links is not counted as extra memory (reasonable
        when the trees are read-only accessed by several processes, each of
        which needs to maintain its own traversal state) - then you can consider
        the tree as a maze (each vertex is a corridor and each node is a meeting
        ^^^^^^ should be "edge"
        place of few corridors). You then follow the maze using the right hand
        law. When using the right hand law, you do not need more than O(1)
        read-write memory.

        Of course, when only a single process needs to traverse the tree at the
        same time, it is more economical to maintain the O(log N) read-write
        memory than to spend space on redundant links in the tree.
        [... snipped ...]
        --- Omer
        --
        Jara Cimrman! He is one of the unsung geniuses--scientist, engineer,
        inventor and literary critic.
        My own blog is at http://www.livejournal.com/users/tddpirate/

        My opinions, as expressed in this E-mail message, are mine alone.
        They do not represent the official policy of any organization with which
        I may be affiliated in any way.
        WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
      • guy keren
        ... aha, but you are forgetting that you do not have an upper-bound on the number of children for a given node. consider this: [ P ] [C1] [C2] [C3] [C4]
        Message 3 of 12 , Aug 25, 2005
        • 0 Attachment
          On Fri, 26 Aug 2005, Omer Zak wrote:

          > If the tree nodes have links to their siblings and parents, and if the
          > memory occupied by the links is not counted as extra memory (reasonable
          > when the trees are read-only accessed by several processes, each of
          > which needs to maintain its own traversal state) - then you can consider
          > the tree as a maze (each vertex is a corridor and each node is a meeting
          > place of few corridors).You then follow the maze using the right hand
          > law.When using the right hand law, you do not need more than O(1)
          > read-write memory.

          aha, but you are forgetting that you do not have an upper-bound on the
          number of children for a given node. consider this:


          [ P ]


          [C1] [C2] [C3] [C4] [C5] [C6] [C7] [C8] [C9] [C10] [C11]


          lets say we were in C2, and are now returning to P. we now need to find
          which is the next node we should visit. the only way to make this in O(1),
          is that each node will keep a link to its sibling. add these links too,
          then. (if this operation is not O(1), it makes your scanning algorithm
          less efficient then O(N)).

          if you'll want to scan the tree in reverse order, you'll need the siblings
          list to be bidirectional.

          if you'll want to make a BFS scan, rather then DFS.....

          so, you see, you're creating a tree that lends itself to one manner of
          traversal, and does not work for other types of traversals.

          this could be useful for specific types of problems, ofcourse, but this is
          not the generic issue of traversing a tree structure.

          > Of course, when only a single process needs to traverse the tree at the
          > same time, it is more economical to maintain the O(log N) read-write
          > memory than to spend space on redundant links in the tree.

          log N is relevant assuming a balanced tree. in fact, it's not log N, but
          log (largest number of children of a single parent).

          > > as i said, omer's in a very strange mood today - it's not like him to come
          > > up with so many fataly flawed ideas. could it be that someone took over
          > > omer's email account and is trying to ruin his reputation? :0
          >
          > Thanks for the belated compliment on my past ideas.
          > If you feel bored by my flawed but nevertheless interesting (at least to
          > my ego) ideas, which were publicized in an attempt to wake up the
          > Hackers-IL mailing list, can you post your own speculative (translation:
          > flawed) but interesting ideas?

          if you can't bring up something useful - it's better to keep the list
          quiet. would you like me to bring up my mission-imposible project of
          devising an algorithm that automatically translates C programs into C++
          programs while introducing classes based on usage relations between data
          and functions in the original C program?

          --
          guy

          "For world domination - press 1,
          or dial 0, and please hold, for the creator." -- nob o. dy
        • Omer Zak
          ... How about that what-is-its-name transformation, which establishes an equivalence relationship between general and binary trees? Then you need to deal only
          Message 4 of 12 , Aug 25, 2005
          • 0 Attachment
            On Fri, 2005-08-26 at 02:13 +0300, guy keren wrote:

            > aha, but you are forgetting that you do not have an upper-bound on the
            > number of children for a given node. consider this:
            >
            >
            > [ P ]
            >
            >
            > [C1] [C2] [C3] [C4] [C5] [C6] [C7] [C8] [C9] [C10] [C11]
            >
            >
            > lets say we were in C2, and are now returning to P. we now need to find
            > which is the next node we should visit. the only way to make this in O(1),
            > is that each node will keep a link to its sibling. add these links too,
            > then. (if this operation is not O(1), it makes your scanning algorithm
            > less efficient then O(N)).

            How about that what-is-its-name transformation, which establishes an
            equivalence relationship between general and binary trees?

            Then you need to deal only with two children per node.

            > if you'll want to scan the tree in reverse order, you'll need the siblings
            > list to be bidirectional.
            >
            > if you'll want to make a BFS scan, rather then DFS.....
            >
            > so, you see, you're creating a tree that lends itself to one manner of
            > traversal, and does not work for other types of traversals.
            >
            > this could be useful for specific types of problems, ofcourse, but this is
            > not the generic issue of traversing a tree structure.

            OK, I give up.
            I propose a bicycle as a transportation vehicle, pointing out that it is
            the best solution for some specialized transportation situations.
            You reply by reminding us that most of the transportation needs of
            humans are better served by cars and airplanes.

            > if you can't bring up something useful - it's better to keep the list
            > quiet. would you like me to bring up my mission-imposible project of
            > devising an algorithm that automatically translates C programs into C++
            > programs while introducing classes based on usage relations between data
            > and functions in the original C program?

            Sounds cool and interesting. Can you tell us more about it?
            How do you avoid the trivial solution of enclosing function declarations
            by extern "C" { ... } declarations?
            --- Omer
            --
            Every good master plan involves building a time machine. Moshe Zadka
            My own blog is at http://www.livejournal.com/users/tddpirate/

            My opinions, as expressed in this E-mail message, are mine alone.
            They do not represent the official policy of any organization with which
            I may be affiliated in any way.
            WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
          Your message has been successfully submitted and would be delivered to recipients shortly.