http://www.perlmonks.org?node_id=180701


in reply to Re: What do you like in a Collection class?
in thread What do you like in a Collection class?

(This also applies to VSarkiss' reply below; Aristotle just came first...)

Arrays do not support all common operations on collections (and hashes don't support all common operations on maps, either). That's why e.g. C++, (which does have support for Perl-like arrays as part of the standard language, VSarkiss; vector<T> is defined in the standard!), also supports other data structures.

One thing array can't support is constant-time insertion (and extraction) of one or more elements. With a linked list, it's easy, but Perl's splice operation is quite expensive. Think of splice on a linked list: it works in constant time!

Same thing for hashes and balanced trees. C++ has the latter (as map<T>); the lack of the former is a known deficiency (most STL implementations support some hash_map<T>, but it is not standard, so precise semantics may change). Why do you need both data structures?

Easy. Hashes give you excellent expected time behaviour. But their worst case behaviour can be appalling (unless you store a balanced tree at each big bucket, in which case you're back to climbing trees). Hashes also don't support range operations ("return all values with keys between ariels and aristotle"). Some times you need the one, other times the other. This is why we have more than one type of data structure.

Perl provides some data structures. This helps make it a Swiss army chainsaw. But don't let's kid ourselves we don't need what Perl doesn't have...

Replies are listed 'Best First'.
Re: What do you like in a Collection class?
by Abigail-II (Bishop) on Jul 10, 2002 at 09:41 UTC
    Splicing on a list only works in constant time if you happen to have a pointer near the part you want to delete. But in general, splicing on an array and on a linked list will take linear time - it's linear on the array because of all the movement of the elements that's needed, and it's linear on a linked list because you first need to get to the part that needs to be deleted. The deletion itself takes time linear to size of the part that needs to be deleted - unless you also have to happen a pointer at the end of the part that needs to be deleted.

    Abigail

Re^3: What do you like in a Collection class?
by Aristotle (Chancellor) on Jul 10, 2002 at 17:14 UTC

    I wasn't saying we don't need what we don't have, just offering an explanation.

    There are times when one needs things that Perl's arrays and hashes cannot provide, but that doesn't happen often. Even when it does, it is usually possible to shoehorn Perl's builtin data structures into the job at the expense of extra code complexity, or to rearrange the task in a less convenient way such that arrays or hashes will suffice (which is really the same thing as the former).

    That doesn't mean it can always be done. It just means that a rare itch will likely get ignored rather than scratched, hence the lack of modules, and that is all I was saying.

    Update in reply to dragonchild: if the need is so seldom and a prior art does not exist, the incentive to invest the effort of writing a generalized solution is low. It's a case of weighing hubris (create CPAN module) vs impatience (just write some code)..

    Makeshifts last the longest.

      "Extra Code Complexity" ... doesn't that just scream to be refactored into a module?

      ------
      We are the carpenters and bricklayers of the Information Age.

      Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.