items and enum O(n^2) time complexity

[chrismwendt]

How difficult would it be to optimize the validation that all items in an array are members of some specified array? Empirical testing shows that this validation has O(n^2) time complexity, and I wonder if this could easily be cut to O(n*log(n)) with a binary search, or perhaps even O(n) using hashing.

Here is the test that I used:

var jjv = require('jjv');

function test(n) {
    var arr1 = [n];
    var arr2 = [n];

    for (var i = 0; i < n; i++) {
        arr1[i] = Math.floor(Math.random() * n);
        arr2[i] = Math.floor(Math.random() * n);
    }

    var env = jjv();

    var schema = {
        properties: {
            left: {
                type: 'array'
            },
            right: {
                type: 'array',
                items: {
                    enum: { $data: '2/left' }
                }
            }
        }
    };

    var data = {
        left: arr1,
        right: arr2
    };

    var s = Date.now();

    var result = env.validate(schema, data);

    console.log(n + ' ' + (Date.now() - s) / 1000);
}

function main() {
    for (var n = 1; n < 100000; n *= 1.1) {
        test(n);
    }
}

main();

[acornejo]

To use binary search on the array, would require first sorting the array. The elements of the array need not be of the same type, so you would need to sort based on something else.

Similarly, to do the hashing, we would first need to create a new hash, and insert all the array items into the hash.

The benefits of this would only be exploited when validating two very large arrays, and the more common use case of smaller arrays would suffer.

So, to answer your question: I think it would be easy, but I don't think the benefits that it would bring when validating huge arrays are worth the cost we would pay when validating smaller arrays (much more common).

That being said, feel free to implement this and issue a pull-request. If when running the benchmarks there is not a significant degradation of speed (and if your code is clean and simple) I will accept the pull request.