Performance: Looping on data on the server or getting data looped on clients via socket connection

Question

I have a web application the mobile app users are connected it by using websocket. The server has data A that can be changed in time. And the clients (mobile app) have data B that also can be changed in time.

When user emitting a message (a request to get data D) to the server by using websocket, I have to apply loops when executing user data B to generate data C and then data D. For this case, there are 2 options I found:

(detail: Because of generating data D has some database operations, clients cannot generate it on the mobile app)

1st: I can apply nested loops to server data A and user data B on the server when user emit a message (request) at every single time. The operation has two nested loop and time complexity is O(A*B). After the loop I would have data C to generate data D.

Pseudo code:

function generateC () {
    var C = []
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < B.length; j++) {
            if (A[i] == B[j]) {
                C.push(A[i])
            }
        }
    }
    generateD(C)
}

2nd: I can send server data A to the clients after compressed the data. Then the clients looped to apply the own data B to data A to generate data C. In this case, when considering the server load time complexity is O(N) N is being characters length I guess.

Pseudo code:

var compressedA = gzip.compress(A)
socket.to("userX").emit("C", compressedA)
socket.on("C", function (C) {
    generateD(C)
})

Also the second method makes network traffic on my bandwidth. I guess network operations more expensive then CPU operations.

So, it's worth doing that if the server has 350.000 active users?

Answer 1

You're computing a set intersection. If you want to do it in linear time very quickly and not in quadratic time, then this is an extremely fast solution (will outperform even the fastest data structure solutions using, say, hash tables) if you can afford the extra boolean field (or bit field if you have a spare bit handy):

var C = [];

// Mark each element in A.
for (let i = 0; i < A.length; i++) {
    A[i].traversed = true;
}

// Look for elements in B that were marked above.
for (let i = 0; i < B.length; i++) {
    // If B[i] was marked by the above loop (meaning element 
    // was found in both A and B), add it to C.
    if (B[i].traversed) {
        C.push(B[i]);
        B[i].traversed = false;
    }
}

// C now contains the set intersection.

I recommend doing it this way on the server for a starter instead of trying to get clients to compute it for you. I doubt it'll become a bottleneck if you do it this way in linear time and there's still room for further micro-optimizations otherwise.