Take from top, evaluate, put on bottom

Question

In this example, I am only looking for the first duplicate - curious if this logic in for loop (take from the top, evaluate, put on the bottom) pattern has a standard form

function findOneDupe(input){
 var b = input.split(/\s|\n/).map(Number);
 b.shift();
 for (var i=0;i<b.length;i++){
 var e = b.shift();
 if (b.indexOf(e) == -1) return e;
 b[b.length] = e;
 }
 return -1;
}

• Heslacher: Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers .

Answer 1

 function findOneDupe(input){

You name this function findOneDupe, but this code finds the first element that is not duplicated.

 function findFirstUnique(input) {

Now it does what it says, not the opposite of what it says.

 var b = input.split(/\s|\n/).map(Number);

Why call this b? That gives me no idea what it holds.

 var tokens = input.split(/\s|\n/).map(Number);

The name tokens is far more understandable in terms of whitespace delineated text.

 b.shift();

Why? Presumably you have some cruft to remove from the array. Comment this and explain why it needs to be done. Then you don't have to worry about someone optimizing it out later.

 for (var i=0;i<b.length;i++){
 var e = b.shift();
 if (b.indexOf(e) == -1) return e;
 b[b.length] = e;
 }

This seems more complicated than it needs to be. You are both maintaining an index variable and removing from the array. Why not pick one or the other?

 for (var i=0; i < tokens.length; i++) {
 if (tokens.indexOf(tokens[i], i+1) == -1 && tokens.indexOf(tokens[i]) == i) {
 return tokens[i];
 }
 }

Now we don't add or remove from the array at all. Which is good, since Javascript arrays are not lists. Removing and adding can cause the array to not fit its memory allocation anymore. When that happens, the array will be copied into a new memory location. Pure waste considering that you never use the array outside this function.

Note that the two indexOf checks will never check more elements than your single check. The first one only checks things after i and the second one only checks up to i (because it always finds at i).

Note that this takes \$O(n^2)\$ time in the worst case, as you loop over every element and search the array for it. You can get better asymptotic performance by sorting the array.

 tokens.sort();
 var i = 1;
 while (i < tokens.length) {
 if (tokens[i-1] != tokens[i]) {
 return tokens[i-1];
 }
 do {
 i++;
 } while (tokens[i-1] == tokens[i] && i < tokens.length);
 // we want to get all the way past anything equal 
 // to the original tokens[i-1] value
 i++;
 }

This takes \$O(n \log n)\$ time for the sort and linear time to find any unique elements.

• Kevin Leary: Thanks very much for the feedback - I don't have enough cred to upvote or I would. I renamed the function poorly when I posted because it had a nonsense name on my local. Anyhow, the original shift is to remove a header that comes with the payload - next time around I will include details like this. In the main part that I was asking about - the for loop, I take the item out of the set so indexOf will return false if it is unique. I put it back in so if it is not unique, the duplicate won't appear unique when it's turn for evaluation comes up. I will study your comments more, and try out.
• Jonah: Note that your rewrite will find the smallest unique element, rather than the first unique element of the original array. See my answer for a method which combines sorting and the original array's order to find the first unique element in O(n log n) time, using the fact that object key creation and lookup is O(1).

Answer 2

First, I would suggest against array.shift. While it is harmless in this case, you can unknowingly mutate an array you don't own.

Also, \n with a \s is already redundant as \s already covers \n.

Now if the goal is finding a duplicate, this can easily be done using array.find, array.indexOf and array.lastIndexOf. If a value is a duplicate, it should only show up in the same index.

function findOneDupe(input){
 const result = input.split(/\s/).map(Number).find((number, index, array) => array.indexOf(number) !== array.lastIndexOf(number));
 return typeof result !== 'undefined' ? result : -1;
}

Older browsers may use array.filter instead of array.find with the difference that array.filter won't stop at the first match and it returns an array of values instead of a single value.

Answer 3

In your comment to @mdfst13, you mention that "the original shift is to remove a header that comes with the payload."

Idiosyncratic data validation like this that is specific to one use-case doesn't belong in a re-usable library function such as "findFirstDuplicate" or "findFirstUnique". Indeed, even the token parsing and finding the first unique element of an array don't belong together: they're different concerns and belong in different functions.

I'd split it up like this:

function spaceDelimitedNumbers(input) {
 return input.split(/\s+/).map(Number);
}

Note: \s+ rather than \s is probably want you want here. Otherwise, numbers separated by more than one whitespace characters will return themselves plus a "0" for each extra whitespace character.

As for finding the first unique element, as others have mentioned, sorting the array first will give you better performance. But to ensure you find the first unique element from the original, unsorted array, you need to do something like this:

function firstUniq(arr) {
 var origOrder = arr.reduce((m,x,i) => m[x] ? m : Object.assign(m,{[x]: i}), {});
 var uniqs = arr.slice(0).sort().filter((x,i,a) => x != a[i+1] && x != a[i-1]);
 return uniqs.sort((a,b) => origOrder[a] - origOrder[b])[0];
}

However, while the above will be much faster for large arrays, it will be slower for small arrays, though probably not noticeably so unless you are running it many times. So, if your arrays are small you can get away with the naive implementation:

function firstUniq(arr) {
 return arr.find((x,i) => arr.slice(0,i).concat(arr.slice(i+1)).indexOf(x) == -1);
}

Finally, now that you have two, well-focused utility functions, you can put together a throw-away function for your particular use case. This one should be named to reflect what you are actually doing in your application. It sounds like you're parsing some kind of payload, so this might look like:

function firstUniqNumberInPayload(input) {
 var payload = spaceDelimitedNumbers(input);
 var payloadBody = payload.slice(1); // remove the header
 return firstUniq(payloadBody);
}

• Kevin Leary: Thank you very much - the question really was intended to be "is there a pattern for removing a value from a set, using an optimized native function like IndexOf to quickly evaluate the set for uniqueness and then return the value from the function or return it to the set". It sounds like the answer is no.
• Jonah: In that case, you might want to check out: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
• Kevin Leary: Lol, thanks. What I took out of this is that even in my testing I should breakout the data preparation from the generic function. If I post again, I have a much better idea of how to do it and what to expect. I am looking at incorporating your suggestions as well as the others.
• Jonah: "What I took out of this is that even in my thinking I should breakout the data preparation from the generic function." -- FYP :)