在同一平台中买卖交易,需要进行订单撮合。相近的金额从大到小递减组合。期初想用mq分别匹配整数的金额倍数处理,总觉的不太完美。最近刚好有空就找到了猴子选大王算法: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);
根据以上算法改造一下。
先确定匹配金额顺序,即做降序排列。
然后每次匹配到小于指定金额后,减去此金额。把匹配金额赋值为差结果。
依次类推。
在这过程中记录匹配到的金额、最后差值的余额。
撮合代码如下:
1 |
|
最近闲来无事,做了测试。如下图做测试数据
测试后生成结果
发现这样撮合数据多的时候会耗时太久,就尝试找优化方法。
如果使用生成器呢,生成结果如下
完整优化代码: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) . '秒';
本文链接: https://erik.xyz/2023/06/06/matching-amount-algorithm/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!