PHP order matching algorithm

🏷️ 撮合算法Matching Algorithms 🏷️ 撮合Order Matching 🏷️ php撮合算法PHP Matching Algorithm 📂 php算法 📂 php 📂 算法 📝 1.8k 字 · ⏱️ 11 分钟 阅读 0 次 👀

When buying and selling on the same platform, orders need to be matched. Similar amounts are combined in descending order. At first I wanted to use mq to separately match integer multiples of amounts, but I always felt it wasn’t quite perfect. Recently I happened to have some free time, so I found the “monkey chooses the king” algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function King($monkeys_arr,$m)
{
    $i = 0;
    $finsh=[];
    while(count($monkeys_arr)>1)
    {
        $i++;
        if($i>count($monkeys_arr)) break;
        $head = array_shift($monkeys_arr);
        if ($head%$m != 0) {
            array_push($monkeys_arr, $head);
            continue;
        }
        $finsh[]=$head;
    }

    return $finsh;
}
$a=king([1,2,6,3,4,8,7],7);
var_dump($a);



Adapt it a bit based on the algorithm above.
First determine the matching amount order, that is, sort in descending order.
Then each time an amount smaller than the specified amount is matched, subtract that amount. Assign the difference back as the amount to match.
And so on.
In the process, record the matched amounts and the remaining balance of the final difference.
The matching code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function marriedDeal($arr, $change_number)
{
    $i = 0;
    $finsh = []; //matched amounts
    $default_total = count($arr);
    if($default_total==0) return [];
    arsort($arr);
    $blance = 0;  //final balance
    while ($default_total >= 1) {
        $i += 1;
        if ($i > $default_total || $change_number <= 0) break;
        $head = array_shift($arr);
        if ($head > $change_number) {
            array_push($arr, $head);
            continue;
        }
        $finsh[] = $head;
        $change_number -= $head;
        $blance = $change_number;
    }
    return [$finsh, $blance, $arr];
}
$get_number = marriedDeal([120, 200,100,300,11,221],20);
print_r($get_number);

Recently, with nothing much to do, I ran a test. The test data is as shown below
https://erik.xyz
The result generated after the test
https://erik.xyz
I found that matching this way takes too long when there is a lot of data, so I tried to find an optimization.
What if I use a generator? The generated result is as follows
https://erik.xyz

The complete optimized code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

function marriedDeal($arr, $change_number)
{
    $default_total = count($arr);
    if ($default_total <= 0 || $change_number<=0) return [];
    $blance = $i = 0;
    arsort($arr);
    while ($default_total >= 1) {
        $i += 1;
        if ($i > $default_total || $change_number <= 0) break;
        $head = array_shift($arr);
        if ($head > $change_number) {
            array_push($arr, $head);
            continue;
        }
        $change_number -= $head;
        $blance = $change_number;
        yield ['finsh'=>$head,"blance"=>$blance,'last_arr'=>[]];
    }
    //yield ['last_arr'=>$arr];
}

$t1 = microtime(true);
$list = [120, 200, 4353, 43543, 435, 546, 56, 435, 3443, 5435,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    180, 11, 223, 2342, 345, 435, 456, 4564, 55, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    232, 3243, 23424, 6576, 7897, 2342, 21342, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 456, 345, 435, 345, 456, 57, 4345, 345435, 435,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    220, 400, 20, 320, 43435, 4564, 45645, 456, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    180, 11, 223, 2342, 345, 435, 456, 4564, 55, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    232, 3243, 23424, 6576, 7897, 2342, 21342, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    456, 345, 435, 345, 456, 57, 4345, 345435, 435, 180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    56546, 566, 456452324, 34543, 435, 435, 435, 45180, 11, 223, 2342, 345, 435, 456, 4564, 55,
    2344, 3242, 342, 4, 34543, 435, 24, 456, 6, 456, 745
];
foreach($get_number as $k){
    var_dump($k);
}
$t2 = microtime(true);
echo '耗时' . round($t2 - $t1, 4) . '秒';

🧑‍💻 本文作者：艾瑞可erik
🔗 本文链接：https://erik.xyz/2023/06/06/matching-amount-algorithm-en/
📜 版权声明：本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可，转载请注明出处！
支付宝💙 支付宝
微信💚 微信