क्लोजर

Question

में आलसी संकल्प एफएन के साथ परेशानी मैं कुछ सिग्नल प्रोसेसिंग सॉफ्टवेयर लिख रहा हूं, और मैं discrete convolution function लिखकर शुरू कर रहा हूं।

यह पहले दस हजार या तो मूल्यों की सूची के लिए ठीक काम करता है, लेकिन जैसे ही वे बड़े होते हैं (कहें, 100k), मुझे निश्चित रूप से स्टैक ओवरफ्लो त्रुटियां मिलनी शुरू होती हैं।

दुर्भाग्य से, मैं एक पुनरावर्ती & आलसी संस्करण है कि वास्तव में काफी तेजी से (लालित्य के कम से कम थोड़ी रूप में अच्छी तरह अच्छा होगा होने का उपयोग करने के लिए आवश्यक घुमाव के एल्गोरिथ्म मैं परिवर्तित मुसीबत का एक बहुत हो रहा है)।

मैं भी 100% सुनिश्चित नहीं हूं कि मेरे पास यह कार्य पूरी तरह से सही है, फिर भी – कृपया मुझे बताएं कि क्या मुझे कुछ गड़बड़ है या कुछ गलत कर रहा है। मैं सोचता हूं यह सही है।

(defn convolve 
    " 
    Convolves xs with is. 

    This is a discrete convolution. 

    'xs :: list of numbers 
    'is :: list of numbers 
    " 
    [xs is] 
    (loop [xs xs finalacc() acc()] 
    (if (empty? xs) 
     (concat finalacc acc) 
     (recur (rest xs) 
      (if (empty? acc) 
       () 
       (concat finalacc [(first acc)])) 
      (if (empty? acc) 
       (map #(* (first xs) %) is) 
       (vec-add 
       (map #(* (first xs) %) is) 
       (rest acc))))))) 

मैं ज्यादा मदद की किसी भी प्रकार के लिए बाध्य नहीं किया था: मैं अभी भी Clojure में मेरी बीयरिंग हो रही है, और इस खूबसूरत और आलसी बना रही है और/या पुनरावर्ती अद्भुत होगा।

मुझे आश्चर्य है कि एक एल्गोरिदम व्यक्त करना कितना मुश्किल है जो लिस्प में एक अनिवार्य भाषा में व्यक्त करना आसान है। लेकिन शायद मैं यह गलत कर रहा हूँ!

संपादित करें: बस दिखाने के लिए कितना आसान है एक अनिवार्य भाषा में व्यक्त करने के लिए है, और लोगों को एल्गोरिथ्म है कि अच्छी तरह से काम करता है और पढ़ने में आसान है, यहाँ अजगर संस्करण है देने के लिए। कम, संक्षिप्त और अधिक आसान होने के कारण, यह क्लोजर कोड की तुलना में तीव्रता के आदेश निष्पादित करता है: जावा सरणी का उपयोग करके मेरा अनिवार्य क्लोजर कोड भी।

from itertools import repeat 

def convolve(ns, ms): 
    y = [i for i in repeat(0, len(ns)+len(ms)-1)] 
    for n in range(len(ns)): 
     for m in range(len(ms)): 
      y[n+m] = y[n+m] + ns[n]*ms[m] 
    return y 

दूसरी ओर, अनिवार्य क्लोजर कोड है। यह अंतिम, गैर पूरी तरह से विसर्जित, संकल्प से मूल्य भी छोड़ देता है। तो धीमी और बदसूरत होने से अलग, यह 100% कार्यात्मक नहीं है। न ही कार्यात्मक।

(defn imp-convolve-1 
    [xs is] 
    (let [ys (into-array Double (repeat (dec (+ (count xs) (count is))) 0.0)) 
     xs (vec xs) 
     is (vec is)] 
    (map #(first %) 
      (for [i (range (count xs))] 
      (for [j (range (count is))] 
       (aset ys (+ i j) 
        (+ (* (nth xs i) (nth is j)) 
         (nth ys (+ i j))))))))) 

यह बहुत निराशाजनक है। कृपया, कोई मुझे दिखाता है कि मैंने अभी कुछ स्पष्ट याद किया है।

संपादित करें 3:

यहाँ एक और संस्करण मैं कल सोचा है, दिखा कैसे मैं (हालांकि अन्य समाधान काफी सुंदर हैं इसे व्यक्त सक्षम होना चाहते हैं, मैं बस वहाँ बाहर एक और एक डाल रहा हूँ!

(defn vec-add 
    ([xs] (vec-add xs [])) 
    ([xs ys] 
    (let [lxs (count xs) 
      lys (count ys) 
      xs (pad-r xs lys) 
      ys (pad-r ys lxs)] 
     (vec (map #(+ %1 %2) xs ys)))) 
    ([xs ys & more] 
    (vec (reduce vec-add (vec-add xs ys) more)))) 
    (vec (reduce vec-add (vec-add xs ys) more)))) 

Answer 1

(defn ^{:static true} convolve ^doubles [^doubles xs ^doubles is] 
    (let [xlen (count xs) 
     ilen (count is) 
     ys (double-array (dec (+ xlen ilen)))] 
    (dotimes [p xlen] 
     (dotimes [q ilen] 
     (let [n (+ p q), x (aget xs p), i (aget is q), y (aget ys n)] 
      (aset ys n (+ (* x i) y))))) 
    ys)) 

यदि मैं क्लोजर इक्विव शाखा में ऐसा कर रहा था तो जे-जी-फास्टस के संस्करण पर रिफिंग। मेरे लिये कार्य करता है। I7 मैकबुक प्रो पर ~ 1,000ms अंक के लिए ~ 400ms, 100,000 के लिए ~ 25ms।

Answer 2

वीं के संभावित कारण:)

(defn convolve-2 
    [xs is] 
    (reduce #(vec-add %1 (pad-l %2 (inc (count %1)))) 
     (for [x xs] 
      (for [i is] 
      (* x i))))) 

यह इस उपयोगिता समारोह vec-add का उपयोग करता है ई स्टैक ओवरफ्लो त्रुटियां यह है कि आलसी थंक्स बहुत गहरे हो रहे हैं। (concat और map आलसी हैं)। उनके कॉल मूल्यों के मूल्यांकन को बल देने के लिए doall में उन कॉल को लपेटने का प्रयास करें।

एक अधिक कार्यात्मक समाधान के लिए के रूप में, कुछ इस तरह का प्रयास करें:

(defn circular-convolve 
    "Perform a circular convolution of vectors f and g" 
    [f g] 
    (letfn [(point-mul [m n] 
     (* (f m) (g (mod (- n m) (count g))))) 
     (value-at [n] 
     (reduce + (map #(point-mul % n) (range (count g)))))] 
    (map value-at (range (count g))))) 

उपयोग reduce उपयोग कर सकते हैं आसानी से योग प्रदर्शन करने के लिए, और के बाद से map एक आलसी अनुक्रम पैदा करता है, इस समारोह भी आलसी है।

Answer 3

एक उच्च प्रदर्शन कार्यात्मक संस्करण के साथ मदद नहीं कर सकता, लेकिन आप आलस्य पूर्वगामी और प्रकार संकेत जोड़कर अनिवार्य संस्करण के लिए एक 100 गुना speedup प्राप्त कर सकते हैं: xs

साथ

(defn imp-convolve-2 [xs is] 
    (let [^doubles xs (into-array Double/TYPE xs) 
     ^doubles is (into-array Double/TYPE is) 
     ys (double-array (dec (+ (count xs) (count is)))) ] 
    (dotimes [i (alength xs)] 
     (dotimes [j (alength is)] 
     (aset ys (+ i j) 
      (+ (* (aget xs i) (aget is j)) 
      (aget ys (+ i j)))))) 
    ys)) 

आकार 100k और is आकार 2, आपके आईपी-कॉन्फोलव -1 को मेरी मशीन पर ~ 6,000ms लगता है जब एक डोल में लपेटा जाता है, जबकि यह ~ 35ms लेता है।

अद्यतन

यहाँ एक आलसी कार्यात्मक संस्करण है:

(defn convolve 
    ([xs is] (convolve xs is [])) 
    ([xs is parts] 
    (cond 
     (and (empty? xs) (empty? parts)) nil 
     (empty? xs) (cons 
        (reduce + (map first parts)) 
        (convolve xs is 
         (remove empty? (map rest parts)))) 
     :else (cons 
       (+ (* (first xs) (first is)) 
       (reduce + (map first parts))) 
       (lazy-seq 
       (convolve (rest xs) is 
        (cons 
        (map (partial * (first xs)) (rest is)) 
        (remove empty? (map rest parts))))))))) 

आकार 100k और 2 पर, यह में घड़ियों ~ 600 मि.से (450-750ms बदलती) बनाम ~ छोटा सा भूत के लिए 6,000ms imp-convolve-2 के लिए convolve-1 और ~ 35ms।

तो यह आलसी कार्यात्मक है, और संतोषजनक प्रदर्शन किया है। फिर भी, यह अनिवार्य संस्करण के रूप में दो गुना कोड है और मुझे खोजने के लिए 1-2 अतिरिक्त घंटे लग गए, इसलिए मुझे यकीन नहीं है कि मैं बिंदु देखता हूं।

मैं शुद्ध कार्यों के लिए सब कर रहा हूँ जब वे कोड कम या सरल, या एक जरूरी संस्करण पर अन्य कोई लाभ न ले ली है। जब वे नहीं करते हैं, तो मुझे अनिवार्य मोड में स्विच करने के लिए कोई आपत्ति नहीं है।

कौन सा कारणों मुझे लगता है कि Clojure, महान है आप मनचाहे ढंग से जब से तुम या तो दृष्टिकोण का उपयोग कर सकते हैं में से एक है।

अद्यतन 2:

मैं संशोधन करेंगे मेरी कह रही है कि मैं this functional implementation (दूसरा एक, पृष्ठ में और नीचे) की तरह डेविड कबाना के द्वारा "क्या कार्यात्मक ऐसा करने का बात है"।

यह के रूप में ऊपर आकार एक ही इनपुट के साथ, संक्षिप्त पठनीय और ~ 140ms बार है (100,000 और 2), उन मैंने कोशिश की अब तक सबसे अच्छा प्रदर्शन कार्यात्मक कार्यान्वयन से यह बना रही है।

यह मानते हुए कि यह कार्यात्मक है (लेकिन आलसी नहीं), किसी भी प्रकार के संकेतों का उपयोग नहीं करता है और सभी संख्यात्मक प्रकारों (केवल युगल नहीं) के लिए काम करता है, यह काफी प्रभावशाली है।

Answer 4

(defn convolve [xs is] 
    (if (> (count xs) (count is)) 
    (convolve is xs) 
    (let [os (dec (+ (count xs) (count is))) 
      lxs (count xs) 
      lis (count is)] 
     (for [i (range os)] 
     (let [[start-x end-x] [(- lxs (min lxs (- os i))) (min i (dec lxs))] 
       [start-i end-i] [(- lis (min lis (- os i))) (min i (dec lis))]] 
      (reduce + (map * 
         (rseq (subvec xs start-x (inc end-x))) 
         (subvec is start-i (inc end-i))))))))) 

संक्षेप में आलसी, कार्यात्मक समाधान व्यक्त करना संभव है। हां,> 2k के लिए प्रदर्शन अव्यवहारिक है। मुझे यह देखने में दिलचस्पी है कि पठनीयता को बलि किए बिना इसे तेज करने के तरीके हैं या नहीं।

संपादित करें: विषय (http://erl.nfshost.com/2010/07/17/discrete-convolution-of-finite-vectors/) पर drcabana के जानकारीपूर्ण पोस्ट को पढ़ने के बाद, मैं अलग-अलग आकार वैक्टर स्वीकार करने के लिए मेरे कोड को नवीनीकृत किया है।उनके कार्यान्वयन बेहतर प्रदर्शन करने वाले है:, आकार 1000000, XS आकार 3 के लिए है ~ बनाम ~ 3s

संपादित 2 2s:

(defn convolve [xs is] 
    (if (> (count xs) (count is)) 
    (convolve is xs) 
    (let [is (concat (repeat (dec (count xs)) 0) is)] 
     (for [s (take-while not-empty (iterate rest is))] 
     (reduce + (map * (rseq xs) s)))))) 

: बस पीछे XS और गद्दी की drcabana के विचारों ले रहा है, मैं पर पहुंचे

यह शायद उतना ही संक्षिप्त है जितना इसे प्राप्त करने जा रहा है, लेकिन यह अभी भी धीमी है, संभवत: ले जाने के कारण। एक अच्छी तरह से विचार दृष्टिकोण के लिए ब्लॉग लेखक के लिए Kudos। यहां एकमात्र लाभ यह है कि उपरोक्त वास्तव में आलसी है अगर मैं (एनएचएस 10000) पूछता हूं, तो परिणामस्वरूप पहुंचने के लिए केवल पहली 10k गणना की आवश्यकता होगी।

Answer 5

वास्तव में आपके द्वारा पूछे गए कई प्रश्नों का उत्तर नहीं है, लेकिन जिन लोगों से आपने नहीं पूछा उन पर मेरी कई टिप्पणियां हैं।

1. आप शायद वैक्टर पर nth उपयोग नहीं करना चाहिए। हां, यह ओ (1) है, लेकिन nth ओ (एन) में अन्य अनुक्रमों पर काम करता है, यह (ए) यह स्पष्ट नहीं करता है कि आप इनपुट को वेक्टर होने की उम्मीद करते हैं, और (बी) का मतलब है कि यदि आप एक बनाते हैं गलती, आपका कोड तुरंत विफल होने की बजाय रहस्यमय रूप से धीमा हो जाएगा।

2. for और map दोनों आलसी हैं, और aset केवल-साइड इफेक्ट है। यह संयोजन आपदा के लिए एक नुस्खा है: साइड-इफेक्टिंग for-व्यवहार के विपरीत, doseq का उपयोग करें।

3. for और doseq एकाधिक बाइंडिंग की अनुमति देता है, इसलिए आपको पाइथन में (जैसे स्पष्ट रूप से) उनके जैसे लोड को ढेर करने की आवश्यकता नहीं है।

   (doseq [i (range (count cs)) 
        j (range (count is))] 
       ...) 
   

   जो भी आप चाहते हैं वह करेंगे।

4. #(first %) अधिक संक्षिप्त रूप से first के रूप में लिखा गया है; इसी तरह #(+ %1 %2)+ है।

5. मध्यवर्ती परिणाम है कि नहीं जरूरत कर का एक समूह पर vec कॉलिंग वैक्टर आप धीमी हो जाएगी किया जाना है। विशेष रूप से vec-add में यह पर्याप्त है करने के लिए केवल vec फोन जब आप एक अंतिम वापसी मान कर: (vec (reduce foo bar)) में foo के लिए कोई कारण नहीं वैक्टर में अपनी मध्यवर्ती परिणाम चालू करने के लिए अगर यह कभी नहीं रैंडम एक्सेस के लिए उन्हें का उपयोग करता है वहाँ।