5
\$\begingroup\$

I want to generate a 'dictionary' containing all 8 character permutations of upper-case letters such that the output file looks like:

AAAAAAAA
AAAAAAAB
AAAAAAAC
...
ZZZZZZZZ

I came up with this solution that uses the product method of itertools:

from itertools import product

per = product('ABCDEFGHIJKLMNOPQRSTUVWXYZ', repeat=8)

f = open('myfile', 'w')

p = ""

for p in per:
    p = "".join(p)
    f.write(p + "\n")

f.close()

I know there's 208,827,064,576 (> 200 billion) possible permutations so it's going to take time no matter what, but how can I optimise this?

\$\endgroup\$
  • \$\begingroup\$ I'd like to point out that what you are doing isn't called permutations (permutations are ordered rearrangements of a set). You a re creating variations (bit archaic) or n-tuples or just tuples (modern statistical term). \$\endgroup\$ – agtoever Oct 22 '14 at 12:14
4
\$\begingroup\$

Not much to do there, maybe use with ... as and inline everything:

from itertools import product

with open('myfile', 'w') as file:
    for p in product('ABCDEFGHIJKLMNOPQRSTUVWXYZ', repeat=8):
        file.write("".join(p) + "\n")

I'm sure there is a clever way to generate the characters as well. Edit: ah yes, you could replace 'A...Z' with map(chr, range(65, 91)) although that seems rather cryptic.

Now why would you want that though? It seems that using that generator and staying in Python would be more than enough instead of generating a static file.

\$\endgroup\$
  • \$\begingroup\$ Would using map be more performant? As for the purpose, it's a dictionary we'll be using for password cracking (all in a safe and controlled environment of course! :) \$\endgroup\$ – Juicy Oct 21 '14 at 13:08
  • \$\begingroup\$ I meant replacing the static string 'AB...Z' with a shorter, generated version. Performance doesn't matter for that. \$\endgroup\$ – ferada Oct 21 '14 at 13:17
4
\$\begingroup\$

Update: I just went through and verified your calculations, and you were off by a factor of 100 in the number of passwords that you will generate. The combinatronics is that you are performing permutations. There's 26 characters, and you can choose them 8 times, so you have \$26^8\$ possibile permutations, which is: 208827064576. Now, if you have 8 bytes plus a newline in the output file, that's 9 bytes per value, which is: 1879443581184 bytes, or.... 1.7TiB of data. I hope you have enough free disk space. Assuming IO will end up being your bottleneck, a decent disk can write 100MB/second, and that works out at almost exactly 5 hours... so, there's not much point in going faster than the Java version I presented unless you have a decent IO subsystem (I presume you don't have 1.7TB of SSD, do you?)


So, it is unusual to make the recommendation I am going to make here, but, in this case, is Python the right tool for the job?

I took your code, and looked through it, and also ferada's version. Really, they are pretty good.

I suspected that there is a problem with many writes to the file, so I 'batched' the writes up in to 1000-at-a-time IO operations, expecting that to be where the real time is spent.

There was not any change in performance (I tested by using just 5 character wide outputs).

Using the 5-char wide output, I calculate about 5.778 seconds on my computer. 5.778*26*26*26 times that for 8 chars, and that's more than 28 hours to run.

As an experiment, I did the same in Java. Now, Java is not the fastest compiled language, I know, but the process is compiled, not interpreted, so, what could it do?

panabox:~/xxx> time python gen.py
5.788u 0.160s 0:06.01 98.8%     0+0k 72+139240io 1pf+0w
panabox:~/xxx> time java PWGen
1.152u 0.336s 0:01.36 108.8%    0+0k 64+139304io 3pf+0w
panabox:~/xxx> diff myfile myfile.txt
panabox:~/xxx>

So, in Java, it's 1.152 seconds, which is 5.6 hours.

So, in the day it can save you to use Java, you can learn the code, and run it.

Now, I imagine that C or C++ will go even faster.... why not try those?

Regardless, here's the Java code I wrote, and, even though it is long-winded, and more verbose than the Python, the results are good. (Note that in Java the concept of the 'product' needs to be manually implemented...):

import java.io.IOException;
import java.io.Writer;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class PWGen implements Iterable<String> {

    public static void main(String[] args) throws IOException {
        int width = 5; // set a start point of 5-char wide output.
        if (args.length == 1) {
            width = Integer.parseInt(args[0]);
        }
        try (Writer writer = Files.newBufferedWriter(Paths.get("myfile.txt"), StandardCharsets.UTF_8)) {
            for(String v : new PWGen(UPPERLETTER, width, true)) {
                writer.write(v);
            }
        }
    }

    private static final char[] UPPERLETTER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();

    private final class PWIterator implements Iterator<String> {
        private final int[] cnts = new int[width];
        private final char[] chars;
        private String nxt = null;

        public PWIterator() {
            char[] nl = System.lineSeparator().toCharArray();
            chars = new char[width + (newline ? nl.length : 0)];
            Arrays.fill(chars, alphabet[0]);
            if (newline) {
                System.arraycopy(nl, 0, chars, width, nl.length);
            }
            nxt = new String(chars);
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public boolean hasNext() {
            return nxt != null;
        }

        @Override
        public String next() {
            if (nxt == null) {
                throw new NoSuchElementException();
            }
            final String toret = nxt;
            int pos = width - 1;
            nxt = null;
            while (pos >= 0) {
                cnts[pos]++;
                if (cnts[pos] != alphabet.length) {
                    chars[pos] = alphabet[cnts[pos]];
                    nxt = new String(chars);
                    break;
                } else {
                    cnts[pos] = 0;
                    chars[pos] = alphabet[0];
                }
                pos--;
            }
            return toret;
        }

    }

    private final int width;
    private final char[] alphabet;
    private final boolean newline;

    public PWGen(char[] alphabet, int width, boolean newline) {
        super();
        this.width = width;
        this.alphabet = alphabet;
        this.newline = newline;
    }



    @Override
    public Iterator<String> iterator() {
        return new PWIterator();
    }
}

The above Java code is more of a general-purpose implementation. You can (if you know Java), easily change the width of the output, and the 'alphabet' that is used.

My answer is not you must use Java. My answer here is: use the right tool for the Job. I would consider writing this in C if I thought that 5 hours was still too long.

\$\endgroup\$
  • \$\begingroup\$ Point duly noted! I did know that Python wasn't the best tool for the job but I didn't think the difference would be 24 hours!!! I will take a look at C. \$\endgroup\$ – Juicy Oct 21 '14 at 14:37
  • \$\begingroup\$ Heh, I absolutely agree with the faster implementation point, but even then for password cracking this still won't be the biggest performance bottleneck. \$\endgroup\$ – ferada Oct 21 '14 at 14:39
  • \$\begingroup\$ Updated with note on disk IO \$\endgroup\$ – rolfl Oct 21 '14 at 15:10
  • \$\begingroup\$ Using C would allow the 'character' data type to be represented by 5 bits [irrespective of issues like ASCII/Unicode]. Six characters would fit in a long and the other two characters could be used to break up the dictionary into 26^2 subdictionaries - that is prime dictionary could be a dictionary of dictionaries. Lookups would still be O(1), the first level of the dictionary could reside in memory and the secondary dictionaries could be distributed across more disk partitions to speed up IO. \$\endgroup\$ – ben rudgers Oct 21 '14 at 17:16
2
\$\begingroup\$
import string

print string.ascii_letters
'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
print string.ascii_uppercase
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

print string.ascii_lowercase
'abcdefghijklmnopqrstuvwxyz'

Check string for even more help from the string modulo.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! That's a nice succinct answer. Adding some amount of explanation to give the OP more info could be helpful, though your suggestion is pretty clear. \$\endgroup\$ – SuperBiasedMan Sep 25 '15 at 8:03
  • \$\begingroup\$ Feel free to correct or add, I am a newby and I don't know what else to add without making a mistake. \$\endgroup\$ – SaNaMeDiO Sep 25 '15 at 8:45
  • \$\begingroup\$ Well there's nothing to correct, but a nice addition might be explaining that the string module has other builtin strings like this, including ascii_uppercase. You could also link to the string module in the docs. If you'd like to know more about good reviewing, check out this post on how to answer here. Hope it helps! \$\endgroup\$ – SuperBiasedMan Sep 25 '15 at 8:54

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.