¿Cómo ordenar una matriz multidimensional con respecto a otra matriz también multidimensional en C, C++ o Fortran para miles de millones de puntos de manera rápida?

Answer

1. 

   davy.ai

   May 29, 2023 at 11:12 am

   Un enfoque posible para ordenar el conjunto de datos B en términos del conjunto de datos A sería crear una matriz multidimensional que combine ambos conjuntos y luego ordenar esa matriz en función de los valores en el conjunto de datos A.

   Aquí hay un ejemplo de código en C para lograr esto:

   #include <stdio.h>
   #include <stdlib.h>
   
   #define NUM_POINTS 1000000000
   
   struct point {
       float cx, cy, cz, vx, vy, vz;
   };
   
   int compare_points(const void * a, const void * b) {
       const struct point * point_a = *(const struct point **)a;
       const struct point * point_b = *(const struct point **)b;
       if (point_a->cx < point_b->cx) {
           return -1;
       } else if (point_a->cx > point_b->cx) {
           return 1;
       } else {
           if (point_a->cy < point_b->cy) {
               return -1;
           } else if (point_a->cy > point_b->cy) {
               return 1;
           } else {
               if (point_a->cz < point_b->cz) {
                   return -1;
               } else if (point_a->cz > point_b->cz) {
                   return 1;
               } else {
                   return 0;
               }
           }
       }
   }
   
   int main() {
       // Crear dos arreglos de puntos
       struct point ** set_a = malloc(sizeof(struct point *) * NUM_POINTS);
       struct point ** set_b = malloc(sizeof(struct point *) * NUM_POINTS);
       for (int i = 0; i < NUM_POINTS; i++) {
           set_a[i] = malloc (sizeof(struct point));
           set_a[i]->cx = rand();
           set_a[i]->cy = rand();
           set_a[i]->cz = rand();
           set_b[i] = malloc (sizeof(struct point));
           set_b[i]->cx = set_a[i]->cx;
           set_b[i]->cy = set_a[i]->cy;
           set_b[i]->cz = set_a[i]->cz;
           set_b[i]->vx = rand();
           set_b[i]->vy = rand();
           set_b[i]->vz = rand();
       }
   
       // Ordenar los arreglos en función de set_a
       qsort(set_b, NUM_POINTS, sizeof (struct point *), compare_points);
   
       // Imprimir los primeros y últimos elementos en set_b para verificar la ordenación
       printf("%8.0f %8.0f %8.0f %8.0f %8.0f %8.0f\n", set_b[0]->cx, set_b[0]->cy, set_b[0]->cz, set_b[0]->vx, set_b[0]->vy, set_b[0]->vz);
       printf("%8.0f %8.0f %8.0f %8.0f %8.0f %8.0f\n", set_b[NUM_POINTS-1]->cx, set_b[NUM_POINTS-1]->cy, set_b[NUM_POINTS-1]->cz, set_b[NUM_POINTS-1]->vx, set_b[NUM_POINTS-1]->vy, set_b[NUM_POINTS-1]->vz);
   
       // Liberar memoria
       for (int i = 0; i < NUM_POINTS; i++) {
           free(set_a[i]);
           free(set_b[i]);
       }
       free(set_a);
       free(set_b);
   
       return 0;
   }
   

   En este ejemplo, primero generamos dos arreglos de puntos (set_a y set_b) con coordenadas y velocidades aleatorias. Luego, usamos la función qsort para ordenar el arreglo set_b en función de los valores en el arreglo set_a definiendo una función de comparación (compare_points) que compara los valores cx, cy, y cz de dos puntos.

   Tenga en cuenta que la complejidad temporal de este enfoque es O(n*logn), lo que puede tomar mucho tiempo para ordenar un conjunto de datos con miles de millones de puntos. Para hacerlo más rápido, podemos intentar paralelizar el proceso de ordenación o usar un marco de cómputo distribuido como Apache Spark.</stdlib.h></stdio.h>

Comments are closed.