Choosing a Python JSON Translator

This is a draft for comments. I already know it needs further work.

Among other things, I plan to move this off WordPress so that the data are more generally usable.

I noticed publication of python-cjson recently. I wondered whether the
claimed 10 to 200 times speed increase was real. It was reasonable to expect that a
“C” back end would make a difference. So, a few lines of code later, here
is a quick evaluation of the popular JSON translators for Python.

If you do not want to read all of this, here is the bottom line.
All of the translators evaluated here work OK. python-cjson is much faster,
but it is less tolerant of edge-case inputs than some. Fortunately, in python
you do not really have to choose. You have the option to send the offending
input to another, more tolerant, implementation when cjson throws an exception.
So, you can have fast JSON processing and still adhere to the mantra, “Be
liberal in what you accept, conservative in what you send.”

This evaluation borrows heavily from a comparison of php json libraries .

Modules Evaluated

In no particular order, here are the JSON translators for this evaluation. Disclosure notification: I am the author of the minjsons.

Speed tests

Code for the testdata object for the speed tests follows.

testdata = []
data1 = [1,1.01,'hello world',True,None,-1,11.011,"~!@#$%^&*()_+|",False,None]
data2 = {}
for k in ['zero','one','two','three','four','five','six','seven','eight','nine']:
    data2[k] = data1
for k in range(10):
    testdata.append(data2)
    

Timings were done using timeit, the minimum time of five sets
of 100 repetitions encoding or decoding the testdata object. These are not
really benchmarks. These numbers only provide a general idea of the
relative speed of the tested implementations.

In the above table, cjson is approximately three to thirty times as fast
encoding objects to JSON as the pure-python translators.

In the above table, cjson is approximately 40 to 200 times as fast
decoding objects from JSON as the pure-python translators.

Decoding tests

Python-cjson is fast. What are the risks? How well does it
decode JSON? json-py and minjson have some legacy code in them from earlier definitions
and misunderstandings of JSON. In particular, c-style comments and
single-quoted strings are allowed to some degree by these implementations.
cjson and simplejson are less tolerant of these and some other edge cases
that may crop up in some user-created JSON. Again, borrowing heavily from
the php evaluation article, following is a table of outputs from the various
python JSON translators, given some edge-case inputs. All of the tested translators
are presumably strict on output, so only input edge cases are illustrated here.

""

"1"

"true"

"null"

""hello""

"not a value"

"[]"

"[1]"

"[1.1]"

"[-1E+4]"

"[100.0e-2]"

"[.5]"

"[5.]"

"[.]"

"[5..5]"

"[10e]"

"[e10]"

"[010e2]"

"[010.2]"

"[010]"

"[0xFF]"

"[0xff]"

"[true]"

"[TRUE]"

"[null]"

"[NULL]"

"[""]"

"["a"]"

" [ "a" ] "

"[1,]"

"[,]"

"[,1]"

"[1,,1]"

"// comment here
[1]"

"[// comment here
1]"

"[1// comment here
]"

"[1]// comment here
"

"/*comment here*/[1]"

"[/*comment here*/1]"

"[1/*comment here*/]"

"[1]/*comment here*/"

"/**/[1]"

"//
[1]"

"[1
// comment here
]"

"[
// comment here
1]"

"[1]// comment here"

"[1]
// comment here"

"["a
// this is a comment
b"]"

"["a // this is not a comment b"]"

"['a']"

"["a]"

"[a"]"

"['a"]"

"["a']"

"[']"

"['']"

"[''']"

"["]"

"["""]"

"["'"]"

"['"']"

"["\'"]"

"["\\'"]"

"["\""]"

"["\"]"

"["\\"]"

"["\\\"]"

"
["a"]"

"[
"a"]"

"["a
"]"

"["a"
]"

"["a"]
"

"["\u0041\u00DC"]"

"["\b\t\f\v\r\n"]"

"["\b\t\f\r\n"]"

"["\x41\xDC"]"

"[ ] [ ]"

"["a" "b"]"

"[1 2]"

"[{}]"

"[ { } ]"

"[{1}]"

"[{1:1}]"

"[{:1}]"

"[{"1":}]"

"[{"1":1}]"

"[{"":1}]"

"[{"a":}]"

"[{"a":1}]"

"[{"true":1}]"

"[{true:1}]"

"[{null:1}]"

"[{a "a":1}]"

"[{"a":1"a"}]"

"[{a b:"a"}]"

"[{a b:a b}]"

"[{a 1:a 1}]"

"[{a:b:c}]"

"[/*comment here*/{"1":1}]"

"[{/*comment here*/"1":1}]"

"[{"1"/*comment here*/:1}]"

"[{"1":/*comment here*/1}]"

"[{"1":1/*comment here*/}]"

"[{"1":1}/*comment here*/]"

Final Notes

The above tables show that there are trade-offs between speed and
liberalness with input JSON. Fortunately, you can have it both ways! python-cjson
defines DecodeError, so your server can try: to decode with cjson, and if it fails,
you can handle the exception to use a more liberal translator. Choose your
secondary decoder by speed and/or how well it handles edge-case inputs from the
tables above. This page is largely automatically generated, (code available on request),
so this page can be re-done with additional or revised translators relatively quickly.
Just let me know if and when another run should be made.

I’m not altogether sure whether the above table shows any implementation bugs.
There seems to be a bit of disagreement in test case 73. I had started this evaluation for
personal reasons, but the results came out so interesting that I thought I would share.

It’s nice to see that there is some interest in the factoradic concept.

I’ve done some updates on the code, particularly “factoring” out some factorial calculations. It was silly to calculate a full factorial for each index when we are iterating through the entire list anyway and can get the factorial value by multiplying as we go.

Anyway, updated code is here. It now memoizes values and their factoradic representations to an sqlite db so that they can be looked up (either way) once calculated. I am using python’s marshal module to represent objects in the db, for speed. My first stab used cPickle, but the code is now different enough that swapping the import will not work. Hint: cPickle.loads wants a string, if you are afraid of marshal. But beware, str(aLargeInt) is surprisingly slow.

The current module is fine for moderately large sets, in the range of a couple of tens of thousands of items. It is extraordinarily zippy for less than a thousand items, which is the size of most Zope 3 containers I am dealing with. The larger the size of the set, the longer it will take for the initial calculations. Even pulling from the database gets slower as the number of items gets very large. I think it is something you just have to deal with when you are working with large numbers.

How to store several different orderings of a set of data?

I want to deliver a test to students. The test is delivered in a computer lab. Johnny can see Janie’s screen. How to keep Johnny from copying Janie’s answers?

The questions are presented to the students one at a time. One solution would be that, even though Janie and Johnny get the same questions, they get them in a different order. Each student would see a different permutation of the questions.

At first guess, one would consider generating a random order for each instance of the test. But what if a computer crashes, or someone sets off a fire alarm during the test? How to know which permutation of questions Johnny has, and which permutation of questions Janie has, so that they can resume the same test with the questions in the same order?

Somehow, the ordering of questions needs to be stored on the server, attached to the student’s data.

The quick solution is to store a list of question ids, in the order randomly generated for each student. Not too bad. But we can do better. We can store an index to the permutation.

Factoradics

A factoradic is a special way to represent any non-negative integer. It’s a little like a basic representation of a number, where the digits are multiplied by a power of a base going from right to left. But instead of a power of the base, the multiplier is the factorial of the index. for example, factoradic [1,2,0,0] would be 1 * 3! + 2 * 2! + 0 * 1! + 0 * 0!. Neat? Maybe. But there’s more. Factoradics can be used to create a two-way mapping from an integer to a particular permutation of a set, and from a particular permutation of a set to an integer.

For any set of n unique items, there are n! possible permutations of the set. I’ll call that a permutation index, where that number (we will use zero-based indexing) may be any integer from 0 to n! – 1. If you want to create a mapping of an integer to a permutation, there are many ways to do that.

But most of those easily-coded functions only work in one direction. You can get the permutation from the index, but not the index from the permutation.

What if you have a particular ordering and want to know what its permutation index is? You can, of course, iterate from 0 using a permutation-generating function until the permutation at the index matches the permutation. But there’s a better way, using factoradics.

Finding the Permutation Index of a Permutation

A simple example will demonstrate the method.

The canonical list is ['a','b','c','d','e'].

We wish to obtain the permutation index of ['c','a','e','d','b'].

The algorithm is:

• copy the canonical list
• for each item in the permutation
  • find the index of the item in the canonical list copy.
  • append that index to a list.
  • remove the item from the canonical list copy.

Working the algorithm:

1. Canonical copy is ['a','b','c','d','e']
2. The index of ‘c’ in the canonical copy is 2.
   Store [2]
   Canonical copy is ['a','b','d','e']
3. The index of ‘a’ in the copy is 0.
   Store [2,0]
   Canonical copy is ['b','d','e']
4. The index of ‘e’ in the copy is 2.
   Store [2,0,2]
   Canonical copy is ['b','d']
5. The index of ‘d’ in the copy is 1.
   Store [2,0,2,1]
   Canonical copy is ['b']
6. The index of ‘b’ in the copy is 0.
   Store [2,0,2,1,0]
   Canonical copy is []
   Done.

We get:
[2,0,2,1,0], which is a factoradic representation of the integer 53:
2 * 4! + 0 * 3! + 2 * 2! + 1 * 1! + 0 * 0!
2 * 24 + 2 * 2 + 1
48 + 4 + 1
53

The total number of permutations is 5!, or 120, and these are numbered 0 to 119.
We can say that, by this method, ['c','a','e','d','b'] is at permutation index 53 of ['a','b','c','d','e']. We obtained that index without generating the previous 53 permutations.

Obtaining a Permutation from a Permutation Index

The forward algorithm is similarly easy:

The canonical list is ['a','b','c','d','e'].

We wish to obtain the permutation at permutation index 53.

First, we need to calculate the factoradic representation of 53, which is [2,0,2,1,0]. The actual calculation is easy, requiring only divmod (%) and a factorial function.

Now that we have the factoradic representation of the permutation index, the algorithm is as follows:

• make a list of integers 0,1,… the same length as the canonical list
• for each item in the factoradic
  • obtain the item at that index in the integer list.
  • append that item to a list.
  • remove the item from the integer list
• using the new list, make a list of the items in the canonical list at the index in the new list

1. The canonical list has five items, so generate [0,1,2,3,4]
2. First item in the factoradic is 2.
   2 is at index 2 in the integer list.
   Store [2]
   Remove 2 from the integer list.
   Integer list is now [0,1,3,4]
3. Next item in the factoradic is 0.
   0 is at index 0 in the integer list.
   Store [2,0]
   Remove 0 from the integer list.
   Integer list is now [1,3,4]
4. Next item in the factoradic is 2.
   4 is at index 2 in the integer list.
   Store [2,0,4]
   Remove 4 from the integer list.
   Integer list is now [1,3]
5. Next item in the factoradic is 1.
   3 is at index 1 in the integer list.
   Store [2,0,4,3]
   Remove 3 from the integer list.
   Integer list is now [1]
6. Next item in the factoradic is 0.
   1 is at index 0 in the integer list.
   Store [2,0,4,3,1]
   Remove 1 from the integer list.
   Integer list is now []
   Done iterating.
7. Using [2,0,4,3,1] as indices to the canonical list, obtain ['c','a','e','d','b'].
   Done.

We know from above that ['c','a','e','d','b'] is at permutation index 53 of ['a','b','c','d','e'].

Where’s the Python Code?

The above algorithms are not Python-specific, but they may be expressed quite nicely in Python. I think there’s enough here for any competent Pythonista to make an acceptable implementation. I provide my own implementation at factoradic.py.

Where Else Can This be Used?

I think this technnique may be useful any time one needs to persist multiple orderings of objects, or any time the ordering process is itself expensive. One particularly nice aspect of this is that obtaining a slice e.g., [65:135] of a previously-stored permutation does not require a possibly-expensive reordering of the entire set each time a slice is requested.

Caveats

For large sets, the indexes are large. For a set with 30,000 items, an index to a random permutation can be over 120,000 digits. The provided code is probably OK to get started, but memoizing some of the function results (perhaps to disk!) and profiling for your specific case may be necessary for an efficient implementation. For small sets of 1000 items or so, the provided code is probably enough. For very large sets, prepare to trade-off memory and disk space for speed. Even with gmpy, calculating 30,000 factorials will take a while.

Credits

I originally found information about the factoradic technique at http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnnetsec/html/permutations.asp.
The algorithm I demonstrate here is from Wikipedia.