> How does bisect achieve this if not by traversing each node in turn and
returning the first found, like how the dict is being used currently?

In all fairness, there is no way, this can be achieved without some sort of
iteration. Bisect is efficient because it implements the binary search
algorithm which runs in O(logN) time in the worst case. For a few hundred
or maybe even few thousand nodes this is better than doing a for loop for
finding a key. The key point is the binary search. In a for loop you go
through each key of the dictionary from top to bottom, in binary search,
you start from the middle and halve the search domain in each iteration,
which is far more efficient. Not to mention, running a for loop inside
another for loop makes this O(n**2)

Dict (hash table) is good only if you know the key beforehand, otherwise,
you will have to implement your own logic to find the right key, value pair
and that logic either bloats up your code and/or sometimes makes it less
efficient in terms of both memory and/or performance. And then python has
these little gotchas when it comes to optimization (simple things like
using `xrange` over `range`, `izip` over `zip`, even using `% (a,)` in
place of `% a` make a considerable difference), which might be overlooked,
if either you don't know them or you don't have time to polish your code.

For me bisect brings two distinct advantages to the table:
1. A compiled efficient fast search code that has been optimized to a
certain level (being a part of core python library) compared to my own
logic that might or might not be the fastest, efficient thing.
2. A neat single line call in my code instead of a for loop and maybe other
conditionals, control flows, lookups etc. with my own logic - readability
does count.

Also, not an answer to your original question but -
I did a dry run of your code replacing the parenting with a simple print
like '{0} ->{1}'.format(parent, child). I saw that parenting was done
multiple times starting from a top parent and going down to the desired
level:
level1->child, level2->child, level3->child etc. With bisect
implementation, you leave all that to the algorithm and just parent once.

In the end, I admit that this was a quick first stab at the problem and
might not be the greatest code or there may be a more beautiful, idiomatic
simpler pythonic way of doing this through the use of dictionaries or some
other standard container.



On Fri, Sep 16, 2016 at 10:04 PM, Marcus Ottosson <konstrukt...@gmail.com>
wrote:

> > but then you should do this lookup only once for each node and not
> iterate through each key and then deep inside it until some condition is
> reached. To me, that is a bit complex.
>
> Ah, yes that is true. I did not think of that. Thanks for pointing that
> out.
>
> As someone who isn't terribly familiar with bisect, how does bisect
> achieve this if not by traversing each node in turn and returning the first
> found, like how the dict is being used currently?
>
> On 16 September 2016 at 15:01, Alok Gandhi <alok.gandhi2...@gmail.com>
> wrote:
>
>> Hi Marcus,
>>
>> My objective was simple, parenting is the main focus and it should be
>> done  once and only once for each node in the hierarchy. To achieve this,
>> during each iteration the node should have knowledge about his parent just
>> by knowing its position (indent).
>>
>> I did not want complex processing of saving states and whole trees and
>> then lookup up and down. The node should have a place (the tuple list) to
>> look for its parent. It simply asks this question - I have this position,
>> who is my parent. This is typically looking for an insertion point in an
>> array and bisect was a perfect candidate for these requirements.
>>
>> After finding the parent, the node attaches itself to the list replacing
>> the current node at that position so that preceding nodes can find it as a
>> parent when required.
>>
>> Using a dict is a better option just for the reason of O(1) lookup times,
>> but then you should do this lookup only once for each node and not iterate
>> through each key and then deep inside it until some condition is reached.
>> To me, that is a bit complex.
>>
>> On Fri, Sep 16, 2016 at 8:44 PM, Marcus Ottosson <konstrukt...@gmail.com>
>> wrote:
>>
>>> Ok, Alok, I had a closer look at your example and the bisect module in
>>> Python.
>>>
>>> In my example, a dict replaces bisect. The dict is limited, in that once
>>> a parent at the same level as an above parent appears, the above parent
>>> vanishes from consideration. But in this case, maybe that works to our
>>> advantage? Could you tell me about your motivation for using bisect?
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Python Programming for Autodesk Maya" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to python_inside_maya+unsubscr...@googlegroups.com.
>>> To view this discussion on the web visit https://groups.google.com/d/ms
>>> gid/python_inside_maya/d86fb040-1d59-492d-8b7c-50dc5cf67d96%
>>> 40googlegroups.com
>>> <https://groups.google.com/d/msgid/python_inside_maya/d86fb040-1d59-492d-8b7c-50dc5cf67d96%40googlegroups.com?utm_medium=email&utm_source=footer>
>>> .
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
>>
>>
>> --
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Python Programming for Autodesk Maya" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to python_inside_maya+unsubscr...@googlegroups.com.
>> To view this discussion on the web visit https://groups.google.com/d/ms
>> gid/python_inside_maya/CAPaTLMTaOkfYe0G_x3JCMxfDwiJzeYeQMyAO
>> bKCGuPqA2n7foQ%40mail.gmail.com
>> <https://groups.google.com/d/msgid/python_inside_maya/CAPaTLMTaOkfYe0G_x3JCMxfDwiJzeYeQMyAObKCGuPqA2n7foQ%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .
>>
>> For more options, visit https://groups.google.com/d/optout.
>>
>
>
>
> --
> *Marcus Ottosson*
> konstrukt...@gmail.com
>
> --
> You received this message because you are subscribed to the Google Groups
> "Python Programming for Autodesk Maya" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to python_inside_maya+unsubscr...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/
> msgid/python_inside_maya/CAFRtmOD02m%3DbffY2GhNbncgEs0OXp0iYeck_
> woAg9fATHt2PTA%40mail.gmail.com
> <https://groups.google.com/d/msgid/python_inside_maya/CAFRtmOD02m%3DbffY2GhNbncgEs0OXp0iYeck_woAg9fATHt2PTA%40mail.gmail.com?utm_medium=email&utm_source=footer>
> .
>
> For more options, visit https://groups.google.com/d/optout.
>



--

-- 
You received this message because you are subscribed to the Google Groups 
"Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to python_inside_maya+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/python_inside_maya/CAPaTLMTxrmjYe%2B%3Dt1f8C6AJO3KziSscq%3DYF4eMGQrwv%3DTy13AA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

Reply via email to