Spinlock

In [303]:

    

from tqdm import tqdm
import numpy as np

def next_head(head, n, key):
    return ((head + key) % n) + 1

def next_lock(lock, head, n, key):
    new_head = next_head(head, n, key)
    return lock[:new_head] + [n] + lock[new_head:], new_head

def spinlock(key, iters):
    lock, head = [0], 0
    for i in range(iters):
        lock, head = next_lock(lock, head, i + 1, key)
    return lock

def first_index_next(key, target):
    lock = spinlock(key, target)
    index = lock.index(target)
    return index, lock[index + 1]


    

In [304]:

    

first_index_next(3, 1)


    

    
Out[304]:





(28, 28)

In [218]:

    

%%time
lock = spinlock(3, 2017)
index = lock.index(2017)
assert(lock[index - 3: index + 4] == [1512, 1134, 151, 2017, 638, 1513, 851])


    

    




CPU times: user 28 ms, sys: 8 ms, total: 36 ms
Wall time: 35.2 ms

In [222]:

    

key = 301
target = 2017
index, next_to_target = first_index_next(key, target)
print('index of target = {0}\nvalue next to target = {1}'.format(index, next_to_target))


    

    




index of target = 567
value next to target = 1642

In [311]:

    

def neighbor_right_zero(key, iters):
    index, neighbor = 0, 1
    head = 0
    for i in range(iters):
        head = next_head(head, i + 1, key)
        if head <= index:
            index += 1
        elif head == index + 1:
            neighbor = i + 1
    return neighbor


    

In [309]:

    

lock = spinlock(3, 5 * 10 ** 4)
index = lock.index(0)
lock[index: index + 2]


    

    
Out[309]:





[0, 38713]

In [313]:

    

neighbor_right_zero(3, 5 * 10 ** 4)


    

    
Out[313]:





38713

In [314]:

    

lock = spinlock(3, 20000)
index = lock.index(0)
lock[index: index + 2]


    

    
Out[314]:





[0, 16332]

In [316]:

    

neighbor_right_zero(3, 20000)


    

    
Out[316]:





16332

In [318]:

    

key = 301
neighbor_right_zero(key, 50 * 10 ** 6)


    

    
Out[318]:





33601318