View mode: basic / threaded / horizontal-split · Log in · Help
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
zwang wrote:
<snip>
> What do you want to prove by this example?
> The compiler does not care how you implement the opCmp operator at all.

Oops.  That code example was a red herring, as there were no hash 
collisions.  I reported this bug a while back

http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D.bugs/2643

and was sure I had discovered that the bug doesn't apply to classes. 
However, it seems that either

(a) I was imagining it
(b) it's just GDC 0.11
(c) there's been a regression somewhere.

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
In article <d7j4u7$bjs$2@digitaldaemon.com>, Walter says...
>
>
>"zwang" <nehzgnaw@gmail.com> wrote in message
>news:d7gp4d$ml7$1@digitaldaemon.com...
>> Walter wrote:
>> > To work in an AA, it needs to be sortable and hashable. How would
>interfaces
>> > be sorted?
>>
>> Why is sortability required for a hashed AA?
>
>To deal with the inevitable hash collisions.

All this requires is an equality check.  Sorting just allows for more optimal
worst-case performance (O(log N) vs. O(N)).


Sean
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
In article <d7khl9$1rh5$1@digitaldaemon.com>, Sean Kelly says...
>>>
>>> Why is sortability required for a hashed AA?
>>
>>To deal with the inevitable hash collisions.
>
>All this requires is an equality check.  Sorting just allows for more optimal
>worst-case performance (O(log N) vs. O(N)).
>
>Sean

Here is a proposal: If objects are unequal according to opEquals, then why can't
it just sort objects according to their memory location/pointer value, or some
other low-level value guaranteed to be different for different objects? This
should be much faster than calling opCmp, and it always works.

Nick
June 01, 2005
Re: Interfaces Suck [Plz read, Walter]
"Stewart Gordon" <smjg_1998@yahoo.com> wrote in message
news:d7juh4$1387$1@digitaldaemon.com...
> Walter wrote:
> > "zwang" <nehzgnaw@gmail.com> wrote in message
> > news:d7gp4d$ml7$1@digitaldaemon.com...
> >
> >> Walter wrote:
> >>
> >>> To work in an AA, it needs to be sortable and hashable. How would
> >>> interfaces be sorted?
> >>
> >> Why is sortability required for a hashed AA?
> >
> > To deal with the inevitable hash collisions.
>
> Doesn't follow:
>
> (a) Last time I checked the AA implementation worked perfectly well on
> classes (but not structs) where unequal objects can rank equally in order.

It'll appear to work if the hashes don't collide.

> (b) Java's HashMap manages perfectly well without this "required"
"feature".

You can resolve collisions by using a linear list. D's AA implementation
uses a binary tree to resolve collisions, which is much faster.
June 02, 2005
Re: Interfaces Suck [Plz read, Walter]
Walter wrote:
> "Stewart Gordon" <smjg_1998@yahoo.com> wrote in message
> news:d7juh4$1387$1@digitaldaemon.com...
<snip>
>> (a) Last time I checked the AA implementation worked perfectly well on
>> classes (but not structs) where unequal objects can rank equally in order.
> 
> It'll appear to work if the hashes don't collide.

At least I *thought* it worked - but see my reply to zwang.  But try 
this modification to the code example I posted that way:

----------
class UintBox {
    uint value;

    this(uint v) { value = v; }

    uint toHash() {
        writefln("toHash: %d", value);
        return 0;
    }

    int opEquals(Object o) {
        writefln("opEquals: %d", value);
        return value == (cast(UintBox) o).value;
    }

    int opCmp(Object o) {
        writefln("opCmp: %d", value);
        return 0;
    }
}
----------

(main function as before)

It calls opEquals during both assignment and lookup.  What does it use 
the result for?

How about using it to check that the match it's found really is a match, 
and if not then look further down the tree?

>> (b) Java's HashMap manages perfectly well without this "required" "feature".
> 
> You can resolve collisions by using a linear list. D's AA implementation
> uses a binary tree to resolve collisions, which is much faster.

You mean reimplement D's AAs to use a linear list instead?  Why not have 
this built in as well?  The answer seems to be because the presence of 
Object.opCmp makes it practically impossible to tell when you need to.

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on
the 'group where everyone may benefit.
Next ›   Last »
1 2 3
Top | Discussion index | About this forum | D home