Topic: What is the fastest and most memory-efficient way to check for RBF-bumped txs? (Read 90 times)
July 07, 2023, 02:31:27 AM
As far as I know, collections.Counter can be used to find and extract duplicates in an array with a time and space complexity of O(N). You also need to apply additional filtering based on the count of similar transactions, fee parameters, and probably transaction status. Use list comprehensions to build these filters because they are more memory-efficient than in-built functions such as map and filter.
July 06, 2023, 07:54:43 AM
In my code, I have a list of transactions from Satoshi's address (the 1A1z... address from the Genesis block), but there is at least one pair of transactions which are i) unconfirmed and ii) one of these transactions bumped the other using RBF, which means the one with smaller fee is invalid and should be dumped.
To safe you time, it's these two:
As I said, I have the list of transactions including these two and I also have vsize and fee/vbyte information. So now I need to find an algorithm that hopefully does not involve looking back at every UTXO that has just been processed, looking for duplicates (because that will take O(N^2) time, and I'm hoping there's something closer to O(N log N) or even O(N)).
For context: This is with Python.
To safe you time, it's these two:
Code:
{'address': '1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa',
'txid': '8784c4c7f32a9173ef33030f87fc07c00db13222c9b112c850adbe08dcb49775',
'index': 0,
'amount': 5.58e-06,
'height': None},
{'address': '1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa',
'txid': 'd081505e5ffc3a1110ba47d09f1273b2ae35297c12e34f5dfdcf72d264e0c90d',
'index': 1,
'amount': 5.58e-06,
'height': None}
'txid': '8784c4c7f32a9173ef33030f87fc07c00db13222c9b112c850adbe08dcb49775',
'index': 0,
'amount': 5.58e-06,
'height': None},
{'address': '1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa',
'txid': 'd081505e5ffc3a1110ba47d09f1273b2ae35297c12e34f5dfdcf72d264e0c90d',
'index': 1,
'amount': 5.58e-06,
'height': None}
As I said, I have the list of transactions including these two and I also have vsize and fee/vbyte information. So now I need to find an algorithm that hopefully does not involve looking back at every UTXO that has just been processed, looking for duplicates (because that will take O(N^2) time, and I'm hoping there's something closer to O(N log N) or even O(N)).
For context: This is with Python.
Jump to: