Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
    
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. –  Emmad Kareem 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

9 Answers 9

up vote 5 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 sorted list of cause not.

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: 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
    
@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. –  MichaelT 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

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.

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

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.