Why does an NFA that accepts/rejects bit strings implemented with a Recursive Backtracking algorithm outperform one that is written using a Parallel Bitmap search?

set up two tests for these algorithms, to evaluate on both different length strings, and different numbers of inputs:

  • First, I created sets of 1,000 random bit strings of length n, where my sets were n = [4, 8, 16, 32, 64].

  • Second, I tested these on input.txt files with varying amounts of strings. In all cases, bit strings were length 10 with files of varying amounts of strings( 10^n strings with n = [1:6]).

  • I timed each of these tests using the Python .time module.

I expected Parallel Bitmap Search to run faster, but the Recursive method was more efficient.

Below is the code for the bit-mapped parallel search method:

 The current set of states, encoded bitwise: 
 state i is represented by the bit 1<<i.
stateSet = 0

 Reset the current state set to {the start state}.
def reset():
    global stateSet
    stateSet = 1<<0

 The transition function represented as an array.
 The set of next states from a given state s and 
 character c is at delta[s,c-'0'].
#rows = states
#cols = transitions
delta =  [[1<<0|1<<1, 1<<0],\ 

 Make one transition from state-set to state-set on 
 each char in the given string.
 @param inp the String to use
def process(inp):
    global stateSet
    for i in range(len(inp)):
        c = inp[i]
        nextSS = 0  # next state set, initially empty
        for s in range(3):  # for each state s
            if (stateSet&(1<<s)) != 0:  # if maybe in s
                    nextSS |= delta[s][int(c)]
                    # in effect, nextSS |= 0
        stateSet = nextSS # new state set after c

Recursive Method:

    class State():
        def __init__(self,name,is_start_state,is_final_state):
            *** constructor ***
            1. name             , the name of the state, i.e. q0
            2. is_start_state   , the name of the state, i.e. True if is start state
            3. is_final_state   , the name of the state, i.e. False if not final state
            4. transitions      , the transition table, contents are filled by add_transitions()
            self.name = name
            self.is_start_state = is_start_state
            self.is_final_state = is_final_state
            self.transitions = {}                   #empty dict for transition table

        def add_transitions(self,string, target_states):

            #trans = (string, target_states)
            self.transitions[string] = target_states

   # NFA below

    q0 = State("q0",True,False)
    q1 = State("q1",False,False)
    q2 = State("q2", False, True)
    #q0 start, not final
    q0.add_transitions("0",[q0,q1])    #adds an entry to the transitions dict:{ "0":[q0]}
    #q1 not start, not final
    #q2 not start, final

    states = [q0,q1,q2]

         Test whether there is some path for the NFA to
         reach an accepting state from the given state,
         reading the given string at the given character
         @param state the current state
         @param inp the input string
         @param pos index of the next char in the string
         @return true if the NFA accepts on some path

        def accept_step(state, inp, pos): 
            if pos == len(inp): # if no more to read
                return state.is_final_state   # accept if the reached state is final state

            c = inp[pos]    # get char

                nextStates = state.transitions[c] #char is dict key for transitions
                return False    # no transition, just reject

            for nextState in nextStates:
                if accept_step(nextState, inp, (pos+1)):
                    return True
            return False    # all moves fail, return false

         Test whether the NFA accepts the string.
         @param in the String to test
         @return true if the NFA accepts on some path
        def accepts(str_input):
            return accept_step(states[0], str_input, 0) # start in q0 at char 0
  • $\begingroup$ What is a 'Parallel Bitmap search' and how does it facilitate NFA acceptance/rejection? Why do you claim that one method outperforms the other? Some benchmark or experiment? If so, please link to or describe it. Additionally, what did you try to answer this question? Where did you get stuck? Did you expect that the bitmap search would outperform the recursive backtracking algorithm? If so, why? $\endgroup$
    – Discrete lizard
    Jan 21, 2018 at 15:17
  • $\begingroup$ In experiment, the backtracking was faster. In the recursive method, I created the states as objects and assigned the possible TO states based on inputs one by one, then recursively ran through each character in string and would back up and re try if it did not reach accepting state. In parallel search, I made an array with the sets of possible states based on bit operations i.e {1<<0 , 0 << 0 | 0 << 1} on first row represents from q0 0 goes to q1 and 1 goes to q0 OR q1. I expected the parallel method to run faster than backtracking since it would not waste time on failed runs $\endgroup$
    – foobarbaz
    Jan 21, 2018 at 15:44
  • $\begingroup$ Could you edit your question to add the information from your comment? In particular, it would help to describe your experiment and the algorithm of the different methods in detail. Often, differences in actual running times of programs depend crucially on their implementation, unless one underlying algorithm is much faster than the other. However, it may also be a result of the a conceptual difference between the algorithms. To determine whether this is the case, I think more detail on the algorithms is needed. $\endgroup$
    – Discrete lizard
    Jan 21, 2018 at 15:53
  • $\begingroup$ @Discretelizard I updated my original question with more context. I am new to finite automaton and CS in general so I was not sure how much context was needed to answer questions like these. $\endgroup$
    – foobarbaz
    Jan 21, 2018 at 18:14
  • 1
    $\begingroup$ Good! Although it would help even more if you could give a high level description of your code instead of the actual code, especially for the bit-mapped parallel search method (I think more people may be familiar with the recursive backtracking method). See this answer for an example of a 'high-level' description of an algorithm (you might want to use more words than that example, but there's no need for code). $\endgroup$
    – Discrete lizard
    Jan 21, 2018 at 18:26


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.

Browse other questions tagged or ask your own question.