How to handle very large arrays in php?

Question

I have this block of code.

$input = 4;
$list_N = array('0', '1');
for($n=1; $n<=$input; $n++) {

    if($n%2 == 0) {
        $c++;
    }

    $reverse_list_N = array_reverse($list_N);

    $A = array();
    $B = array();

    for($i=0; $i<count($list_N); $i++) {
        $A[] = '0' . $list_N[$i];
        $B[] = '1' . $reverse_list_N[$i];
    }

    $list_N = array_merge($A[], $B[]);

    if($n == 1) {
        $list_N = array('0', '1');
    }
}
$array_sliced = array_slice($list_N, -1*$input, $input);
for($i=0; $i<count($array_sliced); $i++) {
    $output = implode("\n", $array_sliced);
}
echo "<pre>"; print_r($output); echo "</pre>";

What this code does is, it generates following data (starting from (0,1)):

0,1
00, 01, 11, 10
000, 001, 011, 010, 110, 111, 101, 100
....... and so on

When $input = 4; the output is:

And as you can see, after every loop the the elements in the $list_N array doubles than the previous one. And with this pace if $input = 25; then the array would have 33554432 elements which is very huge. And that is the problem I couldn't find a solution of. When $input = 60 I get this error

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 36 bytes)

on this line

$list_N = array_merge($A, $B);

Even setting the memory limit to 2G did not solve it. So, how do I optimize my code in order to same the memory. Or, is there any other solution ?

Update: Following steps are used to generate the data.

$list_N is an array
$reverse_list is the reverse of $list_N
0 is appended in the beginning of every element in the $list_N array and stored in $A
1 is appended in the beginning of every element in the $reverse_list_N array and stored in $B
Array $A and array $B are merged and is stored in $list_N.
The main loop runs for $input number of times and the last $input number of elements are displayed from the final array.

What's the goal here? Why are you generating these values? There's probably a way to resolve this on an algorithmic level. — tadman
– tadman, Commented Apr 21, 2017 at 18:35
This is a question from a test that I failed. The goal is to generate the data I mentioned above and display the last $input elements. — Robbin Lama
– Robbin Lama, Commented Apr 21, 2017 at 18:39
Then maybe you should focus on generating just the elements you need, not all the theoretically possible elements. — tadman
– tadman, Commented Apr 21, 2017 at 18:41
Exactly, that's what I want to do and I don't know how. In order to get the new set of data you would still need the previous set of data. I'm sorry if i sound stupid. — Robbin Lama
– Robbin Lama, Commented Apr 21, 2017 at 18:44
so you mean you could just do echo decbin(pow(2, $input-1)) — Jonathan
– Jonathan, Commented Apr 21, 2017 at 18:47

Syakur Rahman · Accepted Answer · 2017-10-18 06:52:18Z

7

Solution:

Try using an SplFixedArray!

About:

A SplFixedArrayis

about 37% of a regular "array" of the same size

and

The SplFixedArray class provides the main functionalities of array. The advantage is that it allows a faster array implementation.

From: Documentation Page

Example:

$startMemory = memory_get_usage();
$array = new SplFixedArray(100000);
for ($i = 0; $i < 100000; ++$i) {
    $array[$i] = $i;
}
echo memory_get_usage() - $startMemory, ' bytes';

Further Reading:

Read more: http://nikic.github.io/2011/12/12/How-big-are-PHP-arrays-really-Hint-BIG.html

Messier Solution:

Another solution that could help, which I don't recommend is to override the default memory capacity. You can do this using this:

ini_set('memory_limit', '-1')

Further Reading:

http://php.net/memory_limit

edited Oct 18, 2017 at 6:52

Syakur Rahman

2,10232 silver badges41 bronze badges

answered Apr 21, 2017 at 19:01

Noah Cristino

7779 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Noah Cristino Over a year ago

@RobbinLama What were the outputs?

Robbin Lama Over a year ago

I still get the same insufficient memory size error.

Noah Cristino Over a year ago

@RobbinLama I think you should consider another language to do this in like C. Does this have to be done in php? If it fails with unlimited memory, then you probably need a server (or computer if it's localhost) with more memory.

Robbin Lama Over a year ago

I want the solution in php. Using high spec computer would be the last option. Isn't there any way around this ?

Noah Cristino Over a year ago

@RobbinLama Try using a service like this: secure.sabalcore.com/Free_Trial_Sabalcore_HPC_Cloud.htm They have a free trial with a high performance cloud pc

|

Subbu · Accepted Answer · 2017-12-06 06:36:31Z

@tadman was right. This requires a different approach. I ran the numbers, the array size at input 65 assuming just 1 byte per array element is 32 Exabytes (insane amount of memory required just to run this script).

Here is a working solution (make sure you enter the input to make the script run):

//we assume user will enter input as a valid positive integer > 1

fscanf(STDIN, "%d\n", $target);

$base=["0","1"];
$root=["0","1"];

$newArr=$base;
for($i=1;$i<7;$i++)//pre-initialize root array
  $newArr=genNextArray($newArr);

//echo "-----------\n";

//print_r($root);

//we're ready to display the output now based on the root array elements
displayNBits($target);

function displayNBits($target)
{
  global $root;
  $arr=array();

  for($i=0;$i<$target;$i++)
  {
    $elem=str_pad($root[$i],$target,"0",STR_PAD_LEFT);
    $elem[0]="1";
    $arr[]=$elem;

  }

  $arr=array_reverse($arr);

  for($i=0;$i<count($arr);$i++)
    echo $arr[$i]."\n";

  //print_r($arr);
}

function genNextArray($arr)
{
  global $root;

  $newArr= array(count($arr)*2);

  $ni=0;

  //0 prefix (left to right sweep)
  for($i=0;$i<count($arr);$i++)
  {
    $newArr[$ni]="0".$arr[$i];
    $ni++;
  }

  //1 prefix (right to left sweep)
  for($i=count($arr)-1;$i>=0;$i--)
  {
    $newArr[$ni]="1".$arr[$i];
    $root[]=$newArr[$ni];
    $ni++;
  }

  return $newArr;
}

Collectives™ on Stack Overflow

How to handle very large arrays in php?

2 Answers 2

7 Comments

Here is a working solution (make sure you enter the input to make the script run):

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Here is a working solution (make sure you enter the input to make the script run):

Comments

Your Answer

Sign up or log in

Post as a guest

Related