3
\$\begingroup\$

I implemented a program that does the following:

Consider the positive quadrant of the xy plane. A colored point is a triple (x,y,c) where x is its x-axis coordinate, y is the y-axis coordinate, and c is an integer representing its color.

This program needs to read a set of N colored points, then take some queries and answer them.

A query is represented by four values, (x₁, y₁, x₂, y₂) and is used to get the number of different colors inside the rectangle confined within the two points of given coordinates.

This program will read:

  1. The number N of colored points and M of queries
  2. N lines, each containing the three numbers that identify a colored point
  3. M lines, each containing a query

It will only output the answers to each query. That is the number of distinct colors within the rectangles.

NOTE

  • This code does not perform input-checks. Don't tell me it doesn't. I know. This exercise was not about input-checking. It also doesn't print any messages to the user. This program is to be tested automatically by my university online platform, so it has to strictly get input from stdin print the output. Also please don't comment on usage of scanf() and printf(); I know there are better options but that's not the point.

That being said, I feel that complexity-wise, this algorithm isn't very efficient, or at least could be done better. I haven't done a thorough analysis of it, but the complexity is at least O(NM), which is potentially very very bad. I'm interested in constructive feedback on how I could improve the algorithm to make it faster and do fewer tests.

Here's the code:

#include <stdio.h>
#include <stdlib.h>

typedef struct colpt {
    int x;
    int y;
    int c;
} Cp;

typedef struct q {
    int x1;
    int x2;
    int y1;
    int y2;
} Query;

typedef struct color {
    int c;
    struct color *nextPtr;
} Color;

void freeList(Color **lPtr) {
    Color *currPtr = *lPtr;

    while(currPtr != NULL) {
        Color *tempPtr = currPtr;
        currPtr = currPtr->nextPtr;
        free(tempPtr);
    }
}

Color *newNode(int color) {
    Color *newPtr = malloc(sizeof(Color));
    if(newPtr == NULL) exit(EXIT_FAILURE);

    newPtr->c = color;
    newPtr->nextPtr = NULL;
    return newPtr;
}

int insertAndIncrease(Color **lPtr, int thiscolor) {
    Color *currPtr = *lPtr;
    Color *prevPtr = NULL;

    if(currPtr == NULL) { // list is empty, add current color and return 1
        *lPtr = newNode(thiscolor);
        return 1;
    }

    while(currPtr != NULL && currPtr->c != thiscolor) {
        prevPtr = currPtr;
        currPtr = currPtr->nextPtr;
    }

    if(currPtr == NULL) { // found no color equal to the one passed, so it's a new color
        prevPtr->nextPtr = newNode(thiscolor);
        return 1;
    }
    return 0;
}

void processQuery(Cp *points, int npoints, Query q, int *ncolors) {
    Color *colors = NULL;

    for(size_t i = 0; i < npoints; i++) {
        if(points[i].x >= q.x1 && points[i].x <= q.x2 && points[i].y >= q.y1 && points[i].y <= q.y2) { // if check is passed, then the point is inside the rectangle
            *ncolors = *ncolors + insertAndIncrease(&colors, points[i].c);
        }
    }
    freeList(&colors);
}

void processQueries(Cp *points, int npoints, Query *queries, int nqueries) {
    for(size_t i = 0; i < nqueries; i++) {
        int thisQColors = 0;
        processQuery(points, npoints, queries[i], &thisQColors);
        printf("%d\n", thisQColors);
    }
}

int main() {
    int numPoints, numQueries;

    scanf("%d%d", &numPoints, &numQueries); // get number of colored points

    Cp *arr = malloc(sizeof(Cp) * numPoints); // allocate array of numPoints colored points
    if(arr == NULL) return EXIT_FAILURE;


    Query *queries = malloc(sizeof(Query) * numQueries); // allocate array of numQueries queries
    if(queries == NULL) return EXIT_FAILURE;


    for(size_t i = 0; i < numPoints; i++) { // fill the array
        scanf("%d%d%d", &arr[i].x, &arr[i].y, &arr[i].c);
    }

    for(size_t i = 0; i < numQueries; i++) { // get the queries
        scanf("%d%d%d%d", &queries[i].x1, &queries[i].y1, &queries[i].x2, &queries[i].y2);
    }

    processQueries(arr, numPoints, queries, numQueries);

    free(arr);
    free(queries);

    return EXIT_SUCCESS;
}

Example inputs and outputs:

INPUT
6 4
0 0 1
6 0 1
6 1 13
1 3 8
4 4 9
4 6 137000
2 2 9 7
0 0 7 7 
6 2 7 8 
0 2 5 5

OUTPUT
2
5
0
2

---

INPUT

10 30
3 16 6
11 1 12
16 3 32
7 7 25
3 14 4
3 0 13
6 15 19
1 4 50
1 10 19
11 5 35
7 10 16 14
2 1 16 8
3 15 11 16
14 4 15 15
2 12 3 15
11 15 16 16
3 2 10 9
1 14 9 16
3 3 3 7
4 6 8 15
14 2 15 4
10 15 11 16
4 0 13 5
2 6 5 10
7 6 12 9
1 1 2 9
5 12 11 15
15 1 15 3
6 9 14 11
15 0 16 3
14 0 16 12
15 9 15 16
7 1 13 8
7 2 8 10
7 2 11 12
11 7 13 10
3 3 9 4
11 11 14 11
5 6 6 16
12 8 15 9

OUTPUT

0
4
2
0
1
0
1
3
0
2
0
0
2
0
1
1
1
0
0
1
1
0
3
1
2
0
0
0
1
0

---

INPUT

16 3
7 97 1
21 8 2
30 21 5
14 45 4
5 83 0
7 2 2
12 91 3
3 26 8
1 62 3
20 34 6
15 65 8
18 14 0
29 49 1
29 58 6
27 28 3
27 13 6
2 69 22 99
25 50 26 57
15 50 16 96

OUTPUT
3
0
1
```
\$\endgroup\$
  • 1
    \$\begingroup\$ Were upper limits specified for the coordinates and the color? \$\endgroup\$ – harold Mar 16 '20 at 23:01
  • 1
    \$\begingroup\$ @harold INT_MAX was the upper limit \$\endgroup\$ – Samuele B. Mar 16 '20 at 23:05
4
\$\begingroup\$

I'm interested in constructive feedback on how I could improve the algorithm to make it faster and do less checks.

processQuery() is O(n) with

for(size_t i = 0; i < npoints; i++) {

An alternative would create a binary like tree in 2 dimensions. Not a BST, bit a quadtree. Then the searching within a rectangle could take advantage of potentially O log(n).

As with any advanced search techniques, the real advantage occurs with large n, not so much with n of OP's test code.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you for the answer. I realize it won't make a difference at a small input size, but here's to things to consider: 1. Our programs will only be accepted by our online platform if it gives the output in under a second. It gets tested against 10 inputs and mine has a problem with one test case (5000 points and 5000 queries), in which it almost takes 2 seconds, indicating that there's margin of improvement 2. I am studying not so much the C code, as much as the algorithm. This is an algorithms course I'm following and I'm looking for the most efficient solution asymptotically. \$\endgroup\$ – Samuele B. Mar 17 '20 at 1:38
3
\$\begingroup\$

The storage of both points and queries is suboptimal - in both cases, they are plain unsorted arrays. We could use better strategies for representing one or both.

As a simple example, consider keeping points as a list of rows in ascending order, with each row being a list of points. Now, when we evaluate a query, we can quickly skip the rows that are before the bounding rectangle, and we can finish when we reach the first row that's after the rectangle. Similarly, we can stop examining a row and quickly move to the next row when we reach the horizontal bound.

Further improvements in indexing rows and columns can be made, potentially leading to a quadtree representation, as used in most serious geospatial applications.


Building a linked list of colours for each query involves a lot of small memory allocations, which can be a serious performance hit. We could instead count distinct colours as we read the list of points, and then use a single array of that size to note the colours found (this can even be shared amongst all the queries). We might consider keeping this array sorted (using bsearch() to find elements), though the cost/benefit trade-off to that is less clear-cut than in a case where we know we have many times more lookups than insertions.


We're gaining nothing by reading all queries into an array and then executing them sequentially. We could just execute each query immediately after we read it.

\$\endgroup\$
  • \$\begingroup\$ As per your point of sorting points, that's the first thing I thought about. However, the second thing I thought is that I'm still not sure how, after having sorted the points (say by their y coordinate), I can skip to the rows that are withing the bounds of the rectangle. Won't I still have to test at least one coordinate per point? This might save me a few checks but asymptotically this part is still O (n) unless I'm missing something. Actually, having to sort first this'll now be O (nlogn). \$\endgroup\$ – Samuele B. Mar 17 '20 at 12:52
  • \$\begingroup\$ My intuition was to somehow use a binary search on the sorted point array, but instead of looking for one key, I'll look for keys within a given range. However, that would only allow me to find a point within the range, whereas what I need to do is find every point within that range. \$\endgroup\$ – Samuele B. Mar 17 '20 at 12:55
  • \$\begingroup\$ I wrote this answer in fairly broad terms on purpose because so much of the workload depends on the nature of the inputs, especially the point density. I'm not recommending any particular approach but rather giving some options to explore. Certainly, a sorted list of sorted rows (or a sorted list of sorted columns) is just a starting point - I'm sure you can think how to best organise your data. \$\endgroup\$ – Toby Speight Mar 17 '20 at 13:53
  • \$\begingroup\$ As hinted, the quadtree will enable the very best performance on large data sets (if you keep a colour-list in each node, then you can update your results directly from that when you reach one that's entirely within the search bounds, without traversing any deeper, and certainly without visiting individual points). \$\endgroup\$ – Toby Speight Mar 17 '20 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.