meritlabs / merit

Merit aims to be the world's most adopted digital currency.
https://www.merit.me
MIT License
192 stars 20 forks source link

Replace linear search with O(logN) search for FindLotteryPos #382

Closed mempko closed 6 years ago

mempko commented 6 years ago

This dramatically speeds up block validation time because FindLotteryPos is called for every output of every transaction in a block.

This particular implementation falls back on linear search which means no reindex is required. As more blocks are added, the faster validation will become because more entries will be added to the inverse position index.