Какие в Питоне самые быстрые способы искать подстроку в списке строк?
Есть список 16 000 URL-ов. Требуется узнать, сколько раз встречается какой домен. Отдельно требуется посчитать число доменов второго уровня. То есть домены вида dpmmax.livejournal.com учтутся дважды — и как dpmmax.livejournal.com, и как livejournal.com.
Список уникальных доменов можно получить регулярным выражением или через urllib:
unique_domains = set( urllib.parse.urlsplit(url).hostname for url in allurls )
unique_domains = sorted(unique_domains.union(m[1] for m in (re.match('.*?([^.]+\.[^.]+)$', d) for d in unique_domains) if m))
Можно для каждого домена в сете перебирать список URL-ов функцией:
def d_count(domain):
d1, d2 = '.' + domain + '/', '/' + domain + '/'
return sum( 1 for url in allurls if d1 in url or d2 in url )
Но это долго — 4-5 секунд для 1500 доменов и 16 000 URLов.
Можно заранее сделать список доменов, соответствующих URLам (allhosts = [urllib.parse.urlsplit(url).hostname for url in allurls]), и проверять по нему функцией:
def d_count(domain):
d1 = '.' + domain
return sum( 1 for hostname in allhosts if hostname.endswith(d1) or hostname == domain )
Но выигрыш получается в пределах погрешности.
Если использовать регулярные выражения, получится на 2 порядка дольше.
sum( 1 for <итератор> if <условие> ) работает на 20-30% быстрее sum( <условие> for <итератор> ). Бывает и все 60%.
Как ещё можно ускорить?
Ответ:
list.count() примерно втрое быстрее.
second_level_domains = [ m[1] for m in (re.match('^.*?([^.]+\.[^.]+)$', host) for host in allhosts) if m ]
counts = { domain: max(allhosts.count(domain), second_level_domains.count(domain)) for domain in unique_domains }
collections.Counter() ещё втрое быстрее:
counts =
collections.Counter(urllib.parse.urlsplit(url).hostname for url in allurls) |
collections.Counter(m[1] for m in (re.match('^.*?([^.]+\.[^.]+)$', urllib.parse.urlsplit(url).hostname) for url in allurls) if m)
Это быстрее в 10 раз.
Ещё вдвое можно ускорить, если не вычислять список хостов дважды:
allhosts = [urllib.parse.urlsplit(url).hostname for url in allurls]
counts = collections.Counter(allhosts) | collections.Counter(m[1] for m in (re.match('^.*?([^.]+\.[^.]+)$', host) for host in allhosts) if m)
Ещё несколько процентов можно получить, если заменить объединение сложением, а для этого регулярным выражением взять только домены 2 уровня из хостов глубже 2 уровня, отбросив всё остальное. Ещё немного даёт замена re.search и re.match на re.fullmatch с отказом от ^ и $:
allhosts = [urllib.parse.urlsplit(url).hostname for url in allurls]
counts = collections.Counter(allhosts) + collections.Counter(m[1] for m in (re.fullmatch('.*?\.([^.]+\.[^.]+)', host) for host in allhosts) if m)
