Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re^8: What makes an array sorted and a hash unsorted?

by ikegami (Patriarch)
on Jun 01, 2009 at 19:23 UTC ( [id://767349]=note: print w/replies, xml ) Need Help??


in reply to Re^7: What makes an array sorted and a hash unsorted?
in thread What makes an array sorted and a hash unsorted?

I'm not sure which you're contending

I'm saying there's no difference between hash and arrays expect in the order they choose to return their values. A hash could return its values in the same order as an array. And if it did, people would still ask how to sort hashes.

With which of these premises do you disagree?

Arrays have one intrinsic ordering. Hashes have zero intrinsic orderings.

So? Even if hashes had an intrinsic ordering, the same problems faced today would still exist. There's more to it than that, or the answer to the posts we see isn't "hashes aren't ordered".

Replies are listed 'Best First'.
Re^9: What makes an array sorted and a hash unsorted?
by Roy Johnson (Monsignor) on Jun 01, 2009 at 20:10 UTC
    I'm saying there's no difference between hash and arrays except in the order they choose to return their values.
    I don't think you're really contending that. It's obviously not true as stated. They are syntactically, functionally, and internally quite different. At a very abstract level, they're notionally about the same: collections of scalars that are indexable. If, by "return their values" you include the notion of having a "first (etc.) element", so that stacks and queues can be implemented, then I suppose that's the major difference (apart from being able to index a hash by string). So I'm still a bit unclear on your point. I kind of get it, but not really.

    I agree that people would still ask how to sort hashes, just as they currently ask how to sort arrays or lists. When they ask how to sort something, they indicate that they know they need to sort it.

    When people say (or hint that they think) that they have a hash whose elements are in some particular order, the answer is "hashes aren't ordered". It is a misconception people have about hashes. Once that misconception has been addressed, the question of how to solve their problem can be addressed. I don't think anyone has suggested that "hashes aren't ordered" is all anybody needs to know about them.

    If hashes had an intrinsic order, but people operated as if they had a different intrinsic order, we'd be telling them "hashes aren't ordered that way, they're ordered this way." Then we'd still have the issue of whatever particular thing the user is trying to accomplish. So the response wouldn't be all that different.


    Caution: Contents may have been coded under pressure.
Re^9: What makes an array sorted and a hash unsorted?
by herveus (Prior) on Jun 05, 2009 at 14:08 UTC
    Howdy!

    When you obtain the list of keys or values from a hash, you no longer have a hash. You have a list, which has an intrinsic order. The mechanism for extracting that list from the hash must traverse the internal data structures in some order to produce the list, but that sequence is explicitly undefined. That is the essence of being unordered.

    It makes no sense to say "A hash could return its values in the same order as an array." The statement presupposes that you can predict the order of the list of keys. You can't do that.

    If your collection imposes a predictable ordering on the indexes/keys, you can iterate over it directly. Iteration relies on order. That's why iterating over the contents of a hash requires helper functions to manage it. Something has to convert the set of key-value pairs into a list. The resulting list may be invisible to the user (as in each()), or explicitly returned (keys(), values()), but it's there. Saying (%foo) also converts the hash into a list. It's no longer a hash at that point.

    Operations over collections, whether ordered or not, may wish to impose an externally defined ordering on a list of the data. That is independent of whether the collection itself is intrinsically ordered. If you want your collection to maintain the data in a specific order, you are stuck with an array, if you intend to use basic Perl data structures. Linked lists and the like are outside the scope of this discourse. Alternately, you impose the desired order on a list each time you generate the list.

    To an extent, it really is that simple.

    yours,
    Michael
      the hash must traverse the internal data structures in some order to produce the list, but that sequence is explicitly undefined. That is the essence of being unordered.

      I've been watching from the sidelines and for the most part, this seems like a prime example of what killed the Pedants' Conference--they died arguing about whether the ' should be before or after the s--but I've always enjoyed a good freindly debate, so here goes nothing :)

      I would say that for all hash implementations, including Perl's current, (and all previous) implementations, they do have an "intrisic ordering". That ordering is a definable and concrete function of 2 factors:

      • The hashing algorithm.
      • The bucket size at the point of traversal.

      And given knowledge of algorithm (use the source), and the current bucket size, (see the second element of scalar %hash), the ordering is knowable; therefore definable; therefore defined by the implementation(s).

      However, I agree with the earlier statement--I've lost track of who made it (first)--that there is a significant difference between "order(|ing|ed)" and "sort(|ing|ed)".

      And the answer to the OP question is:

      Whilst the iteration order of arrays is, (for most (all?) languages), unspecified, it is defined, (by convention), to be the same as the natural ordering of its integer indexes; whereas, the iteration order of hashes, (also unspecified), is defined, (as a matter of practicality), to be the simplest or most efficient, (which are often the same thing), order of traversal of the data-structures underlying the implementation.

      As hash implementations differ, the ordering differs with implementation; whereas the natural ordering of integer indexes does not.

      QED.


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
        And given knowledge of algorithm (use the source), and the current bucket size, (see the second element of scalar %hash), the ordering is knowable; therefore definable; therefore defined by the implementation(s).

        Actually, you have overlooked the order of items on the linked list of a bucket that holds more than one entry.

        - tye        

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://767349]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (5)
As of 2024-03-29 08:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found