Skip to content

Instantly share code, notes, and snippets.

@Derinhelm
Last active Jan 6, 2021
Embed
What would you like to do?
Реализация алгоритма MROC3. Статья "MROC3 - не магия, а справедливое слияние очередей" находится по ссылке https://drive.google.com/file/d/1MeunpCBtUdlfEtXxLqAcidjloVCPHtoJ/view?usp=sharing
Cls_parents, Calc_linear = {}, {}
def not_in_tail(elem, queue):
return elem == queue[0] or elem not in queue #или в начале очереди, или не стоит в ней
def create_queues(parents):
if not parents: return []
queues = []
for parent in parents:
new_queue = Calc_linear[parent].copy()
queues.append(new_queue)
queues.append(parents)
return queues
def delete_from_queues(cls_to_del, queues):
for q in queues:
if q and q[0] == cls_to_del:
del q[0]
return list(filter(len, queues))
def merge(parents):
queues = create_queues(parents)
precedence_order = []
while queues:
for queue in queues:
next_class = queue[0]
if all(not_in_tail(next_class, q) for q in queues):
precedence_order.append(next_class)
queues = delete_from_queues(next_class, queues)
break
else:
raise TypeError # нельзя построить линеаризацию
return precedence_order
def linearize(new_class, parents):
return [new_class, *merge(parents)]
from collections import Counter
Cls_parents, Calc_linear = {}, {}
def create_queues(parents):
if not parents: return []
queues = []
for parent in parents:
new_queue = Calc_linear[parent].copy()
queues.append(new_queue)
queues.append(parents)
return queues
def create_tail_stat(queues):
tail_statistics = Counter()
for queue in queues:
new_stat = Counter(queue)
new_stat[queue[0]] -= 1 # статистика, сколько раз класс в хвосте
tail_statistics += new_stat
return tail_statistics
def delete(cls_to_del, queues, tail):
for q in queues:
if q and q[0] == cls_to_del:
del q[0]
if q:
tail[q[0]] -= 1 # следующий класс стал головой списка
return list(filter(len, queues))
def merge(parents):
queues = create_queues(parents)
tail_statistics = create_tail_stat(queues)
precedence_order = []
while queues:
for queue in queues:
next_class = queue[0]
if tail_statistics[next_class] == 0: # нет в хвосте
precedence_order.append(next_class)
queues = delete(next_class, queues, tail_statistics)
break
else:
raise TypeError # нельзя построить линеаризацию
return precedence_order
def linearize(new_class, parents):
return [new_class, *merge(parents)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment