Re: STL map or hash map using struct as data and find it

On Dec 31, 1:51 pm, kl <kjell.ll...@gmail.com> wrote:


    [...]


But how often are you doing a look-up. Still, 80000 lines is
probably enough to want to use something more efficient than a
linear search.

    [...]

Which is? The format of the IPCOUNTRY struct will vary
enormously between compilers, even on the same platform, and can
change from one release of the compiler to the next, or even
with different compiler options. When you say that the format
is basically the same as that of the IPCOUNTRY struct, you're
basically saying that you don't know the format, and that you
don't care, because you're not going to ever reread the data at
a later date, when the program may have been recompiled with a
more recent version of the compiler, or with different options.


As long as you ensure that both this separate program and your
application are compiled with the same version of the compiler,
using the same options. It still sounds error prone to me (but
I can imagine cases where it is justified).


Do you know of many programs that don't parse a couple of
thousand lines on start up?

I guess it depends on the context. I work on large scale
servers. They're started at most once a day---most of the
projects I've worked on are started once every three or four
years, or more. Whether the start up lasts 1 second, or 5 or
even 30, isn't a big deal.

Still, if you have to parse it, you have to parse it. Doing so
in a separate process is going to take (slightly) more time than
doing so in your own process. What might be useful is if you
only have to update the data (from the CVS file) once a week or
less, but you restart the individual application a lot. In that
case, I might use a memory dump with a header containing the
last update (from the CVS file) date and a checksum based on the
compiler/compiler options. (For the latter, on a Unix system,
I'd simply use the output of /dev/random to initialize an array
of about 16 bytes, regenerating the data each time I relinked.
So anytime I install a newly relinked version of the program, it
will go to the CVS data the first time.) And I'd still put the
parser for the CVS data in the same binary image, with something
like:

    if ( binaryDumpPresent() && binaryDumpOKToUse() ) {
        initializeFromBinaryDump() ;
    } else {
        initializeFromCVSFile() ;
        createBinaryDumpFromData() ;
    }

In this case, of course:

 -- The actual data elements should be POD's, with only basic
    types (integral types, perhaps floating point types as well,
    although there's no need here, but no classes or pointers).

 -- If you're using a sorted vector, you can do this with a
    single read/write, no need to read or write each element
    separately. (In fact, I'd use two reads/writes: one for the
    header, and one for the rest of the data.)

Depending on portability constraints, I might even use mmap (or
its equivalent under Windows); I've done this once (with a file
that took something like five minutes to parse on my old Sun
Sparc, resulted in a memory image of something like 10-15
Megabytes, and in which in 90% of the runs, I never accessed
beyond the first 128 entries---out of more than a
million---anyway).

Although formally not guaranteed... If you define the header
something like:

    struct IpCountryMapHeader
    {
        unsigned char magic[ 16 ] ;
        time_t saved ;
        size_t entryCount ;
    } ;

and each element as:

    struct IpCountryMapEntry
    {
        uint32_t start ;
        uint32_t end ;
        char countryName[ maxCountr=

    } ;

will doubtlessly work. (In theory, you could run afoul of
alignment considerations if both size_t and time_t are smaller
than uint32_t. In practice, if size_t is less than 32 bits,
your table won't fit into memory, and time_t will never be less
than 32 bits anyway.)

Under Unix, a simple script like:

    (
        echo 'unsigned char referenceMagic[] = {' ;
        od -tx1 -N 16 /dev/random |
            tr '[:lower:]' '[:upper:]' |
            sed -e '2,$d'
                -e 's:^[0-9A-Z]* ::'
                -e 's:[0-9A-F][0-9A-F]:0x&,:g' ;
        echo '} ;'
    ) > referenceMagic.cc

in your makefile can be used to regenerate the magic every time
you relink; under Windows, you may have to write a simple C/C++
program to do something similar, using some sort of hash value
of the machines IP address, your current process id (a hex dump
of the HANDLE?), the current time, etc., to seed a quality
random generator, and output from it. (I use scripts like this
all the time in my makefiles, but in this case, if the OS
doesn't support /dev/random, or something similar, the script
won't work, even if you have a full Unix tool kit installed.)

(Also, FWIW: most of the tools which generate your CSV file will
generate closed intervals. I'd convert this to the classical
Unix half open interval when I read the file, and use that from
then on.)

Note too that std::lower_bound will work fine on a C style
array, either loaded with ifstream::read() (on a file opened in
binary mode) or mmapped. Just call it with startAddress,
startAddress + header.entryCount as the first two arguments.

--
James Kanze (GABI Software) email:james.ka...@gmai=

Conseils en informatique orient=E9e objet/
                   Beratung in objektorientierter Date=

9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34- D=

- Visa citerad text -