3

(I've added the .NET tags because the data structures are for .NET, and this question should be considered in the context of the conventions for that platform.)

I'm writing a library of immutable and persistent data structures for .NET. One of my data structures, a type of vector, supports the following core operations:

  1. Addition and removal at the end
  2. Lookup and update by index
  3. Starting subsequence
  4. (Uninteresting things like length, etc)

In addition, there is a special implementation of bulk operations (involving sequences, such as addition of many elements) that is extremely fast for large inputs. This makes addition of many elements to the end very, very fast.

My issue is a bit more complicated than the title of the question makes out. I can implement the following additional operations:

  1. Addition of many elements at the beginning
  2. Insertion of many elements in the middle

Addition of many elements to the end is O(m + logn), where m is the number of elements to be added. These operations would be O(n + m), and if m = n then they are almost as fast as addition to the end. In practice, they would be many orders of magnitude faster than if the user implemented them naively. However, for small numbers of elements, they would still be very slow.

My first problem is that the normal operations are so fast, they might confuse users and make them think these additional operations perform in a similar manner. Unlike for regular collections where even List<T>.Insert is fast, this can actually bottleneck the application. How should I deal with this?

My second problem is that, if I implement these additional operations, should I also provide similar (extremely inefficient) operations that work with single elements? It seems strange not to provide these apparently simpler operations, and I'm sure they will be handy (performance isn't important at all sometimes), but that surprise factor is even worse here, since these operations can never be efficient.

A similar consideration applies for a Skip (ending subsequence) operation.

  • 4
    In practice, they would be many orders of magnitude faster than if the user implemented them naively. That sounds like reason enough for me, especially if there's no way for the user to match the performance without modifying your source code. – Doval Mar 25 '15 at 2:40
  • That's what I think too. No, there is absolutely no way for them to do it. I'm more interested about your answer to the other problem, and also about the ways I might use to avoid surprising the user. – GregRos Mar 25 '15 at 2:46
  • 1
    In my experience, programmers should be reading docs when using methods of classes that they're unfamiliar with. I'd do the implementation, but express the caveat: caller beware. – Lynn Crumbling Mar 25 '15 at 3:11
  • Those comments should be an answer. – Ixrec Mar 25 '15 at 9:17
  • You could call the fast operation on many BulkInsert or InsertMany which implies that they are optimized for the many case. If someone calls them for a single element and it is slow, they are misusing the component. Obviously the documentation should explain the whole story, but those names would give detail about using the API at a glance. – Mike Mar 25 '15 at 12:48
5

Addition of many elements to the end is O(m + logn), where m is the number of elements to be added. These operations would be O(n + m), and if m = n then they are almost as fast as addition to the end. In practice, they would be many orders of magnitude faster than if the user implemented them naively. However, for small numbers of elements, they would still be very slow.

To me, the fact that the user simply can't obtain similar performance for these operations without access to the source code of the data structure is reason enough. To do otherwise punishes the users that actually need the performance while giving no major benefits to those that don't.

I can see where you're coming from; there's certainly something to be said for following the principle of least surprise. However, I don't think there's anything surprising about insertion into the beginning of a vector being slower than insertion at the end, and users that haven't bothered to read about the time complexity of the operations are in no position to complain about them. What's more, regardless of how much slower insertion at the beginning is, that may not be the performance bottleneck in the user's application, or the user may never create vectors big enough that the difference would matter.

What would be surprising is if the user could implement a faster insertion than you despite not having access to the data structure's innards.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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