![]() It is the only JITed/AOTed by numba function, the rest are helper pure-Python wrappers. by batch_size = 1000.Ĭentral internal function is next_batch(.) which actually implements whole algorithm of generating next permutations given previous one. Also it is possible to tweak batch size e.g. Also it is possible to choose whether to iterate by one permutation at a time ( iter_ = True, iter_batches = False) or by batch of permutations at a time which is much faster ( iter_ = True, iter_batches = True) or to return whole array of all permutations without iteration ( iter_ = False). I've implemented possibility to both use numba and no-numba mode and both JIT and AOT variants in numba mode. If iterating by 1 permutation at a time my code is just 1.25x faster than itertools.permutations(.), but according to initial question I needed either whole array of all permutations or at least iterating over large chunks. My next numba-based solution is 25x-50x times faster for large enough n than doing same task using itertools.permutations(.). On my machine, it's about 2x as fast as the original version (0.05 seconds vs 0.12 seconds for n=10).Īs I didn't find a good/fast-enough solution, I decided to implement whole permutations algorithm from scratch using Numba JIT/ AOT code compiler/optimizer. It's more efficient because the memory locations accessed are closer together. This is essentially the transpose of superb rain's version. Permutations() with memory order optimization: 0.62 secondsīased on superb rain's answer, this is a faster version with more efficient memory access patterns: def fast_permutations(n):Ī = np.zeros((n, np.math.factorial(n)), np.uint8)Ī = b + (b >= i) Timings on my machine with n=11: faster_permutations(): 0.12 seconds Perms = np.empty((np.math.factorial(n), n), dtype=np.uint8, order='F') ![]() # order='F' uses Fortran ordering, which makes accessing elements in the same column fast # empty() is fast because it does not initialize the values of the array This approach builds an array by expanding from one corner, using the same basic idea explained in superb rain's answer, but is much faster since it avoids unnecessary work. This solution is about 5x faster than my original answer, due to avoiding unnecessary computation. It does so by filling the next-left column and by copying/modifying the previous block of permutations downwards. Then it turns that into the permutations of range(2): Īnd then into the permutations of range(3): How it proceeds: It starts with a zero-array of the goal size, which already contains the permutations for range(1) at the top-right (I "dotted out" the other parts of the array): Here's a NumPy solution that builds the permutations of size m by modifying the permutations of size m-1 (see more explanation further down): def permutations(n):Ī = np.zeros((np.math.factorial(n), n), np.uint8)ī = a # the block of permutations of range(m-1)įor n=10, the itertools solution takes 5.5 seconds for me while this NumPy solution takes 0.2 seconds.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |