HDCharles/gist:2f15d2b383c4da9251a7245e58d3ac47

## gistfile1.py
import random
random.seed(0)
from collections import deque
import math
import time


### SET UP PROBLEM
l, h = 100,100000
delta = 10
tests = [
    [1000, 2],
    [1000, 4],
    [1000, 8],
    [1000, 16],
    [100000, 2],
    [100000, 4],
    [100000, 8],
    [100000, 16],
    [100000, 32],
    [1000000, 2],
    [1000000, 4],
    [1000000, 8],
    [1000000, 16],
]
deltas = []
for num_modules, num_devices in tests:
    print(f"running comparison with for mods={num_modules}, devs={num_devices}")
    avg_d = int(num_modules*1.25*(h+l)/2/num_devices+1)

    module_sizes = [0]
    device_sizes = [-1]

    while sum(module_sizes) > sum(device_sizes):
        module_sizes = [random.randint(l, h) for i in range(num_modules)]
        device_sizes = [random.randint(avg_d-delta, avg_d+delta) for i in range(num_devices)]

    ### SOLVE PROBLEM USING BINARY SEARCH
    s = time.time()

    def canallocate(module_sizes, device_sizes, target):
        i = 0
        for dev in device_sizes:
            filled = 0
            while i<len(module_sizes) and filled + module_sizes[i] <= dev - target:
                filled += module_sizes[i]
                i+=1
        return i==len(module_sizes)

    low, high = -1, min(device_sizes)
    while high - low > 1:
        mid = (low + high)//2
        if canallocate(module_sizes, device_sizes, mid):
            low = mid
        else:
            high = mid

    res = time.time()-s
    print(f" kylestuff took: {res}")

    s = time.time()

    ### SOLVE PROBLEM USING RIGHT SHIFTING AND SEGMENT TREE
    module_allocation = deque()
    i = 0
    for dev in device_sizes:
        module_allocation.append(deque())
        filled = 0
        while i<num_modules and filled + module_sizes[i] <= dev:
            module_allocation[-1].append(module_sizes[i])
            filled += module_sizes[i]
            i+=1

    device_space = [dev - sum(mods) for mods, dev in zip(module_allocation, device_sizes)]

    def update(tree, index, value):
        j = index + len(tree)//2
        tree[j] = [value, index]
        while j!=0:
            j = (j-1)//2
            tree[j] = min(tree[2*j+1], tree[2*j+2])

    def initialize(values):
        n = len(values)
        m = 2**(math.ceil(math.log2(n)))
        tree = [[]]*(2*n-1)
        for i in list(range(n))[::-1]:
            update(tree, i, values[i])
        return tree

    def moveright(module_allocation, tree, index):
        n = len(tree)//2
        module_allocation[index+1].appendleft(val:=module_allocation[index].pop())
        update(tree, index, tree[index + n][0] + val)
        update(tree, index+1, tree[n + index+1][0] - val)

    tree = initialize(device_space)

    best = -100
    allocation = list(module_allocation)
    while True:
        if tree[0][0] > best:
            best = tree[0][0]
            allocation = list(module_allocation)
        worst = tree[0][1]
        if worst == num_devices-1:
            break
        moveright(module_allocation, tree, worst)

    res2 = time.time()-s
    print(f" rightshift took: {res2}")
    deltas.append(res2-res)
print("deltas:", deltas)
	import random
	random.seed(0)
	from collections import deque
	import math
	import time


	### SET UP PROBLEM
	l, h = 100,100000
	delta = 10
	tests = [
	[1000, 2],
	[1000, 4],
	[1000, 8],
	[1000, 16],
	[100000, 2],
	[100000, 4],
	[100000, 8],
	[100000, 16],
	[100000, 32],
	[1000000, 2],
	[1000000, 4],
	[1000000, 8],
	[1000000, 16],
	]
	deltas = []
	for num_modules, num_devices in tests:
	print(f"running comparison with for mods={num_modules}, devs={num_devices}")
	avg_d = int(num_modules1.25(h+l)/2/num_devices+1)

	module_sizes = [0]
	device_sizes = [-1]

	while sum(module_sizes) > sum(device_sizes):
	module_sizes = [random.randint(l, h) for i in range(num_modules)]
	device_sizes = [random.randint(avg_d-delta, avg_d+delta) for i in range(num_devices)]

	### SOLVE PROBLEM USING BINARY SEARCH
	s = time.time()

	def canallocate(module_sizes, device_sizes, target):
	i = 0
	for dev in device_sizes:
	filled = 0
	while i<len(module_sizes) and filled + module_sizes[i] <= dev - target:
	filled += module_sizes[i]
	i+=1
	return i==len(module_sizes)

	low, high = -1, min(device_sizes)
	while high - low > 1:
	mid = (low + high)//2
	if canallocate(module_sizes, device_sizes, mid):
	low = mid
	else:
	high = mid

	res = time.time()-s
	print(f" kylestuff took: {res}")

	s = time.time()

	### SOLVE PROBLEM USING RIGHT SHIFTING AND SEGMENT TREE
	module_allocation = deque()
	i = 0
	for dev in device_sizes:
	module_allocation.append(deque())
	filled = 0
	while i<num_modules and filled + module_sizes[i] <= dev:
	module_allocation[-1].append(module_sizes[i])
	filled += module_sizes[i]
	i+=1

	device_space = [dev - sum(mods) for mods, dev in zip(module_allocation, device_sizes)]

	def update(tree, index, value):
	j = index + len(tree)//2
	tree[j] = [value, index]
	while j!=0:
	j = (j-1)//2
	tree[j] = min(tree[2j+1], tree[2j+2])

	def initialize(values):
	n = len(values)
	m = 2**(math.ceil(math.log2(n)))
	tree = [[]](2n-1)
	for i in list(range(n))[::-1]:
	update(tree, i, values[i])
	return tree

	def moveright(module_allocation, tree, index):
	n = len(tree)//2
	module_allocation[index+1].appendleft(val:=module_allocation[index].pop())
	update(tree, index, tree[index + n][0] + val)
	update(tree, index+1, tree[n + index+1][0] - val)

	tree = initialize(device_space)

	best = -100
	allocation = list(module_allocation)
	while True:
	if tree[0][0] > best:
	best = tree[0][0]
	allocation = list(module_allocation)
	worst = tree[0][1]
	if worst == num_devices-1:
	break
	moveright(module_allocation, tree, worst)

	res2 = time.time()-s
	print(f" rightshift took: {res2}")
	deltas.append(res2-res)
	print("deltas:", deltas)
No results found