Calculate percent at runtime

Question

I have this problem where I have to "audit" a percent of my transtactions.

If percent is 100 I have to audit them all, if is 0 I have to skip them all and if 50% I have to review the half etc.

The problem ( or the opportunity ) is that I have to perform the check at runtime.

What I tried was:

audit = 100/percent

So if percent is 50

audit = 100 / 50 ( which is 2 )

So I have to audit 1 and skip 1 audit 1 and skip 1 ..

If is 30

audit = 100 / 30 ( 3.3 )

I audit 2 and skip the third.

Question

I'm having problems with numbers beyond 50% ( like 75% ) because it gives me 1.333, ...

When would be the correct algorithm to know how many to audit as they go?... I also have problems with 0 ( due to division by 0 :P ) but I have fixed that already, and with 100 etc.

Any suggestion is greatly appreciated.

Answer 1

Why not do it randomly. For each transaction, pick a random number between 0 and 100. If that number is less than your "percent", then audit the transaction. If the number is greater than your "percent", then don't. I don't know if this satisfies your requirements, but over an extended period of time, you will have the right percentage audited.

If you need an exact "skip 2, audit one, skip 2 audit one" type of algorithm, you'll likely have luck adapting a line-drawing algorithm.

Answer 2

Try this:

1) Keep your audit percentage as a decimal.
2) For every transaction, associate a random number (between 0 and 1) with it
3) If the random number is less than the percentage, audit the transaction.

Answer 3

If you need to audit these transactions in real time (as they are received) perhaps you could use a random number generator to check if you need to audit the transaction.

So if for example you want to audit 50% of transactions, for every transaction received you would generate a random number between 0 and 1, and if the number was greater than 0.5, audit that transaction.

While for low numbers this would not work, for large numbers of transactions this would give you very close to the required percentage.

This is better than your initial suggestion because if does not allow a method to 'game' the audit process - if you are auditing every second transaction this allows bad transactions to slip through.

Another possibility is to keep a running total of the total transactions and as this changes the total number of transactions that need to be audited (according to your percentage) you can pipe transactions into the auditing process. This however still opens the slight possibility of someone detecting the pattern and circumventing the audit.

Answer 4

For a high throughput system the random method is best, but if you don't want randomness, the this algorithm will do the job. Don't forget to test it in a unit test!

// setup
int transactionCount = 0;
int auditCount = 0;
double targetAuditRatio = auditPercent/100.0;

// start of processing
transactionCount++;
double actualAuditRatio = auditCount/transactionCount;

if (actualAuditRatio < targetAuditRatio) {
    auditCount++;
    // do audit
}
// do processing

Answer 5

You can constantly "query" each audit using counter. For example

ctr = 0;
percent = 50
while(1) {
   ctr += percent;
   if (ctr >= 100) {
      audit;
      ctr = ctr - 100;
   } else
      skip
}

You can use floats (however this will bring some unpredictability) or multiply 100 percent by sth to get better resolution.

There is really no need to use random number generator.

Answer 6

    if percent > random.randint(1,100):
        print("audit")
    else:
        print("skip")

Answer 7

To follow your own algorithm: just keep adding that 1.333333 (or other quotient) to a counter.

Have two counters: an integer one and a real one. If the truncated part of the real counter = the integer counter, the audit is carried out, otherwise it isn't, like this:

Integer counter   Real counter

1                 1.333333: audit transaction
2                 2.666666: audit transaction
3                 3.999999: audit transaction
4                 truncated(5.333333) = 5 > 4 => do NOT audit transaction
5                 5.333333: audit transaction

Only increment the real counter when its truncated version = the integer counter. Always increment the integer counter.

In code:

var p, pc: double;
    c: integer;
begin
  p := 100 / Percentage;
  pc := p;
  for c := 1 to NrOfTransactions do begin
    if trunc(pc) = c then begin
      pc := pc + p;
      Do audit on transaction c
    end  
  end;
end;

Answer 8

Not tested, but in the random module there is a function sample. If transactions was a list of transactions, you would do something like:

import random

to_be_audited = random.sample(transactions,len(transactions*100/percentage))

This would generate a list to_be_audited which would be a random, non-duplicating sample of the transactions.

See documentation on random