This should go without saying, but the choice isn't always easy. For example, to find something by name, one could do a O(N) linear search, or a O(1) hashtable lookup. For small or many tables, the linear search might be better.
In a program we may need to make hundreds of such decisions. When in doubt, use a simple algorithm, and revisit the issue later.
A good example of this is the Version Six Unix kernel. It used the simplest data structures until performance showed something better was needed. It required only ten thousand lines of C.
As more efficient algorithms can take more lines of code to implement, you can consider this as trading implementation space for time.
Write the code so that you can revisit the implementation choice later when performance information is available. This is a benefit of writing abstract software.
At the extreme end of remaining flexible, the program itself could choose the appropriate data structures. This may seem extreme at first, but already we give many choices to programs, such as where to allocate a data structure, and when to reuse its storage.
ostream & CXDisplayList::print(ostream& s)
{
s << "CXDisplayList" << endl;
for (int i = 0; i < graphicList.entries(); i++)
{
if (graphicList[i])
{
graphicList[i]->print(s);
s << "\n";
}
}
return s;
}
However, it was really O(N^2) because graphicList[i] was implemented as a loop.
This fact was cleverly hidden by C++ operator overloading.
This is a tall order.
Garbage collection is another good thing with a bad reputation.
Luckily, this is changing as people get first hand experience in languages like
Java, ML, and even C and C++.
http://reality.sgi.com/boehm_mti/
"The Measured Cost of Conservative Garbage Collection"; Benjamin Zorn; Software -- Practice
and Experience; 1993-07;
Ken Anderson