Найти динамическим питоническим способом минимальные элементы в частично упорядоченном множестве

Question

Пусть Os будет частично упорядоченным множеством, и с учетом любых двух объектов O1 и O2 в Os, F (O1, O2) вернет 1, если O1 больше, чем O2, -1, если O1 меньше, чем O2, 2, если онинесравнимы, и 0, если O1 равно O2.

Мне нужно найти подмножество Mn элементов, это Os, которые являются минимальными.То есть для каждого A в Mn, и для каждого B в Os, F (A, B) никогда не равно 1.

Это не сложно, но я уверен, что это можно сделать вболее питонический путь.

Быстрый и грязный способ:

def GetMinOs(Os):
    Mn=set([])
    NotMn=set([])
    for O1 in Os:
       for O2 in Os:
           rel=f(O1,O2)
           if rel==1:       NotMn|=set([O1])
           elif rel==-1:    NotMn|=set([O2])
    Mn=Os-NotMn
    return Mn

В частности, я не доволен тем фактом, что по сути я прохожу все элементы N ^ 2 раза.Интересно, может ли быть динамичный путь?Под «динамическим» я подразумеваю не просто быстрое, но также и такое, что как только что-то обнаруживается, что невозможно в минимуме, возможно, его можно снять.И все это делает pythonic , элегантный способ

Answer 1

GetMinOs2 ниже, «динамически» удаляет элементы, которые, как известно, не являются минимальными.Он использует список Ol, который начинается со всех элементов Os.Индекс «указатель» l указывает на «конец» списка Ol.Когда найден неминимальный элемент, его позиция меняется на значение в Ol[l], а указатель l уменьшается, поэтому эффективная длина Ol уменьшается.При этом удаляются неминимальные элементы, поэтому вы не проверяете их снова.

GetMinOs2 предполагает, что f имеет обычные свойства функции сравнения: транзитивность, коммутативность и т. Д.

В приведенном ниже тестовом коде со сновидением f, мойЗапуск timeit показывает увеличение скорости в 54 раза:

def f(O1,O2):
    if O1%4==3 or O2%4==3: return 2
    return cmp(O1,O2)

def GetMinOs(Os):
    Mn=set([])
    NotMn=set([])
    for O1 in Os:
       for O2 in Os:
           rel=f(O1,O2)
           if rel==1:       NotMn|=set([O1])
           elif rel==-1:    NotMn|=set([O2])
    Mn=Os-NotMn
    return Mn

def GetMinOs2(Os):
    Ol=list(Os)
    l=len(Ol)
    i=0
    j=1
    while i<l:
        while j<l:
            rel=f(Ol[i],Ol[j])
            if rel==1:
                l-=1
                Ol[i]=Ol[l]
                j=i+1
                break
            elif rel==-1:
                l-=1
                Ol[j]=Ol[l]
            else:
                j+=1
        else:
            i+=1
            j=i+1
    return set(Ol[:l])


Os=set(range(1000))

if __name__=='__main__':
    answer=GetMinOs(Os)
    result=GetMinOs2(Os)
    assert answer==result

Результаты timeit:

% python -mtimeit -s'import test' 'test.GetMinOs2(test.Os)'
1000 loops, best of 3: 22.7 msec per loop
% python -mtimeit -s'import test' 'test.GetMinOs(test.Os)'
10 loops, best of 3: 1.23 sec per loop

PS.Пожалуйста, обратите внимание: я не проверил полностью алгоритм в GetMinOs2, но я думаю, что общая идея верна.Я поставил небольшой тест в конце скрипта, который показывает, что он работает, по крайней мере, на примере данных set(range(1000)).