30.000 điểm dữ liệu, tìm sự thay đổi lớn nhất thời gian hơn 2 tuần

Question

tôi có:

- 30,000 data points 
- each data point is a measurement of type float 
- each measurement is associated with a date 
- each date has only one measurement 
- no dates are without measurements 
- the data comes in the form of a text file: 30,000 lines in this form: 
    - YYYY-MM-DD I,F (e.g. 1977-02-08 20.74) 
- measurement appearing in the source file are already sorted by date 

tôi cần:

- a time-interval T with boundaries (s,e) /* start, end */ 
- (s - e = 14 days) the time-interval *must* be 2 weeks 
- define min as the lowest value in the interval T 
- define max as the greatest value in the interval T 
- the chosen T needs to have the greatest distance btwn max and min of all possible Ts 
- break ties among intervals T by choosing the most recent (with the greatest s value) 
- the chosen T must consider all jumps in the 14 days, not just the values @ s and e 
- if the overall "variance" in the interval is great but the jump 
    |max-min| is not the greatest in absolute value, T is not the right choice, 
    even if it's an "exciting" interval 

Tôi hỏi:

- which algorithm to employ, considering algorithms are not my specialty 
- which data structure to use to keep track of the subtotals 

Lưu ý:

- an answer in pseudo code would be preferred, "prose" is fine if pressured for time 
- an answer in Python would be... splendid :) 

Nếu bạn muốn, bạn có thể tạo dữ liệu "giả" và chạy thuật toán được đề xuất làm thử nghiệm hoặc tôi có thể chia sẻ dữ liệu thực tế.

Tôi không quan tâm đến hiệu suất ở đây ngoài việc muốn biết cách nhanh nhất để làm điều này để tìm hiểu cách áp dụng giải pháp đúng và thuật toán chính xác.

Tôi nghĩ rằng tôi có thể "chứng minh" tính chính xác ngay cả với thuật toán lặp lại đơn giản nhất vì tập dữ liệu nhỏ cho các máy tính ngày nay.

Cho đến nay, tôi đang "đi ngang và mang theo 14 vectơ 14 phép đo", nếu bạn có thể dạy tôi cách làm điều này từng bước với các khoản phụ, điều đó sẽ thực sự được đánh giá cao.

Answer 1

Nếu tôi hiểu bạn, bạn có:

30.000 giá trị dữ liệu được sắp xếp riêng biệt. Việc đặt hàng xảy ra là theo ngày, nhưng điều đó không liên quan.

Trong tập hợp này, có 29.986 tập con trong đó nội dung là chuỗi thứ tự bắt đầu tại một điểm dữ liệu và chứa điểm ban đầu đó và mười ba điểm dữ liệu sau đây.


Thực hiện rất chậm:

1) đọc 30.000 điểm dữ liệu của bạn thành một mảng có kích thước 30.000.

2) phân bổ một mảng có kích thước 29,986. Gọi mảng này là "Người chiến thắng tiềm năng".

3) điền vào mảng Người chiến thắng tiềm năng bằng cách quét từng tập hợp con 14 điểm, tạm thời giữ giá trị lớn nhất và giá trị min gặp phải trong tập hợp con. Khi hai giá trị đó nằm trong tay, hãy lưu (Max-Min) tại vị trí chỉ mục - của điểm bắt đầu-- trong Người chiến thắng tiềm năng. Không thử bất kỳ tối ưu hóa cửa sổ trượt nào; xem bên dưới.

4) Thực hiện quét tuyến tính của Người chiến thắng tiềm năng, lưu giá trị và (quan trọng) chỉ mục mà tại đó nó được đặt.

BTW: bạn sẽ làm gì nếu không có người chiến thắng duy nhất? Nếu tất cả các điểm dữ liệu có cùng giá trị, bạn sẽ nhận được 29.986 người chiến thắng ứng cử viên, tất cả đều có cùng giá trị.

5) Tối ưu hóa: không phân bổ và điền vào Người chiến thắng tiềm năng; khởi tạo Người chiến thắng hiện tại cho tuple (giá trị, chỉ mục) là (0, -1). Tính toán giá trị của mỗi tập con 14 điểm như trên nhưng chỉ giữ lại giá trị tốt hơn trong số {Người chiến thắng hiện tại ”, giá trị tôi nhận được từ tập con hiện tại này"}

6) Cửa sổ trượt: Tôi chưa từng nghĩ điều này, nhưng tôi nghĩ rằng việc duy trì một cửa sổ trượt sẽ hoạt động tốt hơn so với đường truyền đơn giản được mô tả ở trên.

Lý do: được, tính giá trị của 14 điểm đầu tiên; nhận được một phút và tối đa, và nhận được khoảng cách giữa chúng. Nhưng chờ đợi, chúng ta cần các giá trị min và max để sử dụng trong cửa sổ tiếp theo. Bây giờ trượt cửa sổ lên một vị trí. Giá trị ở đầu bên trái biến mất; nhưng nó là min, max hay ở giữa?Giả sử nó là min, và nó đã biến mất. Giá trị nào là min thấp thứ hai? Chúng tôi không có thông tin đó.

Để giữ cửa sổ trượt, bạn cần phải sắp xếp từng đoạn sau 14-datapoint và nhớ vị trí chỉ mục của tất cả các giá trị. Sau đó, khi bạn trượt, bạn có thể biết liệu giá trị bỏ ra ở bên trái là một trong các giá trị cũ nhất hoặc min mới là phút hoặc tối đa cũ và liệu giá trị mới có xuất hiện ở bên phải hay không. Nhưng nó không đáng để nỗ lực.

(Tình huống này gợi ý một chút về thuật toán tìm chuỗi con Boyer-Moore nhanh. Tôi không nhớ chi tiết, nhưng nó liên quan đến việc xử lý trước toàn bộ đầu vào và giữ một bảng các vị trí nơi mỗi giá trị xuất hiện. là cách off-topic)

Hope this helps ...

Answer 2

trượt cửa sổ làm thực sự làm việc ở đây, bằng cách giữ hai ngăn xếp (có lẽ đây là một chút sai lệch, vì điều này có lẽ là tốt nhất thực hiện như một gấp đôi hàng chờ). Giữ một ngăn xếp minstack và ngăn xếp được gọi là maxstack. Điểm mấu chốt của thuật toán là minstack phải được nghiêm chỉnh không giảm và maxstack phải nghiêm chỉnh không tăng tại tất cả các điểm của trang trình bày. Vì vậy, làm thế nào để chúng tôi làm điều đó?

Trước tiên, thêm 14 điểm đầu tiên vào ngăn xếp. Hãy xác định add(point) như:

Làm điều này cho minstack:

• Trong khi điểm là nhỏ hơn so với các yếu tố đầu minstack, loại bỏ các yếu tố đầu minstack.
• Thêm điểm vào minstack.

Tương tự như vậy, đối với các maxstack:

• Trong khi điểm mới là lớn hơn so với các yếu tố đầu maxstack, loại bỏ các yếu tố đầu maxstack.
• Thêm điểm vào mức tối đa.

Do thuộc tính trên, min và max của 14 yếu tố đầu tiên phải là phần tử đáy của minstack và maxstack. Bây giờ trượt cửa sổ. Chúng ta chỉ cần lưu ý rằng nếu điểm bên trái vẫn còn "sống" trong bất kỳ ngăn xếp nào, thì nhất thiết phải là điểm cuối cùng. Do đó, điều này phải dễ dàng, đơn giản là:

slide(): 
    add(new_point) 
    if (left_point == bottom(minstack)) remove_bottom(minstack) 
    if (left_point == bottom(maxstack)) remove_bottom(maxstack) 

Làm điều này cho đến khi hết điểm. Khoảng thời gian bạn đang tìm kiếm là khoảng thời gian mà trong đó bottom(maxstack) - bottom(minstack) là lớn nhất. Lưu ý rằng bất kỳ điểm nào vào minstack/maxstack nhiều nhất một lần, và mọi điểm để lại nhiều nhất một lần, do đó, nó có tối đa 4 hoạt động cho mỗi điểm, bất kể kích thước của khoảng thời gian mong muốn là bao nhiêu.

EDIT: Tôi vừa nhận thấy bạn muốn triển khai bằng Python. Tôi thực sự không muốn phân tích cú pháp dữ liệu, do đó hàm lấy danh sách các giá trị làm đầu vào và xuất các chỉ mục (s, e) trong mảng đó:

import collections 

def add(x, minstack, maxstack): 
    while minstack and x < minstack[-1]: minstack.pop() 
    while maxstack and x > maxstack[-1]: maxstack.pop() 
    minstack.append(x) 
    maxstack.append(x) 

def get_largest_interval(points): 
    minstack = collections.deque() 
    maxstack = collections.deque() 

    best_diff = -1 
    best_interval = None 

    for index, elem in enumerate(points): 
     add(elem,minstack,maxstack) 
     if index >= 14: 
      if minstack[0] == points[index-14]: minstack.popleft() 
      if maxstack[0] == points[index-14]: maxstack.popleft() 

     if index >= 13: 
      this_diff = maxstack[0]-minstack[0] 
      if best_diff == -1 or this_diff >= best_diff: 
       best_interval = (index-13, index) 
       best_diff = this_diff 

    return best_interval 


print get_largest_interval([0, 2, 2,2,2,2,2,2,2,2,2,2,2,2,3])