Ускорение разделения и объединения строк - PullRequest
Новая
       4

Ускорение разделения и объединения строк

4 голосов
/ 25 января 2011

Я пытаюсь решить Задача проекта Эйлера # 35

Число 197 называется круговым простым числом, потому что все вращения цифр: 197, 971,и 719 сами просты.

Сколько круговых простых чисел меньше одного миллиона?

Это мое решение: 

import numpy as np

def problem(n=100):

    circulars = np.array([], np.int32)

    p = np.array(sieveOfAtkin(n), np.int32)
    for prime in p:
        prime_str = str(prime)
        is_circular = True
        for i in xrange(len(prime_str)):
            m = int(prime_str[i:]+prime_str[:i])
            if not m in p:
                is_circular = False

        if is_circular:
            circulars = np.append(circulars, [prime])

    return len(circulars)

К сожалению, цикл for очень медленный!Любые идеи, как я могу ускорить это?Я подозреваю, что объединение строк является узким местом, но я не совсем уверен!:)

Есть идеи?:)

1 Ответ

8 голосов
/ 25 января 2011

  1. Использовать набор для проверки членства вместо массива.Поиск по хешу будет O (1) вместо O (n).Это самое большое узкое место.

  2. Прервите петлю, как только вы увидите, что это не круговое простое число вместо попытки других вращений.Это еще одно узкое место.

Здесь я выделил проверку округлости в функцию, позволяющую составлять список с пониманием списка.Имея это в функции, давайте вернем False, как только мы узнаем, что оно не круглое.Другой альтернативой было бы сделать это в цикле for и break, когда мы знаем, что он не круговой.Затем добавьте к списку в предложении цикла else.Вообще говоря, списочные операции выполняются быстрее, чем добавление в цикл.Это может быть не так, потому что это добавляет накладные расходы на вызов функции.Если вы действительно заботитесь о скорости, стоило бы профилировать оба варианта. 

primes = set(primes_to_one_million_however_you_want_to_get_them)

def is_circular(prime, primes=primes):
   prime_str = str(prime)
   # With thanks to Sven Marnach's comments
   return all(int(prime_str[i:]+prime_str[:i]) in primes 
              for i in xrange(len(prime_str)))


circular_primes = [p for p in primes if is_circular(p)]

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

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

circular = []
for p in primes:
   prime_str = str(prime)
   for i in xrange(len(prime_str)):
       if int(prime_str[i:]+prime_str[:i]) not in primes:
            break
   else:
       circular.append(p)
...