how to space points on a ring

At work, I had to place some points on a network ring such that each point was maximally distanced from all the other points. However, only some of the locations on the ring were active at any one time. For those that were active, I wanted them to be maximally distanced from all the other nodes. And when I incrementally add the next point, it should always minimize the separation from other nodes and reduce the clustering of nodes, while leaving room for new nodes to be incrementally spaced. This is all very confusing, but I'm writing this blog post so I don't lose this code. When I google'd, I couldn't find any implementation that I could just use, so I want to post my code.

To give a more concrete example, say you have the face of a clock. The first node you chose has no-one to contend with, so you arbitrarily choose node 12 and you're maximally spaced and have minimal clustering. Next, if you were to "pick" another node such that it was maximally distanced from 12, you'd choose 6. The next node code be either 9 o'clock or 3 o'clock ( let's say you always choose in the clockwise direction from the last node that you picked). Thus you choose 9. The next node that will be maximally distanced from the other nodes is 3. Next you'll choose 4:30, because it is half-way between 3 and 6 ( and clockwise from the last picked node). Then you pick 10:30 (not 7:30, because you also want to reduce clustering of nodes). Then 1:30, and then 7:30.

Thus the sequence of points is:

12,6,9,3,4:30,10:30,1:30,7:30

The trick to the algorithm is that if you look at the spacing between the nodes as a fraction of the total clock that you have to travel to get to the next node, you'll get the sequence:

time	iteration	fraction of clock to next node
12	0	Not Applicable
6	1	1/2
9	2	1/4
3	3	1/2
4:30	4	1/8
10:30	5	1/2
1:30	6	1/4
7:30	7	1/2

The relationship between the iteration number and the divisor for the fraction of the clock to the next node is to find the biggest power of 2 that divides evenly into the iteration number and multiply that number by 2.

If you were to extend this algorithm to incrementally evenly space 16 nodes that relationship still holds. I believe that relationship would continue to hold beyond 16 nodes, but that is just my intuition.

Soo.. going on that intuition, the following python code does satisfy my needs to incrementally space nodes on a ring.

size = 64
desired_slots = 16
initial_pos = 0
cur_pos = initial_pos
bin_spaced_slots = [cur_pos]
for slot_num in xrange(1,desired_slots):
    # find the largest power of 2 that evenly divides into 
    # slot_num and then it by 2 to get the phase shift for
    # the placement of the slot
    max_pow2_divisor = 1
    while slot_num % max_pow2_divisor == 0:
        max_pow2_divisor *= 2
    cur_pos = (cur_pos + size/max_pow2_divisor)%size
    bin_spaced_slots.append(cur_pos)
print bin_spaced_slots

How to get rid of runit and runit-run when it causes your boot to stall

I tried installing runit and runit-run on Ubuntu 8.04. They installed just fine, but my boot stalled after the first restart. It stopped at something like "keyboard mapping" and just hung indefinitely. I tried to reboot into Ubuntu's "recovery mode" so I could remove the runit and runit-run packages, but I couldn't get to a console to type in the "apt-get remove" command. I was working on burning a new copy of Ubuntu to do a re-install. While I was waiting for the Ubuntu CD, I was reading "Embedded Linux Primer" and I came to the section about kernel command line arguments. You can tell Linux which file to use for the 'init' process. It turns out that package runit-run moves the old init to /sbin/init.sysv ( or maybe that file was already there and simply hard-linked ). All you need to do is tell the kernel to use /sbin/init.sysv instead of /sbin/init at boot time. Once I did that, I was able to do a normal boot, and nuke runit and runit-run.

Here's how to use the normal sysv init:

• Start or reboot your machine
• Interrupt the Grub bootloader by hitting the up or down key. That's the program which lets you select between different kernels versions and Windows XP (if you're hard core and you don't have a dual-boot machine, then you're probably not reading this post anyway because you weren't stupid enough to do what I did)
• Select the kernel at the top of your screen
• Type 'e' to edit the kernel command line
• select the kernel command line from this new window
• go to the end of the line and enter
• init=/sbin/init.sysv
• hit 'b' to boot with your modified command line arguments
• when it goes through the boot process, remove runit and runit-run:
• sudo apt-get remove runit runit-run

More kernel command lines may be found at:
www.kernel.org/pub/linux/kernel/people/gregkh/lkn/lkn_pdf/ch09.pdf

How to decorate __init__ or another python class method

I want to decorate a class' __init__ method to magically attach my own instance members to the object being __init__'d and then do something else at the end of the __init__ call. So I need to be able to access to the original __init__'s 'self' reference.

I want code that looks like:

class Foo:
 @my_decorator
 def __init__(self,arg1, arg2):
   self.arg1 = arg1
   self.arg2 = arg2

To magically transform into something like:

class Foo:
  def __init__(self,arg1, arg2):
      #entrypoint
      self.instance_member_inserted_by_decorator = 1       

      self.arg1 = arg1
      self.arg2 = arg2

      #exitpoint
      print "I'm dancing on your mother's grave"

The tricky part of this is writing a decorator such that you can access the 'self' of the object being created. My first implementation looked like this:

class Dec:
       def __init__(self,f):
           self.f = f
       def __call__(self):
           print 'Entry point in decorator'
           self.f(self)
           print 'Exit point in decorator'
  
   class Foo:
       @Dec
       def __init__(self):
           print '    in originalFoo.__init__'
           print '    self.__class__.__name__ ==',self.__class__.__name__
           self.var1 = 'var1'
  
f = Foo()
print "f.__class__.__name__ ==",f.__class__.__name__
print "f.__init__.__class__.__name__ ==",f.__init__.__class__.__name__
print 'f.__dict__.has_key("var1") == ',f.__dict__.has_key("var1")

This prints:

Entry point in decorator
   in originalFoo.__init__
   self.__class__.__name__ == Dec
Exit point in decorator
f.__class__.__name__ == Foo
f.__init__.__class__.__name__ == Dec
f.__dict__.has_key("var1") ==  False

That implementation edits the Dec object instead of the Foo object. It also screws up the original __init__ call so that it doesn't initialize the Foo object at all!

In order to wrapper the __init__ call, you need to use decorators with arguments. This will give you access to the intended self object:

class Dec:   
    def __call__(self,f):
        def wrap(init_self,*args,**kwargs):
            print 'Entry point in decorator'
            init_self.inserted_during_decoration = 1
            f(init_self,*args,**kwargs)
            print 'Exit point in decorator'
        return wrap

class Foo:
    @Dec()
    def __init__(self,var1):
        print '    in originalFoo.__init__'
        print '    self.__class__.__name__ ==',self.__class__.__name__
        self.var1 = var1

f = Foo('my_var1')
print "f.__class__.__name__ ==",f.__class__.__name__
print "f.__init__.__class__.__name__ ==",f.__init__.__class__.__name__
print 'f.__dict__.has_key("var1") == ',f.__dict__.has_key("var1")
print 'f.inserted_during_decoration ==',f.inserted_during_decoration

This prints out:'

Entry point in decorator
    in originalFoo.__init__
    self.__class__.__name__ == Foo
Exit point in decorator
f.__class__.__name__ == Foo
f.__init__.__class__.__name__ == instancemethod
f.__dict__.has_key("var1") ==  True
f.inserted_during_decoration == 1

using 'helper' is a cop out

What's the alternative to a helper function? Why would you insert "helper" in to a function name or variable name? Do people write un-"helpful" functions or variables? "helper" seems to imply some sort of slave variable that only minimally contributes to the goal of a piece of code. A "helper" function returns some intermediate step in the guts of a steaming pile of code. Why not name the function/variable according to what it actually does and omit the useless adjective? Or if you're too lazy, just omit the useless clutter of "helper_" -- we already assume that you wouldn't intentionally write unhelpful variable names or function names.