Skip to content

Instantly share code, notes, and snippets.

@thewisenerd
Last active May 6, 2023 13:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save thewisenerd/9cb09cec3864e17cc493d6efbada8a19 to your computer and use it in GitHub Desktop.
Save thewisenerd/9cb09cec3864e17cc493d6efbada8a19 to your computer and use it in GitHub Desktop.
repeatable assignment or something idk what i'm doing (also solution wrong)
import math
# https://gist.github.com/cincodenada/6557582
def rotr(num, bits):
num &= (2 ** bits - 1)
bit = num & 1
num >>= 1
if (bit):
num |= (1 << (bits - 1))
return num
def job_mask(job_count: int,
worker_idx: int,
worker_count: int) -> range:
worker_bits = math.ceil(math.log2(worker_count))
worker_idx = rotr(worker_idx, worker_bits)
job_bits = math.ceil(math.log2(job_count))
mask_worker = worker_idx << (job_bits - worker_bits)
mask_jobs = int(math.pow(2, job_bits - worker_bits)) - 1
return range(mask_worker, (mask_worker | mask_jobs) + 1)
jobs = list(range(0, 128))
if __name__ == '__main__':
for wc in [1, 2, 4, 8, 16, 32]:
print(f'wc={wc}')
for worker_idx in range(0, wc):
jr = job_mask(len(jobs), worker_idx, wc)
assigned = []
for j in range(0, len(jobs)):
if j in jr:
assigned.append(j)
print('%02d' % worker_idx, ['%03d' % x for x in assigned])
print('---')
- number of workers may increase or decrease
- assume number of workers either double or half (powers of two)
- assume len(jobs) to be constant
- fn(worker_idx, worker_count) output is repeatable
- fn(k, m) is a superset of fn(k, m+1)
caveats:
- why do workers need to increment or decrement in powers of two? can a generalised fn be achieved?
example,
wc=1
00 ['000', '001', '002', '003', '004', '005', '006', '007', '008', '009', '010', '011', '012', '013', '014', '015', '016', '017', '018', '019', '020', '021', '022', '023', '024', '025', '026', '027', '028', '029', '030', '031', '032', '033', '034', '035', '036', '037', '038', '039', '040', '041', '042', '043', '044', '045', '046', '047', '048', '049', '050', '051', '052', '053', '054', '055', '056', '057', '058', '059', '060', '061', '062', '063', '064', '065', '066', '067', '068', '069', '070', '071', '072', '073', '074', '075', '076', '077', '078', '079', '080', '081', '082', '083', '084', '085', '086', '087', '088', '089', '090', '091', '092', '093', '094', '095', '096', '097', '098', '099', '100', '101', '102', '103', '104', '105', '106', '107', '108', '109', '110', '111', '112', '113', '114', '115', '116', '117', '118', '119', '120', '121', '122', '123', '124', '125', '126', '127']
---
wc=2
00 ['000', '001', '002', '003', '004', '005', '006', '007', '008', '009', '010', '011', '012', '013', '014', '015', '016', '017', '018', '019', '020', '021', '022', '023', '024', '025', '026', '027', '028', '029', '030', '031', '032', '033', '034', '035', '036', '037', '038', '039', '040', '041', '042', '043', '044', '045', '046', '047', '048', '049', '050', '051', '052', '053', '054', '055', '056', '057', '058', '059', '060', '061', '062', '063']
01 ['064', '065', '066', '067', '068', '069', '070', '071', '072', '073', '074', '075', '076', '077', '078', '079', '080', '081', '082', '083', '084', '085', '086', '087', '088', '089', '090', '091', '092', '093', '094', '095', '096', '097', '098', '099', '100', '101', '102', '103', '104', '105', '106', '107', '108', '109', '110', '111', '112', '113', '114', '115', '116', '117', '118', '119', '120', '121', '122', '123', '124', '125', '126', '127']
---
wc=4
00 ['000', '001', '002', '003', '004', '005', '006', '007', '008', '009', '010', '011', '012', '013', '014', '015', '016', '017', '018', '019', '020', '021', '022', '023', '024', '025', '026', '027', '028', '029', '030', '031']
01 ['064', '065', '066', '067', '068', '069', '070', '071', '072', '073', '074', '075', '076', '077', '078', '079', '080', '081', '082', '083', '084', '085', '086', '087', '088', '089', '090', '091', '092', '093', '094', '095']
02 ['032', '033', '034', '035', '036', '037', '038', '039', '040', '041', '042', '043', '044', '045', '046', '047', '048', '049', '050', '051', '052', '053', '054', '055', '056', '057', '058', '059', '060', '061', '062', '063']
03 ['096', '097', '098', '099', '100', '101', '102', '103', '104', '105', '106', '107', '108', '109', '110', '111', '112', '113', '114', '115', '116', '117', '118', '119', '120', '121', '122', '123', '124', '125', '126', '127']
---
wc=8
00 ['000', '001', '002', '003', '004', '005', '006', '007', '008', '009', '010', '011', '012', '013', '014', '015']
01 ['064', '065', '066', '067', '068', '069', '070', '071', '072', '073', '074', '075', '076', '077', '078', '079']
02 ['016', '017', '018', '019', '020', '021', '022', '023', '024', '025', '026', '027', '028', '029', '030', '031']
03 ['080', '081', '082', '083', '084', '085', '086', '087', '088', '089', '090', '091', '092', '093', '094', '095']
04 ['032', '033', '034', '035', '036', '037', '038', '039', '040', '041', '042', '043', '044', '045', '046', '047']
05 ['096', '097', '098', '099', '100', '101', '102', '103', '104', '105', '106', '107', '108', '109', '110', '111']
06 ['048', '049', '050', '051', '052', '053', '054', '055', '056', '057', '058', '059', '060', '061', '062', '063']
07 ['112', '113', '114', '115', '116', '117', '118', '119', '120', '121', '122', '123', '124', '125', '126', '127']
---
wc=16
00 ['000', '001', '002', '003', '004', '005', '006', '007']
01 ['064', '065', '066', '067', '068', '069', '070', '071']
02 ['008', '009', '010', '011', '012', '013', '014', '015']
03 ['072', '073', '074', '075', '076', '077', '078', '079']
04 ['016', '017', '018', '019', '020', '021', '022', '023']
05 ['080', '081', '082', '083', '084', '085', '086', '087']
06 ['024', '025', '026', '027', '028', '029', '030', '031']
07 ['088', '089', '090', '091', '092', '093', '094', '095']
08 ['032', '033', '034', '035', '036', '037', '038', '039']
09 ['096', '097', '098', '099', '100', '101', '102', '103']
10 ['040', '041', '042', '043', '044', '045', '046', '047']
11 ['104', '105', '106', '107', '108', '109', '110', '111']
12 ['048', '049', '050', '051', '052', '053', '054', '055']
13 ['112', '113', '114', '115', '116', '117', '118', '119']
14 ['056', '057', '058', '059', '060', '061', '062', '063']
15 ['120', '121', '122', '123', '124', '125', '126', '127']
---
wc=32
00 ['000', '001', '002', '003']
01 ['064', '065', '066', '067']
02 ['004', '005', '006', '007']
03 ['068', '069', '070', '071']
04 ['008', '009', '010', '011']
05 ['072', '073', '074', '075']
06 ['012', '013', '014', '015']
07 ['076', '077', '078', '079']
08 ['016', '017', '018', '019']
09 ['080', '081', '082', '083']
10 ['020', '021', '022', '023']
11 ['084', '085', '086', '087']
12 ['024', '025', '026', '027']
13 ['088', '089', '090', '091']
14 ['028', '029', '030', '031']
15 ['092', '093', '094', '095']
16 ['032', '033', '034', '035']
17 ['096', '097', '098', '099']
18 ['036', '037', '038', '039']
19 ['100', '101', '102', '103']
20 ['040', '041', '042', '043']
21 ['104', '105', '106', '107']
22 ['044', '045', '046', '047']
23 ['108', '109', '110', '111']
24 ['048', '049', '050', '051']
25 ['112', '113', '114', '115']
26 ['052', '053', '054', '055']
27 ['116', '117', '118', '119']
28 ['056', '057', '058', '059']
29 ['120', '121', '122', '123']
30 ['060', '061', '062', '063']
31 ['124', '125', '126', '127']
---
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment