پردازش چند هسته‌ای در پایتون

[MADMAN]

دوستان یه تابع دارم که عددی که بهش می‌دی نتیجه صحیح و غلط بر می‌گردونه که عدد جزو اعداد اول هست یا نه.
الان توی یک حلقه می‌خواهم هزار تا عدد بهش بدم. تا اینجای کار بسیار ساده هست. از اونجایی سخت می‌شه که می‌خواهم از چهار هسته(تعداد هسته‌های سی پی یو یی که دارم) استفاده کنم و هم‌زمان پیش برن.
چه راه حلی داریم؟

کد: [انتخاب]

from time import perf_counter as timer
from multiprocessing.pool import ThreadPool as Pool

def is_prime(number):
    for i in range(2,number):
        if (number % i) == 0:
            return False
    return True
def acual_do(i):
    if is_prime(i):
        print(i)

def single(tedad):
    for i in range(tedad):
        acual_do(i)

def multi(tedad):
    pool = Pool(4)
    for i in range(tedad):
        pool.apply_async(acual_do, (i,))
    pool.close()
    pool.join()

if __name__ == "__main__":
    tedad = 100000
    start = timer()
    single(tedad)
    end_single = timer() - start
    start = timer()
    multi(tedad)
    end_multi = timer() - start
    print()
    print(end_single, end_multi)

این هم از کد من با یک راه حل که بعد از کلی سرچ به این نتیجه رسیدم اما مشکلی که داره اینه که فقط یک هسته سی پی یو درگیره و عملا هیچ تفاوت خاصی نداره تازه بیشتر هم زمان می‌بره
کسی راه حلی داره؟

[Dragon-]

چیزی که میگم زیاد ربطی به مشکلی که بهش خوردید نداره ولی می‌تونه سرعت برنامه رو بهبود بده.

اگه عدد مورد نظر، از ۲ تا جزر عدد + ۱، به هیچکدوم بخش‌پذیر نباشه، حتما اول هست.
به عبارتی لازم نیست از عددِ ۲ تا خود عدد مورد نظر رو بررسی کنید که بخش‌پذیر هست یا نه. بلکه کافیه فقط تا جذر اون عدد + ۱ رو بررسی کنید.

تابع is_prime رو می‌تونید به این شکل تغییر بدید.

کد: [انتخاب]

def is_prime(number):
    for i in range(2,floor(sqrt(number))+1):
        if (number % i) == 0:
            return False
    return True

البته لازمه، متد‌های sqrt و floor از ماژول math رو import کرده باشید.

بهتره یه بررسی هم کنید که عدد بزرگتر یا مساوی ۲ هست یا نه چون اول بودن یا نبودن فقط برای اعداد بزرگتر یا مساوی ۲ تعریف میشه.
عدد ۱ ممکنه به صورت قراردادی اول باشه، ممکن هم هست نباشه.

[MADMAN]

نمی‌دونم چرا ولی با تابع تک رشته‌ای کمی نسبت به قبل زمان بیشتری می‌خواهد این روش ولی از روش تابع چند رشته‌ای زمان حدودا دو سوم شد.

[sajadspeed]

از تردها نمی‌تونید کمک بگیرید؟

[MADMAN]

از تردها نمی‌تونید کمک بگیرید؟

مشکل کنترل تعداد رشته‌ها به وجود میاد سیستم زیادی درگیر می‌شه و سرعت میاد پایین.

[دانیال بهزادی]

از asyncio استفاده کن
https://docs.python.org/3/library/asyncio.html

[Issac]

اگه عدد مورد نظر، از ۲ تا جزر عدد + ۱، به هیچکدوم بخش‌پذیر نباشه، حتما اول هست.
به عبارتی لازم نیست از عددِ ۲ تا خود عدد مورد نظر رو بررسی کنید که بخش‌پذیر هست یا نه. بلکه کافیه فقط تا جذر اون عدد + ۱ رو بررسی کنید.

اصلا نیازی به این کار هم نیست، هر عددی که به اعداد اول قبل از خودش بخش‌پذیر نباشه، عدد اول هست. نیاز به تست همه اعداد نیست.
اگر فقط اعداد اول کوچیک‌تر از جذر+۱ اون عدد رو هم تست کنی، دیگه سرعت برنامه بیشتر میشه.
فقط هم نیاز به اضافه کردن یک لیست داره.

[Dragon-]

خب اعدادِ اولِ قبل از اون عدد مورد نظر رو از کجا بیاریم؟

میشه مستقیم یه سری از اون اعداد اول رو توی خود کد نوشت یا به شیوه‌های دیگه به برنامه داد ولی نمی‌تونیم که همه اعداد اول رو به برنامه بدیم چون مشخص نیست تعداد اعداد اول محدود هست یا نه.

شاید بشه با روشی که گفتید، سرعت بررسی رو یکم افزایش داد به این شکل که اول اون اعداد اولی که میشناسیم بررسی بشن و بعد اگه به هیچکدوم بخش‌پذیر نبود، به طور معمولی همه اعداد بعدی رو امتحان کنیم.

این برنامه رو میشه یه جور دیگه هم بهبود داد.
لازم نیست بررسی بشه که عدد مورد نظر به اعداد زوج بخش‌پذیر هست یا نه. البته به غیر از عدد ۲. چون از بین اعداد زوج، فقط ۲ عدد اول هست و بقیه اعداد زوج، مرکب هستند. (البته اینجا به صفر کاری نداریم. چون کلا اول بودن یا نبودن، برای اعداد بزرگتر یا مساوی ۲  تعریف میشه)

[دانیال بهزادی]

خب اعدادِ اولِ قبل از اون عدد مورد نظر رو از کجا بیاریم؟

برنامه‌نوبسی پوبا!

میشه مستقیم یه سری از اون اعداد اول رو توی خود کد نوشت یا به شیوه‌های دیگه به برنامه داد ولی نمی‌تونیم که همه اعداد اول رو به برنامه بدیم چون مشخص نیست تعداد اعداد اول محدود هست یا نه.

می‌دونیم. نامحدودن!

[nixoeen]

پیاده‌سازی همروندی می‌تونه پیچیده باشه و یک اشتباه در اون می‌تونه باعث بشه نرم‌افزار شما آروم‌تر باشه یا به درستی کار نکنه و پیدا کردن مشکل هم بسیار سخت بشه. پیشنهاد من ابتدا خوندن یک کتاب در زمینهٔ Concurrency هستش.

در این مساله، روش به اینصورته که:
* ابتدا نگاه می‌کنید که چند پردازندهٔ شما امکان بررسی چند ریسمان (Thread) به صورت همزمان رو داره. بعد به همون تعداد ریسمان درست می‌کنید.
* هر ریسمان تنها به بخشی از اعداد رو بررسی می‌کنه و نه همهٔ اون‌ها رو. مثلا اگر عدد ۳۱ هستش و چهار هسته بدون Hyper-threading دارید، چهار ریسمان درست میشه که اولی اعداد ۲ تا ۵، دومی ۶ تا ۹، سومی ۱۰ تا ۱۳ و چهارمی ۱۴ تا ۱۶. (که قاعدتا میشه بهینه کرد و اعداد زوج بزرگتر از ۲ رو بررسی نکرد)
* حالا هر کدوم اعداد رو بررسی می‌کنند و اگر یکی از اون‌ها ضریبی رو پیدا کرد، باید به ریسمان‌های دیگه خبر بده تا اون‌ها کارشون رو متوقف کنند. ریسمان‌ها نباید همزمان یک حافظه رو تغییر بدن یا در حال تغییر، اون رو بخونن. این باید به درستی پیاده‌سازی بشه.
* ریسمان اصلی منتظر می‌مونه تا تمامی ریسمان‌ها کارشون تموم بشه و نتیجه رو بیان می‌کنه.

البته الگوریتم‌های بهینه‌تری هم برای اینکار وجود داره. و توجه کنید که برای اعداد کوچیک، احتمالا ایجاد ریسمان‌ها و ارتباط بین اون‌ها باعث میشه که سرعت بجای افزایش، کاهش داشته باشه.

[Dragon-]

خب اعدادِ اولِ قبل از اون عدد مورد نظر رو از کجا بیاریم؟

برنامه‌نوبسی پوبا!

خب اینجوری اجرای برنامه خیلی طول نمی‌کشه؟

[دانیال بهزادی]

چرا طول بکشه؟ من این رو دارم همین الآن می‌نویسم. قطعاً بهینه نیست و ممکنه خطا هم داشته باشه، ولی به نظرم باید خیلی سریع حساب کنه. در حد این که باید تا صد هزار رو زیر ۳ ثانیه بره.

کد: [انتخاب]

def list_prime(number: int) -> list:
    primes=[2, 3, 5, 7]
    for i in range(11, number, 2):
        for prime in primes:
            p=True
            if i%prime == 0:
                p=False
                break
        if p:
            primes.append(i)
    return primes


[قاسم طلایی]

سلام.شاید بتونید اعداد رو به چند بخش تقسیم کنید و هر بخش رو روی یک thread اجرا کنید.از کد زیر کمک بگیرید

کد: [انتخاب]

import threading

class Prime(threading.Thread):
    def __init__(self, numbers):
        threading.Thread.__init__(self)
        self.numbers = numbers
       
    def is_prime(self, num):
        a = int(num / 2)
        flag = True
        for i in range(2, a+1):
            if num%i == 0:
                flag = False
                break
        return flag
   
    def run(self):
        for num in self.numbers:
            print(str(num) + ' is : ' + str(self.is_prime(num)))
           
part1 = [2,3,4,5,6,7,8,9]
part2 = [10,11,12,546,56,8,7]

thread1 = Prime(part1)
thread2 = Prime(part2)

thread1.start()
thread2.start()


[دانیال بهزادی]

استفاده از threading در پایتون دیگه توصیه نمی‌شه. به‌جاش می‌تونید از asyncio استفاده کنید.

[esmaeelE]

طبق یک نکتهٔ کلی
برای کارهایی که I/O bound هستند از ریسمان(thread)
و برای کارهای پردازنده محدود (CPU bound) از پردازه process استفاده می‌کنیم.

در محاسبهٔ اعداد اول پردازنده درگیر است پس به نظر نمی‌رسد که از ریسمان بهبودی برای کار ایجاد کند.

شما باید راهی بیابید که پردازش شمار زیادی از اعداد را بین چند پردازنده(چند هسته از یک پردازنده) تقسیم کنید.

پس هر هسته باید بتواند قسمتی از آن اعداد را بگیرد روی آن عملیات انجام دهد. یک گام هر ترکیب نتایج به دست آمده از طرف هر پردازنده است.



پاسخ زیر را ببینید.

با استفاده از الگوریتمی بهتر سرعت اجرای برنامهٔ‌ اعداد اول را به شکل قابل ملاحظه‌ای بهبود داده است.

https://stackoverflow.com/a/23206097/7508077

برای رسیدن به سرعت بیشتر می‌تونید از پیاده‌سازی‌های دیگری از پایتون غیر از Cython پیش‌فرض نیز استفاده کنید.
برای نمونه pypy بسیار سریع‌تر است.

کد: [انتخاب]

$ time python3 cs.py 100000

real    0m11.942s
user    0m11.931s
sys     0m0.008s
$ time pypy3 cs.py 100000

real    0m2.046s
user    0m2.010s
sys     0m0.016s


کد: [انتخاب]

$ cat cs.py

import sys

def prime_list3(num):
    num += 1
    candidates = range(3, num, 2)
    results = [2]
    while len(candidates):
        t = candidates[0]
        results.append(t)
        candidates = [i for i in candidates if not i in range(t, num, t)]
    return results

number = int(sys.argv[1])

prime_list3(number)