Ok, I see it now. For number of adds N where N is between 1 and 7 the number of compose calls is N-1, but after that the number of calls to compose per add starts dropping such that when N = 16 the number of compose calls is only 13.
-Tad On Thu, Feb 11, 2010 at 5:29 PM, Alexandre Mah <[email protected]> wrote: > On 2/12/10, Tad Glines <[email protected]> wrote: >> The construction of DocOpCollector seems unnecessarily complex. >> >> Here's the relevant snippet: >> >> private final List<BufferedDocOp> operations = new >> ArrayList<BufferedDocOp>(); >> >> public void add(BufferedDocOp operation) { >> ListIterator<BufferedDocOp> iterator = operations.listIterator(); >> while (iterator.hasNext()) { >> BufferedDocOp nextOperation = iterator.next(); >> if (nextOperation == null) { >> iterator.set(operation); >> return; >> } >> iterator.set(null); >> operation = compose(nextOperation, operation); >> } >> operations.add(operation); >> } >> >> public BufferedDocOp composeAll() { >> BufferedDocOp result = null; >> for (BufferedDocOp operation : operations) { >> if (operation != null) { >> result = (result != null) ? compose(operation, result) : operation; >> } >> } >> operations.clear(); >> return result; >> } >> >> This seems like it could be more simply (and efficiently) expresses as: >> private BufferedDocOp collectedOp = null; >> >> public void add(BufferedDocOp operation) { >> if (collectedOp == null) >> collectedOp = operation; >> else >> collectedOp = compose(collectedOp, operation); >> } >> >> public BufferedDocOp finish() { >> BufferedDocOp result = collectedOp; >> collectedOp = null; >> return result; >> } >> >> Does anyone see a problem with the proposed change? > > The solution you propose has an O(n^2) time complexity for composing a > sequence of operations of total size n, whereas the current code has > an O(n log n) time complexity. > > Perhaps I can explain how the DocOpCollector works, since I think it's > pretty interesting. > If you interpret the operations List as a (little-endian) binary > number, where a null in the list indicates a 0 and a non-null > operation indicates a 1, then adding an operation to the collector > works exactly like incrementing its binary number representation. > > An interesting byproduct of this algorithm is that interpreting the > operations List as a binary number will tell you exactly how many > operations have been collected so far. > > I hope that clears things up. > > Alex > > -- > You received this message because you are subscribed to the Google Groups > "Wave Protocol" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/wave-protocol?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Wave Protocol" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/wave-protocol?hl=en.
