मैं सामान्य लिस्प में गेटहाश लुकअप का पुन: उपयोग कैसे कर सकता हूं?

Question

मेरे पास एक हैश टेबल है जहां कुंजी प्रतीकों और पूर्णांक के उपन्यासकारों के साथ जटिल जटिल सूचियां हैं, और मूल्य पहले से मौजूद मान के आधार पर संशोधित किया जाना चाहिए। तालिका :test #'equal के साथ बनाई गई है।

(defun try-add (i) 
    (let ((old-i (gethash complex-list table nil))) 
    (if (may-add old-i) 
     (push i (gethash complex-list table))))) 

रूपरेखा पता चलता है कि equal परीक्षण बहुत समय ले:

मैं इस एक बहुत करने के लिए कुछ इसी तरह से करते हैं। मेरे पास एक अनुकूलन विचार है, कि gethash लुकअप की राशि दो से एक से कम हो सकती है। यह इटरेटर का पुन: उपयोग करके सी ++ में किया जा सकता है, लेकिन यह सुनिश्चित नहीं है कि यह लिस्प में कैसे किया जाएगा। कोई विचार?

Answer 1

कुछ भी विशेष न करें, क्योंकि कार्यान्वयन आपके लिए करता है।

बेशक, यह दृष्टिकोण कार्यान्वयन-विशिष्ट है, और हैश तालिका प्रदर्शन कार्यान्वयन के बीच भिन्न होता है। (लेकिन फिर अनुकूलन प्रश्न हमेशा कार्यान्वयन-विशिष्ट होते हैं।)

निम्नलिखित उत्तर एसबीसीएल के लिए है। मैं यह जांचने की सलाह देता हूं कि आपकी लिस्प की हैश टेबल समान अनुकूलन करती है या नहीं। अगर वे नहीं करते हैं तो अपने विक्रेता से शिकायत करें!

एसबीसीएल में क्या होता है यह है कि हैश टेबल कैश अंतिम तालिका सूचकांक GETHASH द्वारा उपयोग किया जाता है।

जब PUTHASH (या समतुल्य (SETF GETHASH)) कहा जाता है, यह पहली जाँच करता है कि जो संचित सूचकांक पर कुंजी कुंजी है कि आप में से गुजर रहे हैं करने के लिए EQ है।

यदि ऐसा है तो

, पूरे हैश तालिका लुकअप रूटीन पास-पास है, और पाउथैश सीधे कैश इंडेक्स पर स्टोर करता है।

ध्यान दें कि ईक्यू सिर्फ एक सूचक तुलना है और इसलिए बेहद तेज़ - इसे सूची को पार करने की आवश्यकता नहीं है।

तो आपके कोड उदाहरण में, कोई ओवरहेड नहीं है।

Answer 2

कुछ समाधान हो सकता है:

आम पैटर्न देखने है -> पाते हैं-यह -> अधिलेखित-यह है, तो आप मान प्रकार एक सूची है कि मूल्य प्रकार शामिल करने के लिए बदल सकते थे। फिर कुंजी के लिए मान ऑब्जेक्ट ढूंढने के बाद, केवल अपने पहले तत्व को विनाशकारी रूप से प्रतिस्थापित करें, उदा।

(defun try-add (i) 
    (let ((old-i-list (gethash complex-list table nil))) 
    (if (may-add (first old-i-list)) 
     (setf (first old-i-list) i)      ; overwrite without searching again 
     (setf (gethash complex-list table) (list i))))) ; not there? too bad, we have to gethash again 

वैकल्पिक रूप से, अगर आम पैटर्न अधिक देखने की तरह है -> यह है-नहीं-वहाँ -> एड-यह है, तो आप अपने दम पर कुंजी hashing विचार करना चाह सकते हैं, और फिर हैश तालिका का उपयोग अपने कुंजी के रूप में मूल्य धोया। इन जटिल सूचियों की गहराई और अर्थशास्त्र के आधार पर यह अधिक जटिल हो सकता है। साधारण मामले में, आप एक हैश फ़ंक्शन से दूर हो सकते हैं जो कि (रिकर्सिवली) xor की सूची सूची के तत्वों के हैश मान का हो सकता है।

---

संपादित: टिप्पणी में सवाल का जवाब: विचार है कि मूल्यों के हैश तालिका मानचित्रण कुंजी के बजाय, हैश तालिका अब एक तत्व सूचियों, जहां तत्व मूल्य है की चाबी नक्शा जाएगा। फिर आप हैश टेबल को छूए बिना इन सूचियों की सामग्री को बदल सकते हैं। निम्नलिखित SBCL से है:

* (defparameter *my-hash* (make-hash-table)) 
*MY-HASH* 

* (setf (gethash :my-key *my-hash*) (list "old-value")) 
("old-value") 

* (gethash :my-key *my-hash*) 
("old-value") 
T 

* (defparameter old-value-container (gethash :my-key *my-hash*)) 
OLD-VALUE-CONTAINER 

* (setf (first old-value-container) "new value") 
"new value" 

* (gethash :my-key *my-hash*) 
("new value") 
T 

Answer 3

एक बात तुम कर सकते हो जो अपने हैश तालिका अंक में प्रत्येक प्रविष्टि के लिए एक मूल्य बनाने के लिए उपयोग defstruct है। मूल्यों की आपकी सूची (जिसे आप अपने वर्तमान उदाहरण में दबा रहे हैं) वहां के अंदर संग्रहीत किया जा सकता है। संरचना निर्माण या तो प्रारंभिक गेटैश कॉल (डिफ़ॉल्ट मान के रूप में) में किया जा सकता है, या यदि आप देखते हैं कि वहां कोई मूल्य नहीं है तो मैन्युअल रूप से किया जा सकता है। फिर, ऑब्जेक्ट आपके द्वारा किए जा रहे तरीके से दुष्प्रभावित हो सकता है।

(यह इस सवाल को अनदेखा करता है कि आप वास्तव में ऐसे हैशटेबल कुंजी के रूप में ऐसे जटिल मानों का उपयोग करना चाहते हैं या यदि इसके आसपास काम करने का कोई तरीका है। उदाहरण के लिए, आप संरचनाओं/CLOS ऑब्जेक्ट्स का उपयोग कर सकते हैं आपकी कुंजी के रूप में जटिल सूचियां, और फिर आप एक ईक्यू हैशटेबल का उपयोग कर सकते हैं। लेकिन यह आपके द्वारा किए जा रहे कार्यों पर बहुत निर्भर करता है।)

Answer 4

"प्रोफाइलिंग से पता चलता है कि बराबर परीक्षण लंबे समय तक लेते हैं।"

हां, लेकिन आपने सत्यापित किया है कि # 'EQUAL हैश तालिका लुकअप भी बहुत समय लगता है?

क्या आपने इसे एसबीसीएल जैसे ऑप्टिमाइज़िंग कंपाइलर पर गति के लिए संकलित किया है और संकलक नोट्स को देखा है?

इन दो प्रश्नों को हल करने के बाद आप अपनी सूची कुंजी के प्रत्येक स्तर के लिए नेस्टेड हैश तालिका भी आज़मा सकते हैं। मनमाने ढंग से नेस्टेड हैश टेबल के लिए मैक्रो लिखना मुश्किल नहीं होना चाहिए।

Answer 5

शायद मैं कुछ स्पष्ट याद कर रहा हूँ, लेकिन:

(defun try-add (i) 
    (let ((old-i (gethash complex-list table))) 
    (when (may-add old-i) 
     (push i old-i)))) 

के बाद से:

• शून्य पहले से ही GETHASH
• के लिए डिफ़ॉल्ट GETHASH पूरी वस्तु बाहर खींचती है, ताकि आप केवल संशोधित कर सकते हैं है यह पुश को कहने के बजाए जगह में
• (शैली बिंदु: जब कोई और खंड नहीं है तो IF के बजाय WHEN का उपयोग करें)

संपादित करें: ओह, मैं था: मुझे उस मामले को याद आया जहां पुराना-मैं शून्य हूं। लेकिन अगर वह आम मामला नहीं है, तो यह अभी भी एक जीत के बाद से आप केवल उस स्थिति में देखने क्या करने की जरूरत हो सकती है,:

(defun try-add (i) 
    (let ((old-i (gethash complex-list table))) 
    (when (may-add old-i) 
     (if old-i 
     (push i old-i) 
     (push i (gethash complex-list table)))))) 

हम्म, यह काम करता है?

Answer 6

आप वास्तव में हैश तालिका को तीन बार एक्सेस कर सकते हैं। क्यूं कर? चूंकि push मैक्रो कोड में विस्तार कर सकता है जो सूची प्राप्त करने के लिए gethash करता है, और फिर मान को संग्रहीत करने के लिए कुछ system::sethash ऑपरेशन करता है।

इस समस्या में, आप किसी स्थान की मान का निरीक्षण कर रहे हैं, जो एक सूची है। यदि वह सूची कुछ अनुमानित परीक्षण को पूरा करती है, तो आप उस स्थान पर कुछ धक्का देते हैं।

(push-if <new-value> <predicate> <place>) 

उदाहरण के लिए::

यह समस्या जो इस अर्थ विज्ञान कब्जा विशेष प्रयोजन ऑपरेटर बनाने के द्वारा हमला किया जा सकता है

(push-if i #'may-add (gethash complex-list table)) 

यह push-if एक मैक्रो पर get-setf-expansion फ़ंक्शन का उपयोग करता है जो के रूप में परिभाषित किया गया है <place> उस स्थान तक पहुंचने के लिए कोड उत्पन्न करने के लिए आवश्यक टुकड़े प्राप्त करने के लिए फॉर्म तर्क।

जेनरेट कोड स्थान से पुराना मान प्राप्त करने के लिए लोड फॉर्म का मूल्यांकन करता है, फिर पुराने मान पर स्थिति लागू करता है, और यदि यह सफल होता है, तो यह get-setf-expansion से प्राप्त उचित अस्थायी स्टोर चर में नया मान तैयार करता है और स्टोर फॉर्म का मूल्यांकन करता है।

यह पोर्टेबल लिस्प में आप सबसे अच्छा कर सकते हैं, और आप पाते हैं कि यह अभी भी ऊपर बताए गए दो हैश ऑपरेशंस करता है। (जो मामले में आप आशा है कि हैश तालिका अपने आप में एक सभ्य कैशिंग अनुकूलन है लेकिन कम से कम यह दो ऑप्स के लिए नीचे है।।)

दृष्टिकोण के रूप में जगह परिवर्तनशील रूपों में बनाया के रूप में अनुकूलित किया जाएगा:, pushincf , rotatef, आदि। हमारे push-if बिल्ट-इन्स के बराबर होंगे।

यदि यह अभी भी बेकार है (कोई हैश स्थान अपडेट करने के लिए दो हैश करता है, कैशिंग ऑप्टिमाइज़ेशन के साथ), तो इसे ठीक करने का एकमात्र तरीका कार्यान्वयन स्तर पर है।

push-if कोड इस प्रकार है:

(defmacro push-if (new-value predicate-fun list-place &environment env) 
    (multiple-value-bind (temp-syms val-forms 
         store-vars store-form access-form) 
         (get-setf-expansion list-place env) 
    (let ((old-val (gensym))) 
     (when (rest store-vars) 
     (error "PUSH-IF: cannot take ref of multiple-value place")) 
     `(multiple-value-bind (,@temp-syms) (values ,@val-forms) 
     (let ((,old-val ,access-form)) 
      (when (funcall ,predicate-fun ,old-val) 
      (setf ,(first store-vars) (cons ,new-value ,old-val)) 
      ,store-form)))))) 

नमूना विस्तार:

> (macroexpand '(push-if new test place)) 
(LET* ((#:VALUES-12731 (MULTIPLE-VALUE-LIST (VALUES)))) 
(LET ((#:G12730 PLACE)) 
    (WHEN (FUNCALL TEST #:G12730) (SETF #:NEW-12729 (CONS NEW #:G12730)) 
    (SETQ PLACE #:NEW-12729)))) ; 

सरल मामले के लिए समझदार लगता है जब जगह एक चर है। केवल थोड़ी सी समस्या है जिसे मैं ठीक नहीं कर रहा हूं: फॉर्म new, test और place का मूल्यांकन केवल एक बार किया जाता है, लेकिन बाएं से दाएं क्रम में नहीं! एक हैश तालिका जगह के साथ

टेस्ट (CLISP):

> (macroexpand '(push-if new test (gethash a b))) 
(LET* 
((#:VALUES-12736 (MULTIPLE-VALUE-LIST (VALUES A B))) 
    (#:G12732 (POP #:VALUES-12736)) (#:G12733 (POP #:VALUES-12736))) 
(LET ((#:G12735 (GETHASH #:G12732 #:G12733))) 
    (WHEN (FUNCALL TEST #:G12735) (SETF #:G12734 (CONS NEW #:G12735)) 
    (SYSTEM::PUTHASH #:G12732 #:G12733 #:G12734)))) ; 

अहा; a और b का मूल्यांकन करने से बचने के लिए अब कुछ और दिलचस्प कोड उत्पन्न किया जा रहा है। gethash फ़ंक्शन एक बार लागू किया जाता है, लेकिन इसके तर्क gensym चर हैं। पुराना मान #:G12735 के रूप में कब्जा कर लिया गया है। परीक्षण इस पर लागू होता है, और यदि यह गुजरता है, तो स्टोर variabel #:G12734 को पुराने सूची मूल्य के साथ अपडेट किया गया है जिसमें new इसके सामने लगाया गया है। फिर, वह मान हैश तालिका में system::puthash के साथ रखा गया है।

तो इस लिस्प कार्यान्वयन में, अद्यतन करने के लिए दो हैश तालिका संचालन से बचने का कोई तरीका नहीं है: gethash और system::puthash। यह सबसे अच्छा है जो हम कर सकते हैं और उम्मीद करते हैं कि दो अनुकूलित अनुकूलित जोड़ी के रूप में काम करते हैं।