Помогите ускорить этот алгоритм? Сито из Eratosthenes

Question

Я написал алгоритм, который, я считаю, корректен для вычисления простых чисел до n с помощью сита Эратосфена. К сожалению, эта программа зависает на действительно больших значениях n (попробуйте 10 миллионов). Вот что я написал ...

Protected Function Eratosthenes(ByVal n As Integer) As String 
    Dim maxValue As Integer = Math.Sqrt(n) 
    Dim values As Generic.List(Of Integer) = New Generic.List(Of Integer) 
    Dim i As Integer 
    ''//create list. 
    For i = 2 To n 
     values.Add(i) 
    Next 

    For i = 2 To maxValue 
     If values.Contains(i) Then 
      Dim k As Integer 
      For k = i + 1 To n 
       If values.Contains(k) Then 
        If (k Mod i) = 0 Then 
         values.Remove(k) 
        End If 
       End If 
      Next 
     End If 
    Next 

    Dim result As String = "" 
    For i = 0 To values.Count - 1 
     result = result & " " & values(i) 
    Next 

    Return result 
End Function 

Как я могу ускорить этот алгоритм? Где мои узкие места?

Answer 1

Извлечение элементов из большого списка происходит медленно.

Почему бы вам не создать массив значений типа Booleans и установить значение «True», если вы знаете, что это неправа?

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

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

Вот реализация C#, которая только распечатывает их, как только это происходит. (В C#, если я хотел, чтобы вернуть значения я вернуть IEnumerable<T> и использовать блок итератора.)

using System; 

public class ShowPrimes 
{ 
    static void Main(string[] args) 
    { 
     ShowPrimes(10000000); 
    } 

    static void ShowPrimes(int max) 
    {   
     bool[] composite = new bool[max+1]; 
     int maxFactor = (int) Math.Sqrt(max); 

     for (int i=2; i <= maxFactor; i++) 
     { 
      if (composite[i]) 
      { 
       continue; 
      } 
      Console.WriteLine("Found {0}", i); 
      // This is probably as quick as only 
      // multiplying by primes. 
      for (int multiples = i * i; 
       multiples <= max; 
       multiples += i) 
      { 
       composite[multiples] = true; 
      } 
     } 
     // Anything left is a prime, but not 
     // worth sieving 
     for (int i = maxFactor + 1; i <= max; i++) 
     { 
      if (composite[i]) 
      { 
       continue; 
      } 
      Console.WriteLine("Found {0}", i); 
     } 
    } 
} 

Answer 2

Я не VB парень, но я думаю:

values.Remove(k) 

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

Answer 3

Вот C# реализация я бросил вместе некоторое время назад.

Возможно, это поможет!

using System; 
using System.Collections.Generic; 

namespace sieve050707 
{ 
class MainClass 
{ 
public static void Main(string[] args) 
{ 
Console.WriteLine(”Sieve of Eratosthenes – 05 July 2007″); 
int sampleSize = 100; 

if (args.Length > 0) 
{ 
sampleSize = Int32.Parse(args[0]); 
} 

List sampleData = new List(); 
List primesFound = new List(); 

for (int counter=2; counter < sampleSize; counter++) 
{ 
sampleData.Add(counter); 
} 

for (int counter=2; counter < sampleSize; counter++) 
{ 
if(sampleData.Contains(counter)) 
{ 
primesFound.Add(counter); 
sampleData.Remove(counter); 
for (int multiple=counter*2; multiple < sampleSize; multiple = multiple + counter) 
{ 
sampleData.Remove(multiple); 
} 
} 
} 
foreach(int prime in primesFound) 
{ 
Console.WriteLine(prime.ToString() + ” is prime”); 
} 
} 
} 
} 

НТН,

Dan

Answer 4

использовать строку строитель.

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

возможно преобразовать список int в массив?

Вы уверены, что содержит прекращение действия после того, как товар будет найден?

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

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

Answer 5

Ваша бутылочная горловина - это использование списка, простого и простого. List.contains - O (n), List.Remove (n).

Вы ускорите свое приложение, используя лучшую структуру данных, а именно BitArray. Предположим, что элементы, установленные в True, являются первичными, а те, которые не являются составными. Это означает, что поиск, добавление или удаление элементов из вашего основного набора будет выполнять операцию O (1).

Answer 6

Было доказано, что достаточно для проверки простых только на интервале 2..sqrt (MaxValue)

Answer 7

узким местом в этом коде является призванием values.Contains (I) и values.Contains (к) для каждого целого кандидата. Один простой способ ускорить ваш текущий подход состоит в том, чтобы иметь второй список рядом с первым, который хранит false/true для каждого номера, так что вместо выполнения содержит алгоритм O (n), позволяющий осуществлять прямой поиск, который является O (1). Заключительный цикл в этом случае будет проверять истинность относительно того, следует ли включать значение.

Однако существуют более быстрые способы решения проблемы. Традиционный алгоритм Эратосфена состоит в том, чтобы генерировать числа от 2 до sqrt (n) и тестировать их против каждого числа, известного в списке простых чисел. Если число делит на какой-либо из них отлично, то оно выбрасывается, а следующее число проверяется, иначе оно добавляется как простое в этом списке. Вероятно, это будет быстрее, чем предлагаемая выше оптимизация.

Answer 8

Создание массива всех чисел до введенного максимального числа - безумие; потому что по определению большинство из них не будут простыми. Таким образом, вы уже держите как минимум 2x столько данных, сколько вам нужно.

Существует много известных методов поиска простых чисел.

Что вы пытаетесь сделать? Печать более 10 миллионов? На сколько больше? Какова цель здесь?

Если вам нужно только узнать о простых числах, изучите GCD и другие забавные вещи. (Китайская теорема о остатках).

Answer 9

без изменения алгоритма, вот некоторые оптимизации:

Dim result As String = "" 
For i = 0 To values.Count - 1 
    result = result & " " & values(i) 
Next 

Это Schlemiel художник ... Используйте string.join вместо этого.

---

values.Contains(i) 
values.Contains(k) 

Это дорого - Используйте HashSet вместо списка, чтобы сделать его дешевле.

---

If values.Contains(k) Then 
    If (k Mod i) = 0 Then 
     values.Remove(k) 
    End If 
End If 

Mod является способ дешевле, чем Содержит (даже с HashSet). Сначала выполните проверку мод.

Answer 10

Если вы используете .NET 3.5, вы можете переписать так:

Protected Function Eratosthenes(ByVal n As Integer) As String 
    Dim values As List(Of Integer) = Enumerable.Range(0,n).ToList() 

    For i = 2 To Math.Sqrt(n) 
     If values(i) > 0 Then 
      For k As Integer = i + 1 To n 
       If values(k) AndAlso (k Mod i) = 0 Then 
        values(k) = 0 
       End If 
      Next 
     End If 
    Next 

    Return string.Join(" ", values.Where(Function(i) i>1).Select(Function(i) i.ToString()).ToArray()) 
End Function 

Answer 11

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

Величие просеивания заключается в том, что он позволяет избежать дорогостоящей операции с модулем: если вы знаете, что p является простым, чтобы устранить все его кратность, а не проверять, все ли числа в сите делятся на p, вы устраняете предметы 2p, 3p, 4p ...На самом деле, как решето Erathostenes работает, можно показать, что первый элемент, который вы исключите р , так что вам нужно только, чтобы проверить, если р , р + р, р ^- + 2p, p + 3p есть.

С моим полным отсутствием знаний о Visual Basic, это должно заботиться о своем главном бутылочного горлышка:

Protected Function Eratosthenes(ByVal n As Integer) As String 
    Dim maxValue As Integer = Math.Sqrt(n) 
    Dim values As Generic.List(Of Integer) = New Generic.List(Of Integer) 
    Dim i As Integer 
    ''//create list. 
    For i = 2 To n 
     values.Add(i) 
    Next 

    For i = 2 To maxValue 
     If values.Contains(i) Then 
      Dim k As Integer 
      For k = i * i To n Step i 
       If values.Contains(k) Then 
        values.Remove(k) 
       End If 
      Next 
     End If 
    Next 

    Dim result As String = "" 
    For i = 0 To values.Count - 1 
     result = result & " " & values(i) 
    Next 

    Return result 
End Function 

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

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

Answer 12

Это будет делать n = 10 000 000 в 0,28 секунды и n = 100 000 000 за 4 секунды. (VB 2008, Pentium e8500)

Самая медленная часть была конкатенацией строк. VB очень медленно объединяет большие строки, поэтому я использовал целочисленный массив для сохранения простых чисел.

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

VB не оптимизировал int (i/2) в инструкции «для k», поэтому я переместил его в переменную max2.

Для больших n, переназначение массива ответов стало узким местом, поэтому я добавил 100 000 элементов каждый раз, когда он нуждался в расширении.

Как обычно ... Я не проверял это полностью, поэтому могут быть ошибки.

Protected Function Eratosthenes(ByVal n As Integer) As Integer() 

Dim nPrime As Integer 
Dim values(n) As Byte 
Dim ans(1) As Integer 

Dim maxValue As Integer = Math.Sqrt(n) 
For i = 0 To n 
    values(i) = 1 
Next i 

Dim max2 As Integer 
For i = 2 To maxValue 
    If values(i) <> 0 Then 
     max2 = Int(n/i) 
     For k = 2 To max2 
      values(k * i) = 0 
     Next k 
    End If 
Next i 

nPrime = 0 
For i = 2 To UBound(values) 
    If values(i) <> 0 Then 
     nPrime = nPrime + 1 
     If nPrime > UBound(ans) Then ReDim Preserve ans(nPrime + 100000) 
     ans(nPrime) = i 
    End If 
Next i 

ReDim Preserve ans(nPrime) 
Eratosthenes = ans 

End Function