Using deque for composing a string from 2 alternating stacks

Question

We have 2 strings, say "JACK" and "DANIELS". We create two stacks from these strings, and then loop over them comparing first elements: whichever of the 2 goes first in lexicographic order gets popped from its stack and added to a string (the second value is left alone). So it goes, until we end up with a string containing all the elements from both stacks. In this example it would be "DAJACKNIELS"

My solution takes advantage of the fact that min function, when applied to deque() objects, returns the one whose first element goes lexicographically first. As it happens, it works well enough for small testcases, but fails large ones, for it takes all the memory it can get and then some.

Perhaps, something can be improved in my code, or there's a better solution altogether (like, without a while loop).

def morgan(a, b): string = "" stack_a = deque() stack_b = deque() stack_a.extend(a) stack_b.extend(b) while True: if len(stack_a) != 0 and len(stack_b) != 0: if stack_a == min(stack_a, stack_b): string += stack_a.popleft() else: string += stack_b.popleft() elif len(stack_a) == 0 and len(stack_b) == 0: break elif len(stack_a) == 0: string += stack_b.popleft() elif len(stack_b) == 0: string += stack_a.popleft() return(string) 

Example of a large testcase:

string a: https://pastebin.com/raw/pebMbcA6 string b: https://pastebin.com/raw/bwNEqJcr 

Answer 1

There is no need to read the whole string into a deque. Just iterate over the strings using iterators. The only gotcha is handling the fact that either of the strings can be empty at the beginning and that one can be exhausted before the other.

def _morgan(a, b): a, b = iter(a), iter(b) try: x = next(a) except StopIteration: yield from b return try: y = next(b) except StopIteration: yield x yield from a return while True: if x <= y: # `<=` because that's what `min` does yield x try: x = next(a) except StopIteration: yield y yield from b return else: yield y try: y = next(b) except StopIteration: yield x yield from a return def morgan(a, b): return "".join(_morgan(a, b)) 

Note that both the original strings and the resulting string still need to fit into memory for this to work. If you only need to iterate over the resulting string, use only the private function. In that case the original strings still need to fit into memory, unless you also have them as generators (e.g. by streaming the contents from the URLs):

import requests def stream(url, chunk_size=1000): with requests.get(url, stream=True) as r: for chunk in r.iter_content(chunk_size=chunk_size, decode_unicode=True): yield from iter(chunk) if __name__ == "__main__": a = stream("https://pastebin.com/raw/pebMbcA6") b = stream("https://pastebin.com/raw/bwNEqJcr") c = _morgan(a, b) while (chunk := "".join(islice(c, 1000))): print(chunk, end='') print() 

This works on my machine with the given strings, but so does the morgan function I defined above.

---

Note that you need Python 3.8+ for the walrus operator :=. With earlier Python versions it is slightly more verbose:

 if __name__ == "__main__": a = stream("https://pastebin.com/raw/pebMbcA6") b = stream("https://pastebin.com/raw/bwNEqJcr") c = _morgan(a, b) chunk = "".join(islice(c, 1000)) while chunk: print(chunk, end='') chunk = "".join(islice(c, 1000)) print() 

Answer 2

next(iterable, [ default ])

I find too many try-except block can be distracting. next() takes an optional second argument--a default value to return when the iteration finishes. Here is @Graipher's _morgan() function using the 2-argument form of next() instead of try-except.

def _morgan(a, b): a = iter(a) x = next(a, None) b = iter(b) y = next(b, None) while x and y: if x <= y: yield x x = next(a, None) else: yield y y = next(b, None) if x: yield x yield from a else: yield y yield from b