2017-03-22 15 views
5

Tôi gặp vấn đề khi cần (chắc chắn ít nhất) đi qua toàn bộ danh sách để giải quyết. Câu hỏi là để tìm ra số lượng lớn nhất của các số liên tiếp trong một danh sách mà thêm đến một yếu tố (lớn hơn) trong danh sách đó. Nếu không có thì chúng ta chỉ lấy giá trị lớn nhất trong danh sách khi tổng kết ứng viên và 1 là số phần tử liên tiếp lớn nhất.Tăng tốc mã Python phải trải qua toàn bộ danh sách

Mã chung của tôi hoạt động, nhưng không quá tốt đối với các danh sách lớn (> 500.000 phần tử). Tôi chỉ tìm kiếm các mẹo để làm thế nào tôi có thể tiếp cận vấn đề một cách khác nhau. Cách tiếp cận hiện tại của tôi:

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 

Trong trường hợp này, câu trả lời sẽ là [1,2,3,4] khi chúng thêm tối đa 10 và độ dài là 4 (rõ ràng ví dụ này L là một ví dụ rất đơn giản) .

sau đó tôi đã làm cho nó nhanh hơn bằng cách thay đổi ban đầu trong khi điều kiện vòng lặp để:

while i < (N-1)/largest_count 

Không phải là một giả định tuyệt vời, nhưng suy nghĩ cơ bản mà việc phân phối số có phần thống nhất, vì vậy hai con số trên nửa cuối năm danh sách là trung bình lớn hơn số cuối cùng trong danh sách, và do đó bị loại.

Tôi chỉ tìm kiếm cho:

  • tắc nghẽn có thể
  • đề nghị như những cách tiếp cận khác nhau để thử
+4

Bạn cần xác định vấn đề của mình chính xác hơn.Danh sách luôn được sắp xếp và đơn điệu? Liệu có bất kỳ khoảng trống nào trong chúng? Giải pháp tốt nhất sẽ khác nhau tùy thuộc vào tuyên bố vấn đề chính xác. –

+1

@ ŁukaszRogalski danh sách luôn được sắp xếp, tất cả các yếu tố là duy nhất để danh sách là đúng tăng và có, có khoảng cách giữa các số liên tiếp – dimebucker91

Trả lời

4
  • nghiêm ascending: không có sự trùng lặp của các yếu tố hoặc subsequences, đơn thể giải pháp

  • Khoảng cách tùy ý: không có arithm phím tắt etical, có hoạt động brute-force

hiệu quả C thực hiện sử dụng con trỏ số học, đa hình bán so với các loại số:

#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; 
} 

Vòng lặp chính trong num s là parallelizable. dịch tương đối thẳng về phía trước vào Python 3 sử dụng các loại danh sách động-mảng cho arrfor each loop:

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 Đây là một chức năng một phần; Danh sách Python có thể trống. Thuật toán thích hợp cho các ngôn ngữ mệnh lệnh được biên dịch giống như C cung cấp tính toán lập chỉ mục nhanh và số học tĩnh. Cả hai đều tương đối đắt bằng Python. Một thuật toán (hoàn toàn được xác định) chứ không phải giống như của bạn, bằng cách sử dụng loại set dữ liệu cho lượng hóa phổ performant hơn, và tránh số học tạo kiểu động của Python, có thể được giải thích một cách hiệu quả hơn:

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 
2

Tôi sẽ bỏ qua khả năng của một giá trị mục tiêu thay đổi, và cho phép bạn tìm ra điều đó, nhưng để trả lời câu hỏi của bạn "có cách nào nhanh hơn để làm điều đó không?" Có: bằng cách sử dụng tổng tích lũy và một số toán để loại bỏ một trong các vòng lặp của bạn.

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') 
+0

Dường như mã này không xử lý các trường hợp khi không có giải pháp là có thể. Bạn cần đảm bảo rằng 'start <= end' và' end

+0

@LakshayGarg 'start' không được lớn hơn' kết thúc' vì 'cum_sum' được sắp xếp nếu' L' được sắp xếp. Nếu chúng bằng 'end' sẽ được tăng lên trên lần lặp tiếp theo. Tôi cố định vấn đề không có giải pháp, và một lỗi toán học .. – Aaron

+0

@LakshayGarg thực sự là điều kiện là tất cả 'L' là> 0, không phải là' L' được sắp xếp, nhưng điều đó giữ cho ví dụ tôi đã cho .. Nó là cũng phần nào cần thiết cho phương pháp này để làm việc (không có sửa đổi đáng kể). – Aaron

Các vấn đề liên quan