Faster way to check for a string in a array of string

Question

I have a array of object, I need to sort them by time (hours, days or months) and separate the number of new IP.

result is an array of object with property time (JavaScript timestamp), user IP (string).

This code does work, but for request resulting in over 10k element, it is slow as hell.

I think the problem is the comparison for new IP, but I can't find any faster way.

Here the slow code:

    result.forEach(function (element) {
        if (ip.indexOf(element.get('user_ip')) < 0) {
            ip.push(element.get('user_ip'));
            visitors_u[get_time_index(element, type)] = visitors_u[get_time_index(element, type)] + 1;
        }
        visitors[get_time_index(element, type)] = visitors[get_time_index(element, type)] + 1;

    });

If you want to try the app, you ll need a mongoDB database:

var mongoose = require('mongoose'),
    express = require('express'),
    app = express(),
    bots = [/bot/i, /crawler/i, /spider/i, /topsy/i, /search/i, /coccoc/i],
    db_web = 'player_web_log_xxx',
    db;


function connect (callback) {
    console.log('Connecting to MongoDB...');
    mongoose.connect('mongodb://xxx/stats');          //Creer la connexion a mongodb
    db = mongoose.connection;                                           //Assigner la connexion

    console.log('Starting server');
    app.listen(8080);                                                   //Lancer le serveur
    console.log('Listening');

    db.on('error', console.error.bind(console, 'connection error:'));
    db.once('open', function () {                                       //Une fois connecte

        console.log('Connected');

        S_logs =  new mongoose.Schema({
                /*
                user_ip     : String
                video_id    : String,                                       //Identifiant de la video
                time        : Number,
                */
            }, {
                strict: false,
                collection: db_web
        });

        M_logs = mongoose.model(db_web, S_logs, db_web);

        console.log('Ready');
        callback();
    });
}

function x_process(query, type, from, to) {
    query.exec(function (err, result) {                     //Executer la requete
        if (err) {
            console.log('ERR: ' + err);
            result = [];                                    //Si erreur, vider result
        }
        views_render(result, type, from, to);

    });
}

function get_size(type, to) {
    switch (type) {
    case 'hour':
    case 'hours':
        return 24;
    case 'day':
    case 'days':
        var d = new Date(to * 1000);
        return new Date(d.getFullYear(), d.getMonth(), 0).getDate() + 1;
    case 'month':
    case 'months':
        return 12;
    default:
        return 0;
    }
}

function get_time_index(element, type) {
    var time = new Date((element.get('time') || element.date) * 1000);
    switch (type) {
    case 'hour':
    case 'hours':
        return time.getHours();
    case 'day':
    case 'days':
        return time.getDate();
    case 'month':
    case 'months':
        return time.getMonth();
    default:
        return 0;
    }
}
/*_________________________________________________________________.
|                                                                  |
|                              Views                               |
|/terminal/web/views/_ et /terminal/mobile/views/_                 |
|_________________________________________________________________*/

    function views_get_query(from, to) {
        return M_logs.find()
        .select('time user_ip user_agent')
        .gt('time', from)
        .lt('time', to)
        .ne('video_id', -1)
        .ne('from', 'mobile')
        .nin('user_agent', bots);
    }

    function views_render(result, type, from, to) {
        var visitors = [],
            visitors_u = [],
            ip = [],
            i = 0;

        console.log('Init');

        while (visitors.length < get_size(type, to)) {
            visitors.push(0);
            visitors_u.push(0);
        }

        console.log('Sort');

        result.forEach(function (element) {
            if (ip.indexOf(element.get('user_ip')) < 0) {
                ip.push(element.get('user_ip'));
                visitors_u[get_time_index(element, type)] = visitors_u[get_time_index(element, type)] + 1;
            }
            visitors[get_time_index(element, type)] = visitors[get_time_index(element, type)] + 1;

        });

        if (type === 'days') {
            console.log('Formating');
            visitors.shift();
            visitors_u.shift();
        }

        console.log('Sending');

        if(visitors.length === 0 && visitors_u.length === 0) {
            console.log('No data');
            //res.render('404.ejs', {from: from, to: to});
        } else {
            console.log('From ' + from + ' to ' + to + ' :');
            console.log('Visitors  :' + visitors);
            console.log('Visitors_u:' + visitors_u);
            //res.render(view, {from: from, to: to, visitors: visitors, visitors_u: visitors_u});
        }
    }

    /*
        Routage des requete vers le fichier ejs correspondant avec les donnees demandée
    */

connect(function () {
    var now = new Date(),
        from,
        to,
        query;

    console.log('Got request for /web/views/hours');

    from = new Date(now.getFullYear(), now.getMonth(), now.getDate(), 0, 0, 0, 0).getTime() / 1000;
    to = now.getTime() / 1000;

    query = views_get_query(from, to);

    x_process(query, 'hours', from, to, views_render);
});

Answer 1

As far as I've read: indexOf is a slow linear search through your entire list to see if it finds the string.

So:

If you either sort the values in ip so you can use a faster searching algorithm or implement ip as a hashmap you should be able to get improved efficiency.

So:

Option 1:

• Sort the array that holds all your ip values somehow. (You could sort by ip 'value' or something else)
• Implement & use non-linear searching algorithm. (Eg.: Binary Search)

Note: If you're going to sort the ip array, you might want to use a quick sorting algorithm for that as well

Option 2:

• Implement Java HashMap (Add all the ip's as keys with value 1 or whatever you need, this way you instantly know that that IP has been added already if the corresponding hashmap key already has a value.)
• Access all the keys for your ip's.

Here's an example of someone's custom hashmap implementation, for option 2: https://gist.github.com/alaa-eddine/6317515

Note: If you cannot create the ip array as a hashmap, see if your performance still increases by creating a hashmap and adding all the ip's that way. Then you only have to iterate through the *full* ip array once to create the hashmap, and after that you can use the hashmap.

Answer 2

As ZeroStatic hinted, you should use a hashmap, fortunately you can simply use an object for this ( assuming i.p. addresses are always strings ).

You would declare ip as a an object intead of an array

var ip = {};

Your loop would look then look like this:

result.forEach(function (element) {
    var user_ip = element.get('user_ip'); //Cache this for extra speeds
    if (!ip[user_ip]) {
        ip[user_ip] = true;
        visiteurs_u[get_time_index(element, type)] = visiteurs_u[get_time_index(element, type)] + 1;
    }
    visiteurs[get_time_index(element, type)] = visiteurs[get_time_index(element, type)] + 1;
});

Furthermore, forEach is not ideal for time sensitive operations, the good old for loop with cached length will always beat it.

So something like this:

for( var i = 0 , length = result.length ; i < length ; i++ ){
    var element = result[i]
    var user_ip = element.get('user_ip'); //Cache this for extra speeds
    var time_index = get_time_index(element, type); //Cached as well for extra speeds
    if (!ip[user_ip]) {
        ip[user_ip] = true;
        uniqueVisitors[time_index] += 1;
    }
    visitors[time_index] += 1
};

Furthermore I replaced visiteurs with visitors, no French in code, sorry ;) Also the use of +=1 makes much more cleaner what you are doing.

Answer 3

As reference:

I ended up using hashmap for ip.

I also used reverse while (sorry, I hate for syntax).

3933ms for 314530 element instead of 985867ms : )

while (i--) {
            user_ip = result[i].get('user_ip');
            ti = get_time_index(result[i], type);
            if (!ip.has(user_ip)) {
                ip.set(user_ip);
                visiteurs_u[ti] = visiteurs_u[ti] + 1;
            }
            visiteurs[ti] = visiteurs[ti] + 1;
        }