From -3986167530053810844
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f78e5,fbd36da46c3cc7a0
X-Google-Attributes: gidf78e5,public
From: "TiTi" <Tha.Main.Man@Fraggin.Bastard.Com>
Subject: Re: Discussion: type_info
Date: 1999/12/07
Message-ID: <82ifvb$nif$1@trex.antw.online.be>#1/1
X-Deja-AN: 557752796
Approved: Fergus Henderson <fjh@cs.mu.oz.au>
References: <81u646$kln$1@nnrp1.deja.com> <memo.19991201143603.18269G@btinternet.com> <82gmer$gqm$1@nnrp1.deja.com>
X-Original-Date: Tue, 7 Dec 1999 09:26:30 +0100
X-Priority: 3
X-Mimeole: Produced By Microsoft MimeOLE V5.00.2918.2701
X-Complaints-To: news@news.unimelb.edu.au
X-Trace: ariel.ucs.unimelb.edu.au 944583314 23480 128.250.37.153 (7 Dec 1999 16:15:14 GMT)
Organization: Won't tell ya
X-Auth: PGPMoose V1.1 PGP comp.std.c++ iQBFAgUAOE0ynOEDnX0m9pzZAQEjqgF7Bb3gDRVXLcq2iALR0CGMr//sehFX59XG ZoEhYwA2c2FhyjOcmEANZ3yR3FQtnZ+O =MLJH
X-Msmail-Priority: Normal
NNTP-Posting-Date: 7 Dec 1999 16:15:14 GMT
Newsgroups: comp.std.c++

> process.  During the design of type_info, name would have been the last
> choice for several reasons:
> 1.  In order to gaurantee unique name strings the string must become
> much larger than is reasonable to store.  The mangled names (and
> remember that name would be reasonable to return unmangled) for
> template types already cause warnings in one known compiler because it
> grew larger than 256 bytes.

This is (AFAIK) only in debug-mode for MSVC compilers. I doubt if the same
occurs for release mode.



> 2.  String hashing algorithms are expensive, especially as the length
> of the string grows (see 1 above).  Further, it's impossible to
> gaurantee a perfect hash, which is desirable if not required.



It is possible to construct hashkey algorithms for strings which are
calculated in constant time (e.g. only use N chars from M char string
(0<N<=M), hashsize is HS, I'm just trying something here:


    unsigned hashkey(const char* pChar, int size)
    {
        if(size<=0)
            return 0;
        unsigned index = 0, result = 0, to_where = MIN( N, size );
        for(int i = 0; i < to_where; i++)
        {
            result = ( (result << 5) + ( (unsigned) pChar[index] ) ) % HS;
            index = ( ( index << 5 ) + ( (unsigned) pChar[index] ) ) %
to_where;
        }
        return result;
    }


Anyway, I'm not telling that this is an ideal hash algorithm, but it's
calculated in constant time however.



> 3.  The "collation" ordering required by "before" neatly aligns itself
> with a method for providing a true hash with little expense.  In other
> words, a simple integer type can be used, which is incremented with
> each type added to the system.  This integer is a "perfect hash", as
> well as well suited for implementing the collation ordering.



Indeed, both for hash tables and for trees, this would come in handy.



> No, let's not use strings for hashing at all if we can, thank you very
> much.  I've given two compelling reasons for this:  memory requirements
> and the speed problems with string hashing functions.




Depends in what system you work on (speeds + memory), and what the algorithm
is you're working on(!). In some algorithms, you can't just store things in
a simple list, or you can wait for days to get some results (O(n^2) or
worse). And calculating a hash key can be done faster than traversing a
whole list to find the item (which still needs comparison!), especially if
we're talking about lots 'o' data.




TiTi
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]