Проект Эйлера: программная оптимизация для задачи 7? - PullRequest
Новая
       13

Проект Эйлера: программная оптимизация для задачи 7?

3 голосов
/ 19 апреля 2010

Так что я бы назвал себя довольно начинающим программистом, так как я сосредоточился в основном на оборудовании в моей школе, а не на многих курсах компьютерных наук.

Итак, я решил проблему 7 в Project Euler:

Перечисляя первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы можем видеть, что шестое простое число равно 13.

Что такое 10001-е простое число?

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

Является ли цикл зацикливанием и оператором while, что съедает время обработки? И как это можно оптимизировать? Опять же, не ищем причудливого математического уравнения ... в потоке решений их много.

SPOILER Мое решение указано ниже. 

public class PrimeNumberList {

private ArrayList<BigInteger> primesList = new ArrayList<BigInteger>();

public void fillList(int numberOfPrimes) {
    primesList.add(new BigInteger("2"));
    primesList.add(new BigInteger("3"));
    while (primesList.size() < numberOfPrimes){
        getNextPrime();
    }
}

private void getNextPrime() {
    BigInteger lastPrime = primesList.get(primesList.size()-1);
    BigInteger currentTestNumber = lastPrime;
    BigInteger modulusResult;
    boolean prime = false;
    while(!prime){
        prime = true;
        currentTestNumber = currentTestNumber.add(new BigInteger("2"));
        for (BigInteger bi : primesList){
            modulusResult = currentTestNumber.mod(bi);
            if (modulusResult.equals(BigInteger.ZERO)){
                prime = false;
                break;
            }
        }
        if(prime){
            primesList.add(currentTestNumber);
        }
    }
}

public BigInteger get(int primeTerm) {
    return primesList.get(primeTerm - 1);
}

}

Ответы [ 9 ]

13 голосов
/ 19 апреля 2010

Поскольку 10001-е простое число не так велико, вы можете начать с использования long вместо BigInteger. Экземпляр BigInteger - это полноценный Java-объект, и при их создании и манипулировании возникает много накладных расходов.

6 голосов
/ 19 апреля 2010

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

Еще одно (очень небольшое по сравнению) улучшениебыть в кэшировании new BigInteger("2") и использовать его снова вместо создания нового BigInteger с тем же значением каждый раз в цикле while. <- по-прежнему хорошая практика, но в этом случае она менее значительна, чем ошибка округления.</p>

4 голосов
/ 19 апреля 2010

Также попробуйте Сито эратостенов с простыми числами, представленными BitSet, это намного быстрее, чем тестирование кандидатов по отдельности.

1 голос
/ 17 января 2012

Вам лучше использовать int / long и просто пробегать циклы, чтобы проверить, простое ли число. Чтобы оптимизировать и ускорить вашу программу, вы можете уменьшить количество итераций в цикле for, установив ограничение Math.sqrt (num).

Ссылка: http://www.mycoding.net/2012/01/program-to-find-10001st-prime-number-project-euler-problem-7/

1 голос
/ 19 апреля 2010

Так как вы зацикливаетесь на while(!prime) в getNextPrime(), гарантированно возвращается простое число, так что вы можете изменить свой цикл в fillList, не вызывая size() каждый раз.Возможно, это не так уж и много, но не имеет смысла вычислять размер каждый раз, когда вы знаете, что он увеличивается на 1.

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

1 голос
/ 19 апреля 2010

Используйте целые. Используйте массив фиксированного размера для вашего primesList, чтобы вам не приходилось платить за выделение памяти (или сделать начальный размер достаточно большим, чтобы динамический список не создавал проблем).

Используйте нормаль для того, чтобы вместо этого считать целое число, причем Count находится вне цикла.

0 голосов
/ 11 марта 2014

Я просто перевел Сито Эратосфена на Java. Предполагается, что это один из наиболее эффективных способов алгоритмического решения простых чисел. 

public static void main(String[] args){

    ArrayList<Integer> List = new ArrayList<Integer>();
    ArrayList<Integer> Primes = new ArrayList<Integer>();
    Primes.add(2);
    Integer p=2;
    Integer n=105000; 
    Integer i=1;

    while(p < n) {

        i=1;

        while((p*i)<=n) {
            List.add(p*i);
            i++;
        }

        while (p < n) {
            p++;
            if(List.contains(p)){                     }
            else                {Primes.add(p); break;}
        }

    }

    System.out.println("PRIME 10,001 is.... " + Primes.get(10000));
    // 104743

}
0 голосов
/ 19 апреля 2010

Вот решение .NET ... Мои тесты показали, что я получил 10001-е простое число в 132 мс и 100 000 простое в 4417 мс. 

public static IEnumerable<long> GetPrimes(int numberPrimes)
{
  List<long> primes = new List<long> { 1, 2, 3 };
  long startTest = 3;

  while (primes.Count() < numberPrimes)
  {
    startTest += 2;
    bool prime = true;
    for (int pos = 2; pos < primes.Count() && primes[pos] < Math.Sqrt(startTest); pos++)
    {
      if (startTest % primes[pos] == 0)
      {
        prime = false;
      }
    }
    if (prime)
      primes.Add(startTest);
  }
  return primes;
}
0 голосов
/ 19 апреля 2010

Я заметил, что ваш код проверяет всех кандидатов на делимость на два. Но ваши главные кандидаты никогда не бывают равными. Таким образом, вы можете пропустить этот первый тест. Это мелочь, но вы сэкономите 9999 модов.

...