Calculate a large amount without running out of memory

Question

I think this will be a pretty hard or even impossible question. I have some code here that is build around my scenario describet here.

I took that python code and translated it into lua code but then I spottet an error I made.

If the code is used for a list of ~10 weigths it will work fine but in my case I have lists with up to 60 weights. the code generates an array with all possible bitstrings of length n. and with n = 60 this array would be 2^60 large and that is way to much.

Is there any way to calculate this without generation such a large array? My final code will be in lua but if you know a solution in any other language it will be fine to, I can still translate it later.

python code:

from math import prod
def bitstrings(n) :
    """Return all possible bitstrings of length n"""
    if n == 0 :
        yield []
        return
    else :
        for b in [0,1] :
            for x in bitstrings(n-1) :
                yield [b] + x


def prob_selected(weights, num_selected = 5) :

    # P(n generated, including e)*P(e of n selected | n generated including e)
    # i.e. Sum_n (n generated, including e) * #num_selections / #generated
    # num_selected = how many will be drawn out of the hat (at most)

    n = len(weights)
    final_probability = [0] * n
    
    for bits in bitstrings(n) :
        num_generated = sum(bits)
        prob_generated = prod([w if b else (1-w) for (w,b) in zip(weights, bits)])
        
        for i in range(n) :
            if bits[i] :
                final_probability[i] += prob_generated * min(num_selected, num_generated) / num_generated
    return final_probability


print(prob_selected([1, 1, 1, 1, 1,
                     0.5, 0.2, 0.8, 0.9, 0.1]))

lua code:

-- python sum()
table.reduce = function (list, fn) 
    local acc
    for k, v in ipairs(list) do
        if 1 == k then
            acc = v
        else
            acc = fn(acc, v)
        end 
    end 
    return acc 
end

local function generateBitstrings (global_arr, n, arr, i)
    if i == n then
        table.insert(global_arr, {table.unpack(arr)})
        return
    end
    
    arr[i] = 0
    generateBitstrings(global_arr, n, arr, i + 1)
    
    arr[i] = 1
    generateBitstrings(global_arr, n, arr, i + 1)
end

local function prob_selected (weights, num_selected)
    local n = #weights
    local final_probability = {}
    
    for i=1, n do
        final_probability[i] = 0
    end
    
    local globalArr = {}
    generateBitstrings(globalArr, n + 1, {}, 1)
    for ibots, bits in ipairs(globalArr) do 
        local num_generated = table.reduce(
            bits,
            function(a, b)
                return a + b
            end
        )

        local prob_generated = 1
        local bitsLength = #bits
        for i=1,bitsLength do
            if bits[i] == 1 then
                prob_generated = prob_generated * weights[i]
            else
                prob_generated = prob_generated * (1 - weights[i])
            end
        end
        
        for i=1,n do
            if bits[i] == 1 then
                final_probability[i] = final_probability[i] + (prob_generated * math.min(num_selected, num_generated) / num_generated)
            end
        end
    end
    return final_probability
end

print (table.concat (prob_selected({1, 1, 1, 1, 1,0.5, 0.2, 0.8, 0.9, 0.1}, 5), ', '))

user_6632736 · Answer

The below code will save you from running out of memory, though not from anything else. It uses a recursively called iterator, implemented as a coroutine, to generate all possible binary arrays (UPD: I also made the same iterator return the number of non-zero array items):

local function bitStrings (size)
    return coroutine.wrap (function ()
        if size == 0 then
            coroutine.yield ({}, 0)
        else
            for bit_string, bits in bitStrings (size - 1) do
                bit_string [size] = 0
                coroutine.yield (bit_string, bits)
                bit_string [size] = 1
                coroutine.yield (bit_string, bits + 1)
            end
        end
    end)
end         
    
local start = os.clock()
local function prob_selected (weights, num_selected)
    local format, min, clock, print = string.format, math.min, os.clock, print
    
    local n = #weights
    local final_probability = {}
    local counter = 0
    local total = 2 ^ n
    local total_s = format ('%d', total)
    for bits, num_generated in bitStrings (n) do
        counter = counter + 1
        local percent = counter / total
        local now = clock()
        local left = (now - start) / percent * (1 - percent)
        print (format ('%d', counter) .. ' / ' .. total_s .. '(' .. format ('%.0f', percent * 100) .. ' %), ' .. format ('%.1f minutes', left / 60) .. ' left')
        local ratio = min (num_selected, num_generated) / num_generated

        local prob_generated = 1
        for i = 1, n do
            if bits[i] == 1 then
                prob_generated = prob_generated * weights[i]
            else
                prob_generated = prob_generated * (1 - weights[i])
            end
        end
        
        for i = 1, n do
            if bits[i] == 1 then
                final_probability[i] = (final_probability[i] or 0) + (prob_generated * ratio)
            end
        end
    end
    return final_probability
end

-- Test:
local size = 20
local probabilities = {}
for i = 1, size do
    probabilities [i] = math.random ()
end
local selection = 5
print ('Size', size, 'selection', selection)
print ('Probabilities', table.concat (probabilities, ', '))
print ('Probabilities to be selected into ' .. tostring (selection), table.concat (prob_selected(probabilities, selection), ', '))
print (string.format ('%.1f seconds', os.clock() - start))

Below is a variant, for Lua 5.3 with bitmaps represented by integers, but it is not any faster, and I am not sure it is reliable:

local function countBits (i)
    local counter = 0
    local shifted = i
    while (shifted ~= 0) do
        counter = counter + (shifted & 1)
        shifted = shifted >> 1
    end
    return counter
end

local function checkBit (bits, n)
    return (bits >> (n - 1)) & 1
end

local start = os.clock()
local function prob_selected (weights, num_selected)
    local format, min, clock, print = string.format, math.min, os.clock, print

    local n = #weights
    local final_probability = {}
    local counter = 0
    local total = 2 ^ n
    local total_s = string.format ('%d', total)
    for bits = 0, total - 1 do
        counter = counter + 1
        local percent = counter / total
        local now = clock()
        local left = (now - start) / percent * (1 - percent)
        print (format ('%d', counter) .. ' / ' .. total_s .. '(' .. format ('%.0f', percent * 100) .. ' %), ' .. format ('%.1f minutes', left / 60) .. ' left')
        local num_generated = countBits (bits)
        local ratio = min (num_selected, num_generated) / num_generated     
        local prob_generated = 1
        for i = 1, n do     
            if checkBit (bits, i) == 1 then
                prob_generated = prob_generated * weights[i]
            else
                prob_generated = prob_generated * (1 - weights[i])
            end
        end
        
        for i = 1, n do
            if checkBit (bits, i) == 1 then
                final_probability[i] = (final_probability[i] or 0) + (prob_generated * ratio)
            end
        end
    end
    return final_probability
end

-- Test:
local size = 25
local probabilities = {}
for i = 1, size do
    probabilities [i] = math.random ()
end
local selection = 5
print ('Size', size, 'selection', selection)
print ('Probabilities', table.concat (probabilities, ', '))
print ('Probabilities to be selected into ' .. tostring (selection), table.concat (prob_selected(probabilities, selection), ', '))
print (string.format ('%.1f seconds', os.clock() - start))

And this is a combination of the above two approaches, faster than either:

local function bitMaps (size)
    return coroutine.wrap (function ()
        if size == 1 then
            coroutine.yield (0, 0)
        else
            for bit_string, bits in bitMaps (size - 1) do
                bit_string = bit_string << 1
                coroutine.yield (bit_string, bits)
                coroutine.yield (bit_string | 1, bits + 1)
            end
        end
    end)
end     

local function checkBit (bits, n)
    return (bits >> (n - 1)) & 1
end

local start = os.clock()
local function prob_selected (weights, num_selected)
    local format, min, clock, print = string.format, math.min, os.clock, print

    local n = #weights
    local final_probability = {}
    local counter = 0
    local total = 2 ^ n
    local total_s = string.format ('%d', total)
    for bits, num_generated in bitMaps (n) do
        counter = counter + 1
        local percent = counter / total
        local now = clock()
        local left = (now - start) / percent * (1 - percent)
        print (format ('%d', counter) .. ' / ' .. total_s .. '(' .. format ('%.0f', percent * 100) .. ' %), ' .. format ('%.1f minutes', left / 60) .. ' left')
        local ratio = min (num_selected, num_generated) / num_generated     
        local prob_generated = 1
        for i = 1, n do     
            if checkBit (bits, i) == 1 then
                prob_generated = prob_generated * weights[i]
            else
                prob_generated = prob_generated * (1 - weights[i])
            end
        end
        
        for i = 1, n do
            if checkBit (bits, i) == 1 then
                final_probability[i] = (final_probability[i] or 0) + (prob_generated * ratio)
            end
        end
    end
    return final_probability
end

-- Test:
local size = 25
local probabilities = {}
for i = 1, size do
    probabilities [i] = math.random ()
end
local selection = 5
print ('Size', size, 'selection', selection)
print ('Probabilities', table.concat (probabilities, ', '))
print ('Probabilities to be selected into ' .. tostring (selection), table.concat (prob_selected(probabilities, selection), ', '))
print (string.format ('%.1f seconds', os.clock() - start))

Calculate a large amount without running out of memory

1 Answers