0

Данные код имеет оптимизацию по памяти. Так это сито сегментированное. Мне нужна оптимизация по времени.

WinForm

        void simpleSieve(ulong limit, ArrayList prime)
        {

            bool[] mark = new bool[limit + 1];

            for (int i = 0; i < mark.Length; i++)
                mark[i] = true;

            for (ulong p = 2; p * p < limit; p++)

            {

                if (mark[p] == true)
                {

                    for (ulong i = (ulong)(p * p); i < limit; i += (ulong)p)
                        mark[i] = false;
                }
            }


            for (ulong p = 2; p < limit; p++)

            {
                if (mark[p] == true)
                {
                    prime.Add(p);
                    richTextBox1.AppendText(p + " ");

                }
            }
        }

        void segmentedSieve(ulong n)
        {

            int limit = (int)(Math.Floor(Math.Sqrt(n)) + 1);
            ArrayList prime = new ArrayList();
            simpleSieve((ulong)limit, prime);


            ulong low = (ulong)limit;
            ulong high = (ulong)(2 * limit);


            while (low < n)
            {
                if (high >= n)
                    high = n;


                bool[] mark = new bool[limit + 1];

                for (int i = 0; i < mark.Length; i++)
                    mark[i] = true;


                for (int i = 0; i < prime.Count; i++)
                {

                    ulong loLim = ((ulong)Math.Floor((double)(low / (ulong)prime[i])) * (ulong)prime[i]);
                    if (loLim < low)
                        loLim += (ulong)prime[i];


                    for (ulong j = loLim; j < high; j += (ulong)prime[i])
                        mark[j - low] = false;
                }


                for (ulong i = low; i < high; i++)
                    if (mark[i - low] == true)
                        richTextBox1.AppendText(i + " ");
                low = low + (ulong)limit;
                high = high + (ulong)limit;
            }
        }

Console

 static void simpleSieve(int limit,
                        ArrayList prime)
{
    /
    bool[] mark = new bool[limit + 1];
     
    for (int i = 0; i < mark.Length; i++)
        mark[i] = true;
 
    for (int p = 2; p * p < limit; p++)
    {
       
        if (mark[p] == true)
        {
            
            for (int i = p * p; i < limit; i += p)
                mark[i] = false;
        }
    }
 
   
    for (int p = 2; p < limit; p++)
    {
        if (mark[p] == true)
        {
            prime.Add(p);
            Console.Write(p + " ");
        }
    }
}
 

static void segmentedSieve(int n)
{
    
    int limit = (int) (Math.Floor(Math.Sqrt(n)) + 1);
    ArrayList prime = new ArrayList();
    simpleSieve(limit, prime);
 
    
    int low = limit;
    int high = 2*limit;
 
    
    while (low < n)
    {
        if (high >= n)
            high = n;

        
        bool[] mark = new bool[limit + 1];
         
        for (int i = 0; i < mark.Length; i++)
            mark[i] = true;
 
        
        // primes in current range
        for (int i = 0; i < prime.Count; i++)
        {
            
            int loLim = ((int)Math.Floor((double)(low /
                        (int)prime[i])) * (int)prime[i]);
            if (loLim < low)
                loLim += (int)prime[i];
 
            
            for (int j = loLim; j < high; j += (int)prime[i])
                mark[j-low] = false;
        }
 
        
        for (int i = low; i < high; i++)
            if (mark[i - low] == true)
                Console.Write(i + " ");
 
        
        low = low + limit;
        high = high + limit;
    }
}
 

static void Main()
{
    int n = 100;
    Console.WriteLine("Primes smaller than " + n + ":");
    segmentedSieve(n);
}
17
  • 1
    иногда нужно не алгоритм оптимизировать, а использовать более быстрые алгоритмы.
    – KoVadim
    14 апр 2022 в 6:54
  • оптимизация по времени - сколько сейчас и сколько надо? Как тестируете?
    – aepot
    14 апр 2022 в 7:13
  • Необходимо использовать именно сито Эратосфена@KoVadim
    – kamaha
    14 апр 2022 в 7:16
  • 1
    Необходимо до 1000000000 @aepot
    – kamaha
    14 апр 2022 в 7:25
  • 1
    я думаю, что можно один раз посчитать, сохранить в файл. И готово. А когда то я уже здесь писал, как упаковать очень компактно такое.
    – KoVadim
    14 апр 2022 в 8:14

1 ответ 1

3

Понизить асимптотическую сложность данного алгоритма без ущерба потреблению памяти практически невозможно.

Но здесь можно сделать следующие вещи:

  • Уменьшить количество генерируемого мусора, это позволит сборщику реже останавливтаь код для сборки, следовательно увеличит производительность кода.
  • Данные, используемые часто разместить в массиве, а не в списке для блоее быстрого к ним доступа.
  • Избавиться от вывода на экран во время расчетов, результатом работы метода считать наполненную коллекцию простых чисел, смысл выводить на экран 50847534 чисел, верно? Вы же никогда не сможете визуально проверить каждое.
  • Избавиться от лишних приведений типов, если это не повлияет на результат работы. long.MaxValue - вполне достаточно для задания интервала поиска. Если вы зададите это число, считать будет очень долго, поэтому увеличение его в 2 раза за счет ulong не считаю полезным.
static void Main(string[] args)
{
    Stopwatch sw = Stopwatch.StartNew();
    List<long> result = SegmentedSieve(1000000000);
    Console.WriteLine($"Elapsed = {sw.Elapsed}");
    Console.WriteLine($"Total numbers = {result.Count}");
    Console.ReadKey();
}

static void SimpleSieve(int limit, List<long> prime)
{
    bool[] mark = new bool[limit];

    for (int p = 2; p * p < limit; p++)
    {
        if (!mark[p])
        {
            for (int i = p * p; i < limit; i += p)
                mark[i] = true;
        }
    }

    for (int p = 2; p < limit; p++)
    {
        if (!mark[p])
            prime.Add(p);
    }
}

static List<long> SegmentedSieve(long n)
{
    int limit = (int)Math.Ceiling(Math.Sqrt(n));
    List<long> result = new(limit);
    SimpleSieve(limit, result);
    long[] prime = result.ToArray();

    long low = limit;
    long high = 2 * limit;
    bool[] mark = new bool[limit];

    while (low < n)
    {
        if (high >= n)
            high = n;

        foreach (long p in prime)
        {
            long loLim = low / p * p;
            if (loLim < low)
                loLim += p;

            for (long j = loLim; j < high; j += p)
                mark[j - low] = true;
        }

        for (long i = low; i < high; i++)
            if (!mark[i - low])
                result.Add(i);

        low += limit;
        high += limit;
        Array.Fill(mark, false);
    }

    return result;
}

Вывод в консоль Debug сборки

Elapsed = 00:00:08.8822729
Total numbers = 50847534

Вывод в консоль Release сборки

Elapsed = 00:00:03.3784039
Total numbers = 50847534

3,4 секунды - думаю, неплохо

9
  • 1
    Спасибо за помощь. Буду дома проверю как работает @aepot
    – kamaha
    14 апр 2022 в 9:19
  • capacity в конструкторе списка вроде как за размер внутреннего массива и отвечает, поэтому не должно быть разницы массив prime или список result
    – Grundy
    14 апр 2022 в 10:20
  • @Grundy есть разница при обращении по индексу. При работе с массивом выполняется просто адресация в памяти, при работе со списком вызывается геттер индексатора, который очевидно работает медленнее, чем просто прямое обращение к памяти. Я здесь задаю capacity только для того чтобы избежать лишнего мусора на ранних стадиях работы алгоритма, список по умолчанию имеет размер 16 элементов и далее удваивает внутренний массив при добавлении элементов. Закидывая туда побольше при создании списка, я избегаю лишних аллокаций.
    – aepot
    14 апр 2022 в 12:55
  • @aepot, хотелось бы тестов
    – Grundy
    14 апр 2022 в 13:06
  • @Grundy ru.stackoverflow.com/a/1306279/373567, но с индексаторами ровно та же история, что и с перечислителем.
    – aepot
    14 апр 2022 в 13:06

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.