Where would you start your order number iteration at?

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Re: Where would you start your order number iteration at?

Post by Jenk »

Even if tables are dropped and recreated, PostgreSQL (our DB of choice) maintains PK/Auto-increment number as they are a separate entity :)

and I wasn't referring to Automated testing. We don't touch the DB at all for those, as per the discussion on here before.. ;) all those test records are done by the user and/or developer(s) who are having a muse during the applications development time.
User avatar
kaisellgren
DevNet Resident
Posts: 1675
Joined: Sat Jan 07, 2006 5:52 am
Location: Lahti, Finland.

Re: Where would you start your order number iteration at?

Post by kaisellgren »

Why do you need to even reveal the ID? Just display the buyer's name, time and product details and that should be enough. :crazy:
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Re: Where would you start your order number iteration at?

Post by Jenk »

Users, generally, want an Order number/reference.
User avatar
kaisellgren
DevNet Resident
Posts: 1675
Joined: Sat Jan 07, 2006 5:52 am
Location: Lahti, Finland.

Re: Where would you start your order number iteration at?

Post by kaisellgren »

Jenk wrote:Users, generally, want an Order number/reference.
Probably something like what PayPal does then?
sparrrow
Forum Commoner
Posts: 81
Joined: Mon Oct 20, 2008 12:22 pm

Re: Where would you start your order number iteration at?

Post by sparrrow »

kaisellgren wrote:
Jenk wrote:Users, generally, want an Order number/reference.
Probably something like what PayPal does then?
Yes, like that. Paypal has txn id, ebay has item number, and most credible e-shops provide an invoice id of some sort. When a customer needs to know about their order (shipping status, etc) when they call or email support, there needs to be a unique identifier that the customer can provide so the order can be pulled up quickly and easily. When the business is commercial, you may have dozens or hundreds of orders from the same customer, so using customer details is inefficient.

Also, the sales are generated and pooled from eBay auctions, company homepage, local face-to-face, and other sources, and paid via paypal, merchant account, or cash. So no matter what type of order, they go into the same database and the customer gets an order id. So again, the customer calls support for shipping status, support doesn't have to ask millions questions about the order to find it. They just ask for the order id.

Scalability is wonderful. :)

Excellent discussion by the way. Very enlightening; thank you all! Keep it coming!
User avatar
kaisellgren
DevNet Resident
Posts: 1675
Joined: Sat Jan 07, 2006 5:52 am
Location: Lahti, Finland.

Re: Where would you start your order number iteration at?

Post by kaisellgren »

sparrrow wrote:Yes, like that. Paypal has txn id, ebay has item number, and most credible e-shops provide an invoice id of some sort. When a customer needs to know about their order (shipping status, etc) when they call or email support, there needs to be a unique identifier that the customer can provide so the order can be pulled up quickly and easily. When the business is commercial, you may have dozens or hundreds of orders from the same customer, so using customer details is inefficient.

Also, the sales are generated and pooled from eBay auctions, company homepage, local face-to-face, and other sources, and paid via paypal, merchant account, or cash. So no matter what type of order, they go into the same database and the customer gets an order id. So again, the customer calls support for shipping status, support doesn't have to ask millions questions about the order to find it. They just ask for the order id.
Well then. How about you keep the primary key ID private, and have a column "order_id" or whatever, then you generate this order_id based on some detail (the id). I have not been coding such things, but the idea I have is simple:

Code: Select all

$order_id = hash('ripemd320',$id);
That would generate a RipeMD-320 hash of the primary key ID value. Theoretically, there would be collisions (same order IDs), but that is not likely. The hash would generate 80 characters long text that has 0-9a-f characters. That is 16 different chars for each letter, so, it's 16^80 (2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936576) different combinations.

I'm just throwing an idea. You could easily decrease the likelihood of collisions by adding another hash, but I don't think that is really necessary :P

Btw, RipeMD is a fast algo.
sparrrow
Forum Commoner
Posts: 81
Joined: Mon Oct 20, 2008 12:22 pm

Re: Where would you start your order number iteration at?

Post by sparrrow »

kaisellgren wrote: The hash would generate 80 characters long text that has 0-9a-f characters. That is 16 different chars for each letter, so, it's 16^80 (2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936576) different combinations.
Rep: "Hello, what is your order id?"
Customer: "Um, this big long number?? You need the whole thing?"
:P

A good idea for generating a unique key, but doesn't seem very usable from a customer service standpoint.
User avatar
kaisellgren
DevNet Resident
Posts: 1675
Joined: Sat Jan 07, 2006 5:52 am
Location: Lahti, Finland.

Re: Where would you start your order number iteration at?

Post by kaisellgren »

sparrrow wrote:
kaisellgren wrote: The hash would generate 80 characters long text that has 0-9a-f characters. That is 16 different chars for each letter, so, it's 16^80 (2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936576) different combinations.
Rep: "Hello, what is your order id?"
Customer: "Um, this big long number?? You need the whole thing?"
:P

A good idea for generating a unique key, but doesn't seem very usable from a customer service standpoint.
Like I said that is an example only. You could also use another hash like RipeMD-128, which produces 32-characters long one.
alixaxel
Forum Newbie
Posts: 15
Joined: Thu Mar 12, 2009 9:00 am

Re: Where would you start your order number iteration at?

Post by alixaxel »

Good topic, I enjoyed reading this discussion.

If you want a short ID, that is easy to write (or spell over the phone) and gives a little more credibility to your orders I suggest that you implement a check digit function, I personally use the Verhoeff algorithm all the time since it only adds a single digit, supports arbitrary-length numbers and is superb at error detection which is always a plus.

ORDER # - (ID #)
1 - 15
2 - 27
3 - 36
...
42 - 420
...
1337 - 13375

Of course the down side is that you have to know the auto-incremented ID à priori.
User avatar
kaisellgren
DevNet Resident
Posts: 1675
Joined: Sat Jan 07, 2006 5:52 am
Location: Lahti, Finland.

Re: Where would you start your order number iteration at?

Post by kaisellgren »

alixaxel wrote:ORDER # - (ID #)
1 - 15
2 - 27
3 - 36
...
42 - 420
...
1337 - 13375
Hmm, so it adds a random number into the end? This means the order ID is unique, but also too small for the first orders, which I think the OP wants to avoid?
alixaxel
Forum Newbie
Posts: 15
Joined: Thu Mar 12, 2009 9:00 am

Re: Where would you start your order number iteration at?

Post by alixaxel »

kaisellgren wrote:
alixaxel wrote:ORDER # - (ID #)
1 - 15
2 - 27
3 - 36
...
42 - 420
...
1337 - 13375
Hmm, so it adds a random number into the end? This means the order ID is unique, but also too small for the first orders, which I think the OP wants to avoid?
Nope, the last digit is not a random number, it's a unique check digit computed using the Verhoeff algorithm. Check digits are used all over the world on books (ISBNs), barcodes (GTINs), credit cards (Luhn) and so on... Like I said before the Verhoeff algorithm is pretty versatile so if one check digit is not enough you can do something like this:

Verhoeff(Verhoeff(1)) = 158
Verhoeff(Verhoeff(2)) = 270
Verhoeff(Verhoeff(3)) = 362
...
Verhoeff(Verhoeff(42)) = 4204
...
Verhoeff(Verhoeff(1337)) = 133758

Check digit algorithms aren't random numbers, they allow you to check if the ORDER # is valid without even having to query the database.
User avatar
kaisellgren
DevNet Resident
Posts: 1675
Joined: Sat Jan 07, 2006 5:52 am
Location: Lahti, Finland.

Re: Where would you start your order number iteration at?

Post by kaisellgren »

alixaxel wrote:Nope, the last digit is not a random number, it's a unique check digit computed using the Verhoeff algorithm.
I see, although it wouldn't hurt to have a random number. It would still be unique, but like you said, you can check for validity without database queries - so that could be one reason to use Verhoeff.

I was reading the Wikipedia article and I got a bit interested in this algorithm. Here is my PHP implementation.

Code: Select all

<?php
 
/*/
 * --¥--=====----- -----=====---------- -----=====---------------
 *   |
 *   |     Verhoeff
 *   |   ¯¯¯¯¯¯¯¯¯¯¯¯
 *   |
 *   »   × Written by Kai Sellgren.
 *   »   × These notes must stay here intact.
 *   |
 * --¥--=====----- -----=====---------- -----=====---------------
/*/
 
class verhoeff
 {
  private $d = array(array(0,1,2,3,4,5,6,7,8,9),
                     array(1,2,3,4,0,6,7,8,9,5),
                     array(2,3,4,0,1,7,8,9,5,6),
                     array(3,4,0,1,2,8,9,5,6,7),
                     array(4,0,1,2,3,9,5,6,7,8),
                     array(5,9,8,7,6,0,4,3,2,1),
                     array(6,5,9,8,7,1,0,4,3,2),
                     array(7,6,5,9,8,2,1,0,4,3),
                     array(8,7,6,5,9,3,2,1,0,4),
                     array(9,8,7,6,5,4,3,2,1,0));
 
  private $p = array(array(0,1,2,3,4,5,6,7,8,9),
                     array(1,5,7,6,2,8,3,0,9,4),
                     array(5,8,0,3,7,9,6,1,4,2),
                     array(8,9,1,6,0,4,3,5,2,7),
                     array(9,4,5,3,1,2,6,8,7,0),
                     array(4,2,8,6,5,7,3,9,0,1),
                     array(2,7,9,3,8,0,6,4,1,5),
                     array(7,0,4,6,9,1,3,2,5,8));
 
  private $inv = array(0,4,3,2,1,5,6,7,8,9);
 
  public function calculate($int)
   {
    for ($a = 0,$n = strrev($int),$b = strlen($n),$c = 0;$a < $b;$a++)
     $c = $this -> d[$c][$this -> p[($a+1) % 8][$n[$a]]];
    return $this -> inv[$c];
   }
 
  public function is_valid($int)
   {
    for ($a = 0,$n = strrev($int),$b = strlen($n),$c = 0;$a < $b;$a++)
     $c = $this -> d[$c][$this -> p[$a % 8][$n[$a]]];
    return ($c == 0) ? true : false;
   }
 }
 
?>
Feel free to use it, just remember to credit me. ;)

Usage (calculate):

Code: Select all

$v = new verhoeff;
echo $v -> calculate(1337); // 13375
alixaxel wrote:they allow you to check if the ORDER # is valid without even having to query the database.
Yes and you can even check that the value is proper:
Usage (check):

Code: Select all

$v = new verhoeff;
if ($v -> is_valid(13375)) // true
 echo 'true';
alixaxel
Forum Newbie
Posts: 15
Joined: Thu Mar 12, 2009 9:00 am

Re: Where would you start your order number iteration at?

Post by alixaxel »

Nice implementation, given the example in my previous post I would suggest two things:

Code: Select all

 
<?php
 
$id = 1337;
 
// returns the whole number (13375) instead of just the check digit (5)
verhoeff::calculate($id);
 
// returns 133758, same as doing verhoeff::calculate($id . verhoeff::calculate($id));
verhoeff::calculate($id, 2);
 
?>
 
The is_valid() method could also return the original ID on true, or false on error - this way you wouldn't need to store the verhoeffed ID on the database.
alixaxel
Forum Newbie
Posts: 15
Joined: Thu Mar 12, 2009 9:00 am

Re: Where would you start your order number iteration at?

Post by alixaxel »

I've modified my code in order to reflect the changes in my previous topic, here is my implementation (you can also try it @ http://codepad.org/vNjgkgAu):

Code: Select all

 
<?php
 
class Verhoeff
{
    public $d = null;
    public $inv = null;
    public $p = null;
 
    function __construct()
    {
        $this->d = json_decode('[[0,1,2,3,4,5,6,7,8,9],[1,2,3,4,0,6,7,8,9,5],[2,3,4,0,1,7,8,9,5,6],[3,4,0,1,2,8,9,5,6,7],[4,0,1,2,3,9,5,6,7,8],[5,9,8,7,6,0,4,3,2,1],[6,5,9,8,7,1,0,4,3,2],[7,6,5,9,8,2,1,0,4,3],[8,7,6,5,9,3,2,1,0,4],[9,8,7,6,5,4,3,2,1,0]]');
        $this->inv = json_decode('[0,4,3,2,1,5,6,7,8,9]');
        $this->p = json_decode('[[0,1,2,3,4,5,6,7,8,9],[1,5,7,6,2,8,3,0,9,4],[5,8,0,3,7,9,6,1,4,2],[8,9,1,6,0,4,3,5,2,7],[9,4,5,3,1,2,6,8,7,0],[4,2,8,6,5,7,3,9,0,1],[2,7,9,3,8,0,6,4,1,5],[7,0,4,6,9,1,3,2,5,8]]');
    }
 
    function Calculate($number, $iterations = 1)
    {
        $result = 0;
        $number = str_split(strrev($number), 1);
 
        foreach ($number as $key => $value)
        {
            $result = $this->d[$result][$this->p[($key + 1) % 8][$value]];
        }
 
        $result = strrev(implode('', $number)) . $this->inv[$result];
 
        if ($iterations > 1)
        {
            return $this->Calculate($result, --$iterations);
        }
 
        return $result;
    }
 
    function Check($number, $iterations = 1)
    {
        $result = 0;
        $number = str_split(strrev($number), 1);
 
        foreach ($number as $key => $value)
        {
            $result = $this->d[$result][$this->p[$key % 8][$value]];
        }
 
        if ($result == 0)
        {
            unset($number[0]);
 
            $result = strrev(implode('', $number));
 
            if ($iterations > 1)
            {
                return $this->Check($result, --$iterations);
            }
 
            return $result;
        }
 
        return false;
    }
}
 
$Verhoeff = new Verhoeff();
 
/*
1 Check Digit
*/
var_dump($Verhoeff->Calculate(1337, 1)) . "\n"; // 13375
var_dump($Verhoeff->Check(13375, 1)) . "\n"; // 1337 (true)
var_dump($Verhoeff->Check(13375, 2)) . "\n"; // false
 
/*
4 Check Digits
*/
var_dump($Verhoeff->Calculate(1337, 4)) . "\n"; // 13375421
var_dump($Verhoeff->Check(13375421, 4)) . "\n"; // 1337 (true)
var_dump($Verhoeff->Check(13375421, 5)) . "\n"; // false
 
?>
 
Please bear in mind that the Check() method can also be coded using the Calculate() method and the substr() function.
User avatar
kaisellgren
DevNet Resident
Posts: 1675
Joined: Sat Jan 07, 2006 5:52 am
Location: Lahti, Finland.

Re: Where would you start your order number iteration at?

Post by kaisellgren »

Here is my modified version of Verhoeff.

Code: Select all

<?php
 
/*/
 * --¥--=====----- -----=====---------- -----=====---------------
 *   |
 *   |     Verhoeff
 *   |   ¯¯¯¯¯¯¯¯¯¯¯¯
 *   |
 *   »   × Written by Kai Sellgren.
 *   »   × These notes must stay here intact.
 *   |
 * --¥--=====----- -----=====---------- -----=====---------------
/*/
 
class verhoeff
 {
  private $d = array(array(0,1,2,3,4,5,6,7,8,9),
                     array(1,2,3,4,0,6,7,8,9,5),
                     array(2,3,4,0,1,7,8,9,5,6),
                     array(3,4,0,1,2,8,9,5,6,7),
                     array(4,0,1,2,3,9,5,6,7,8),
                     array(5,9,8,7,6,0,4,3,2,1),
                     array(6,5,9,8,7,1,0,4,3,2),
                     array(7,6,5,9,8,2,1,0,4,3),
                     array(8,7,6,5,9,3,2,1,0,4),
                     array(9,8,7,6,5,4,3,2,1,0));
 
  private $p = array(array(0,1,2,3,4,5,6,7,8,9),
                     array(1,5,7,6,2,8,3,0,9,4),
                     array(5,8,0,3,7,9,6,1,4,2),
                     array(8,9,1,6,0,4,3,5,2,7),
                     array(9,4,5,3,1,2,6,8,7,0),
                     array(4,2,8,6,5,7,3,9,0,1),
                     array(2,7,9,3,8,0,6,4,1,5),
                     array(7,0,4,6,9,1,3,2,5,8));
 
  private $inv = array(0,4,3,2,1,5,6,7,8,9);
 
  public function calculate($int,$iterations = 1,$loop = false)
   {
    for ($a = 0,$n = strrev($int),$b = strlen($n),$c = 0,$d = 0;$a < $b;$a++)
     $c = $this -> d[$c][$this -> p[($a+1) % 8][$n[$a]]];
    $d = $this -> inv[$c];
    while (--$iterations)
     $d .= $this -> calculate($int.$d,1,true);
    return ($loop ? '' : $int).$d;
   }
 
  public function check($int,$iterations = 1,$loop = false)
   {
    for ($a = 0,$n = strrev($int),$b = strlen($n),$c = 0,$d = 0,$e = $iterations;$a < $b;$a++)
     $c = $this -> d[$c][$this -> p[$a % 8][$n[$a]]];
    if ($c != 0)
     return false;
    while (--$iterations)
     {
      if ($this -> check(substr($int,0,strlen($int)-$iterations),1,true) === false)
       return false;
     }
    return $loop ? true : substr($int,0,strlen($int)-$e);
   }
 }
 
?>
It accepts a parameter $iterations and will return the correct value instead of boolean "true". Note, if the correct value is 0, e.g. if you check whether 04 is correct, then it returns 0 so you must do the check like this:

Code: Select all

if ($v -> check(04) !== false)
Note that there are two equal signs.

More over, my implementation seems faster. In the below examples, my implementation is verhoeff and yours is verhoeff2.

Initialization performance test:

Code: Select all

header('content-type: text/plain');
 
$time = time()+microtime(1);
for ($a = 0;$a < 1000;$a++)
$v2 = new verhoeff2();
echo (time()+microtime(1))-$time."\n";
 
$time = time()+microtime(1);
for ($a = 0;$a < 1000;$a++)
$v = new verhoeff();
echo (time()+microtime(1))-$time."\n";
Results:
0.04516696929931640625
0.00075626373291015625
My implementation initializes 60 times faster.

One iteration based calculations:

Code: Select all

$v2 = new verhoeff2();
$time = time()+microtime(1);
for ($a = 0;$a < 1000;$a++)
$v2 -> calculate(1337);
echo (time()+microtime(1))-$time."\n";
 
$v = new verhoeff();
$time = time()+microtime(1);
for ($a = 0;$a < 1000;$a++)
$v -> calculate(1337);
echo (time()+microtime(1))-$time."\n";
Results:
0.0079860687255859375
0.00634098052978515625
My implementation calculates single iterations 1.26 times faster. With 100 iterations, the results were:
11.2837162017822265625
6.5020313262939453125
Which makes my implementation 1.7 times faster on a higher iteration count.

Then I tried the "check" method against "1337542174997737309409585646347774933584845524277550726944602127053306892533169692847127657489822187309". First I tried one iteration:
0.072235107421875
0.067127227783203125
My implementation was 1.07 times faster. Then I tried the same value with 100 iterations and they both returned 1337 like they should have.
10.1588001251220703125
7.62356472015380859375
The difference was the performance, again. Mine was roughly 1.33 times faster.

Both implementations work, but I aimed for better performance. :D
Post Reply