Перебор в Python: есть ли способ ускорить?

Question

[JRazor]

Нужно организовать перебор в Python, но при проверке большого количества информации он выполняется слишком долго.

Пример: нужно фильтровать все сайты, которые содержат точку и расширение файла из списка.

sites_list = ["http://google.com",
              "http://www.yandex.com",
              "http://rambler.com/ololo.jpg",
              "http://ya.ru/a.bmp"]

format_files = ['jpg', 'bmp', 'jpeg']

print list(filter(lambda url: not any('.' + format_file in url for format_file in format_files),  sites_list))

Но представим, что список сайтов состоит из более чем 200к элементов. Как ускорить процесс?

Answer 1

[throughtheether]

Пример: нужно фильтровать все сайты, которые содержат точку и расширение файла из списка.

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

import timeit
setup_code="""
sites_list = ["http://google.com",
              "http://www.yandex.com",
              "http://rambler.com/ololo.jpg",
              "http://ya.ru/a.bmp"]

format_files = ['jpg', 'bmp', 'jpeg']
"""
print timeit.timeit("x=list(filter(lambda url: not any('.' + format_file in url for format_file in format_files),  sites_list))",setup=setup_code,number=100000)
print timeit.timeit("x=list(url for url in sites_list if not url.endswith(tuple(format_files)))",setup=setup_code,number=100000)

Результаты:

1.01494306967
0.616600117219

Кроме того, я бы заменил, где это возможно, списки (list) на кортежи (tuple) или множества (set).

Comments

[JRazor]

Про кортежи не знал, обязательно заменю. А поводу endswith - встречаются URL типа site.com/image.jpg?=48fuu922

[throughtheether]

> А поводу endswith
код, отмеченный вами, как решение, также использует endswith.
>встречаются URL типа site.com/image.jpg?=48fuu922
так можно предварительно обработать такие случаи:
sites_filtered=list(url.split('?')[0] if '?' in url else url for url in sites_list)
но это вернет вас к прежней производительности, скорее всего

[throughtheether]

кроме того, стоит учитывать, что наличие "расширения" ".jpg" в конце url не гарантирует, что сервер при запросе по этому url даст вам картинку.

Answer 2

[leclecovich]

1 У Вас явный оверхед в

list(filter(lambda url: not any('.' + format_file in url for format_file in format_files), sites_list))

Можно сделать проще и, самое главное, быстрее.
2 Кортежи и словари итерируются в общем случае быстрее, чем списки.
3 Если этого мало - поделите исходный список на несколько частей, распараллельте вычисления.
4 Используйте C. Если Вам не нравиться использование массива - C++, STL, Boost Вам в помощь. Помните, о том, что нативный код легко можно вызвать из питона (CPython).

Comments

[JRazor]

Можно ли из стандартного PYthon вызвать C конструкцию?

[yttrium]

@JRazor ctypes

Answer 3

[Максим]

используйте pypy.org

Comments

[JRazor]

Я слышал, что под PyPy портировано слишком мало библиотек.

Answer 4

[4yBa4oK]

попробуйте регулярные выражения
аж интересно