2
\$\begingroup\$

I was reading this question: Why is my function timing out when run with a larger data set?

And although I couldn't quite grasp the OP's implementation and so didn't feel like answering. I did some implementations of my own and created a benchmark for them.

Here is the problem definition:

There is a queue for the self-checkout tills at the supermarket.

Your task is write a function to calculate the total time

required for all the customers to check out!

input:

customers: an array of positive integers representing the queue. Each integer represents a customer, and its value is the amount of time they require to check out.

k: a positive integer, the number of checkout tills.

And here is a "common solution" provided by OP of the above mentioned question, which is O(n*k) in time and O(k) in space (I believe).

const queueTimeOriginal = (customers, k) => {
  const n = customers.length
  const tills = new Array(k).fill(0)
  for (let i = 0; i < n; ++i) {
    const min = Math.min(...tills)
    const imin = tills.indexOf(min)
    tills[imin] += customers[i]
  }
  return Math.max(...tills)
}

The call to Math.min() is O(k) in time and then the call to Array.indexOf() is also O(k). This can be put together into one loop where we find the index of the minimum in O(k) and then we access the minimum value using the index in O(1).

const minItemIndex = (input) => {
  const n = input.length
  let imin = 0
  for (let i = 1; i < n; ++i) {
    if (input[i] < input[imin]) {
      imin = i
    }
  }
  return imin
}

const queueTimeMinLookup = (customers, k) => {
  const n = customers.length
  const tills = new Array(k).fill(0)
  for (let i = 0; i < n; ++i) {
    const imin = minItemIndex(tills)
    tills[imin] += customers[i]
  }
  return Math.max(...tills)
}

This alone improved the performance about 1.3 - 4x for the various cases that i benched (see on the bottom).

Then I thought that maybe if I keep the tills sorted, it may get even another bit faster.

Further if n<=k then the result is simply the largest customer, turning the algorithm from O(n*k) to O(n) for these cases.

/**
 * @param input: Array<number> Input array of numbers sorted in ascending order
 * @param index: number Valid index to the input array
 * @param value: number Value to be added to the current value on given index
 * @return void
 */
const ascendingArrayAdd = (input, index, value) => {
  const n = input.length;
  const target = input[index] + value;
  let i = index + 1
  while (i < n) {
    const current = input[i];
    if (target <= current) {
        break;
    }
    input[i - 1] = current;
    for (++i; i < n && input[i] === current; ++i);
  }
  input[i - 1] = target;
}

/**
 * @param customers: Array<number> Customer queue
 * @param k: number number of tills
 * @return number Time to check out all customers
 */
const queueTimeSortedTills = (customers, k) => {
  const n = customers.length;
  if (n <= k) {
    return Math.max(...customers);
  }
  const tills = new Array(k).fill(0);
  for (let i = 0; i < n; ++i) {
    // faster equivalent of:
    // tills[0] += customers[i]
    // tills.sort((a,b) => a- b)
    ascendingArrayAdd(tills, 0, customers[i]);
  }
  return tills[k - 1];
}

This improved the performance yet 0.9-2.1x compared to the already improved version. Or about 1.4-7x faster then the original. So it is not always faster, but it seems most of the time it is. It depends on various things, probably also the individual customers and their order too. But when it is slower, it is not slower by more then 10%, while it can be faster by about 100%

That's not including the cases when n<=k which made improvement about 600-2000x, but this optimization can be done in all the implementations. And the improvement is so big because it's a completly different complexity curve. It would be even bigger difference for bigger inputs (and number of tills).

Here I'm including some tests and the benchmark code:

/**
 * @param a {Array} Left array operand 
 * @param b {Array} Right array operand
 * @return bool True if left contains exactly the same elements as right in the same order, false otherwise
 */
const arraysEqual = (a, b) => {
  if (a === b) return true;
  const n = a.length;
  if (n !== b.length) return false;
  for (let i = 0; i < n; ++i) {
    if (a[i] !== b[i]) return false;
  }
  return true;
}

const testArraysEqual = (a, b, expect) => {
  console.log("TEST: arraysEqual(", a, ", ", b, ")")
  const result = arraysEqual(a, b)
  if (result !== expect) {
    console.error("expected: ", expect)
    console.error("got: ", result)
  } else {
    console.log("OK: ", result)
  }
}


const testAscendingArrayAdd = (input, index, value, expect) => {
  console.log("TEST: ascendingArrayAdd(", input, ", ", index, ", ", value, "")
  const result = input.slice();
  ascendingArrayAdd(result, index, value);
  if (!arraysEqual(result, expect)) {
    console.error("expected: ", expect)
    console.error("got: ", result)
  } else {
    console.log("OK: ", result);
  }
}

/*********************************************************/


const testQueueTimeOriginal = (customers, k, expect) => {
  console.log("TEST: queueTimeOriginal(", customers, ", ", k, ")")
  const result = queueTimeOriginal(customers, k);
  if (result !== expect) {
    console.error("expected: ", expect)
    console.error("got: ", result)
  } else {
    console.log("OK: ", result)
  }
}

const testQueueTimeMinLookup = (customers, k, expect) => {
  console.log("TEST: queueTimeMinLookup(", customers, ", ", k, ")")
  const result = queueTimeMinLookup(customers, k);
  if (result !== expect) {
    console.error("expected: ", expect)
    console.error("got: ", result)
  } else {
    console.log("OK: ", result)
  }
}

const testQueueTimeSortedTills = (customers, k, expect) => {
  console.log("TEST: queueTimeSortedTills(", customers, ", ", k, ")")
  const result = queueTimeSortedTills(customers, k);
  if (result !== expect) {
    console.error("expected: ", expect)
    console.error("got: ", result)
  } else {
    console.log("OK: ", result)
  }
}

const testQueueTime = (customers, k, expect) => {
  testQueueTimeOriginal(customers, k, expect)
  testQueueTimeMinLookup(customers, k, expect)
  testQueueTimeSortedTills(customers, k, expect)
}

/**************************************************************/

const generateRandomArray = (n, max) => 
  Array.from({length: n}, () => Math.floor(Math.random() * max));


const meassure = (callback, repeat) => {
  const expect = callback()
  let sum = 0;
  for (let i = 0; i < repeat; ++i) {
    const start = performance.now()
    const result = callback()
    sum += performance.now() - start;  
    
    if (result !== expect) {
        throw "Meassurement #" + i + "returned different result."
    }
  }
  
  return {
    average: sum / repeat,
    result: expect
  }
}

const comparativeTest = (n, max, k) => {
  // estimate number of repetitions assuming we are benchmarking O(n*k) algorithm
  // so that each test runs about the same time
  const repeat = Math.floor(300000000 / n / k);

  const customers = generateRandomArray(n, max)
  
  console.log("MEASSURE ", {
    customers: n,
    tills: k,
    customerMaxTime: max,
    repeat: repeat
  })
  
  const og = meassure(() => queueTimeOriginal(customers, k), repeat)
  const ml = meassure(() => queueTimeMinLookup(customers, k), repeat)
  const st = meassure(() => queueTimeSortedTills(customers, k), repeat)
  
  if (ml.result !== st.result || og.result !== ml.result) {
    throw "Results do not match"
  }
  
  console.log("original: ", og.average)
  console.log("min-lookup: ", ml.average)
  console.log("sorted-tills: ", st.average)
  
  console.log("min-lookup is " + (og.average / ml.average).toFixed(2) + "x faster then the original")
  console.log("sorted-tills is " + (og.average / st.average).toFixed(2) + "x faster then the original")
  console.log("sorted-tills is " + (ml.average / st.average).toFixed(2) + "x faster then the min-kookup")
}

console.log("--------------TEST START----------------");
testArraysEqual([], [], true)
testArraysEqual([0], [0], true)
testArraysEqual([1,2,3], [1,2,3], true)
testArraysEqual([0], [], false)
testArraysEqual([0, 0], [0], false)
testArraysEqual([1,2,3],[3,2,1], false)

testAscendingArrayAdd([1], 0, 1, [2]);
testAscendingArrayAdd([1,2,3], 0, 2, [2,3,3]);
testAscendingArrayAdd([1,1,1], 0, 1, [1,1,2]);
testAscendingArrayAdd([1,1,2,2,3], 0, 1, [1,2,2,2,3]);
testAscendingArrayAdd([1,1,2,2,3], 2, 2, [1,1,2,3,4]);

testQueueTime([10, 5, 15, 20], 2, 30);
testQueueTime([10, 5, 15, 20], 5, 20);
console.log("--------------TEST ENDS-----------------");


comparativeTest(1000, 10, 10)
comparativeTest(10000, 10, 10)
comparativeTest(100000, 10, 10)

comparativeTest(1000, 100, 10)
comparativeTest(10000, 100, 10)
comparativeTest(100000, 100, 10)

comparativeTest(1000, 1000, 10)
comparativeTest(10000, 1000, 10)
comparativeTest(100000, 1000, 10)

comparativeTest(1000, 10000, 10)
comparativeTest(10000, 10000, 10)
comparativeTest(100000, 10000, 10)

comparativeTest(1000, 10, 100)
comparativeTest(10000, 10, 100)
comparativeTest(100000, 10, 100)

comparativeTest(1000, 100, 100)
comparativeTest(10000, 100, 100)
comparativeTest(100000, 100, 100)

comparativeTest(1000, 1000, 100)
comparativeTest(10000, 1000, 100)
comparativeTest(100000, 1000, 100)

comparativeTest(1000, 10000, 100)
comparativeTest(10000, 10000, 100)
comparativeTest(100000, 10000, 100)

comparativeTest(1000, 10, 1000)
comparativeTest(10000, 10, 1000)
comparativeTest(100000, 10, 1000)

comparativeTest(1000, 100, 1000)
comparativeTest(10000, 100, 1000)
comparativeTest(100000, 100, 1000)

comparativeTest(1000, 1000, 1000)
comparativeTest(10000, 1000, 1000)
comparativeTest(100000, 1000, 1000)

comparativeTest(1000, 10000, 1000)
comparativeTest(10000, 10000, 1000)
comparativeTest(100000, 10000, 1000)

I would like to get a general review of the benchmark code, maybe see if I did some mistake that would invalidate the results obtained.

But review of the problem implementations is also welcome. With emphasis on the ascendingArrayAdd() function, which if could be a bit improved, maybe the problem implementation that uses it could never be 0.9x-1.0x faster then the min-lookup variation which would make it an ultimate winner.

Also if someone can explain what is the dependency on the inputs that causes the sorted-tills implementation to sometimes be slower then the min-lookup implementatio, I'm all ears :)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Seems like tills should be a priority queue, with \$O(n\log k)\$ complexity. \$\endgroup\$ – vnp Jul 13 '20 at 22:12
  • \$\begingroup\$ @vnp Oh man, of course. I should not be doing these things so late :D Unfortunately i dont feel like implementing a min heap. Thats gonna beat all these implementations and i dont think it would be interesting to bench O(nlog(k)) against O(nk) implementation. But thanks anyway. \$\endgroup\$ – slepic Jul 14 '20 at 3:41
  • \$\begingroup\$ @vnp It turns out that i can build the heap for first k customers in O(k), turning the algorithm to O(min(n,k) + max(n-k,0) * log(k)). \$\endgroup\$ – slepic Jul 18 '20 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.