Tuesday, March 07, 2006
Associative arrays: form over substance
The ASP.NET 2.0 Dictionary and Hashtable objects provide the form of associative arrays without guaranteeing the substance. The main objective of conventional implementations has always been to provide rapid insertion and retrieval.
Dictionary and Hashtable objects are containers of (key, value) pairs, and they provide the semantics of associative arrays. If oTable is one of these, then oTable[qKey] retrieves a value that has been associated with a key.
Conventional implementations of associative arrays maintain binary indexes and provide rapid insertion and retrieval using binary search. In its C++ library, Microsoft provides map<> containers committed to these O(log n) levels of performance.
Bjarne Stroustrop has a concise summary of C++ container performance guarantees in his book, "The C++ Programming Language," Third Edition, p. 464. David Musser and Atul Saini explain the meaning of such performance guarantees in their book, "STL Tutorial and Reference Guide," pp. 12-15.
By comparison, Microsoft documentation of ASP.NET 2.0 is scattered and opaque. Because of that, the programmer who needs O(log n) performance for both insertion and retrieval is forced to carry out performance testing and may have to write what should be, and in other environments what is, a standard library class.
Dictionary and Hashtable objects are containers of (key, value) pairs, and they provide the semantics of associative arrays. If oTable is one of these, then oTable[qKey] retrieves a value that has been associated with a key.
Conventional implementations of associative arrays maintain binary indexes and provide rapid insertion and retrieval using binary search. In its C++ library, Microsoft provides map<> containers committed to these O(log n) levels of performance.
Bjarne Stroustrop has a concise summary of C++ container performance guarantees in his book, "The C++ Programming Language," Third Edition, p. 464. David Musser and Atul Saini explain the meaning of such performance guarantees in their book, "STL Tutorial and Reference Guide," pp. 12-15.
By comparison, Microsoft documentation of ASP.NET 2.0 is scattered and opaque. Because of that, the programmer who needs O(log n) performance for both insertion and retrieval is forced to carry out performance testing and may have to write what should be, and in other environments what is, a standard library class.
Subscribe to Posts [Atom]