एक आइटम में एक अनुक्रम के कई संगत वस्तुओं को आलसी ढंग से पतन करने का सबसे अच्छा तरीका

Question

[नोट: शीर्षक और पाठ को अधिक स्पष्ट करने के लिए संपादित किया गया था कि मैं विशेष रूप से स्ट्रिंग के बाद नहीं हूं, लेकिन सामान्य अनुक्रमों के बाद, और आलसी प्रसंस्करण एक ही]

चरित्र दृश्यों का उपयोग करते हुए/एक उदाहरण के रूप तार, कहते हैं कि मैं की तरह

एक स्ट्रिंग चालू करने के लिए "चाहते हैं \ टा \ r           s \ टीडी \ t \ r \ n                   च \ r \ n asdf "

अधिक सामान्य शब्दों में"

में

", मैं सभी सन्निहित खाली स्थान के (या किसी अन्य arbitray चालू करना चाहते हैं वस्तुओं का सेट) एक ही क्रम में अनुक्रम में, और वह आलसी।

मैं निम्नलिखित विभाजन-द्वारा/मैपकैट कॉम्बो के साथ आया हूं, लेकिन आश्चर्य कीजिए कि क्या एक ही चीज़ को पूरा करने के लिए आसान या अन्यथा बेहतर तरीके (पठनीयता, प्रदर्शन, कुछ भी) हैं।

(defn is-wsp? 
    [c] 
    (if (#{\space \tab \newline \return} c) true)) 

(defn collapse-wsp 
    [coll] 
    (mapcat 
    (fn [[first-elem :as s]] 
    (if (is-wsp? first-elem) [\space] s)) 
    (partition-by is-wsp? coll))) 

कार्रवाई में:

=> (apply str (collapse-wsp "\t a\r   s\td \t \r \n   f \r\n")) 
" a s d f " 

अद्यतन: मैं तार/चरित्र दृश्यों/WSP इस्तेमाल किया, एक उदाहरण के रूप में, लेकिन क्या मैं वास्तव में चाहते हैं किसी भी प्रकार के दृश्यों पर एक सामान्य समारोह है कि संगत वस्तुओं की मनमानी संख्याओं को ध्वस्त कर देता है, जो कुछ पूर्वनिर्धारित आइटम द्वारा वस्तुओं के पूर्वनिर्धारित सेट का हिस्सा हैं। मुझे विशेष रूप से यह जानने में दिलचस्पी है कि विभाजन-द्वारा/मैपकैट के बेहतर विकल्प हैं, अगर इसे 'स्ट्रिंग' विशेष मामले के लिए अनुकूलित किया जा सकता है तो इतना नहीं।

अद्यतन 2: - ऊपर एक, पूरी तरह से आलसी नहीं है मुझे डर है, के अलावा है कि यह निरर्थक कर रहा है-WSP

यहाँ एक पूरी तरह से आलसी संस्करण है? जाँच करता है। मैंने पैरामीटर नाम इत्यादि को सामान्यीकृत किया है, इसलिए यह ऐसा कुछ नहीं दिखता है जिसे आप आसानी से स्ट्रिंग द्वारा प्रतिस्थापित कर सकते हैं। जो भी() कॉल - यह मनमाने ढंग से अनुक्रमों के बारे में है।

(defn lazy-collapse 
    ([coll is-collapsable-item? collapsed-item-representation] (lazy-collapse coll is-collapsable-item? collapsed-item-representation false)) 
    ([coll is-collapsable-item? collapsed-item-representation in-collapsable-segment?] 
    (let [step (fn [coll in-collapsable-segment?] 
       (when-let [item (first coll)] 
       (if (is-collapsable-item? item) 
        (if in-collapsable-segment? 
        (recur (rest coll) true) 
        (cons collapsed-item-representation (lazy-collapse (rest coll) is-collapsable-item? collapsed-item-representation true))) 
        (cons item (lazy-collapse (rest coll) is-collapsable-item? collapsed-item-representation false)))))] 
    (lazy-seq (step coll in-collapsable-segment?))))) 

यह तेजी से, पूरी तरह से आलसी है, लेकिन मुझे लगता है कि व्यक्त करने के लिए और अधिक संक्षेप में, के रूप में मैं काफी आलसी अपने आप को कर रहा हूँ में सक्षम होना चाहते हैं। आलसी collapsers की

मानक अब तक: चाहे कोड पठनीय या आसान कोड को देखकर न्यायाधीश करने, लेकिन आदेश को देखने के लिए कैसे वे प्रदर्शन के मामले में तुलना, यहाँ मेरी मानक हैं में नहीं है।मैं पहली बार जाँच समारोह करता है, तो क्या यह करने के लिए माना जाता है, और फिर मैं बाहर थूक कितना समय

1. आलसी seq बनाने के लिए 1M बार
2. आलसी seq बना सकते हैं और लेने के पहले आइटम 1M बार लेता है
3. आलसी seq बना सकते हैं और दूसरे मद 1M बार
4. ले आलसी seq बना सकते हैं और अंतिम आइटम ले (यानी पूरी तरह से आलसी seq एहसास) 1M बार

टेस्ट 3 के माध्यम से 1 गेज के लिए होती हैं आलस्य कम से कम एक ली थोड़ा सा मैंने परीक्षण को दो बार भाग लिया, और निष्पादन समय में कोई महत्वपूर्ण बदलाव नहीं था।

user=> (map 
    (fn [collapse] 
    (println (class collapse) (str "|" (apply str (collapse test-str is-wsp? \space)) "|")) 
    (time (dotimes [_ 1000000] (collapse test-str is-wsp? \space))) 
    (time (dotimes [_ 1000000] (first (collapse test-str is-wsp? \space)))) 
    (time (dotimes [_ 1000000] (second (collapse test-str is-wsp? \space)))) 
    (time (dotimes [_ 1000000] (last (collapse test-str is-wsp? \space))))) 
    [collapse-overthink collapse-smith collapse-normand lazy-collapse]) 

user$collapse_overthink | a s d f | 
"Elapsed time: 153.490591 msecs" 
"Elapsed time: 3064.721629 msecs" 
"Elapsed time: 4337.932487 msecs" 
"Elapsed time: 24797.222682 msecs" 

user$collapse_smith | a s d f | 
"Elapsed time: 141.474904 msecs" 
"Elapsed time: 812.998848 msecs" 
"Elapsed time: 2112.331739 msecs" 
"Elapsed time: 10750.224816 msecs" 

user$collapse_normand | a s d f | 
"Elapsed time: 314.978309 msecs" 
"Elapsed time: 1423.779761 msecs" 
"Elapsed time: 1669.660257 msecs" 
"Elapsed time: 8074.759077 msecs" 

user$lazy_collapse | a s d f | 
"Elapsed time: 169.906088 msecs" 
"Elapsed time: 638.030401 msecs" 
"Elapsed time: 1195.445016 msecs" 
"Elapsed time: 6050.945856 msecs" 

नीचे की रेखा अब तक: सबसे अच्छा कोड सबसे धीमा है, सबसे ऊंचा कोड सबसे तेज़ है। मुझे पूरा यकीन है कि यह इस तरह से नहीं होना चाहिए ...

Answer 1

एक पूरी तरह से आलसी समाधान, एक पुनरावर्ती शैली में लिखा:

(defn collapse [l p v] 
    (cond 
    (nil? (seq l)) 
    nil 
    (p (first l)) 
    (lazy-seq (cons v (collapse (drop-while p l) p v))) 
    :otherwise 
    (lazy-seq (cons (first l) (collapse (rest l) p v))))) 

l, सूची है p विधेय है, और v subsequences उस के साथ विधेय से मेल को बदलने के लिए मूल्य है।

आप पठनीयता की कीमत पर शुद्ध गति के बाद कर रहे हैं, तो आप ऐसा कर सकते हैं:

(defn collapse-normand2 
    ([l p v] 
    (lazy-seq (collapse-normand2 (seq l) p v nil))) 
    ([l p v _] 
    (when l 
     (lazy-seq 
     (let [f (first l) 
       r (next l)] 
      (if (p f) 
      (cons v (collapse-normand2 r p v nil nil)) 
      (cons f (collapse-normand2 r p v nil))))))) 
    ([l p v _ _] 
    (when l 
     (lazy-seq 
     (let [f (first l) 
       r (next l)] 
      (if (p f) 
      (collapse-normand2 r p v nil nil) 
      (collapse-normand2 r p v nil))))))) 

शायद यह अधिक पठनीय बनाने के लिए एक तरीका है। यह सभी 4 परीक्षणों पर बहुत अच्छा है।

Answer 2

क्यों जावा का String फ़ंक्शन replaceAll का उपयोग न करें?

user=> (.replaceAll "\t a\r   s\td \t \r \n   f \r\n" "\\s+" " ") 
" a s d f " 

मुझे लगता है, कि यह भारी ऐसे कार्यों के लिए अनुकूलित किया गया है ...

अद्यतन:

(defn is-blank? [^Character c] (not (nil? (#{\space \tab \newline \return} c)))) 

(defn collapse [coll fun replacement] 
    (first (reduce (fn [[res replaced?] el] 
        (if (fun el) 
        (if replaced? 
         [res replaced?] 
         [(conj res replacement) true]) 
        [(conj res el) false])) 
       [[] false] coll))) 

(def aa-str "\t a\r   s\td \t \r \n   f \r\n") 

user> (apply str (collapse aa-str is-blank? \space)) 
" a s d f " 

यह भी अन्य seqs साथ काम करता है: अद्यतन स्पष्टीकरण के बाद जवाब का संस्करण

user> (collapse [1 1 2 3 1 1 1 4 5 6 1 1] #(= % 1) 9) 
[9 2 3 9 4 5 6 9] 

एक और प्रदर्शन अनुकूलन आयन मानक अनुक्रमों के बजाय ट्रांजिस्टर का उपयोग किया जा सकता है ...

Answer 3

क्लोजर में स्ट्रिंग्स जावा स्ट्रिंग्स हैं, इसलिए आप स्ट्रिंग को आलसी नहीं बना सकते हैं (यानी, आपको स्ट्रिंग बनाने के लिए सभी इनपुट का उपभोग करने की आवश्यकता है)। के बाद से निकालें अपने अंतिम तर्क पर seq कॉल

USER> (remove #(Character/isWhitespace %) "\t a\r   s\td \t \r \n   f \r\n") 
(\a \s \d \f) 

आप एक स्ट्रिंग या इनपुट यहाँ के रूप में एक seq उपयोग कर सकते हैं,:

आप एक चरित्र अनुक्रम lazily, हालांकि बना सकते हैं।

Answer 4

यह एक पूरी तरह से आलसी कार्यान्वयन थोड़ा क्लीनर है कि है: (एम स्मिथ के रूप में मूलतः एक ही है, लेकिन कोई destructuring)

(defn collapse [xs pred rep] 
    (when-let [x (first xs)] 
    (lazy-seq 
     (if (pred x) 
     (cons rep (collapse (drop-while pred (rest xs)) pred rep)) 
     (cons x (collapse (rest xs) pred rep)))))) 

:

<!-- language: lang-clojure --> 
(defn collapse [ss pred replacement] 
    (lazy-seq  
      (if-let [s (seq ss)] 
       (let [[f & rr] s] 
       (if (pred f) 
        (cons replacement (collapse (drop-while pred rr) pred replacement)) 
        (cons f (collapse rr pred replacement))))))) 

Answer 5

यहाँ मेरी सबसे तेजी से समाधान अब तक है यहां एक सुंदर समाधान है, लेकिन 3x (!) धीमा: (प्रभावी रूप से सुपरहोर्स्ट के प्रारंभिक संस्करण के समान ...)

(defn collapse [col pred rep] 
    (let [f (fn [[x & more :as xs]] (if (pred x) [rep] xs))] 
    (mapcat f (partition-by #(if (pred %) true) col)))) 

मिनी बेंचमार्क (full code) उत्पादन:

$ clj collapse.clj 
    SuperHorst: "Elapsed time: 58535.737037 msecs" 
     Overthink: "Elapsed time: 70154.744605 msecs" 
     M Smith: "Elapsed time: 89484.984606 msecs" 
    Eric Normand: "Elapsed time: 83121.309838 msecs" 

उदाहरण:

(def test-str "\t a\r  s\td \t \r \n   f \r\n") 
(def is-ws? #{\space \tab \newline \return}) 

user=> (apply str (collapse test-str is-ws? \space)) 
" a s d f " 

seq एक अलग प्रकार पर उपयोग किया:

user=> (collapse (range 1 110) #(= 2 (count (str %))) \X) 
(1 2 3 4 5 6 7 8 9 \X 100 101 102 103 104 105 106 107 108 109) 

यह पूरी तरह से आलसी है :

user=> (type (collapse test-str is-ws? \space)) 
clojure.lang.LazySeq 
user=> (type (collapse (range 1 110) #(= 2 (count (str %))) \X)) 
clojure.lang.LazySeq 

---

पुरानी गाड़ी संस्करण:

(defn collapse-bug [col pred rep] 
    (let [f (fn [x] (if (pred x) rep x))] 
    (map (comp f first) (partition-by f col)))) 

बग है कि यह pred मिलान नहीं लगातार आइटम को खाता है।