fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <cmath>
  5. #include <omp.h> // Include only if using OpenMP
  6.  
  7. #define LD_CONFIDENCE_THRESH 0.5
  8. #define MIN_KPS_PER_LANE_LINE 3
  9. #define N_POINTS 1000000
  10.  
  11. typedef struct {
  12.     double x;
  13.     double y;
  14.     double score;
  15. } key_point_t;
  16.  
  17. /* Original quadratic regression function */
  18. void quadratic_regression(const key_point_t *__restrict__ points, int n, double *__restrict__ a, double *__restrict__ b, double *__restrict__ c) {
  19.     double sum_x = 0.0, sum_x2 = 0.0, sum_x3 = 0.0, sum_x4 = 0.0;
  20.     double sum_y = 0.0, sum_xy = 0.0, sum_x2y = 0.0;
  21.     int valid_points = 0;
  22.     for (int i = 0; i < n; i++) {
  23.         /* Check if the point is valid */
  24.         if ((points[i].x != 0 || points[i].y != 0) && (points[i].score > LD_CONFIDENCE_THRESH)) {
  25.             double x = points[i].x;
  26.             double y = points[i].y;
  27.             /* Calculate powers of x on the fly (may do redundant multiplications) */
  28.             sum_x  += x;
  29.             sum_x2 += x * x;
  30.             sum_x3 += x * x * x;
  31.             sum_x4 += x * x * x * x;
  32.             sum_y  += y;
  33.             sum_xy += x * y;
  34.             sum_x2y += (x * x) * y;
  35.             valid_points++;
  36.         }
  37.     }
  38.     if (valid_points <= MIN_KPS_PER_LANE_LINE)
  39.         return;
  40.     double determinant = (valid_points * (sum_x2 * sum_x4 - sum_x3 * sum_x3)) -
  41.                          (sum_x * (sum_x * sum_x4 - sum_x2 * sum_x3)) +
  42.                          (sum_x2 * (sum_x * sum_x3 - sum_x2 * sum_x2));
  43.     if (determinant == 0)
  44.         return;
  45.     *a = ((valid_points * (sum_x2 * sum_x2y - sum_x3 * sum_xy)) -
  46.           (sum_x * (sum_x * sum_x2y - sum_xy * sum_x2)) +
  47.           (sum_y * (sum_x * sum_x3 - sum_x2 * sum_x2))) / determinant;
  48.     *b = ((valid_points * (sum_xy * sum_x4 - sum_x2y * sum_x3)) -
  49.           (sum_y * (sum_x * sum_x4 - sum_x2 * sum_x3)) +
  50.           (sum_x2 * (sum_x * sum_x2y - sum_xy * sum_x2))) / determinant;
  51.     *c = ((sum_y * (sum_x2 * sum_x4 - sum_x3 * sum_x3)) -
  52.           (sum_x * (sum_xy * sum_x4 - sum_x2y * sum_x3)) +
  53.           (sum_x2 * (sum_xy * sum_x3 - sum_x2y * sum_x2))) / determinant;
  54. }
  55.  
  56. /* Fill an array of key_point_t with random data.
  57.    We generate x and y values between -50 and 50, and a score between 0.5 and 1.0 to ensure the point is valid. */
  58. void fill_points(key_point_t *points, int n) {
  59.     for (int i = 0; i < n; i++) {
  60.         points[i].x = ((double)rand() / RAND_MAX) * 100.0 - 50.0;
  61.         points[i].y = ((double)rand() / RAND_MAX) * 100.0 - 50.0;
  62.         points[i].score = ((double)rand() / RAND_MAX) * 0.5 + 0.5;
  63.     }
  64. }
  65.  
  66. int main() {
  67.     key_point_t *points = (key_point_t *)malloc(N_POINTS * sizeof(key_point_t));
  68.     if (!points) {
  69.         fprintf(stderr, "Memory allocation failed\n");
  70.         return 1;
  71.     }
  72.     srand((unsigned int)time(NULL));
  73.     fill_points(points, N_POINTS);
  74.  
  75.     double a1 = 0, b1 = 0, c1 = 0;
  76.     double a2 = 0, b2 = 0, c2 = 0;
  77.     clock_t start, end;
  78.     double time_original;
  79.  
  80.     /* Time the original algorithm */
  81.     start = clock();
  82.     quadratic_regression(points, N_POINTS, &a1, &b1, &c1);
  83.     end = clock();
  84.     time_original = ((double)(end - start)) / CLOCKS_PER_SEC;
  85.  
  86.  
  87.     printf("Original: a = %.6f, b = %.6f, c = %.6f, time = %f seconds\n", a1, b1, c1, time_original);
  88.  
  89.     free(points);
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0.06s 24348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original: a = 0.000033, b = -0.000104, c = 0.000560, time = 0.005256 seconds
https://ideone.com/YYtCge
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!