PHP algorithm big arrays issue with memory

Question

I am working on some algorithm in PHP dealing with binary values or strings containing 0s and 1s. I am calculating the list for n-numbers, from starting list 0f {0,1} for n=1; Anyway, arrays a[] and b[] are becoming big after for n > 20, reaching memory issue. So my question is how this algorithm can be optimized to use less memory? Should i store binary strings in a different format in memory except string format or do I need to restructure the algorithm itself? Any idea?

while ($n < 1 || $n > 65)
 fscanf(STDIN, "%d\n", $n);

$listn = array("0","1");
$doublearray[] = $listn;

for ($i=1; $i<$n;$i++) {
  foreach ($listn as $member) {
    $a[] = "0" . $member;
  }

  $reflectedlistn = array_reverse($listn);

  foreach ($reflectedlistn as $member) {
    $b[] = "1" . $member;
  }

  $listn = array_merge($a, $b);
  $doublearray[] = $listn;
  $a = array();
  $b = array();

}

$arr = array_slice($doublearray[$n-1], -$n);
echo "\n";
foreach ($arr as $item) {
    echo $item . "\n";
}

You've shown the algorithm, but not the task you've tried to solve. While there are obvious areas of improvement (using plain numbers instead of 0-and-1-filled arrays, converting them into binaries when necessary), it's not clear what are you really trying to do here. — raina77ow
– raina77ow, Commented Sep 29, 2015 at 19:29
I am just interested how can i store binaries instead of strings in a more optimized way — Vikast
– Vikast, Commented Sep 29, 2015 at 19:36
With bindec, you can convert any string of 0 and 1 into a plain number. Watch for platform limitations, though. — raina77ow
– raina77ow, Commented Sep 29, 2015 at 19:39

sectus · Accepted Answer · 2015-10-27 10:41:52Z

You could optimize your algorithm by storing numbers.

while ($n < 1 || $n > 65)
 fscanf(STDIN, "%d\n", $n);

$listn = array(0, 1); // use numbers
$doublearray[] = $listn;

for ($i = 1; $i < $n; $i++) {
    foreach ($listn as $member) {
        $a[] = 0 + $member; //actually do nothing
    }

    $reflectedlistn = array_reverse($listn);

    foreach ($reflectedlistn as $member) {
        $b[] = (1 << $i) + $member; // add 1 to the begining
    }

    $listn = array_merge($a, $b);
    $doublearray[] = $listn;
    $a = array();
    $b = array();
}
$arr = array_slice($doublearray[$n - 1], -$n);
echo "\n";
foreach ($arr as $item) {
    echo decbin($item) . "\n"; // convert dec into bin string representation
}

It saves near 15% of memory.

Then remove useless array $a.

$listn = array(0, 1); // use numbers
$doublearray[] = $listn;

for ($i = 1; $i < $n; $i++) {
    $reflectedlistn = array_reverse($listn);

    foreach ($reflectedlistn as $member) {
        $b[] = (1 << $i) + $member; // add 1 to the begining
    }

    $listn = array_merge($listn, $b);
    $doublearray[] = $listn;
    $a = array();
    $b = array();
}
$arr = array_slice($doublearray[$n - 1], -$n);
echo "\n";
foreach ($arr as $item) {
    echo decbin($item) . "\n"; // convert dec into bin string representation
}

more 20% of memory.

But it won't help, because this algorithm creates arrays with 2^n elements. And arrays are Very Huge in PHP.

So, is there any point to optimize it? Or better create new one? Please, describe what are you want to achieve to get better solution.

Collectives™ on Stack Overflow

PHP algorithm big arrays issue with memory

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related