0

我需要选择最佳比特币交易组合进行发送。我使用 PHP 实现了结果，但它使用了大量内存，并且数据库很可能会更好地处理它。

整个交易清单：

+------------------+------+--------+
|  Transaction ID  | Vout | Amount |
+------------------+------+--------+
| transactionid1   |    0 | 10     |
| transactionid1   |    1 | 1.5    |
| transactionid2   |    0 | 0.5    |
| transactionid3   |    0 | 0.7    |
+------------------+------+--------+

我需要创建某种函数或选择查询，当我提供数量 = 0.4 时，它将返回我下面的行

+------------------+------+--------+
|  Transaction ID  | Vout | Amount |
+------------------+------+--------+
| transactionid2   |    0 | 0.5    |
+------------------+------+--------+

当我提供金额 = 2.1

+------------------+------+--------+
|  Transaction ID  | Vout | Amount |
+------------------+------+--------+
| transactionid1   |    1 | 1.5    |
| transactionid3   |    0 | 0.7    |
+------------------+------+--------+

所以这是一种关于剩菜的背包问题。这是我使用组合学解决问题的方法。我已将交易数据扁平化为 $key => $value 数组，其中 $key 是 transactionid_vout，value 是金额。

$flatterTransactions = 数组（4）（
  [transactionid1_0] => (int) 10
  [transactionid1_1] =>（浮动）1.5
  [transactionid2_0] => (float) 0.5
  [transactionid3_0] => (float) 0.7
)

然后我从该交易中创建组合

$combinations = 数组（15）（
    [0] => 数组
        (
            [transactionid1_0] => 10
        )

    [1] => 数组
        (
            [transactionid1_1] => 1.5
        )

    [2] => 数组
        (
            [transactionid2_0] => 0.5
        )

    [3] => 数组
        (
            [transactionid3_0] => 0.7
        )

    [4] => 数组
        (
            [transactionid1_0] => 10
            [transactionid1_1] => 1.5
        )

    [5] => 数组
        (
            [transactionid1_0] => 10
            [transactionid2_0] => 0.5
        )

    [6] => 数组
        (
            [transactionid1_0] => 10
            [transactionid3_0] => 0.7
        )

    [7] => 数组
        (
            [transactionid1_1] => 1.5
            [transactionid2_0] => 0.5
        )

    [8] => 数组
        (
            [transactionid1_1] => 1.5
            [transactionid3_0] => 0.7
        )

    [9] => 数组
        (
            [transactionid2_0] => 0.5
            [transactionid3_0] => 0.7
        )

    [10] => 数组
        (
            [transactionid1_0] => 10
            [transactionid1_1] => 1.5
            [transactionid2_0] => 0.5
        )

    [11] => 数组
        (
            [transactionid1_0] => 10
            [transactionid1_1] => 1.5
            [transactionid3_0] => 0.7
        )

    [12] => 数组
        (
            [transactionid1_0] => 10
            [transactionid2_0] => 0.5
            [transactionid3_0] => 0.7
        )

    [13] => 数组
        (
            [transactionid1_1] => 1.5
            [transactionid2_0] => 0.5
            [transactionid3_0] => 0.7
        )

    [14] => 数组
        (
            [transactionid1_0] => 10
            [transactionid1_1] => 1.5
            [transactionid2_0] => 0.5
            [transactionid3_0] => 0.7
        )

)

然后我通过组合并创建带有评分的求和组合数组。这里的评分目标是使用更少的事务。

$summedCombinations[$key] = array(
                'sum' => $sum,
                'count' => count($combination),
                'score' => $sum * (count($combination) * 2)
            );

毕竟我按总和字段过滤数组，只留下涵盖我金额的交易。按分数排序并获得最佳匹配。

4

1 回答 1

0

最好在这里有点问题，但这就是我的处理方式。不管你怎么做，你必须处理一个选择组合的算法。

 WITH target AS (select ? as target),
 RECURSIVE largest_txs AS (
      select transaction_id, vout, amount, amount as running_total
        from transactions
  CROSS JOIN target 
       where amount < target.target
    order by amount desc limit 1
   UNION ALL
      SELECT t.transaction_id, t.vout, t.amount, t.amount + l.running_total
        FROM transactions
        JOIN (select * from largest_txs order by amount asc limit 1) l
  CROSS JOIN target 
       WHERE amount < target.target + l.running_total AND t.transaction_id NOT IN
             (select transaction_id from largest_txs)
 )
 SELECT transaction_id, vout, amount, running_total FROM largest_txs
  UNION
 SELECT t.transaction_id, t.vout, t.amount, null
   FROM transactions t 
  WHERE t.transaction_id NOT IN (select transaction_id from largest_txs)
  ORDER BY amount asc limit 1;

这应该和预期的一样好。但是，如果表格大小不一，您肯定会想要一个金额索引。

于 2013-11-13T05:36:24.183 回答