Revisions to Count duplicates in a JavaScript array

Commonmark migration

Source Link

edited Jun 10, 2020 at 13:24

Community Bot

1

##Reduce time

Reduce time

##A look at memory.

A look at memory.

deleted 1204 characters in body

Source Link

edited Sep 4, 2018 at 16:28

Blindman67

22.3k
2
16
40

##Reduce time

You can improve the function's time complexity at the expense of memory by tracking the duplicates in a separate Set. This will reduce the number of iterations by the number of unique items in the input array, and increase the memory need by the same number.

function countDuplicates(original) {
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
    }
  }
  return duplicates.size;
} 



/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

##A look at memory.

Just out of interest I wanted to see the memory use. It turns out that the more unique items the lower the use (makes sense). The next snippet shows the memory use over 10000 calls to random arrays 1000 items long with a max range of item values to 10000.

function countDuplicatesMemory(original) {
  var maxSize = 0;
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
      maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
    }
  }
  return maxSize;
}



var memoryUse = 0;
var min = Infinity;
var max = 0;
const cycles = 10000;
const arraySize = 1000;
const maxRange = 10000;

for(let i = 0; i < cycles; i++){
  const arr = [];
  const range = Math.random() * maxRange | 0;
  for(let i = 0; i < arraySize; i++){
     arr.push(Math.random() * range | 0);
  }
  const mem = countDuplicatesMemory(arr);
  memoryUse += mem;
  min = Math.min(mem, min);
  max = Math.max(mem, max);
}
console.log("Mean memory use O(n * " + (memoryUse / cycles / arraySize).toFixed(3)+ ")");
console.log("Min memory use  O(n * " + (min / arraySize).toFixed(3)+ ")");
console.log("Max memory use  O(n * " + (max / arraySize).toFixed(3)+ ")");

The mean memory use is around O(n * 0.85)

These values are for a random set of values, there are cases where non random values may push the max memory just over O(n)

You can improve the function's time complexity at the expense of memory by tracking the duplicates in a separate Set. This will reduce the number of iterations by the number of unique items in the input array, and increase the memory need by the same number.

function countDuplicates(original) {
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
    }
  }
  return duplicates.size;
}


/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

##Reduce time

You can improve the function's time complexity at the expense of memory by tracking the duplicates in a separate Set. This will reduce the number of iterations by the number of unique items in the input array, and increase the memory need by the same number.

function countDuplicates(original) {
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
    }
  }
  return duplicates.size;
} 



/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

##A look at memory.

Just out of interest I wanted to see the memory use. It turns out that the more unique items the lower the use (makes sense). The next snippet shows the memory use over 10000 calls to random arrays 1000 items long with a max range of item values to 10000.

function countDuplicatesMemory(original) {
  var maxSize = 0;
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
      maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
    }
  }
  return maxSize;
}



var memoryUse = 0;
var min = Infinity;
var max = 0;
const cycles = 10000;
const arraySize = 1000;
const maxRange = 10000;

for(let i = 0; i < cycles; i++){
  const arr = [];
  const range = Math.random() * maxRange | 0;
  for(let i = 0; i < arraySize; i++){
     arr.push(Math.random() * range | 0);
  }
  const mem = countDuplicatesMemory(arr);
  memoryUse += mem;
  min = Math.min(mem, min);
  max = Math.max(mem, max);
}
console.log("Mean memory use O(n * " + (memoryUse / cycles / arraySize).toFixed(3)+ ")");
console.log("Min memory use  O(n * " + (min / arraySize).toFixed(3)+ ")");
console.log("Max memory use  O(n * " + (max / arraySize).toFixed(3)+ ")");

The mean memory use is around O(n * 0.85)

These values are for a random set of values, there are cases where non random values may push the max memory just over O(n)

Post Undeleted by Blindman67

occurred Sep 4, 2018 at 15:56

deleted 1204 characters in body

Source Link

edited Sep 4, 2018 at 15:55

Blindman67

22.3k
2
16
40

You can improve the function's time complexity at the expense of memory by tracking the duplicates in a separate setSet. This will reduce the number of iterations by the number of unique items in the input array, and increase the memory need by the same number.

function countDuplicates(original) {
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
    } else {
      uniqueItems.add(value);
    }
  }
  return duplicates.size;
}


/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

You canA further reduce the memory complexity by increasing the logic inimprovement can be gained if you delete duplicates from the loop, thisunique set as you go. This will slow downbring the function by not increase its time complexitymemory use down.

function countDuplicates(original) {
  var maxSize = 0;
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      uniqueItems.delete(value);
 
    } else {
      uniqueItems.add(value);
    }
    maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
  }
log(maxSize)
  return duplicates.size;
}


/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

You can improve the function's time complexity at the expense of memory by tracking the duplicates in a separate set. This will reduce the number of iterations by the number of unique items in the input array, and increase the memory need by the same number.

function countDuplicates(original) {
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
    } else {
      uniqueItems.add(value);
    }
  }
  return duplicates.size;
}


/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

You can further reduce the memory complexity by increasing the logic in the loop, this will slow down the function by not increase its time complexity.

function countDuplicates(original) {
  var maxSize = 0;
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      uniqueItems.delete(value);
 
    } else {
      uniqueItems.add(value);
    }
    maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
  }
log(maxSize)
  return duplicates.size;
}


/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

You can improve the function's time complexity at the expense of memory by tracking the duplicates in a separate Set. This will reduce the number of iterations by the number of unique items in the input array, and increase the memory need by the same number.

A further improvement can be gained if you delete duplicates from the unique set as you go. This will bring the memory use down.

function countDuplicates(original) {
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
    }
  }
  return duplicates.size;
}


/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

Post Deleted by Blindman67

occurred Sep 4, 2018 at 15:52

Source Link

created Sep 4, 2018 at 15:50

Blindman67

22.3k
2
16
40

Loading

Stack Exchange Network

Return to Answer

Reduce time

A look at memory.

Reduce time

A look at memory.