in reply to Re: Array or Hash
in thread Array or Hash

Are you sure about that? Unlike C, perl can do sparse arrays without using lots of memory for the empty slots, so you can write:

my @test = ();
$test[ 0 ] = 'first';
$test[ 10_000_000 ] = 'last';

[download]

If the array index was used to directly calculate the RAM location of the data, then perl would have to allocate lots of it for the table. The fact that the code above works suggests that perl keeps a lookup table somewhere of valid values. That lookup table will be similar to the one needed for a hash, and potentially no faster.

Replies are listed 'Best First'.
Re^3: Array or Hash
by BrowserUk (Patriarch) on Jan 21, 2011 at 09:47 UTC
    Are you sure about that?

    Yes. I am very sure.

    Unlike C, perl can do sparse arrays without using lots of memory for the empty slots,

    No. It cannot.

    The second assignment in your example (on a 64-bit system) results is the allocation of 134 megabytes of ram:

    $a[0]=1; print total_size( \@a );;
232

$a[1]=1; print total_size( \@a );;
256

$a[2]=1; print total_size( \@a );;
280

$a[10_000_000]=1; print total_size( \@a );;
134217984

    [download]

    To gain a better appreciation for how Perl uses memory, see PerlGuts Illustrated and scan down to the AV heading.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]

      Thanks ikegami and BrowserUk I stand corrected.

      I am surprised that perl is inefficient with sparse arrays. I guess that if I need to create one, I should in future use a hash with numbers as the keys.

[reply]
        I am surprised that perl is inefficient with sparse arrays.

        It's more than a little inaccurate to say that, given that Perl doesn't even attempt to implement sparse arrays.

        You might just as well say that Perl is inefficient at implementing birth control or nuclear fusion :)

        I guess that if I need to create one, I should in future use a hash with numbers as the keys.

        Indeed. If your "array" is likely to be less that 45% full, using a hash with numeric keys will save you memory at the cost of a little speed.

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

      Can you provide the code of the "total_size" sub?

      As it looks interesting.

[reply]

        See Devel::Size

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
Re^3: Array or Hash
by ikegami (Patriarch) on Jan 21, 2011 at 09:46 UTC

    That's not a sparse array. It has 10,000,001 allocated slots, all of which are in use.

    You make "keeping track of valid values" sound very complicated but it's just 3 numbers. 

    >perl -MDevel::Peek -e"$a[6]=1; $a[7]=1; shift(@a); Dump(\@a,1)"
SV = IV(0x1acf60) at 0x1acf68
  REFCNT = 1
  FLAGS = (TEMP,ROK)
  RV = 0x336af0
  SV = PVAV(0x1adc30) at 0x336af0
    REFCNT = 2
    FLAGS = ()
    ARRAY = 0x330590 (offset=1)    -- Address of first element
    ALLOC = 0x330588
    FILL = 6                       -- Index of last element
    MAX = 12                       -- Index of last allocated element
    ARYLEN = 0x0
    FLAGS = (REAL)

    [download]

    The array has 7 elements and 14 allocated elements (-1..12 relative to ARRAY).

    Update: Replaced description with an example.

[reply]
[d/l]

In Section Seekers of Perl Wisdom