Проверка информации в наборе данных в Python

В настоящее время у меня есть требование провести сравнение строк, содержащих MAC-адреса (например, «11: 22: 33: AA: BB: CC» с использованием Python 2.7. В настоящее время у меня есть предварительно настроенный набор, содержащий MAC-адрес, и мой сценарий повторяет через набор, сравнивающий каждый новый MAC-адрес с указанными в списке. Это отлично работает, но по мере роста набора скрипт сильно замедляется. Имея всего 100 или около того, вы можете заметить огромную разницу.

Есть ли у кого-нибудь советы по ускорению этого процесса? Является ли их хранение в наборе лучшим способом для сравнения или лучше, например, хранить их в CSV / DB?

Пример кода ...

def Detect(p): 
    stamgmtstypes = (0,2,4)
    if p.haslayer(Dot11):
        if p.type == 0 and p.subtype in stamgmtstypes:
            if p.addr2 not in observedclients: 
                # This is the set with location_mutex: 
                detection = p.addr2 + "\t" + str(datetime.now())
                print type(p.addr2)
                print detection, last_location
                observedclients.append(p.addr2)

python list performance iteration scapy
person thefragileomen    schedule 21.10.2011    source источник
comment
Извинения, Авасал - я имел в виду «набор» - исходное сообщение изменено. Прости!   -  person thefragileomen    schedule 21.10.2011
comment
вы можете преобразовать список в набор, это устранит дубликаты .. (удалите исходный комментарий по ошибке)   -  person avasal    schedule 21.10.2011
comment
observedclients тот, который предполагается набором? Что ж, судя по тому, что вы показываете, это список, а не набор. В наборах нет .append метода. Добавляешь в наборы с .add.   -  person Avaris    schedule 21.10.2011
comment
Наблюдаемые клиенты - это действительно набор (по крайней мере, я так считал). Я объявил это как Observableclients = [] в начале моего кода. Может быть, тогда в этом моя проблема? Теперь я предполагаю, что я должен был объявить свой набор как наблюдаемый = [], а затем наблюдать клиентов = набор (наблюдаемый)?   -  person thefragileomen    schedule 21.10.2011
comment
Что ж, [] создает список. Вам нужно set(), чтобы создать его. И вы добавляете к нему observedclients.add(p.addr2). Это может улучшить производительность.   -  person Avaris    schedule 21.10.2011
comment
вы проверили список / набор .__ содержит метод __ (элемент),   -  person avasal    schedule 21.10.2011

Ответы (3)


arrow_upward
1
arrow_downward

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

Кроме того, в качестве общей рекомендации рассмотрите Psyco, хотя бывает несколько раз когда psyco не помогает

Если вы обнаружите узкое место, cython может оказаться полезным, но вы должны быть уверены, что объявили все свои переменные в исходный код cython.

person This    schedule 21.10.2011
comment
Спасибо, Майк. Я предположил, что узким местом был просто размер списка MAC-адресов. Как уже говорилось, он отлично работает только с небольшим количеством MAC-адресов, но по мере увеличения размера списка скрипт замедляется. Я полагаю, что мне следует иметь в виду правило - никогда не делать предположений! - person thefragileomen; 21.10.2011
comment
@thefragileomen, как долго ваш сценарий? - person This; 21.10.2011
comment
Майк, это всего около 100 строк с 5 функциями. Функция, которая, как мне кажется, вызывает проблемы, состоит всего из нескольких строк, но в ней есть несколько вложенных функций if. Я отредактировал свой основной вопрос, указав его в - person thefragileomen; 21.10.2011
comment
@thefragileomen, похоже, вы используете scapy, верно? scapy - это чистый питон, и в результате он становится довольно медленным ... некоторые другие библиотеки для передачи пакетов (например, ПК) разгрузите работу с cython для вас ... так что это может помочь в вашей ситуации ... Я не могу сказать наверняка - person This; 21.10.2011

arrow_upward
0
arrow_downward

Попробуйте использовать set. Чтобы объявить набор, используйте set(), а не [] (потому что последний объявляет пустой list).

Поиск в list имеет O(n) сложность. Это то, что происходит в вашем случае, когда список растет (сложность растет с ростом n как O(n)).

Поиск в set в среднем имеет O(1) сложность.

http://wiki.python.org/moin/TimeComplexity

Также вам нужно будет изменить некоторую часть вашего кода. В set нет метода append, поэтому вам нужно будет использовать что-то вроде observedclients.add(address).

person ovgolovin    schedule 21.10.2011
comment
овголовин, извиняюсь - ошибка в моем исходном посте. Я имел в виду «набор», а не «список». Я уже использую набор, а НЕ список, но все еще испытываю ту же проблему. - person thefragileomen; 21.10.2011
comment
@thefragileomen Очень странно, потому что, если размер набора растет, это не должно увеличивать сложность алгоритма (поскольку сложность равна O(1) и не зависит от размера set). - person ovgolovin; 21.10.2011

arrow_upward
0
arrow_downward

В сообщении упоминается, что «сценарий выполняет итерацию по набору, сравнивая каждый новый MAC-адрес с адресами в списке».

Чтобы воспользоваться всеми преимуществами наборов, не зацикливайтесь на них, сравнивая одно за другим. Вместо этого используйте такие операции набора, как union (), correction () и difference ():

s = set(list_of_strings_containing_mac_addresses)
t = set(preconfigured_set_of_mac_addresses)
print s - t, 'addresses in the list but not preconfigured'
person Raymond Hettinger    schedule 21.10.2011