Как можно улучшить метод, который оценивает список, чтобы определить, содержит ли он определенные последовательные элементы? - PullRequest
Новая
       26

Как можно улучшить метод, который оценивает список, чтобы определить, содержит ли он определенные последовательные элементы?

1 голос
/ 26 марта 2019

У меня есть вложенный список из десятков миллионов списков (я также могу использовать кортежи).Каждый список состоит из 2-7 пунктов.Каждый элемент в списке представляет собой строку из 1-5 символов и встречается не более одного раза в списке.(Я использую отдельные символы в моем примере ниже для простоты) 

#Example nestedList: 

nestedList = [
    ['a', 'e', 'O', 'I', 'g', 's'],
    ['w', 'I', 'u', 'O', 's', 'g'],
    ['e', 'z', 's', 'I', 'O', 'g']
]

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

Я использую следующую функцию, но она кажется довольно медленной, и я просто знаю, что должен быть более разумный способ сделать это. 

def isBadInList(bad, checkThisList):
    numChecks = len(list) - 1
    for x in range(numChecks):
        if checkThisList[x] == bad[0] and checkThisList[x + 1] == bad[1]:
            return True
        elif checkThisList[x] == bad[1] and checkThisList[x + 1] == bad[0]:
            return True
    return False

Я сделаю это, 

bad = ['O', 'I']

for checkThisList in nestedLists:
    result = isBadInList(bad, checkThisList)
    if result:
        doStuffToList(checkThisList)

#The function isBadInList() only returns true for the first and third list in nestedList and false for all else.

Мне нужен способ сделать это быстрее, если это возможно.Я могу использовать кортежи вместо списков или что угодно.

Ответы [ 2 ]

0 голосов
/ 26 марта 2019

Я думаю, что вы могли бы использовать некоторые regex здесь, чтобы ускорить это, хотя это все равно будет последовательная операция, так что ваш лучший вариант - O(n), использующий этот подход, поскольку вам приходится перебирать каждый список, однако, поскольку мы имеемитерации по каждому подсписку, что сделало бы его O(n^2). 

import re

p = re.compile('[OI]{2}|[IO]{2}') # match only OI or IO

def is_bad(pattern, to_check): 
    for item in to_check:
        maybe_found = pattern.search(''.join(item))
        if maybe_found:
            yield True
        else:
            yield False


l = list(is_bad(p, nestedList))

print(l)
# [True, False, True]
0 голосов
/ 26 марта 2019 
nestedList = [
    ['a', 'e', 'O', 'I', 'g', 's'],
    ['w', 'I', 'u', 'O', 's', 'g'],
    ['e', 'z', 's', 'I', 'O', 'g']
]

#first create a map
pairdict = dict()


for i in range(len(nestedList)):
    for j in range(len(nestedList[i])-1):
        pair1 = (nestedList[i][j],nestedList[i][j+1])
        if pair1 in pairdict:
            pairdict[pair1].append(i+1)
        else:
            pairdict[pair1] = [i+1]
        pair2 = (nestedList[i][j+1],nestedList[i][j])
        if pair2 in pairdict:
            pairdict[pair2].append(i+1)
        else:
            pairdict[pair2] = [i+1]

del nestedList

print(pairdict.get(('e','z'),None))

создайте пару значений и сохраните их в карту, ключ - пара, значение - индекс, а затем удалите ваш список (это может занять слишком много памяти), а затем вы можете воспользоваться диктом дляпосмотрите вверх и распечатайте индексы, где появляется значение.

...