0
$\begingroup$

I have a binary file with lots of 128 bit strings:
For Example Line 1. 1000101001000100001111001010.....
Line 2. 011010010101001001010..... and many more.
I want to sort them in ascending order, and I know that counting the frequency of all strings would be as good as sorting them (as original order does not matter).
But I don't know which is faster : sorting the file or counting the frequency of strings.
So, I want to know which option will be faster ?

$\endgroup$
1
  • $\begingroup$ Which one do you need? Being able to count frequencies very fast is useless if you need sorted strings. So knowing which one is faster is pointless. $\endgroup$
    – gnasher729
    Commented Sep 6, 2021 at 7:04

1 Answer 1

0
$\begingroup$

Asymptotically speaking, both tasks can be performed in time $O(n)$ (which is also a trivial lower bound) since there can be only finitely many distinct binary strings.

I don't know which of the two approaches is faster since it depends on the specific implementation details of the data structures used so you might try both of them. In practice I would implement the two approaches as follows:

To sort the strings use radix sort where each binary string is written some base $b$ which is a power of $2$. Chose $b$ to be a good trade-off between the memory you need to allocate (i.e., $\Theta(2^b)$ words) and the number of iterations of radix sort (i.e., $\lceil 128/b \rceil$). You could start, e.g., with $b=16$. This will require linear time in the worst case.

To count the number of occurrences use an Hashmap pre-sized to a capacity $\alpha n$, where $\alpha$ depends on the load-factor of the Hashtable's implementation (the idea here is to prevent re-hasing). The keys of the hashmap are the strings, and the associated values are their number of occurrences. This will require linear time in expectation.

$\endgroup$
1
  • $\begingroup$ Thank you for the answer. $\endgroup$
    – Akash
    Commented Sep 5, 2021 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.