Page 2 of 3

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

Posted: Mon Feb 23, 2009 10:29 am
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.

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

Posted: Mon Mar 09, 2009 10:07 am
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:

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

Posted: Mon Mar 09, 2009 11:14 am
by Jenk
Users, generally, want an Order number/reference.

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

Posted: Mon Mar 09, 2009 11:25 am
by kaisellgren
Jenk wrote:Users, generally, want an Order number/reference.
Probably something like what PayPal does then?

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

Posted: Mon Mar 09, 2009 10:07 pm
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!

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

Posted: Tue Mar 10, 2009 9:20 am
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.

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

Posted: Tue Mar 10, 2009 11:26 am
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.

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

Posted: Tue Mar 10, 2009 12:15 pm
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.

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

Posted: Thu Mar 12, 2009 9:18 am
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.

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

Posted: Thu Mar 12, 2009 9:53 am
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?

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

Posted: Thu Mar 12, 2009 6:51 pm
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.

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

Posted: Thu Mar 12, 2009 7:30 pm
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';

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

Posted: Thu Mar 12, 2009 8:18 pm
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.

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

Posted: Thu Mar 12, 2009 11:15 pm
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.

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

Posted: Fri Mar 13, 2009 3:12 am
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