Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Data structure challenge

by gjb (Vicar)
on Mar 17, 2004 at 18:11 UTC ( [id://337447]=note: print w/replies, xml ) Need Help??


in reply to Data structure challenge

Trouble is caused by initialisation, so what data structure to use that is initialized in constant time? The answer may be to use simple strings for A and B. The length should be U*log_10(U) so that each group of log_10(U) characters represents an "array element". Initialisation can be done using pack that should be constant time, array access can be simulated using substr which is also constant time.

Just my 2 cents, might be totally wrong, -gjb-

Replies are listed 'Best First'.
Re: Data structure challenge
by Abigail-II (Bishop) on Mar 17, 2004 at 20:58 UTC
    Initialisation can be done using pack that should be constant time
    Well, that would be interesting. I'm not a pack() wizard, and I can't see how I would do it with pack. What format would I use?

    Abigail

      Wouldn't a pack(a[U*log_10(U)], 'z') do the trick?

      Thanks Aristotle, I was too lazy/huried to check the correct syntax. The length of the string we want to allocate is N = U*ceil(log_10(U)), so I hoped pack(aN, '') would create a string of N '\0' characters using some low level memory allocation function. Unfortunately that doesn't seem to happen, the resulting string consists of N spaces, so there goes constant time... :(

      Just my 2 cents, -gjb-

        That isn't valid Perl. What exactly were you thinking of?

        I too though that if there's any way to achieve this, pack will be it, but there doesn't seem to be any pack format that would leave any part of the result string uninitialized.

        Makeshifts last the longest.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (5)
As of 2024-03-28 08:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found