[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Bug#1011343: WISHLIST: Offical ALL-IN-ONE images?


On 2022/6/26 03:30, Thomas Schmitt wrote:
Complexity-wise this replaces a slow O(n) algorithm by a faster O(n) and
an additional O(n * log(n)) run. At some size of Debian the slow speed
of the linear loop will be compensated by the sorting complexity.
But there is still room: A sort of 11,000 lines lasts about 0.03 seconds.

Theoretically if both file is already sorted, we can use the `-m' option (e.g. `sort -m -k 2 A.txt B.txt') to merge them in O(n) like mergesort. However I don't think O(n * log(n)) is a bottleneck so we may just keep it simple and stupid.

Best Regards,
Zhang Boyang

Reply to: