طبق هذه الخوارزمية بلغتك المفضلة ج1: الأعداد الأولية

سأبدأ أنا بلغة بايثون

def get_primes(n):
  compo=set()
  for i in xrange(2, n):
    if i in compo: continue
    yield i
    compo.update(xrange(i*2, n,i))

جوانب التفوق:

• لا تستخدم return بل yield مما يوفر الذاكرة

• يستخدم xrange (أو range في بايثون 3) وهي تعيد كائن يسير على الأعداد ولا يحجزها في الذاكرة (بمعنى لا نعمل منظومة array من 10 آلاف عنصر)

• تستخدم تركيد البيانات المسمى set وهو تركيب يفحص الوجود من عدمه بسرعة (ربما O1 أو Ologn) وهو أسرع من in_array في php والتي تسريع على كل العناصر أي On

جوانب القصور

• قد يكون تحديث منظومة الأعداد المركبة عملية مكلفة خصوصا أن بايثون لا تسمح لنا أن نقدم لها نصيحة مسبقة بالحجم الأقصى كما في جافا

هذا المنهج يعيد مجموعة الأعداد الأولية ضمن مجال معين

بلغة سي شارب #C

    public static IEnumerable<int> GetPrimes(int range)
    {
        bool[] isNotPrimes = new bool[range];
        for(int i = 2; i < range; i++)
            for(int j = i * 2; j < range; j += i)
                isNotPrimes[j] = true;
        for(int k = 0; k < range; k++)
            if(!isNotPrimes[k])
                yield return k;
    }

ولطباعتها في تطبيق كونسول

    static void Main(string[] args)
    {
        var primes = GetPrimes(10000);
        foreach(var number in primes)
        {
            Console.Write(number + " | ");
        }
    }

تم تحسين الخوارزمية

وإنقاص الزمن وذلك بتجاهل المجموعات التي هي مشطوبة يقينا

    public static IEnumerable<int> GetPrimes(int range)
    {
        bool[] isNotPrimes = new bool[range];

        for(int i = 2; i <= 3; i++)
        {
            yield return i;
            for(int j = i * 2; j < range; j += i)
                isNotPrimes[j] = true;
        }

        for(int k = 6; k < range; k += 6)
        {
            int i = k - 1;
            if(!isNotPrimes[i])
            {
                yield return i;
                for(int j = i * 2; j < range; j += i)
                    isNotPrimes[j] = true;
            }
            i = k + 1;
            if(!isNotPrimes[i])
            {
                yield return i;
                for(int j = i * 2; j < range; j += i)
                    isNotPrimes[j] = true;
            }
        }
    }

حيث بدلا من تمرير الحلقة الخارجية على جميع الأعداد نجعلها تمر على مضاعفات 6 فقط ومن ثم نفحص الذي قبله والذي بعده وما عداها فهي قد شطبت بمضاعفات 2 و 3 و 5

لأن القاعدة تقول أن أي عدد أولي أكبر من 3 هو إما 6K-1 أو 6K+1

وبالتالي نمرر حلقتين على 2 و 3 لأنهما استثناء للقاعدة

ثم نمرر الحلقة على مضاعفات الـ 6 و نفحص مرة i-1 و مرة i+1

وهذه المرة كان الزمن 0.1

عذرا أخطأت باسمه الخوارزمية فهي غربال Eratosthenes لكن وصفها صحيح.

مثال بالجافا سكريبت لا شئ مميز بخلاف ان زمن التنفيذ لـ 500 مرة أقل من نصف ثانية في متصفح كروم و nodejs ولو أن الأخيرة أسرع قليلا من المتصفح

function getPrimes(max){
    var primes = [] ,
         numbers= {};

    for ( i = 2 ; i < max ; ++i){

    if (!numbers[i]) numbers[i] = false
    if (numbers[i]) continue;

      primes.push(i)

    for (j=i*2;  j<max;  j+=i )
       numbers[j] = true;

    }
    return primes;
}
function benchmarck(count) {

    d = new Date();

    for (var i = 0 ; i < count; ++i)
       getPrimes1(10000);

    console.log((new Date()) - d);
}
benchmarck(500);

الآن بعد إقصاء الحلقات من أجل الأعداد التي شطبت من قبل تم تحسين المنهج

أي لا داعي لشطب مضاعفات 4 أو 6 أو 8 أو 9 أو .. الخ لأنهما شطبتا من قبل عندما مررنا على أصغر قاسم أولي لها أي 2 و 3 و 5 .. الخ

    public static IEnumerable<int> GetPrimes(int range)
    {
        bool[] isNotPrimes = new bool[range];
        for(int i = 2; i < range; i++)
        {
            if(!isNotPrimes[i])
            {
                yield return i;
                for(int j = i * 2; j < range; j += i)
                    isNotPrimes[j] = true;
            }
            else
                continue;
        }
    }

وانخفض الزمن إلى الربع

أي من أجل عشرة ملايين نزل الزمن ليصبح نصف ثانية

هذه الخوارزمية بجافاسكربت 1.7 مستخدمة المولدات (generators):

'use strict';
function* getPrimes(n) {
    let compos = [];
    for (let i = 2; i <= n; i++) {
        if (!!compos[i]) continue;
        yield i;
        for (let j = i* 2; j <= n; j += i) {
            compos[j] = true;
        }
    }
}

function benchmark(n, iterations) {
    let start = new Date;
    for (let j = 0; j < iterations; j++) {
        let generator = getPrimes(n), array = [];
        for (let prime of generator) {
            array.push(prime);
        }
        // console.log(array);
    }
    return new Date - start;
}

console.log(benchmark(10000, 500));

لتنفيذ البرنامج تحتاج Node.js بنسخة 0.11.23 مع الوسم --harmony

تم حساب الأعداد حتى 10000 مكررة 500 مرة وكانت النتيجة 778 ميكروثانية.

في فايرفوكس Nightly استغرق التنفيذ حوالي 12 ثانية!

أين محبي روبي؟

الكود بلغة لوا

استغرق حوالي ثانية ونصف على لوا و أقل من عشري ثانية على luajit.

مرحبا ...

Haskell

Erlang

انا غير مقتنع بطريقة القياس :) المقترحة من alsadi ..

لان من الممكن ان تكون النتائج محفوظة ب Cache او شئ من ذلك . خصوصا ان استدعاء الدالة دائما بنفس المعطى 10000

السلام عليكم

على ماذا تتحدث هذه الدورة و ما الفائدة اذا قمت بتتبعها

كود بايثون المنفذ عبر مفسر بايثون المكتوب بلغة جافاسكربت repl.it استغرق الكثير من الوقت تقريبا أكثر من نصف دقيقة (على كروم ولم ينتهي على فايرفوكس 26 مع أني أعطيته أكثر من 10 دقائق)

كذلك لو قمنا بتغير الخوارزمية لاستعمال منظومة عادية عوضا عن المجموعة بل إن الوقت زاد 20%

/1

مع أنها في مفسر بايثون بلغة سي استغرق بهذه الطريقة الأخيرة ثانتين وعلى مفسر بايثون المكتوب بلغة بايثون pypy مع JIT أقل من 300 ميليثانية من الثانية.

لوا lua عبر جافاسكربت من خلال خدمة repl.it ومتصف كروم استغرقت حوالي ثلث ساعة مع أن أنها عبر المفسر العادي ثلاث ثواني وعبر luajit ربع ثانية.

كنت أظنه السلاح السري لكنه كان سريع لكن ليس بشكل كبير وصادم. إليكم سي/سي++

يمكننا إخراج عمل حجز الذاكرة alloc لمتغير compo خارج الحلقة وتمريره كمعامل لكني أعتبر هذا غش

أين محبي جافا؟ يمكنك استعمال هذه المكتبة

لكني أفضل أن أرى تنفيذ دون استعمالها.

ما شاء الله

متابع بنهم

سلام عليكم ومرحبا !

لاحظت ماف شاركة بلغة الجافا فحبيت أشارككم ..

للي بينفذ الكود .. هذا الكود لـ Java8 يعني لازم يكون عندك آخر نسخة من جافا عشان تدعم الــ APIs يا اللي استخدمتها و الميزات الثانية ..

هذا هو الكود .. ما بعرف اذا طريقة تطبيقي صحيحة أو خطأ .. أو ممكن أكون فهمت المسألة غلط .. يريت تقارنوا التنفيذ .. و الكود عشان توروني فين خطأي ..

package com.matar.alog.primes;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.lang.reflect.Method;

import java.util.HashSet;

import java.util.Iterator;

import java.util.function.Predicate;

public class AtkinAlogrithmWithJava {

/* Class Body */

private static  int $limitPoint = 0;
private static long $startTime = 0;
private static long $endTime = 0;
private static HashSet<Integer> primes;
public static void main(String... mo9){
    BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
    try {
        System.err.println("Enter LimitPoint Please : ");
        $limitPoint = Integer.parseInt(buffer.readLine());
    } catch (NumberFormatException e) {
        System.err.println("Inter Number Please ! <.Error.>");
    } catch (IOException e) {
        System.err.println("Can't Read With BufferReader ! <.Excp.>");
    }
    calculatePrimes($limitPoint);
}
private static void calculatePrimes(int $limitPoint){
    $startTime = System.currentTimeMillis();

    primes = new HashSet<Integer>();
    for(int $num = 2; $num<= $limitPoint ;$num++){
        primes.add($num);
    }
    System.out.println("Before ... ");
    System.out.println(primes);
    System.out.println("^__^.");
    System.out.println("After ... ");

    Object arr[] = primes.toArray();

    for(int x = 0 ; x <= arr.length-1;x++){
        int p = (int)arr[x];
        primes.removeIf(new Predicate<Integer>(){
            @Override
            public boolean test(Integer t) {
                boolean result = (
                        t == p * 2||
                        t == p * 3||
                        t == p * 4||
                        t == p * 5||
                        t == p * 6||
                        t == p * 7||
                        t == p * 8||
                        t == p * 9
                        ) ? true:false;
                return result;
            }
        }
    );
    }
    System.out.println(primes);
    $endTime = System.currentTimeMillis();
    long $long = $endTime - $startTime;
    System.err.println("Time = "+$long);
}

}

(^)_(^)

محمد مطر

(Complexity: O(nlogn

انا مبتدأ بروبي

و هذا تطبيقي

puts "enter your maxium number"
n = gets.to_i
puts "prime number : "
if n == 2
    puts 2
elsif n < 2
    puts "no prime number less than 2"
else
    puts 2
    puts 3
end
for i in 4..n
    next if i % 2 == 0 or i % 3 == 0
    puts i
end