पायथन

Question

में संभाव्यता घनत्व कार्यों का तेज़ संकल्प मान लीजिए कि सामान्य संभाव्यता घनत्व कार्यों की सामान्य संख्या के संकल्प की गणना की जानी चाहिए।

import numpy as np 
pdfs = np.array([[0.6,0.3,0.1],[0.5,0.4,0.1],[0.3,0.7,0.0],[1.0,0.0,0.0]]) 

घुमाव के इस तरह पाया जा सकता है: उदाहरण के लिए नीचे दिए गए चार वितरण जो मूल्यों पर ले निर्दिष्ट संभावनाओं के साथ 0,1,2 हैं

pdf = pdfs[0]   
for i in range(1,pdfs.shape[0]): 
    pdf = np.convolve(pdfs[i], pdf) 

0 देखकर की संभावनाओं, 1, ..., 8 तब तक

array([ 0.09 , 0.327, 0.342, 0.182, 0.052, 0.007, 0. , 0. , 0. ]) 

दिया जाता है इस भाग मेरी कोड में अड़चन है और ऐसा लगता है इस कार्य को करने के लिए उपलब्ध vectorize कुछ किया जाना चाहिए। क्या किसी को इसे तेजी से बनाने के लिए कोई सुझाव है?

वैकल्पिक रूप से

है, जहां आप

pdf1 = np.array([[0.6,0.3,0.1],[0.5,0.4,0.1]]) 
pdf2 = np.array([[0.3,0.7,0.0],[1.0,0.0,0.0]]) 
convolve(pd1,pd2) 

का उपयोग करें और जोड़ो में convolutions

array([[ 0.18, 0.51, 0.24, 0.07, 0. ], 
     [ 0.5, 0.4, 0.1, 0. , 0. ]]) 

मिल भी काफी मदद मिलेगी सकता है एक समाधान।

Answer 1

आप तेजी से चारियर ट्रांसफॉर्म (एफएफटी) का उपयोग करके अपने सभी पीडीएफ के संकल्प की गणना कर सकते हैं: मुख्य तथ्य यह है कि FFT of the convolution व्यक्तिगत संभाव्यता घनत्व कार्यों के एफएफटी का उत्पाद है। तो प्रत्येक पीडीएफ को बदलें, एक साथ परिवर्तित पीडीएफ गुणा करें, और उसके बाद उलटा परिवर्तन करें। रैपरराउंड से प्रभाव से बचने के लिए आपको प्रत्येक इनपुट पीडीएफ को उचित लंबाई तक शून्य के साथ पैड करने की आवश्यकता होगी।

यह यथोचित कुशल होना चाहिए: आप m PDF, प्रत्येक युक्त n प्रविष्टियों, तो समय घुमाव के इस विधि (m^2)n log(mn) के रूप में विकसित करना चाहिए का उपयोग कर की गणना करने के है। समय एफएफटी का प्रभुत्व है, और हम प्रभावी रूप से m + 1 स्वतंत्र एफएफटी (m आगे रूपांतरण और एक उलटा परिवर्तन) की गणना कर रहे हैं, प्रत्येक लंबाई mn से अधिक नहीं है। लेकिन हमेशा के रूप में, यदि आप वास्तविक समय चाहते हैं तो आपको प्रोफाइल करना चाहिए।

यहाँ कुछ कोड है:

import numpy.fft 

def convolve_many(arrays): 
    """ 
    Convolve a list of 1d float arrays together, using FFTs. 
    The arrays need not have the same length, but each array should 
    have length at least 1. 

    """ 
    result_length = 1 + sum((len(array) - 1) for array in arrays) 

    # Copy each array into a 2d array of the appropriate shape. 
    rows = numpy.zeros((len(arrays), result_length)) 
    for i, array in enumerate(arrays): 
     rows[i, :len(array)] = array 

    # Transform, take the product, and do the inverse transform 
    # to get the convolution. 
    fft_of_rows = numpy.fft.fft(rows) 
    fft_of_convolution = fft_of_rows.prod(axis=0) 
    convolution = numpy.fft.ifft(fft_of_convolution) 

    # Assuming real inputs, the imaginary part of the output can 
    # be ignored. 
    return convolution.real 

आपके उदाहरण में लागू करने के लिए, यहाँ मैं क्या मिलेगा:

>>> convolve_many([[0.6, 0.3, 0.1], [0.5, 0.4, 0.1], [0.3, 0.7], [1.0]]) 
array([ 0.09 , 0.327, 0.342, 0.182, 0.052, 0.007]) 

मूलभूत विचार दिया गया है। यदि आप इसे ट्वीक करना चाहते हैं, तो आप numpy.fft.rfft (और इसके विपरीत, numpy.fft.irfft) को भी देख सकते हैं, जो इस तथ्य का लाभ उठाते हैं कि इनपुट अधिक कॉम्पैक्ट ट्रांसफॉर्म किए गए सरणी उत्पन्न करने के लिए वास्तविक है। आप शून्य के साथ rows सरणी पैडिंग करके कुछ गति प्राप्त करने में भी सक्षम हो सकते हैं ताकि एफएफटी करने के लिए कॉलम की कुल संख्या इष्टतम हो। यहां "इष्टतम" की परिभाषा एफएफटी कार्यान्वयन पर निर्भर करेगी, लेकिन उदाहरण के लिए दो की शक्तियां अच्छे लक्ष्य होंगी। अंत में, कुछ स्पष्ट सरलीकरण हैं जिन्हें rows बनाते समय बनाया जा सकता है यदि सभी इनपुट सरणी समान लंबाई में हों। लेकिन मैं आपको इन संभावित संवर्द्धन को छोड़ दूंगा।