list-dict-DB 20170911.3

Install

Simply

pip install list_dict_DB

Usage:

For more full example usage, including the flexible query methods, see the tests.

Consider the following: (please do not argue accuracy. It is an example)

items = [
    {'first':'John', 'last':'Lennon','born':1940,'role':'guitar'},
    {'first':'Paul', 'last':'McCartney','born':1942,'role':'bass'},
    {'first':'George','last':'Harrison','born':1943,'role':'guitar'},
    {'first':'Ringo','last':'Starr','born':1940,'role':'drums'},
    {'first':'George','last':'Martin','born':1926,'role':'producer'}
]

If we want to find all members of The Beatles who’s name is “George Harrison”, we could do the following:

[item for item in items if item['first']=='George' and item['last']=='Harrison']

Which is an O(N) operation. If we are only doing it once, it is fine, but if we are doing it multiple times (especially in loops) it can cause a major bottleneck.

Instead do:

from list_dict_DB import list_dict_DB
DB = list_dict_DB(items) # Will index them all

DB.query(first='George',last='Harrison')

The creation is O(N) but the query is O(1) and can be done many times.

Queries

There are a few different methods to perform queries. It is designed to be flexible and allow for easy construction

DB.query(first='George')
DB.query({'first':'George'})
DB[{'first':'George'}]      # item indecies can be queries or a number
DB(first='George')          # Directly calling the object is a query()

DB.query(first='George',last='Harrison')

DB.query({'first':'George'},last='Harrison')

Q = DB.Qobj() # Instantiate it with the DB. DB.Q() will also work
DB.query( (Q.first=='George') & (Q.last != 'Martin') )

DB.query( (DB.Q().first=='George') & (DB.Q().last != 'Martin') )

DB.query( ~( (Q.role=='guitar') | (Q.role=='drums')))

# Traditional lookup:
DB.query(Q.first == 'George') # equality is O(1)

# Filter lookup
filt = lambda item: True if item['first'] == 'George' else False
DB.query(Q.filter(filt))

Loading and Saving (Dumping)

There is intentionally no built in way to dump these as they are intended to be in-memory. Of course, the a good way to save or load is as follows:

Dump:

import json
with open('DB.json','w') as F:
    json.dump(DB.items(),F)

Load:

from list_dict_DB import list_dict_DB
import json
with open('DB.json') as F:
    DB = list_dict_DB(json.load(F))

Lists:

All attributes must be hashable. The only exception are lists in which case the list is expanded for each item. For example, an entry may be:

{'first':'George','last':'Harrison','born':1943,'role':['guitar','sitar']}

and

DB.query(role='sitar')

will return him.

Benchmarks & Complexity Testing

I compared the creating and querying a large database with the following methods. Note that some cache results so I recreated and re-queried from scratch. In practice, even caching the results does not help much if the queries change.

• list_dict_DB

• simple looping with a copied list (not deepcopy though)

• Pandas dataframe (0.16.2)

• TinyDB (3.2.2) with in-memory storage

• dataset (0.6.0) with slite3 in-memory storage

  • dataset is a wrapper to SQLAlchemy that (in my words) provides a noSQL interface to SQL.

I tested on my MacBook Pro (Retina, 15-inch, Mid 2014) laptop with 2.8 GHz i7 and 16 gb of ram using Python 2.7.9.

The following figure is the time to build and query the resulting data object. Note that for TinyDB, the object was deleted between tests since it caches queries

From the slope of the plots, you can estimate the complexity. I just calculated from the final point. The order is O(N^{slope})

dataset gives this tool a run for its money but it also has a lot more dependancies and was the slowest in creation time (though, if you use it with a file, once it is created, you do not have to recreate it again). Pandas also performs well and only starts to have the O(N) dependency creep in at larger sizes. Of course, this is a scaling analysis. When you look at actual query times, list_dict_DB is orders of magnitude faster!

Which tool is the best will be problem dependent, but these results make a strong argument for list_dict_DB

Known Issues

None at the moment.

There is 100% (!!!) test coverage. Of course that doesn’t mean there aren’t bugs. If you find any, please report them.

Limitations

• The entire DB exists in memory

• Serializing (dumping) is not included though is easy to do with JSON or the like. See above

• The index used in the dictionary is itself a dictionary with keys as any value. Since these are all done as pointers to original list, the memory footprint should be small.

• This has not been tested for thread-safety!