1

I have a loop that generates all the possible combinations of bits by giving the number of bits desired, bu the issue is that I got out of memory when number of bits goes beyond 20, is there any optimizations that I can do, to solve this issue.

here my code :

function bitsGenerator($N)
{
    $listN = $N;
    $bits = ['0', '1'];

    //check if input is valid or not
    if (!is_int($listN)) {
        echo 'Input must be numeric!';
    }

    if ($listN >= 1 && $listN <= 65) {
        if ($listN == 1) {
            echo '1';
            exit;
        }

        for ($i = 1; $i <= ($listN - 1); $i++) {
            $reverseBits = array_reverse($bits);

            $prefixBit = preg_filter('/^/', '0', $bits);

            $prefixReverseBits = preg_filter('/^/', '1', $reverseBits);

            $bits = array_merge($prefixBit, $prefixReverseBits);

            unset($prefixBit, $prefixReverseBits, $reverseBits);
        }

        $finalBits = array_slice($bits, -$listN);

        foreach ($finalBits as $k => $v) {
            echo $v . "\n";
        }
    } else {
        echo 'Invalid input!';
    }
}

The purpose of this function is to get the last $N combinations and display them all other combinations are thrown away, I'm looking for some kind of optimization to my code so that the $bits array will not store more than 65 item because the maximum number to bits thus the maximum number of combination to display is 65.

Thanks to every one for helping me.

15
  • search memory_limit in you php.ini file and increase the value.
    – urfusion
    Nov 23, 2017 at 12:54
  • Add ini_set("memory_limit", "-1"); in the first line of your page... Nov 23, 2017 at 12:55
  • 1
    Best optimisation is not to build large arrays in memory; can't you just echo each result out as you build it rather than adding it to an array using array_merge()?
    – Mark Baker
    Nov 23, 2017 at 12:56
  • @MarkBaker I have to add them to an array in order to manipulate the results after it finishes Nov 23, 2017 at 12:59
  • Not necessarily so.... what are you doing with them once it's finished? Can you use a Generator instead of an array? Building large arrays in memory is never a good idea
    – Mark Baker
    Nov 23, 2017 at 13:04

1 Answer 1

0

The main problem is the size of the $bits array holding all your results. The array will contain 2^$N elements, each of $N length times 8 bits for each character (because you are using strings to have leading zeroes) so you'll end up with a memory consumption of approx (2^$N)*$N*8 which is 167772160 bytes. It won't get any smaller when using RAM.

Your working copies of $bits, preg_filter and array_merge will also consume a lot of RAM. Running your function with $N = 20 consumes 180375552 (172MiB).

BTW: unseting the variables will not reduce the consumed RAM because they would get overwritten in the next iteration anyway (or destroyed at the end of the function)

The following function was my first sketch based on your function and uses a bit less RAM: 171970560 bytes or 164MiB (vs 172MiB).

function myBitsGenerator($length)
{
    if (!is_int($length)) {
        die('Input must be numeric!');
    }

    if ($length < 1 || $length > 65) {
        die('Input must be between 1 and 65');
    }

    $bitsArray = ['0', '1'];
    $count = 2;

    if ($length > 1) {
        for ($i = 0; $i < $length; $i++) {
            for ($j = 0; $j < $count; $j++) {
                $bitsArray[] = $bitsArray[$j] . '1';
                $bitsArray[$j] = $bitsArray[$j] . '0';
            }
            $count += $j;
        }
    }

    $printArray = array_slice($bitsArray, $count - $length);

    array_walk(
        $printArray,
        function ($value) {
            echo $value . PHP_EOL;
        }
    );
}

However, the generation of those numbers is too complicated and should be simplified:

Theoretical: A binary number can be written in decimal and vice versa. The number of possible combinations of binary numbers with the fixed length of $N are x = 2 ^ $N. Each decimal number from 0 to x represents a binary number in the results.

Practical example: (binary) (0b101 === 5) (int)

All you have to do is to pad the calculated binary number with zeroes.

The simplified generator looks like:

    $n = pow(2, $length);
    for ($i = 0; $i < $iterations; $i++) {
        $binary = str_pad(decbin($i), $length, '0', STR_PAD_LEFT);
    }

You can use this generator to generate

If you really need to use even less RAM you should think about storing it in a file, which makes the whole think slower but it will use way less RAM.

function fileBitsGenerator($length)
{
    $handle = fopen('bits.txt', 'w+');

    $iterations = pow(2, $length);

    for ($i = 0; $i < $iterations; $i++) {
        fwrite($handle, str_pad(decbin($i), $length, '0', STR_PAD_LEFT) . PHP_EOL);
    }
}

This consumes just 2097152 bytes and scales! But be aware that the performance will depend on your HDD/SSD speed and it executes a lot of write operations (which might shorten your SSD life span). For example: the resulting file bits.txt is 92MB big if length = 22

1
  • BTW you can control offset and limit by manipulating $i (e.g. initialize it with $i = $iterations - $length to generate only the last $length entries
    – VerteXVaaR
    Nov 23, 2017 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.