पाइथन कोड को तेज करना जो पूरी सूची

Question

से गुज़रना है, मुझे एक समस्या है जहां मुझे हल करने के लिए पूरी सूची के माध्यम से जाना चाहिए (कम से कम सुनिश्चित करें)। सवाल यह है कि सूची में लगातार संख्याओं की सबसे बड़ी संख्या को समझना है जो उस सूची में किसी अन्य (अधिक) तत्व को जोड़ता है। यदि कोई नहीं है तो हम उम्मीदवार के सारांश के रूप में सूची में सबसे बड़ा मूल्य लेते हैं और 1 तत्वों की लगातार सबसे बड़ी संख्या के रूप में।

मेरा सामान्य कोड काम करता है, लेकिन बड़ी सूचियों (> 500,000 तत्व) के लिए बहुत अच्छा नहीं है। मैं केवल सुझावों की तलाश में हूं कि मैं इस समस्या से अलग कैसे हो सकता हूं। मेरे वर्तमान दृष्टिकोण:

L = [1,2,3,4,5,6,7,8,9,10] 
candidate_sum = L[-1] 
largest_count = 1 
N = len(L) 
i = 0 

while i < N - 1: 
    s = L[i] 
    j = 0 
    while s <= (N - L[i + j + 1]): 
     j += 1 
     s += L[i+j] 
     if s in L and (j+1) > largest_count: 
      largest_count = j+1 
      candidate_sum = s 
    i+=1 

इस मामले में, इस सवाल का जवाब होगा [1,2,3,4] के रूप में वे 10 को जोड़ने और लंबाई 4 है (जाहिर है इस उदाहरण एल एक बहुत ही सरल उदाहरण है) ।

मैं तो यह तेजी से प्रारंभिक बदलकर बनाया जबकि पाश हालत के लिए:

while i < (N-1)/largest_count 

नहीं एक महान धारणा है, लेकिन मूल सोच है कि संख्या के वितरण को कुछ हद तक समान है, इसलिए की दूसरी छमाही पर दो नंबर सूची सूची में अंतिम संख्या की तुलना में औसत पर बड़ी है, और इसलिए अयोग्य हैं।

मैं बस के लिए देख रहा हूँ:

• संभव बाधाओं विभिन्न दृष्टिकोणों के रूप में
• सुझाव

Answer 1

• कड़ाई से आरोही कोशिश करने के लिए: तत्वों या subsequences का कोई दोहराव, एकल संभव समाधान

• मनमानी दूरी: कोई अंक नहीं etical शॉर्टकट, जानवर बल सांख्यिक प्रकारों पर

कुशल सी कार्यान्वयन सूचक का उपयोग कर गणित, अर्ध बहुरूपी संचालित करने के लिए है:

#define TYPE int 

int max_subsum(TYPE arr [], int size) { 
    int max_length = 1; 

    TYPE arr_fst = * arr; 
    TYPE* num_ptr = arr; 

    while (size --) { 
     TYPE num = * num_ptr++; 

     TYPE* lower = arr; 
     TYPE* upper = arr; 

     TYPE sum = arr_fst; 
     int length = 1; 

     for (;;) { 
     if (sum > num) { 
      sum -= * lower++; 
      -- length; 
     } 
     else if (sum < num) { 
      sum += * ++upper; 
      ++ length; 
     } 
     else { 
      if (length > max_length) { 
       max_length = length; 
      } 

      break; 
     } 
     } 
    } 

    return max_length; 
} 

मुख्य पाश से अधिक num रों में चलाने योग्य है। अजगर 3 arr के लिए गतिशील सरणी सूची प्रकार और for each पाश का उपयोग कर में अपेक्षाकृत सीधी-सपाट अनुवाद:

def max_subsum(arr): 
    max_len = 1 
    arr_fst = arr[0] 

    for n in arr: 
     lower = 0 
     upper = 0 

     sum = arr_fst 

     while True: 
     if sum > n: 
      sum -= arr[lower] 
      lower += 1 
     elif sum < n: 
      upper += 1 
      sum += arr[upper] 
     else: 
      sum_len = upper - lower + 1 

      if sum_len > max_len: 
       max_len = sum_len 

      break 

    return max_len 

यह max_subsum एक आंशिक समारोह है, पायथन सूची खाली हो सकती है। एल्गोरिदम सी-जैसी संकलित अनिवार्य भाषाओं के लिए उपयुक्त है जो तेजी से अनुक्रमण और स्थिर रूप से टाइप किए गए अंकगणित की पेशकश करते हैं। दोनों पायथन में तुलनात्मक रूप से महंगा हैं। ए (पूरी तरह से परिभाषित) एल्गोरिथ्म बल्कि, आपके जैसे ही अधिक performant सार्वभौमिक मात्रा के लिए set डेटा प्रकार का उपयोग कर, और अजगर की तेज़ी से टाइप किया अंकगणित से परहेज, और अधिक कुशलता से व्याख्या की जा सकती:

def max_subsum(arr): 
    size = len(arr) 
    max_len = 0 

    arr_set = set(arr) 

    for i in range(size): 
     sum = 0 
     sum_len = 0 

     for j in range(i, size): 
     sum_mem = sum + arr[j] 

     if num_mem not in arr_set: 
      break 

     sum = sum_mem 
     sum_len += 1 

     if sum_len > max_len: 
     max_len = sum_len 

    return max_len 

Answer 2

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

import numpy as np 

L = np.random.randint(0,100,100) 
L.sort() 
cum_sum = np.cumsum(L) 

start = 0 
end = 0 

target = 200 

while 1: 
    total = cum_sum [end-1] - (cum_sum [start-1] if start else 0) 
    if total == target: 
     break 
    elif total < target: 
     end += 1 
    elif total > target: 
     start += 1 
    if end >= len(L): 
     raise ValueError('something informative')