yếu tố danh sách đầu tiên n Tăng được đưa ra một điều kiện

Question

tôi có một danh sách ví dụ

l = [10, 20, 30, 40, 50, 60] 

tôi cần phải tăng các n yếu tố đầu tiên của danh sách được đưa ra một điều kiện. Điều kiện độc lập với danh sách. Ví dụ, nếu n = 3, danh sách l nên trở thành:

l = [11, 21, 31, 40, 50, 60] 

Tôi hiểu rằng tôi có thể làm điều đó với một vòng lặp for trên mỗi phần tử của danh sách. Nhưng tôi cần phải làm như vậy khoảng 150 triệu lần. Vì vậy, tôi đang tìm kiếm một phương pháp nhanh hơn để làm điều này. Bất kỳ sự trợ giúp nào cũng được đánh giá cao. Cảm ơn trước

Answer 1

Bạn có thể sử dụng danh sách hiểu biết và thêm danh sách còn lại

[x + 1 for x in a[:n]]+a[n:] 

Answer 2

Bạn có thể tạo ra một cấu trúc dữ liệu đơn giản trên đầu danh sách của bạn mà các cửa hàng bắt đầu và kết thúc phạm vi của mỗi hoạt động tăng. Bắt đầu sẽ là 0 trong trường hợp của bạn để bạn có thể lưu trữ kết thúc.

Bằng cách này bạn không phải thực sự duyệt qua danh sách để tăng các phần tử, nhưng bạn chỉ giữ lại rằng bạn đã thực hiện các gia số trên phạm vi ví dụ {0 đến 2} và {0 đến 3}. Hơn nữa, bạn cũng có thể đối chiếu một số thao tác, để nếu nhiều thao tác tăng lên cho đến cùng một chỉ mục, bạn chỉ cần lưu trữ một mục nhập.

Độ phức tạp của trường hợp xấu nhất của giải pháp này là O(q + g x qlogq + n) trong đó g là số hoạt động nhận được, q là số lần cập nhật và n là độ dài của danh sách. Vì chúng tôi có thể có tối đa n kết thúc riêng biệt cho các khoảng thời gian này, hãy giảm xuống còn O(q + nlogn + n) = O(q + nlogn). Một giải pháp ngây thơ sử dụng bản cập nhật cho mỗi truy vấn sẽ là O(q * l) trong đó l (chiều dài của truy vấn) có thể lên đến kích thước của n cho O(q * n). Vì vậy, chúng ta có thể mong đợi giải pháp này tốt hơn khi q > log n.

python làm việc ví dụ dưới đây:

def RangeStructure(object): 

    def __init__(self, l): 
    self.ranges = collections.defaultdict(int) 
    self.l = l 

    def incToPosition(self, k): 
    self.ranges[k] += 1 

    def get(self): 
    res = self.l 
    sorted_keys = sorted(self.ranges) 
    last = len(sorted_keys) - 1                                                     
    to_add = 0 
    while last >= 0: 
     start = 0 if last < 1 else sorted_keys[last - 1] 
     end = sorted_keys[last] 
     to_add += self.ranges[end] 
     for i in range(start, end): 
      res[i] += to_add 
     last -= 1 
    return res 

rs = RangeStructure([10, 20, 30, 40, 50, 60]) 
rs.incToPosition(2) 
rs.incToPosition(2) 
rs.incToPosition(3) 
rs.incToPosition(4) 
print rs.get() 

Và một lời giải thích:

1. sau dãy hoạt động inc sẽ chứa (bắt đầu, kết thúc, inc) tuples có dạng (0, 2, 2), (0, 3, 1), (0, 4, 1); này sẽ được trình bày trong dict như {2: 2, 3: 1, 4: 1} kể từ đầu luôn luôn là 1 và có thể được bỏ qua

2. trong hoạt động get, chúng tôi đảm bảo rằng chúng tôi chỉ hoạt động trên danh sách bất kỳ phần tử một lần; chúng tôi sắp xếp các dãy thứ tự tăng dần của điểm cuối cùng của họ, và đi qua chúng theo thứ tự ngược lại cập nhật các yếu tố danh sách chứa và sum (to_add) để được thêm vào dãy sau

in này, như mong đợi:

[14, 24, 32, 41, 50, 60] 

Answer 3

Dưới đây là một thực hiện hoạt động-tập hợp trong NumPy:

initial_array = # whatever your l is, but as a NumPy array 
increments = numpy.zeros_like(initial_array) 
... 
# every time you want to increment the first n elements 
if n: 
    increments[n-1] += 1 
... 
# to apply the increments 
initial_array += increments[::-1].cumsum()[::-1] 

Đây là O(ops + len(initial_array)), nơi ops là num ber của các hoạt động tăng.Trừ khi bạn chỉ làm một số lượng nhỏ các gia số trên một phần rất nhỏ của danh sách, điều này sẽ nhanh hơn nhiều. Không giống như việc triển khai ngây thơ, nó không cho phép bạn lấy các giá trị phần tử cho đến khi các giá trị gia tăng được áp dụng; nếu bạn cần làm điều đó, bạn có thể cần một giải pháp dựa trên cấu trúc BST hoặc BST giống như để theo dõi gia số.

Answer 4

m - số truy vấn, n - danh sách để tăng độ dài, ý tưởng thuật toán O (n + m):
vì bạn chỉ phải tăng từ đầu đến phần tử thứ k. Hãy để tăng của chúng tôi được ghép nối (lên đến vị trí, tăng dần). Ví dụ:
(1, 2) - vị trí gia tăng 0 và 1 bằng 2
Nếu chúng tôi đang cố gắng tính giá trị tại vị trí k thì chúng ta nên thêm gia số có vị trí lớn hơn hoặc bằng k đến giá trị hiện tại tại vị trí k. Làm thế nào chúng ta có thể nhanh chóng tính tổng số gia số có vị trí lớn hơn hoặc bằng k? Chúng ta có thể bắt đầu tính toán các giá trị từ mặt sau của danh sách và sau đó ghi lại tổng các giá trị gia tăng.
Bằng chứng về khái niệm:

# list to increment 
a = [1, 2, 5, 1, 6] 
# (up to and including k-th index, increment by value) 
queries = [(1, 2), (0, 10), (3, 11), (4, 3)] 

# decribed algorithm implementation 
increments = [0]*len(a) 
for position, inc in queries: 
    increments[position] += inc 

got = list(a) 
increments_sum = 0 
for i in xrange(len(increments) -1, -1, -1): 
    increments_sum += increments[i] 
    got[i] += increments_sum 


# verify that solution is correct using slow but correct algorithm 
expected = list(a) 
for position, inc in queries: 
    for i in xrange(position + 1): 
     expected[i] += inc 

print 'Expected: ', expected 
print 'Got:  ', got 

đầu ra:

Expected: [27, 18, 19, 15, 9] 
Got:  [27, 18, 19, 15, 9]