पायथन

Question

में एक सूची से एन न्यूनतम या अधिकतम तत्व प्राप्त करने का तेज़ तरीका वर्तमान में मेरे पास एक लम्बा फ़ंक्शन f का उपयोग करके क्रमबद्ध एक लंबी सूची है। मैं फिर पहले पांच तत्वों से यादृच्छिक तत्व चुनता हूं। कुछ ऐसा:

f = lambda x: some_function_of(x, local_variable) 
my_list.sort(key=f) 
foo = choice(my_list[:4]) 

प्रोफाइलर के मुताबिक यह मेरे कार्यक्रम में एक बाधा है। मैं चीजों को कैसे गति दे सकता हूं? क्या तत्वों को पुनर्प्राप्त करने के लिए एक तेज़, अंतर्निहित तरीका है (सिद्धांत में पूरी सूची को सॉर्ट करने की आवश्यकता नहीं है)। धन्यवाद।

Answer 1

heapq.nlargest या heapq.nsmallest का उपयोग करें।

उदाहरण के लिए

:

import heapq 

elements = heapq.nsmallest(4, my_list, key=f) 
foo = choice(elements) 

यह हे ले जाएगा (N + KlogN) समय (जहां कश्मीर तत्वों की संख्या लौटे है और N सूची के आकार है) है, जो हे की तुलना में तेजी है (NlogN) सामान्य प्रकार के लिए जब के 0 एन

Answer 2

से थोड़ा सा सापेक्ष है तो यह औसत पर रैखिक समय (ओ (एन)) में वास्तव में संभव है।

def partition(seq, pred, start=0, end=-1): 
    if end == -1: end = len(seq) 
    while True: 
     while True: 
      if start == end: return start 
      if not pred(seq[start]): break 
      start += 1 
     while True: 
      if pred(seq[end-1]): break 
      end -= 1 
      if start == end: return start 
     seq[start], seq[end-1] = seq[end-1], seq[start] 
     start += 1 
     end -= 1 

जो एक nth_element एल्गोरिथ्म द्वारा इस्तेमाल किया जा सकता:

nth_element(my_list, 4, key=f) 

:

def nth_element(seq_in, n, key=lambda x:x): 
    start, end = 0, len(seq_in) 
    seq = [(x, key(x)) for x in seq_in] 

    def partition_pred(x): return x[1] < seq[end-1][1] 

    while start != end: 
     pivot = (end + start) // 2 
     seq[pivot], seq[end - 1] = seq[end - 1], seq[pivot] 
     pivot = partition(seq, partition_pred, start, end) 
     seq[pivot], seq[end - 1] = seq[end - 1], seq[pivot] 
     if pivot == n: break 
     if pivot < n: start = pivot + 1 
     else: end = pivot 

    seq_in[:] = (x for x, k in seq) 

इन को देखते हुए, बस के साथ अपने दूसरे (प्रकार) लाइन की जगह

आप एक विभाजन एल्गोरिथ्म की जरूरत है