2010-05-30 39 views
6

Tôi đang cố gắng để có được mức trung bình có trọng số của một vài số. Về cơ bản tôi có:Tính trung bình có trọng số cho số lớn

Price - 134.42 
Quantity - 15236545 

Có thể có ít nhất một hoặc hai hoặc nhiều năm mươi sáu mươi cặp giá và số lượng. Tôi cần phải tìm ra mức trung bình của giá. Về cơ bản, mức trung bình có trọng số nên cung cấp trọng lượng rất nhỏ cho các cặp như

Price - 100000000.00 
Quantity - 3 

và nhiều hơn nữa cho cặp ở trên.

Công thức Tôi hiện đang có là:

((price)(quantity) + (price)(quantity) + ...)/totalQuantity 

Cho đến nay tôi có điều này thực hiện:

 double optimalPrice = 0; 
     int totalQuantity = 0; 
     double rolling = 0; 
     System.out.println(rolling); 

     Iterator it = orders.entrySet().iterator(); 
     while(it.hasNext()) { 
      System.out.println("inside"); 
      Map.Entry order = (Map.Entry)it.next(); 
      double price = (Double)order.getKey(); 
      int quantity = (Integer)order.getValue(); 
      System.out.println(price + " " + quantity); 

      rolling += price * quantity; 
      totalQuantity += quantity; 
      System.out.println(rolling); 
     } 
     System.out.println(rolling); 
     return rolling/totalQuantity; 

Vấn đề là tôi rất nhanh chóng tối đa ra "lăn" biến.

Làm cách nào để có được mức trung bình có trọng số của mình?

Trả lời

3

Một giải pháp là sử dụng java.math.BigInteger cho cả hai rollingtotalQuantity và chỉ chia chúng ở cuối. Điều này có độ ổn định số tốt hơn, vì bạn chỉ có một bộ phận dấu chấm động ở cuối và mọi thứ khác là các phép toán số nguyên.

BigInteger về cơ bản là không bị chặn nên bạn không nên chạy vào bất kỳ tình trạng tràn nào.

CHỈNH SỬA: Xin lỗi, chỉ khi đọc lại tôi mới nhận thấy giá của bạn là double. Có lẽ nó đáng giá bằng cách nhân nó với 100 và sau đó chuyển đổi sang BigInteger - vì tôi thấy trong ví dụ của bạn nó có chính xác 2 chữ số bên phải của dấu thập phân - và sau đó chia cho 100 ở cuối, mặc dù nó là một chút của một hack .

+0

'1.055' ->' 105', bạn nên thêm '0,005' vào giá trị trước khi nhân với' 100' hoặc '0,5' sau khi nhân với' 100' nhưng trước chuyển đổi số nguyên, chẳng hạn như: '1,055 '->' 106', là số làm tròn chính xác. – Pindatjuh

+0

@Pindatjuh: ý tưởng không mất đi bất kỳ độ chính xác nào cả. Tôi đề nghị nhân với 100 vì có vẻ như giá của OP có hai chữ số chính xác sau thời điểm đó, không nhiều hơn. – Oak

+0

tất nhiên, nhưng nó không phải là lời chỉ trích cho đề xuất tuyệt vời của bạn (+1), chỉ là một lưu ý để làm tròn tốt hơn khi sử dụng "hack" nhân với 100 và chuyển thành số nguyên, trong trường hợp có nhiều hơn 2 chữ số. – Pindatjuh

3

Một đôi có thể chứa một số khá lớn (khoảng 1,7 x 10^308, theo tài liệu), nhưng bạn có lẽ không nên sử dụng nó cho các giá trị chính xác được yêu cầu (chẳng hạn như giá trị tiền tệ).

Kiểm tra lớp BigDecimal thay thế. This question on SO nói về chi tiết hơn.

1

Để linh hoạt tối đa, hãy sử dụng BigDecimal cho rollingBigInteger cho totalQuantity. Sau khi chia (lưu ý, bạn có nó ngược, nó sẽ được lăn/totalQuantity), bạn có thể trả về một BigDecimal, hoặc sử dụng doubleValue tại một mất chính xác.

0

Tại bất kỳ điểm đã cho nào, bạn đã ghi lại cả tổng giá trị ax + by + cz + ... = pq tổng trọng lượng a + b + c + ... = p. Biết cả hai cung cấp cho bạn giá trị trung bình pq/p = q. Vấn đề là pqp là số tiền lớn tràn, mặc dù bạn chỉ muốn có kích thước vừa phải q.

Bước tiếp theo thêm, ví dụ: trọng lượng r và giá trị s.Bạn muốn tìm số tiền mới (pq + rs)/(p + r) bằng cách chỉ sử dụng giá trị q, điều này chỉ có thể xảy ra nếu ppq bằng cách nào đó "tiêu diệt" bằng cách ở tử số và mẫu số của cùng một phân số. Điều đó là không thể, như tôi sẽ trình bày.

Giá trị mà bạn cần phải thêm vào lặp này là, một cách tự nhiên,

(pq + rs)/(p + r) - q 

nào không thể được đơn giản hóa đến một điểm mà p*qp biến mất. Bạn cũng có thể tìm thấy

(pq + rs)/q(p + r) 

yếu tố mà bạn sẽ nhân q để có được mức trung bình tiếp theo; nhưng một lần nữa, pqp vẫn còn. Vì vậy, không có giải pháp thông minh.

Những người khác đã đề cập đến các biến số chính xác tùy ý và đó là giải pháp tốt ở đây. Kích thước của ppq tăng tuyến tính với số lượng mục nhập và tốc độ sử dụng bộ nhớ và tốc độ tính toán của số nguyên/phao tăng theo lôgarit với kích thước của các giá trị. Vì vậy, hiệu suất là O (log (n)) không giống như thảm họa mà nó sẽ nếu p bằng cách nào đó là bội số của nhiều số.

0

Trước tiên, tôi không thấy cách bạn có thể "tối đa hóa" biến số rolling. Như @Ash chỉ ra, nó có thể đại diện cho các giá trị lên đến khoảng 1.7 x 10^308. Khả năng duy nhất tôi có thể nghĩ là bạn có một số giá trị xấu trong đầu vào của mình. (Có lẽ vấn đề thực sự là bạn đang mất chính xác ...)

Thứ hai, việc bạn sử dụng số Map để đại diện cho đơn đặt hàng là lạ và có thể bị hỏng. Cách bạn hiện đang sử dụng, bạn không thể đại diện cho các đơn đặt hàng liên quan đến hai hoặc nhiều mục có cùng mức giá.

+0

Có, tại sao không chỉ lưu trữ đơn hàng trong danh sách? –

+0

Phần trước của chương trình kết hợp các đơn đặt hàng với cùng mức giá. – Travis

0

Kết quả cuối cùng của bạn chỉ là trọng số trung bình, vì vậy bạn không cần phải tuân thủ các quy tắc được sử dụng khi tính toán số dư tài khoản, v.v. BigDecimal, double sẽ đủ.

Sự cố tràn có thể được giải quyết bằng cách lưu trữ "mức trung bình đang chạy" và cập nhật nó với mỗi mục nhập mới. Cụ thể, chúng ta hãy

a_n = (sum_ {i = 1}^n x_i * w_i)/(sum_ {i = 1}^n w_i)

cho n = 1, ..., N. Bạn bắt đầu bằng a_n = x_n và sau đó thêm

d_n: = a_ {n + 1} - a_n

cho nó. Công thức cho d_n là

d_n = (X_ {n + 1} - w_ {n + 1} * a_n)/W_ {n + 1}

nơi W_n: = sum_ {i = 1}^n w_n. Bạn cần phải theo dõi W_n, nhưng vấn đề này có thể được giải quyết bằng cách lưu trữ nó như double (nó sẽ được OK vì chúng tôi chỉ quan tâm đến mức trung bình). Bạn cũng có thể chuẩn hóa trọng số, nếu bạn biết rằng tất cả trọng số của bạn là bội số của 1000, chỉ chia chúng cho 1000.

Để có được độ chính xác bổ sung, bạn có thể sử dụng compensated summation.

Giải thích ưu tiên: có thể sử dụng số học dấu chấm động ở đây. double có độ chính xác tương đối 2E-16.OP là số trung bình tích cực, do đó sẽ không có lỗi hủy. Những người ủng hộ số học chính xác tùy ý không nói với bạn là, để nguyên tắc làm tròn sang một bên, trong trường hợp khi nó không cung cấp cho bạn nhiều chính xác hơn so với số học dấu chấm động IEEE754, điều này sẽ có chi phí hiệu năng và bộ nhớ đáng kể. Số học dấu chấm động được thiết kế bởi những người rất thông minh (Giáo sư Kahan, trong số những người khác), và nếu có một cách tăng giá trị số học một cách rẻ tiền so với những gì được cung cấp bởi điểm nổi, họ sẽ làm điều đó.

Tuyên bố từ chối trách nhiệm: nếu trọng lượng của bạn hoàn toàn điên (một là 1, khác là 10000000), thì tôi không chắc chắn 100% nếu bạn đạt được độ chính xác, nhưng bạn có thể kiểm tra nó trên một số ví dụ khi bạn biết câu trả lời nên là.

+0

Bạn vẫn gặp sự cố khi W_n tăng kích thước bằng số cặp (số lượng, giá). Nhưng điều này có thể không phải là vấn đề với tối đa 60 cặp. –

+0

Có lẽ nó sẽ không tràn 'double'. –

0

Thực hiện hai vòng: tính toán totalQuantity trước tiên trong vòng lặp đầu tiên. Sau đó, trong vòng lặp thứ hai tích lũy giá * (số lượng/totalQuantity).

+0

Sau đó, OP có thể bị tràn thay vì tràn. –

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