Tính toán so với bảng tra cứu cho hiệu suất giá trị sin?

Question

Giả sử bạn phải tính sin (cosin hoặc tiếp tuyến - bất kỳ điều gì) trong đó miền nằm trong khoảng từ 0,01 đến 360,01. (sử dụng C#)

Điều gì sẽ hiệu quả hơn?

1. Sử dụng Math.sin
2. Sử dụng một mảng tra cứu với các giá trị precalculated

tôi sẽ anticpate đó được đưa ra miền, phương án 2 sẽ nhanh hơn nhiều. Tại điểm nào trong độ chính xác của miền (0,0000n) thì hiệu suất của phép tính vượt quá sự tra cứu.

Answer 1

Cập nhật: đọc đến cuối. Có vẻ như bảng tra cứu nhanh hơn Math.Sin.

Tôi đoán rằng phương pháp tra cứu sẽ nhanh hơn Math.Sin. Tôi cũng sẽ nói rằng nó sẽ là nhiều hơn nhanh hơn, nhưng câu trả lời của Robert khiến tôi nghĩ rằng tôi vẫn muốn điểm chuẩn này để chắc chắn. Tôi làm rất nhiều xử lý đệm âm thanh, và tôi đã nhận thấy rằng một phương pháp như thế này:

for (int i = 0; i < audiodata.Length; i++) 
{ 
    audiodata[i] *= 0.5; 
} 

sẽ thực hiện nhanh hơn đáng kể so với

for (int i = 0; i < audiodata.Length; i++) 
{ 
    audiodata[i] = Math.Sin(audiodata[i]); 
} 

Nếu sự khác biệt giữa Math.sin và một phép nhân đơn giản là đáng kể, tôi đoán rằng sự khác biệt giữa Math.Sin và tra cứu cũng sẽ là đáng kể.

Tôi không biết, và máy tính của tôi với Visual Studio nằm trong tầng hầm và tôi quá mệt mỏi để dành 2 phút để xác định điều này.

Cập nhật: OK, phải mất hơn 2 phút (hơn như 20) để kiểm tra điều này, nhưng có vẻ như Math.sin là ít nhất hai lần nhanh như một bảng tra cứu (sử dụng một từ điển). Đây là lớp Sin dùng Math.Sin hoặc một bảng tra cứu:

public class SinBuddy 
{ 
    private Dictionary<double, double> _cachedSins 
     = new Dictionary<double, double>(); 
    private const double _cacheStep = 0.01; 
    private double _factor = Math.PI/180.0; 

    public SinBuddy() 
    { 
     for (double angleDegrees = 0; angleDegrees <= 360.0; 
      angleDegrees += _cacheStep) 
     { 
      double angleRadians = angleDegrees * _factor; 
      _cachedSins.Add(angleDegrees, Math.Sin(angleRadians)); 
     } 
    } 

    public double CacheStep 
    { 
     get 
     { 
      return _cacheStep; 
     } 
    } 

    public double SinLookup(double angleDegrees) 
    { 
     double value; 
     if (_cachedSins.TryGetValue(angleDegrees, out value)) 
     { 
      return value; 
     } 
     else 
     { 
      throw new ArgumentException(
       String.Format("No cached Sin value for {0} degrees", 
       angleDegrees)); 
     } 
    } 

    public double Sin(double angleDegrees) 
    { 
     double angleRadians = angleDegrees * _factor; 
     return Math.Sin(angleRadians); 
    } 
} 

Và đây là các mã kiểm tra/thời gian:

SinBuddy buddy = new SinBuddy(); 

System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch(); 
int loops = 200; 

// Math.Sin 
timer.Start(); 
for (int i = 0; i < loops; i++) 
{ 
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
     angleDegrees += buddy.CacheStep) 
    { 
     double d = buddy.Sin(angleDegrees); 
    } 
} 
timer.Stop(); 
MessageBox.Show(timer.ElapsedMilliseconds.ToString()); 

// lookup 
timer.Start(); 
for (int i = 0; i < loops; i++) 
{ 
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
     angleDegrees += buddy.CacheStep) 
    { 
     double d = buddy.SinLookup(angleDegrees); 
    } 
} 
timer.Stop(); 
MessageBox.Show(timer.ElapsedMilliseconds.ToString()); 

Sử dụng một giá trị bước 0,01 độ và Looping qua đầy đủ các giá trị gấp 200 lần (như trong mã này) mất khoảng 1,4 giây sử dụng Math.Sin và khoảng 3,2 giây bằng cách sử dụng bảng tra cứu từ điển. Việc giảm giá trị bước xuống 0,001 hoặc 0,0001 khiến cho việc tra cứu hoạt động thậm chí tệ hơn với Math.Sin. Ngoài ra, kết quả này thậm chí còn có lợi hơn cho việc sử dụng Math.Sin, vì SinBuddy.Sin thực hiện phép nhân để biến góc theo độ thành radian trên mọi cuộc gọi, trong khi SinBuddy.SinLookup chỉ thực hiện tra cứu thẳng.

Đây là máy tính xách tay giá rẻ (không có lõi kép hoặc bất kỳ thứ gì lạ mắt). Robert, bạn da man! (Nhưng tôi vẫn nghĩ rằng tôi sẽ nhận được kiểm tra, coz tôi đã làm công việc).

Cập nhật 2: OK, tôi hoàn toàn chậm phát triển. Nó quay ra dừng lại và khởi động lại đồng hồ bấm giờ không thiết lập lại các mili giây trôi qua, do đó, tra cứu chỉ có vẻ một nửa nhanh vì đó là thời gian đã bao gồm thời gian cho các cuộc gọi Math.Sin. Ngoài ra, tôi đọc lại câu hỏi và nhận ra rằng bạn đang nói về việc lưu trữ các giá trị trong một mảng đơn giản, thay vì sử dụng một từ điển. Đây là mã của tôi sửa đổi (tôi rời khỏi mã cũ lên như một lời cảnh báo cho các thế hệ tương lai):

public class SinBuddy 
{ 
    private Dictionary<double, double> _cachedSins 
     = new Dictionary<double, double>(); 
    private const double _cacheStep = 0.01; 
    private double _factor = Math.PI/180.0; 

    private double[] _arrayedSins; 

    public SinBuddy() 
    { 
     // set up dictionary 
     for (double angleDegrees = 0; angleDegrees <= 360.0; 
      angleDegrees += _cacheStep) 
     { 
      double angleRadians = angleDegrees * _factor; 
      _cachedSins.Add(angleDegrees, Math.Sin(angleRadians)); 
     } 

     // set up array 
     int elements = (int)(360.0/_cacheStep) + 1; 
     _arrayedSins = new double[elements]; 
     int i = 0; 
     for (double angleDegrees = 0; angleDegrees <= 360.0; 
      angleDegrees += _cacheStep) 
     { 
      double angleRadians = angleDegrees * _factor; 
      //_cachedSins.Add(angleDegrees, Math.Sin(angleRadians)); 
      _arrayedSins[i] = Math.Sin(angleRadians); 
      i++; 
     } 
    } 

    public double CacheStep 
    { 
     get 
     { 
      return _cacheStep; 
     } 
    } 

    public double SinArrayed(double angleDegrees) 
    { 
     int index = (int)(angleDegrees/_cacheStep); 
     return _arrayedSins[index]; 
    } 

    public double SinLookup(double angleDegrees) 
    { 
     double value; 
     if (_cachedSins.TryGetValue(angleDegrees, out value)) 
     { 
      return value; 
     } 
     else 
     { 
      throw new ArgumentException(
       String.Format("No cached Sin value for {0} degrees", 
       angleDegrees)); 
     } 
    } 

    public double Sin(double angleDegrees) 
    { 
     double angleRadians = angleDegrees * _factor; 
     return Math.Sin(angleRadians); 
    } 
} 

Và mã kiểm tra/thời gian:

SinBuddy buddy = new SinBuddy(); 

System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch(); 
int loops = 200; 

// Math.Sin 
timer.Start(); 
for (int i = 0; i < loops; i++) 
{ 
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
     angleDegrees += buddy.CacheStep) 
    { 
     double d = buddy.Sin(angleDegrees); 
    } 
} 
timer.Stop(); 
MessageBox.Show(timer.ElapsedMilliseconds.ToString()); 

// lookup 
timer = new System.Diagnostics.Stopwatch(); 
timer.Start(); 
for (int i = 0; i < loops; i++) 
{ 
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
     angleDegrees += buddy.CacheStep) 
    { 
     double d = buddy.SinLookup(angleDegrees); 
    } 
} 
timer.Stop(); 
MessageBox.Show(timer.ElapsedMilliseconds.ToString()); 

// arrayed 
timer = new System.Diagnostics.Stopwatch(); 
timer.Start(); 
for (int i = 0; i < loops; i++) 
{ 
    for (double angleDegrees = 0; angleDegrees <= 360.0; 
     angleDegrees += buddy.CacheStep) 
    { 
     double d = buddy.SinArrayed(angleDegrees); 
    } 
} 
timer.Stop(); 
MessageBox.Show(timer.ElapsedMilliseconds.ToString()); 

Những kết quả khá khác nhau. Sử dụng Math.Sin mất khoảng 850 mili giây, bảng tra cứu từ điển mất khoảng 1300 mili giây và bảng tra cứu dựa trên mảng mất khoảng 600 mili giây. Vì vậy, có vẻ như một bảng tra cứu (viết đúng) [gulp]) thực sự nhanh hơn một chút so với sử dụng Math.Sin, nhưng không nhiều.

Hãy tự mình xác minh những kết quả này, vì tôi đã chứng tỏ sự thiếu năng lực của mình.

Answer 2

Math.Sin nhanh hơn. Những người viết thông minh và sử dụng tra cứu bảng khi chúng chính xác và nhanh hơn và sử dụng toán học khi nó nhanh hơn. Và không có gì về tên miền mà làm cho nó đặc biệt nhanh hơn, điều đầu tiên nhất triển khai chức năng trig làm là để bản đồ xuống một miền thuận lợi anyway.

Answer 3

Đối với câu hỏi về hiệu suất, câu trả lời đúng duy nhất là câu trả lời bạn đạt được sau khi thử nghiệm. Tuy nhiên, trước khi bạn kiểm tra, bạn cần xác định xem nỗ lực của thử nghiệm có xứng đáng với thời gian của bạn hay không - nghĩa là bạn đã xác định được vấn đề về hiệu suất.

Nếu bạn chỉ tò mò, bạn có thể dễ dàng viết một bài kiểm tra để so sánh tốc độ. Tuy nhiên, bạn cần phải nhớ rằng việc sử dụng bộ nhớ cho bảng tra cứu có thể ảnh hưởng đến phân trang trong các ứng dụng lớn hơn. Vì vậy, ngay cả khi phân trang nhanh hơn trong thử nghiệm nhỏ của bạn, nó có thể làm chậm mọi thứ xuống trong một ứng dụng lớn hơn sử dụng nhiều bộ nhớ hơn.

Answer 4

Nó từng là một tra cứu mảng là một tối ưu hóa tốt để thực hiện các phép tính trig nhanh.

Nhưng với lần truy cập bộ nhớ cache, bộ xử lý toán học tích hợp (sử dụng tra cứu bảng) và các cải tiến hiệu suất khác, tốt nhất là bạn nên tự xác định mã nào sẽ hoạt động tốt hơn.

Answer 5

Câu trả lời cho điều này phụ thuộc hoàn toàn vào số lượng giá trị trong bảng tra cứu của bạn. Bạn nói "tên miền là giữa 0,01 và 360,01", nhưng bạn không nói có bao nhiêu giá trị trong phạm vi đó có thể được sử dụng, hoặc bạn cần câu trả lời chính xác đến mức nào. Tha thứ cho tôi vì không mong đợi để xem các chữ số có nghĩa được sử dụng để truyền tải ý nghĩa tiềm ẩn trong bối cảnh phi khoa học.

Cần thêm thông tin để trả lời câu hỏi này. Phân phối giá trị mong đợi giữa 0,01 và 360,01 là bao nhiêu? Bạn đang xử lý rất nhiều dữ liệu khác với tính toán sin đơn giản()?

36000 giá trị chính xác gấp đôi mất hơn 256k bộ nhớ; bảng tra cứu quá lớn để vừa với bộ đệm L1 trên hầu hết các máy; nếu bạn đang chạy thẳng qua bảng, bạn sẽ bỏ lỡ L1 một lần cho mỗi truy cập sizeof (cacheline)/sizeof (double), và có thể nhấn L2. Mặt khác, nếu truy cập bảng của bạn ít nhiều ngẫu nhiên, bạn sẽ thiếu L1 gần như mỗi khi bạn thực hiện tra cứu.

Nó cũng phụ thuộc rất nhiều vào thư viện toán của nền tảng bạn đang sử dụng. Việc triển khai i386 thông thường của hàm sin, ví dụ, phạm vi từ ~ 40 chu kỳ lên đến 400 chu kỳ hoặc thậm chí nhiều hơn, tùy thuộc vào kiến ​​trúc vi mô và nhà cung cấp thư viện chính xác của bạn. Tôi đã không hẹn giờ thư viện Microsoft, vì vậy tôi không biết chính xác nơi thực hiện C# Math.sin sẽ giảm.

Vì tải từ L2 thường nhanh hơn 40 chu kỳ trên nền tảng lành mạnh, một hợp lý hy vọng bảng tra cứu sẽ được xem xét nhanh hơn trong sự cô lập. Tuy nhiên, tôi nghi ngờ bạn đang tính toán sin() trong sự cô lập; nếu đối số của bạn để sin() nhảy qua tất cả các bảng, bạn sẽ thổi các dữ liệu cần thiết cho các bước khác của tính toán của bạn ra khỏi bộ nhớ cache; mặc dù tính toán sin() nhanh hơn, nhưng sự chậm lại đến các phần khác của phép tính của bạn có thể lớn hơn tốc độ tăng tốc. Chỉ đo lường cẩn thận mới thực sự có thể trả lời câu hỏi này.

Tôi có hiểu các nhận xét khác của bạn rằng bạn đang thực hiện việc này như một phần của tính toán FFT không? Có một lý do mà bạn cần phải cuộn FFT của riêng bạn thay vì sử dụng một trong rất nhiều triển khai chất lượng cực kỳ cao đã tồn tại?

Answer 6

Kể từ khi bạn đề cập đến biến đổi Fourier là một ứng dụng, bạn cũng có thể xem xét để tính sin của bạn/cosin bằng cách sử dụng phương trình

sin (x + y) = sin (x) cos (y) + cos (x) sin (y)

cos (x + y) = cos (x) cos (y) - sin (x) sin (y)

Ie bạn có thể tính sin (n * x), cos (n * x) cho n = 0, 1, 2 ... lặp đi lặp lại từ sin ((n-1) * x), cos ((n-1) * x) và hằng số sin (x), cos (x) với 4 phép nhân. Tất nhiên chỉ hoạt động nếu bạn phải đánh giá sin (x), cos (x) trên một chuỗi số học.

So sánh các phương pháp tiếp cận mà không thực hiện thực tế là khó khăn. Nó phụ thuộc rất nhiều vào các bảng của bạn phù hợp với bộ đệm.

Answer 7

Vì bạn có thể có hàng ngàn giá trị trong bảng tra cứu, bạn có thể muốn có từ điển và khi bạn tính toán giá trị, hãy đặt nó vào từ điển, vì vậy bạn chỉ tính mỗi giá trị một lần và sử dụng hàm C# để thực hiện phép tính.

Nhưng, không có lý do gì để tính toán lại cùng một giá trị.