इसे बनाए गए सूचियों की सूची कैसे बनाए रखें

Question

मैं एक फाइल में पढ़ रहा हूं और डेटा में खींच रहा हूं जिसमें कुछ स्ट्रिंग्स और कुछ नंबर शामिल हैं, पायथन में। मैं सूचियों की सूची के रूप में यह जानकारी संग्रहीत कर रहा हूँ, इस तरह:

dataList = [ 

['blah', 2, 3, 4], 

['blahs', 6, 7, 8], 

['blaher', 10, 11, 12], 

] 

मैं उप सूची का दूसरा तत्व के अनुसार क्रमबद्ध DataList रखना चाहते हैं: DataList [] [1]

मैंने सोचा था कि मैं कर सकता जब मैं उन्हें जोड़ना चाहता हूं तो इन्सोर्ट या बाइसक्ट का उपयोग करें, लेकिन मैं यह नहीं समझ सकता कि इसे उप सूची के दूसरे तत्व को कैसे देखना है।

कोई विचार यहाँ? मैं अंत में डेटा को जोड़ रहा था और फिर चीजों को बाद में ढूंढने के लिए एक रैखिक प्रकार कर रहा था। लेकिन, यहां कुछ 10 हजार उप-सूचियों को फेंक दें और फिर 100k वस्तुओं की खोज करें और इसमें कुछ समय लगेगा।

Answer 1

dataList.sort(key=lambda x: x[1]) 

यह जगह में सूची सॉर्ट करता, प्रत्येक आइटम में दूसरा तत्व द्वारा।

जैसा टिप्पणियों में बताया गया है, यह केवल एक बार (अंत में) क्रमबद्ध करने के लिए और अधिक कुशल है। पाइथन की अंतर्निहित सॉर्ट विधि तेजी से काम करने के लिए अनुकूलित है। परीक्षण के बाद ऐसा लगता है कि बिल्ट-इन प्रकार heap method का उपयोग दूसरे उत्तर में सुझाए गए विभिन्न आकार सूचियों (मैंने 600000 तक के आकार का परीक्षण) के मुकाबले 3.7 गुना तेज है।

Answer 2

में कुछ बातों पर निर्भर करता है, लेकिन पहली बात यह है कि मन में आता है heapq मॉड्यूल उपयोग कर रहा है:

import heapq 
heap = [] 
for row in rows: 
    heapq.heappush(heap, (row[1], row)) 

यह एक ढेर tuples, से भरा बनाएं जहां पहला तत्व तत्व आप करना चाहते हैं द्वारा क्रमबद्ध करें, और दूसरा तत्व पंक्ति है।

सरलतम विधि उन्हें ढेर से वापस पढ़ने के लिए फिर पॉप आइटम कॉपी करने के लिए होगा:

new_heap = list(heap) 
while new_heap: 
    _, row = heapq.heappop(new_heap) 
    print row 

ढेर में प्रत्येक आइटम डालने के क्रम O(lg N) है, इसलिए ढेर बनाने O(N lg N) समय की आवश्यकता होगी , और ढेर से वस्तुओं को पॉप करने के लिए O(lg N) समय की आवश्यकता होती है, इसलिए O(N lg N) समय को पार करने की आवश्यकता होगी।

इन समझौतों से आदर्श नहीं हैं, तो आप एक द्विआधारी खोज वृक्ष (कोई मानक पुस्तकालय में मौजूद हैं, लेकिन they are easy to find) इस्तेमाल कर सकते हैं, या के रूप में अन्य टिप्पणीकर्ताओं का सुझाव दिया है, उन्हें पढ़ने के बाद पंक्तियां क्रमित: rows.sort(key=lambda row: row[1])।

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

अंत में, bisect, एक गरीब विचार है क्योंकि अजगर सूचियों में डालने O(N) समय तो O((N lg N) * N) = O(N**2) समय के कुल समय की आवश्यकता है, इसलिए द्विविभाजित साथ डालने आइटम आइटम प्रति O(N lg N) समय की आवश्यकता होगी,।