5
\$\begingroup\$

So I am trying to calculate the longest run of True's in a boolean sequence in Python. The sequence is very long (>10^10) and so it's not possible to generate it in reasonable time, let alone store it in memory. Instead, I generate the n-th item in the sequence. Is a more efficient algorithm in terms of speed possible, without multiprocessing or statistical analysis of the sequence? Abstracting away the details of the generator, the code looks like this:

run = 1
record = 1
i = 0
while i < sequence_length:
    if nth_place(i): 
        for j in range(i-1, -1, -1):
            if nth_place(j): run += 1
            else: break

        for j in range(i+1, sequence_lengh):
            if nth_place(i): run += 1
            else:
                if run > record: record = run
                run = 1
                i = j
                break

    i += (record + 1)

Description: Instead of checking every position, the algorithm makes jumps of size of current record+1. If the result is False then it jumps again and repeats - this ensures that the longest run that could be missed has at most the length of current record. If the result is True, then it starts counting backwards until it reaches a False. Then it picks up from (i+1)-th place and continues counting forwards until it reaches a False. If the counted run is longer than the current record, the record gets updated. i gets updated too, and the algorithm repeats, now jumpring from the current position.


Full description as follows:
I am trying to calculate the longest possible run of pairs of numbers of format (6n+1,6n-1) between pairs of twin primes, that are created by the first m primes.
For this, I have a list of m primes that are greater than 3 and for each prime in the list there is associated boolean sequence of according length, with False everywhere except at positions p//3 and p-(p//3)-1. For example, given a list [5,7], the list of associated sequences is [[0,1,0,1,0],[0,0,1,0,1,0,0]].
The long sequence that the question is about is then generated by cyclically iterating the sequences and storing the logical disjunction. For example:

01010010100101001010010100101001010
00101000010100001010000101000010100
-----------------------------------
01111010110101001010010101101011110

Generating the sequence is fine for small lists of primes, but as the number of primes increases, the sequence grows with primorial time complexity, which is worse than factorial. Therefore I can't generate the whole sequence, but only get the n-th term. The full program is here:
(the function in question is count_ones)

import math

def is_prime(n): #checks whether a given number is prime
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False

    sqr = int(math.sqrt(n)) + 1

    for divisor in range(3, sqr, 2):
        if n % divisor == 0: return False
    return True

def next_prime(current_prime): #returns the next prime
    if current_prime == 2: return 3

    counter = current_prime + 2
    while 1:
        if is_prime(counter): return counter
        counter += 2

def get_pattern(n): #generates a pattern of a prime
    lis = [False for x in range(n)]
    lis[n//3] = True
    lis[n-(n//3)-1] = True
    return lis

def list_product(lis): #computes the product of a list of numbers
    product = 1
    for i in range(len(lis)): product *= lis[i]
    return product

def nth_place(patterns,primes,n):
    for a,b in zip(patterns, primes):
        if a[n%b]: return True
    else:
        return False

def count_ones(patterns,primes):
    if primes[-1] == 5: return 1 #skip trivial case with a single prime 5

    for i in patterns: i = dict(enumerate(i)) 
    primes = tuple(primes) 
    patterns = tuple(patterns) 

    run = 1
    record = 1
    #since the sequence is symmetrical, we'll need only half of it
    sequence_length = list_product(primes)//2 + 1 
    i = 0

    while i < sequence_length:
        if nth_place(patterns, primes, i): 
            for j in range(i-1, -1, -1):
                if nth_place(patterns, primes, j): run += 1
                else: break

            for j in range(i+1, sequence_length):
                if nth_place(patterns, primes, j): run += 1
                else:
                    if run > record: record = run
                    run = 1
                    i = j
                    break

        i += (record + 1)

    return record


def main():
    number_of_primes = 6 #change this value
    prime = 3
    primes = []
    patterns = []

    for i in range(number_of_primes):
        prime = next_prime(prime)
        primes.append(prime)
        patterns.append(get_pattern(prime))

    record = count_ones(patterns,primes)
    print('{} - {}'.format(primes,record))

main()

A minor and obvious improvement that I missed in the main loop of count_ones function: allocate a separate variable to hold the value of record+1 and recalculate it only when the current record itself changes, instead of every iteration of the loop.

\$\endgroup\$
  • 1
    \$\begingroup\$ It would help if you could add the implementation of nth_place. This way, your code could actually be run by the reviewers and they can check themselves if the alternatives they propose are actually better. \$\endgroup\$ – Graipher Jun 27 '17 at 11:58
  • \$\begingroup\$ @Graipher this is actually a bit tricky to explain without context. I tried to explain how the whole program works. \$\endgroup\$ – ZyTelevan Jun 27 '17 at 16:51
  • \$\begingroup\$ sequence_lengh in snippet isn't quite correct. I have difficulties recognising said snippet in The full program: could you factor out the predicate (nth_place())? \$\endgroup\$ – greybeard Jan 10 '18 at 10:29
  • \$\begingroup\$ @greybeard sorry for causing confusion, I edited the full program to be more analogous to the snippet. \$\endgroup\$ – ZyTelevan Jan 10 '18 at 17:21
1
\$\begingroup\$

Checking from the end of a promising index range intending to leap as far ahead as possible, thereby reducing the number of checks, is the way to go.
There is nothing special about the indexes you start to check from:
Why start checking upwards without knowing there's a new record?

Work in progress: not named, not documented, not tested

target = 1
''' record if met '''
good = 0
''' number of good indices seen '''
bad = -1
''' known bad index '''
while bad < length - target:
    goal = bad + target  # if predicate(bad+1 .. goal): new record
    for check in range(goal, bad + good, -1):  # exclude known good
        if not predicate(check):
            good = goal - check  # may be lower than before
            bad = check
            break
    else:  # new record!
        for goal in range(goal + 1, length):
            if not predicate(goal):
                good = 0
                break
        target = goal - bad
        bad = goal  # not really if above for-loop terminated normally
record = target - 1

(Where record lengths are more likely at the end of a sequence, reverse before or invert range()s & such.)

\$\endgroup\$
  • 1
    \$\begingroup\$ (What to call ugly?) \$\endgroup\$ – greybeard Jan 10 '18 at 10:27
  • \$\begingroup\$ (Going to remain unfinished for lack of zeal.) \$\endgroup\$ – greybeard Aug 2 '18 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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