 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> Darren New <dne### [at] san rrcom> wrote:
>> You're saying "a hastable is for lookups. It doesn't have an order.
>> Therefore, Python is right to base its data structures on hash tables."
>
> It's supposed to be a hashtable.
What is "supposed" to be a hashtable? And why do you say it's "supposed" to
be a hashtable?
> If you don't want a hashtable, you shouldn't use it.
Of course not. Because it *is* a hashtable, whether that's what you want or
not.
>> Well, there ya go. So why isn't that built in, like it is in PHP, since it
>> allows both random and sequential lookups? :-)
>
> Because Python, Scheme and Haskell attempt to use the correct approaches. Form
> follows function.
And what is incorrect about PHP's approach? Why is Python more "correct"
than PHP? (Note: "because it uses hashtables" is a circular argument.)
>> So, it's OK for a mathematical set to maintain order when it's simpler,
>
> A math set has no order. I was saying the notation of functions over set
> domains employs the convention of lists of arguments because it's simpler to
> notate than named arguments out of order.
I understand that. You're missing my point. You're arguing that keyed data
structures in a programming language should not preserve insertion order.
I'm asking you why that is the case, and you're answering "Because!"
I'm just trying to figure out why you think a structure with a superset of
the functionality that a hashtable provides is a bad thing.
> and that ought to be a good thing.
Why? Do you actually *have* a reason beyond "because"? Or is this a
faith-based argument?
If you need a hashtable, PHP's arrays give that to you. If you need a list,
PHP's arrays give that to you. If you need order-preserving keyed-access
data structures, PHP's arrays gives that to you, and Python doesn't. If you
need order-preserving keyed-access data structures in Python, you have to
implement it yourself. I'd say that's a bad thing, for all the same reasons
that having non-standardized implementations of any application-independent
data structures in any language is a bad thing.
--
Darren New, San Diego CA, USA (PST)
There's no CD like OCD, there's no CD I knoooow!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> Ahh, yeah, that's exactly the sort of use case I was looking for.
It took me a bit of thinking. That, and getting rows back from a SQL server
indexed by primary key but sorted by something else, for example.
> Good to know. Thanks!
It looks like it just keeps the order even for integer indecies:
$pdq[10] = "Ten";
$pdq[20] = "Twenty";
$pdq[15] = "Fifteen";
$pdq[12] = "Twelve";
print_r($pdq);
Array
(
[10] => Ten
[20] => Twenty
[15] => Fifteen
[12] => Twelve
)
Weird, but understandable. It looks like a list of pairs. :-)
--
Darren New, San Diego CA, USA (PST)
There's no CD like OCD, there's no CD I knoooow!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Just to throw in two cents of mine:
Darren New <dne### [at] sanrrcom> wrote:
> I'm just trying to figure out why you think a structure with a superset of
> the functionality that a hashtable provides is a bad thing.
I think there's nothing wrong about it - if that structure also provides the
same performance as a true hashtable (which, as a quick guess, it probably
doesn't). Or if performance is not an issue.
Added features typically come with added execution time. So added features you
don't need for a certain job typically come with wasted execution time.
As stated before: No problem if you have enough time to waste.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> outweighed it's somewhat higher inefficiency,
Actually, thinking on it, it doesn't need to be noticeably less efficient.
You can just implement it as a regular hashtable except have a head and tail
pointer in the top-level structure, and a couple of pointers in each entry.
Adding a new index also links it to the tail of the linked list, deleting an
entry takes it out of the linked list and the hashtable, etc. So there
doesn't seem to be more than a handful of machine instructions on an insert
or delete to maintain this extra information, and it's certainly not wasting
a lot of space compared to keeping a hashtable sufficiently below full that
you avoid too many collisions.
--
Darren New, San Diego CA, USA (PST)
There's no CD like OCD, there's no CD I knoooow!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> I think there's nothing wrong about it
That's why I was confused. You were characterizing it as "incorrect" and
"not a good thing", rather than "inefficient", and talking about
mathematical constructs rather than computational elements.
> if that structure also provides the
> same performance as a true hashtable (which, as a quick guess, it probably
> doesn't). Or if performance is not an issue.
I think if you're using Python or PHP, you're not too worried about the
performance issues. If you're using PHP and your program runs more than five
seconds CPU time, you're probably doing something wrong and ought to be
using a different language anyway.
> Added features typically come with added execution time. So added features you
> don't need for a certain job typically come with wasted execution time.
It adds a handful of instructions to inserts and deletes, and no overhead to
lookups, and probably *saves* time iterating over the array.
In other words, it's all O(1) with a constant on the order of a dozen
machine instructions amortized (not counting hashing the key), regardless of
whether you preserve order or not.
5 million integer key array inserts in PHP: 3.3 seconds
5 million dict inserts in Python: 2.3 seconds
5 million list appends in Python: 1.9 seconds
5 million integer key inserts then lookups in PHP: 4.2 seconds
5 million dict inserts and then lookups in python: 4.3 seconds
5 million list element appends then lookups in Python: 3.4 seconds
5 million inserts and iterate-over-values in PHP: 9.5 seconds
5 million inserts and iterate-over-values in python: 133 seconds
(Each is 5 cycles of a million entries each, lest we run out of RAM
in the VM. :-)
I guess it depends what you want to do. If you often iterate over the
values, clearly you should go with PHP. If you often work with more than
five million entries in one PHP page, you're probably doing something wrong.
> As stated before: No problem if you have enough time to waste.
Given the languages are interpreted to start with, if four machine
instructions per insert into your dictionary is breaking the bank, you
probably shouldn't be using hashtables to start with. You should be using
interned strings and modulus operators on the addresses.
If you want to use PHP or Python and have trouble with how slow the built-in
data structures are, chances are you should be using PHP anyway.
--
Darren New, San Diego CA, USA (PST)
There's no CD like OCD, there's no CD I knoooow!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> clipka wrote:
>> I think there's nothing wrong about it
>
> That's why I was confused. You were characterizing it as "incorrect" and
No he (clipka) wasn't. nemesis was :)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> Thinking back, didn't objective-C use named parameters only for calling
> object methods? Did the order matter there? I can't really remember.
Order matters, because method:param1:param2 is the function signature.
method:param2:param1 would be a different function.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> Interesting. So, to make sure I understand correctly if dicts in python
> were to operate like this then:
>
> D = dict()
> d["a"] = "foo"
> d["b"] = "bar"
> d["c"] = "baz"
>
> would give me {"a":"foo", "b":"bar", "c":"baz"} where the order matters
> so D[1] gives "bar"?
No, because key 1 isn't set to any value. However, if you iterate over the
array, you'll get items a, b, c, in that order.
> If so, then what happens in the following case:
>
> D = dict()
> d[3] = "foo"
> d[2] = "bar"
> d[1] = "baz"
Then d[3] is "foo", but if you iterate, it will be the first item to show
up.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> It looks like it just keeps the order even for integer indecies:
>
> $pdq[10] = "Ten";
> $pdq[20] = "Twenty";
> $pdq[15] = "Fifteen";
> $pdq[12] = "Twelve";
> print_r($pdq);
>
> Array
> (
> [10] => Ten
> [20] => Twenty
> [15] => Fifteen
> [12] => Twelve
> )
>
> Weird, but understandable. It looks like a list of pairs. :-)
A list of pairs; exactly.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez wrote:
> Darren New wrote:
>> clipka wrote:
>>> I think there's nothing wrong about it
>> That's why I was confused. You were characterizing it as "incorrect" and
>
> No he (clipka) wasn't. nemesis was :)
My bad.
--
Darren New, San Diego CA, USA (PST)
There's no CD like OCD, there's no CD I knoooow!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
