4
$\begingroup$

As a subroutine for an algorithm we’re working on, we need to compute the lexicographically minimal rotation (or least circular shift) of a list of lists of integers.

The problem, in the more usual setting of strings of (atomic) symbols, is well-known and several linear time algorithms have been published, the first one being Booth’s LCS algorithm, which is based on Knuth-Morris-Pratt.

However, the analyses proving the $O(n)$ runtime that I find in the literature all seem to be based on the finite alphabet assumption or, to be more precise, on constant-time comparisons between symbols.

As mentioned above, in our application we have lists $\langle \ell_1, \ldots, \ell_m \rangle$ of $m$ lists of integers, where each list $\ell_i$ contains integers whose value is bounded by the total length $n = |\ell_1| + \cdots + |\ell_m|$, rather than a string of atomic symbols, so comparing two lists $\ell_i$, $\ell_j$ by lexicographic order requires time proportional to length of the longest common prefix of $\ell_i$ and $\ell_j$ (here, we assume that a comparison between two integers can be carried out in constant time).

Experimentally, on our data (which is admittedly not arbitrary lists of lists), it seems that Booth’s LCS algorithm does indeed work in time $O(n)$ in this case, i.e., in linear time with respect of the sum of the length of the lists.

Is there a simple argument I’m missing (or a complicated argument published somewhere) that proves that this is indeed the case, either for Booth’s LCS algorithm, or alternatively for Knuth-Morris-Pratt? Or is this actually false?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Is it possible that two strings are compared in constant expected time? That would be the case, for example, if they are "different" enough on average so the typical case is that you only need to look at a few characters to decide. $\endgroup$
    – Steven
    Jul 25, 2022 at 13:35
  • $\begingroup$ @Steven, that’s an interesting remark, but I am not currently aware of any such patterns in our data. (I mean, we are not comparing arbitrary strings, but I’d rather not go into details unless it’s really necessary in order to answer the question, since they’re rather complicated.) $\endgroup$
    – Antonio E. Porreca
    Jul 25, 2022 at 13:39
  • $\begingroup$ @Steven, I’ve tried a little test and it seems like it works in linear time even when all strings are identical, which triggers the worst case for the comparisons (while not making a difference for Booth’s algorithm itself, unless I’m mistaken). $\endgroup$
    – Antonio E. Porreca
    Jul 25, 2022 at 14:01
  • 1
    $\begingroup$ If your data distribution allows O(1) hash tables, you can precompute a hash table from strings to small integers in time linear to the total size of the strings, and then apply a linear time algorithm on the list of small integers. You'd probably lose all the benefits of algorithms that are fast because they manage to completely skip a lot of elements, though, so it fits the letter but not the spirit of the question (hence why I'm not posting this as an answer). But maybe you can get the benefits of both worlds with some kind of laziness or caching? $\endgroup$
    – Gilles 'SO- stop being evil'
    Jul 29, 2022 at 18:01
  • $\begingroup$ @Gilles'SO-stopbeingevil', your remark (while interesting, and thank you for it) made me realise that I should probably avoid the term “strings” here, since we’re actually dealing with lists of integers bounded by the number of elements $n$ in the list. I’m modifying the questions accordingly. $\endgroup$
    – Antonio E. Porreca
    Jul 29, 2022 at 18:36

1 Answer 1

Reset to default
5
$\begingroup$

This doesn't answer your question about why your naive comparisons are fast, but the following appears to allow comparisons in constant time:

  • Concatenate the lists of integers together
  • Compute the suffix tree of the result, which can be done in linear time after sorting the integers that appear in it (possible in linear time from your assumption that the integers have magnitude bounded by the input length)
  • For each list of integers, find where you get to in the suffix tree by following a matching path down from the root
  • Replace each list of integers in your list of lists by the index of the resulting suffix tree node, as numbered using a preorder traversal of the suffix tree
  • Compare sequences by these numbers, with ties broken by length
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks, I think we have already found (what I believe to be) a simpler alternative linear-time solution for our specific case, but this does indeed seem to be another possibility. (I’m not accepting this answer not because it’s not insightful, it is!, but because I’m really interested in the efficiency of the naive approach.) $\endgroup$
    – Antonio E. Porreca
    Aug 11, 2022 at 13:15

Your Answer

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

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