1
\$\begingroup\$

I want to create Sudoku grids using Python. As it's pretty slow if I want to create a bunch of grids, I decided to use multiprocessing.

My computer has 4 virtual cores (dual core with hyper threading), so I expected the new program to run about 4 times faster, minus a little overhead maybe. But it's only almost exactly two times faster!

Here's the snippet where I use a multiprocessing.Pool:

worker_pool = Pool(processes)
sudokus = list(filter(None, worker_pool.imap_unordered(create_sudoku, range(n), n // processes)))

Why does this happen? Am I using the multiprocessing module in a wrong or inefficient way? Please help me to optimize it.

Here's the code of the main module, I guess the grid module is not important for multiprocessing performance:

import grid  # my own sudoku grid module

import subprocess
import random
import time
from multiprocessing import Pool, cpu_count


def create_sudoku(*_, level="medium"):
    numbers = list("123456789")

    random.shuffle(numbers)
    grid_string = "".join(numbers[:3]) + "." * 6 + "".join(numbers[3:6]) + "." * 6 + "".join(numbers[6:9]) + "." * 6
    random.shuffle(numbers)
    grid_string += "." * 3 + "".join(numbers[:3]) + "." * 6 + "".join(numbers[3:6]) + "." * 6 + "".join(numbers[6:9])
    random.shuffle(numbers)
    grid_string += "." * 9 + "".join(numbers[:3]) + "." * 6 + "".join(numbers[3:6]) + "." * 6 + "".join(numbers[6:9])
    g = grid.Grid(grid_string)
    g.try_to_solve()

    return (grid_string, level) if g.is_solved() else None


if __name__ == "__main__":

    n = int(input("How many grids to create? "))
    use_multiprocessing = None
    while use_multiprocessing is None:
        answer = input("Use multiprocessing to speed things up? (Y/n) ").strip().lower()
        if len(answer) == 1 and answer in "yn":
            use_multiprocessing = True if answer == "y" else False
    print()

    t0 = time.time()

    if use_multiprocessing:
        processes = cpu_count()
        worker_pool = Pool(processes)

        print("Creating {} sudokus using {} processes. Please wait...".format(n, processes))
        sudokus = list(filter(None,
                              worker_pool.imap_unordered(create_sudoku, range(n), n // processes)
                              ))
    else:
        progress_bar, progress_bar_length = 0, 10
        sudokus = []

        print("Creating {} sudokus".format(n), end="", flush=True)
        for i in range(n):
            p = int((i / n) * progress_bar_length)
            if p > progress_bar:
                print("." * (p-progress_bar), end="", flush=True)
                progress_bar = p
            new_sudoku = create_sudoku()
            if new_sudoku:
                sudokus.append(new_sudoku)
        print()

    t = time.time() - t0
    print("\nSuccessfully created {}/{} grids ({:.1f}%) in {:.3f}s (average {:.3f}s per grid)!".format(
        len(sudokus), n, 100*len(sudokus)/n, t, t/n
    ))

And here are two sample runs:

How many grids to create? 100
Use multiprocessing to speed things up? (Y/n) y

Creating 100 sudokus using 4 processes. Please wait...

Successfully created 100/100 grids (100.0%) in 19.507s (average 0.195s per grid)!

How many grids to create? 100
Use multiprocessing to speed things up? (Y/n) n

Loading 100 sudokus.........

Successfully created 100/100 grids (100.0%) in 37.675s (average 0.377s per grid)!
\$\endgroup\$
  • 1
    \$\begingroup\$ I wrote a sudoku generator in Python that got reviewed here ages back, take a look here. You seem to be making the same key mistake I did, where you're throwing away full puzzles for any mistake. Instead intelligently choosing letters and discarding small pieces will speed up your code a lot. \$\endgroup\$ – SuperBiasedMan Jan 22 '16 at 14:47
  • 1
    \$\begingroup\$ @SuperBiasedMan Wow, your revised approach is about 100x faster than mine (3ms per grid on the same machine as the results from above)! I just randomly filled the 1st, 5th and 9th block with numbers and then ran it through my solver, which starts guessing numbers as soon as its rules can't eliminate any more candidates. I am actually not throwing away entire puzzles, as there are no conflicting outputs possible, but I spend far too much time trying to solve the grid. Thanks for the link, if you don't mind, I'll take it as inspiration and replace some of my own lines with it. \$\endgroup\$ – Byte Commander Jan 22 '16 at 15:36
  • 1
    \$\begingroup\$ I think this answers your question on why it's not 4 times faster. Also the specification page's descriptions of '# of Cores' and '# of Threads' reads to me that only cores do work, not virtual cores. \$\endgroup\$ – Peilonrayz Jan 22 '16 at 15:54

Your Answer

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

Browse other questions tagged or ask your own question.