Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to work with a variety of data structures (arrays, singly/doubly linked lists, sorted structures, etc.) on a plug-and-play basis. For example, I want to be able to easily swap in and out the sorted list and the array (which is re-sorted after every insertion/deletion), to test which one has better performance.

In every language I know of, the public interface to such data structures is very inconsistent. So changing the implementation requires a lot of work.

Is there a language, or a language-agnostic design pattern, that makes it easy to define a generic public interface that works with any data structure?

Of course, I understand how different performance would be (e.g., binary search in a sorted array vs linear search in a regular array). All I ask is that the performance of the data structure doesn't degrade asymptotically or by a large constant factor due to the use of the standard interface.

Example problem: iterate through the container of numbers, find the two numbers that are nearest each other, and remove the pair of them. (If several pairs are equal distance, pick an arbitrary pair).

I'd like the code to solve the problem to be unchanged as I switch in and out different containers.

share|improve this question
1  
You could create your own library of such methods and call it from your chosen language. A pattern will eventually have to be implemented in (a) specific language. – NoChance May 1 '12 at 4:08
    
The collection interface in java, implemented by List and Set, but not Map. – NimChimpsky May 1 '12 at 8:32

10 Answers 10

up vote 6 down vote accepted

The best designed collection framework I have personally worked with, is Scala's, especially combined with the extensions from the Scalaz library.

The Haskell community currently seems to be the frontrunner when it comes to figuring out very general collection interfaces, see e.g. the Data.Traversable or Data.Foldable type classes, zippers, iteratees, enumeratees etc. (A lot of this is also implemented in Scalaz.)

Here's an example how to solve your problem in Scala. Note, I haven't done anything to make this efficient or beautiful, nor have I given any thought to whether this algorithm is sensible or not.

The important feature is that this code is only dependent on operations provided by the Seq trait (zipWithIndex, sorted, foldRight, filterNot), which is very general: it only assumes that the collection has a definite size and that elements may appear multiple times. That's it.

val s = Seq(5, 1, 9, 2, 6) // our test sequence

val sWithIndex = s zipWithIndex

val rejects = sWithIndex.sorted.foldRight(
  (Int.MaxValue, (
    (Int.MinValue, Int.MinValue), (Int.MinValue, Int.MinValue)))) {
  case ((el, i), (minDist, ((n1, i1), (n2, i2)))) => 
    if(math.abs(n2 - el) <= minDist)
      (math.abs(n2 - el), ((n2, i2), (el, i)))
    else
      (minDist, ((n1, i1), (n2, i2)))
  }._2

val rejectIndices = (rejects._1._2, rejects._2._2)

val result = sWithIndex filterNot { case (_, i) =>
  i == rejectIndices._1 || i == rejectIndices._2 } map (_._1)
// result = List(1, 9, 2)

This algorithm is O(n*log n), because sorted is a generic stable sort. You could make it O(n) by using a radix sort, since the elements are known to be integers.

share|improve this answer

The problem with the data structures you mentioned is, that they have a different semantic. I.e. they work in a different way and cannot have a common interface. E.g. a list could have an Add method that would add an element to the list. An array, however, cannot have such a method, since the length of the array fixed. An array allows you access elements randomly through an indexer (a[i] = x; print(a[k]);), but you cannot do that with a linked list. In a linked list you can only access the next or previous element starting at the list header or tail. An unsorted collection would probably have a Sort method, a inherently sorted collection (e.g. a binary tree sorted by a given key) of course not, as the elements get sorted at insertion.

One single interface won't work. You need a set of interfaces, each of them exposing specific aspects of collections.


If you want to compare different collection types, I suggest you to create wrappers using a common interface. You would then perform the tests on the wrappers.

Such a wrapper interface could look like this

public interface ICollectionTestWrapper<T>
{
    void FillWithTestData(IEnumerable<T> data);

    bool IsSortable { get; }
    void Sort();

    void FindElement(T element); // No return value needed for speed tests.

    // TODO: Add functionality for the tests you have in mind
    ...
}
share|improve this answer
1  
-1: this is so wrong. An array would obviously throw a FixedLengthException or somesuch on Add, a linked list very much has an indexer (it's slow! don't use it for iteration! but you would use an iterator for iteration for an array anyway - it doesn't break anything). Of course a sorted collection would have a sort method (if sort wasn't implemented externally), so that you can sort generic collections; it would just return self. Etc! – naiad May 1 '12 at 16:25
2  
@sparkleshy: It's not wrong. The OP is NOT referring to the .NET Framework here, where arrays are indeed pretending to implement IList<T> which defines an Add method throwing an exception if used (which violates LSP and is a severe design error in my mind). We are talking about data structures in a very general way here and a good implementation of an array would not implement an Add method (and adding an indexer to a linked list is not a good idea either). – Olivier Jacot-Descombes May 1 '12 at 16:35
    
@sparkleshy: A sorted collection, as described by the OP, sorts the elements at insertion. The elements are ALWAYS sorted in a sorted collection. A sorted collection could be implemented as a binary tree for instance. Does a binary tree have a Sort method? – Olivier Jacot-Descombes May 1 '12 at 16:49

Java does this somewhat.

See the List, Set, or Map interfaces. Each interface has a number of implementations, implementing the various operations in different ways.

Python also does this somewhat by virtue of its duck typing. The interface of different objects is similar, so you use the same code on different data structures.

share|improve this answer
    
Could you please see the update to the question (Example problem) that clarifies what I'm trying to do? Can Java do that? – max May 1 '12 at 6:22
    
@max - List and Set are both implementations of the Collection interface. iterator(), contains(Object o), and remove(Object o) are all defined in the Collection interface. Note thought that List and Set have some different features (lists may contain multiple identical values, sets may not) to them and swapping a List for a Set may fundamentally change some aspects of the algorithm. – user40980 May 1 '12 at 16:12

Also there is a generic programming style, which allows to split data and algorithms. For more details see also C++ Standard Template Library

share|improve this answer
    
would you mind expanding a bit on what each of these resources have and why do you recommend these as answering the question asked? "Link-only answers" are not quite welcome at Stack Exchange – gnat Aug 24 '13 at 17:08

Its called Table in most systems:

OO systems that provide the concept of an Interface support swapping out implementations transparently. Java specifically does this Collection <- List <- ArrayList, LinkedList, etc.

C++ supports this as well. Python supports this. C would not support this directly.

Dependency Injection in the languages that support this would making plugging concrete implementations in and out configurable as well.

  • Java: For a extremely generalized interface Guava has the Table interface and enough specific implementations to cover almost all cases.

  • Lua really on has one collection type and that is Table.

A Table interface can serve all the general purposes of an Associative Array as well as a random access normal Array if you just use numbers for the keys.

share|improve this answer

Example problem: iterate through the container of numbers, find the two numbers that are nearest each other, and remove the pair of them. (If several pairs are equal distance, pick an arbitrary pair).

Data structures have different interfaces because they do different things. Arrays and linked lists are somewhat comparable in that they both store an ordered collection, but there are important differences even here: you generally don't refer to items in a linked list by index, memory is managed very differently, etc. When you start looking at other structures (heaps, sets, maps, binary trees, etc.) the differences increase and the similarities decrease.

If you're willing to give up some of the advantages of each of the structures you test for the sake of providing a uniform interface, there's nothing to stop you from defining a "List" interface and implementing it using each of the structures you want to test. Any language that supports polymorphism will do the job, and you can easily imagine a set of operations that are common to all the structures (insert, remove, sort, search). Just don't forget that your test conditions will be somewhat contrived -- by forcing the structures you test to conform to a common interface, you'll be ignoring the aspects that differentiate each structure from the group.

share|improve this answer
    
Suppose my algorithm stays the same. Sort, if the structure isn't sorted. Iterate, and observe differences. Find the two closest elements. Remove them. This can be done without loss of performance in each of these data structures; trouble is, I cannot find a common interface to do it with. – max May 1 '12 at 17:17
    
So create one. Create a list class, and then implement it in terms of array, linked list, heap, and whatever else you like. – Caleb May 1 '12 at 17:26
    
One example of what I'm struggling with. To efficiently delete an element from a linked list I need the pointer to the previous element; from an array, the element's index; from a set, the element itself; and so on. I was trying to design an iteration protocol that provides me such things uniformly from all classes, but I feel if it makes sense, it would have been done already. So perhaps I'm on the wrong path. – max May 1 '12 at 17:47
    
If you want to find the 17th element in a linked list, start at the head and follow the first 16 next links. Works fine but it's slow because a linked list is not an array. Want to insert an element at the beginning of an array? Move all the others up one spot first. Again, works fine but it's slow because an array is not a linked list. This is just what I was saying above: to impose a standard interface on these different structures is to lose the features which make them different and useful. – Caleb May 1 '12 at 18:21
    
That's why I'm asking for an efficient common interface. If you already iterated through a list, and you want to delete the element you found, you need to be given, during the iteration, a pointer to the previous element. When you already iterated through an array, and you want to delete an element you found, you need to be given, during the iteration, the index of the element. Of course some operations would still take longer; e.g., removal from an array is slower than from a list - but at least I won't have to search for the element before I can remove it! – max May 1 '12 at 18:37

It sounds like you're looking for the strategy pattern. What you'll do is define your own interface (like find-nearest-neighbors(NumericCollection) or find-closest-value(NumericCollection, Integer)) and provide several implementations of it. Details of calling the various implementations are necessarily language-specific, but as long as each supports the defined interface, you should have a good basis for comparison.

share|improve this answer

C++'s STL has something along these lines - all collections support iterators which you can use to access the members, and the iterator is a standard class itself, so has the operations you want.

So you can walk an array using begin() to end(), and you can swap the array for a list without any issues.

However, some collections support different operations - although you can sort both array, list and queue, you can't sort a map or set (they're already sorted). This just means some operations don't make sense for some collections.

Look at the algorithms section of the STL for a set of operations that apply to every different type of STL collection.

share|improve this answer

You should research the Adapter Pattern. Using the Adapter Pattern, you'd define an interface, IContainer, that provides all the required operations, such as indexing, sorting, etc. You would then create different implementations of your IContainer interface, such as ArrayContainer, LinkedListContainer, and so on. Next, using a technique such as Dependency Injection, you could write your algorithms around your IContainer interface, thereby decoupling your code from any one particular container type. This would allow you to substitute and measure the performance of different kinds of containers.

share|improve this answer

Is there a language, or a language-agnostic design pattern, that makes it easy to define a generic public interface that works with any data structure?

Haskell seems like an awesome suggestion, but maybe a bit hardcore. At least I'm a little bit afraid of Haskell (it's a language whose code always inspires me, but I never actually got the nerve to try anything substantial).

I'd personally recommend C++ for this since the code generation of C++ templates allows you to eliminate any abstraction cost (dynamic dispatch, i.e.) out of the picture and just focus on the efficiency of the data structures themselves while likewise mutating the data structure easily (might be a little bit hard in functional languages without kind of changing the whole way you approach data structures). It's one of the few languages I personally know where you can write a contiguous data structure which performs just as well for random access as a plain old array, e.g., since the optimizer just squashes all that code structure you built down to smithereens.

It also comes with a pretty complete set of standard containers (though missing a few semi-common ones like tries) with a "near" data structure-agnostic interface. A little bit of wrapping should give you a universal interface that lets you do whatever you want, at least for value types (set vs. map). Key/value associative containers are a bit harder to generalize and might need to be in their own category, simply because they tend to call for a very different interface design.

The key to doing this to me is to define your universal interface. A C++ standard sequence like vector has these functions:

push_back -- appends an element to the back of the container.
insert -- inserts an element to any place in the container.
erase -- erases an element from any place in the container.
range insert -- inserts multiple elements to any place in the container.
range erase -- removes a range of elements from any place in the container.
empty -- returns size() == 0.
size -- returns the number of elements.
clear -- removes all elements from the container.
begin -- returns an iterator pointing to the beginning of the container.
end -- returns an iterator pointing to the end of the container.

There's also a fill constructor, range constructor, etc. (and you can even pass in your own memory allocator which usually isn't that helpful for something like vector but can make a huge difference for linked structures).

The linked-list, std::list, conforms to the same interface requirements except with some minor differences in this context like a push_front member function which is omitted from std::vector deliberately to discourage its use there.

You can easily wrap all these containers and, with little effort, apply a universal interface... maybe with functions like so:

push_front -- insert to front.
push_back -- insert to back.
erase -- erase anywhere.
insert -- insert anywhere with no regard about where the element goes.
insert_sorted -- do an insertion sort.
...

Etc. It won't take much time to wrap all applicable existing C++ containers to conform to this universal interface of your design as well as implement new ones that conform to it, and then you can benchmark your heart out and generate graphs and whatever you want.

A major thing to note about C++ is the iterator design driving algorithms. You can implement a custom data structure there, and by merely exposing iterators, hundreds of existing algorithms (not just standard but also third party) suddenly become applicable to your data structure with no extra effort. There's no need to implement like a sort method for your custom data structure, for example, as std::sort will work on it once you expose iterators to it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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