выбор самой ранней записи в списке, которая также удовлетворяет другим критериям

Question

Скажем, у меня есть список L1, а записи в L1 состоят из 4 частей и имеют такой формат cat1, cat2, date, ID.Список отсортирован в алфавитном порядке по записям cat1, затем по алфавиту по записям cat2, затем по самым ранним date.Я хочу подмножество этого списка, которое содержит запись с самой ранней датой для каждой пары cat1, cat2.Вот код, который у меня уже есть:

L1=[A, X, 2008-06-01, 1858
A, X, 2008-12-05, 1905
B, X, 2001-08-08, 1149
B, Y, 2006-03-05, 1638
B, Y, 2009-06-09, 1950
C, X, 2005-12-01, 1611
C, X, 2006-08-08, 1689
C, X, 2006-11-22, 1712
C, X, 2008-04-22, 1842
C, Y, 2008-12-05, 1816
C, Y, 2008-12-05, 1821
C, Y, 2008-12-05, 1882
C, Z, 2008-12-05, 1905
C, Z, 2009-06-01, 1935
C, Z, 2009-06-09, 1950
D, X, 2009-11-06, 1989
D, Y, 2008-12-05, 1905
D, Z, 2008-12-05, 1905
D, Z, 2008-12-05, 1905
E, X, 2008-12-05, 1905
E, Z, 2008-12-05, 1905
F, Y, 2008-12-05, 1905
G, X, 2008-12-05, 1905
G, Z, 2007-12-01, 1807]

L2=[j.next() for i, j in itertools.groupby(L1, lambda x: x.split(",", 2)[:2])]

L2=[A, X, 2008-06-01, 1858
B, X, 2001-08-08, 1149
B, Y, 2006-03-05, 1638
C, X, 2005-12-01, 1611
C, Y, 2008-12-05, 1816
C, Z, 2008-12-05, 1905
D, X, 2009-11-06, 1989
D, Y, 2008-12-05, 1905
D, Z, 2008-12-05, 1905
E, X, 2008-12-05, 1905
E, Z, 2008-12-05, 1905
F, Y, 2008-12-05, 1905
G, X, 2008-12-05, 1905
G, Z, 2007-12-01, 1807]

Хитрость в том, что я хочу получить самую раннюю запись для каждой пары cat1, cat2, где ID находится в списке значений в <= 3 ключа в <code>dict1 И dict2.Другими словами, как только самая ранняя запись для пары cat1, cat2 найдена, она должна быть проверена в каждом dict1 и dict2, и, если найдено, что ID содержится в списке значений для 4+ клавиш любого изсловарь, он должен перейти к следующей самой ранней записи для этой пары cat1, cat2, и для добавления записи в L2 ее ID должно быть в 3 или менее ключах как dict1, так и dict2.Я не совсем уверен, как это сделать ... может быть, использовать re.search или что-то?

dict1[key]=[ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID]    
dict2[key]=[ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID,ID]

, поэтому вместо L2, имеющего только самую раннюю запись для пары cat1, cat2, она будет содержать самую раннюю запись, где ID из этой записи не входит в список ID в 4+ клавишахв обоих dict1 И dict2.

Answer 1

Если списки значений dict1 и dict2 не слишком велики, вы можете сначала сгенерировать набор всех допустимых идентификаторов, а затем отфильтровать L1, чтобы он содержал только те кортежи (X, Y, дата, ID), чьи Идентификаторы находятся в наборе идентификаторов значений:

import collections
def valid_ids(*dcts):
    valid=collections.defaultdict(int)
    for dct in dcts:
        for key,value in dct.iteritems():
            valid[value]+=1
    return set(value for value,count in valid.iteritems() if count<=3)

ids=valid_ids(dict1,dict2)

L1_filtered=[text.split(',') for text in L1 if text.split(',')[-1].strip() in ids]
L2 = [j.next() for i, j in itertools.groupby(L1_filtered, lambda x: x.split(",", 2)[:2])]

Обратите внимание, что если dict1 и dict2 имеют списки значений с огромным количеством идентификаторов, то описанный выше метод не идеален, потому что вы тратите много времени на определение набора идентификаторов значений при формировании L2 вам может понадобиться только немного этих данных.

---

Используя идею Хью Ботвелла , если dict1 и dict2 имеют большие списки значений, то стоит просто проверить, действительны ли определенные идентификаторы при необходимости:

def is_valid(ID,*dcts):    
    return sum(1 for dct in dcts
               for key,value in dct.iteritems()
               if ID in value) <= 3       

L2=[]
for key, group in itertools.groupby(L1, lambda x: x.split(",", 2)[:2]):
    for text in group:
        X,Y,date,ID = text.split(',')
        X = X.strip()
        Y = Y.strip()
        date = date.strip()
        ID = ID.strip()
        if is_valid(ID,dict1,dict2):
            L2.append(X,Y,date,ID)
            break
    else:
        # There is no valid ID for this group!
        continue

---

Обратите внимание, что если вы используете первый метод, с valid_ids, вы проходите через диктовку только один раз. Если вы используете второй метод, вы будете проходить через диктовки как минимум один раз для каждой группы (уникальные пары X и Y) и, возможно, несколько раз для каждой группы.

Я предполагаю, что первый метод будет быстрее для большинства наборов данных, но профилирование обоих методов с вашими реальными данными, вероятно, самый безопасный способ сказать.

Answer 2

Я думаю, вам нужно что-то вроде

L2 = []
for xy,rem in itertools.groupby(L1, lambda x: x.split(",", 2)[:2]):
    for s in rem:
        date,id = s.split(",")
        if TEST_ID(id):
            L2.append(s)
            break