Author Archives: admin

MongoDB aspirin

Basically this is a list in progress of common errors/tasks/gripes I get when using Mongo. I’ve noted down what usually works. Maybe you’ll find it useful 🙂

Why has my remote mongodb connection been refused?

from pymongo import MongoClient
c = MongoClient('some ip address')
...
pymongo.errors.ConnectionFailure: could not connect to 123.456.0.1:27017: [Errno 111] Connection refused

from pymongo import MongoClient

c = MongoClient('some ip address')

...

pymongo.errors.ConnectionFailure: could not connect to 123.456.0.1:27017: [Errno 111] Connection refused

Delete the mongod.lock file from your main mongodb storage folder and restart [SO]
If on redhat, check sestatus
Modify /etc/sysconfig/iptables to have the correct firewall rules according to the mongodb docs.

How do can you iterate through all mongoDB collections in pymongo?

I normally access collections as object attributes like: conn.Database.Collection.find_one() but actually databases and connections can be accessed as keys in a dictionary as well:

from pymongo import MongoClient
conn = MongoClient() #use this instead of Connection()

#[1:] is used here because the first collection is system.indexes
for collection in conn.Database.collection_names()[1:]:
    #Do something
    conn.Database[collection].find_one()

#We can say anything like:
conn['Database'].collection.find_one()
conn.Database['collection'].find_one()

from pymongo import MongoClient

conn = MongoClient() #use this instead of Connection()

#[1:] is used here because the first collection is system.indexes

for collection in conn.Database.collection_names()[1:]:

#Do something

conn.Database[collection].find_one()

#We can say anything like:

conn['Database'].collection.find_one()

conn.Database['collection'].find_one()

Why is mongod terminating whenever I close the shell? Even when using & at the end

When starting mongod, use mongod --fork (note: fork must be right after the word mongod) and it will start as a background process instead. Or just add fork = true to your config.

I just created an authenticated database and can’t even use show dbs !

Create a new user with all 4 of the following permissions: userAdminAnyDatabase, readWriteAnyDatabase, dbAdminAnyDatabase, clusterAdmin:

> db.addUser({ user: "hilarious_name", pwd: "something_memorable", roles: ['clusterAdmin','userAdminAnyDatabase', 'dbAdminAnyDatabase' 'readWriteAnyDatabase'] } )
{
        "user" : "hilarious_name",
        "pwd" : "0c3032130d7123a36c1913b2f55a3c84",
        "roles" : [
                "clusterAdmin",
                "userAdminAnyDatabase",
                "readWriteAnyDatabase",
                "dbAdminAnyDatabase",
        ],
        "_id" : ObjectId("535956f010b65cad1f7906f7")
}

> db.addUser({ user: "hilarious_name", pwd: "something_memorable", roles: ['clusterAdmin','userAdminAnyDatabase', 'dbAdminAnyDatabase' 'readWriteAnyDatabase'] } )

{

"user" : "hilarious_name",

"pwd" : "0c3032130d7123a36c1913b2f55a3c84",

"roles" : [

"clusterAdmin",

"userAdminAnyDatabase",

"readWriteAnyDatabase",

"dbAdminAnyDatabase",

"_id" : ObjectId("535956f010b65cad1f7906f7")

}

Shared Variables in Python Multiprocessing to pre-map/reduce

Leave a reply

I’ve been using the multiprocessing library in Python quite a bit recently and started using the shared variable functionality. It can change something like this from my previous post:

from multiprocessing import pool
from pymongo import Connection

def how_many(server_number):
    """Returns how many documents in the collection"""
    c = Connection("192.168.0." + server_number) #connects to remote DB
    return c.MyDB.MyCollection.count()

pool = Pool(processes=4)
servers = [1,2,3,4]
result = pool.map(how_many,servers) #map stage
pool.close()

#reduce stage
result = sum(result)

print "You have {0} docs across all MongoDB servers!".format(result)

from multiprocessing import pool

from pymongo import Connection

def how_many(server_number):

"""Returns how many documents in the collection"""

c = Connection("192.168.0." + server_number) #connects to remote DB

return c.MyDB.MyCollection.count()

pool = Pool(processes=4)

servers = [1,2,3,4]

result = pool.map(how_many,servers) #map stage

pool.close()

#reduce stage

result = sum(result)

print "You have {0} docs across all MongoDB servers!".format(result)

Into a much nicer:

from multiprocessing import Value, pool
from pymongo import Connection

def how_many(server_number):
    """Returns how many documents in the collection"""
    c = Connection("192.168.0." + server_number) #connects to remote DB
    shared_count.value += c.MyDB.MyCollection.count()

#setup 
pool = Pool(processes=4)
servers = [1,2,3,4]
shared_count = Value("i", 0)

result = pool.map(how_many,servers) #map stage
pool.close()

print "You have {0} docs across all MongoDB servers!".format(shared_count)

from multiprocessing import Value, pool

from pymongo import Connection

def how_many(server_number):

"""Returns how many documents in the collection"""

c = Connection("192.168.0." + server_number) #connects to remote DB

shared_count.value += c.MyDB.MyCollection.count()

#setup

pool = Pool(processes=4)

servers = [1,2,3,4]

shared_count = Value("i", 0)

result = pool.map(how_many,servers) #map stage

pool.close()

print "You have {0} docs across all MongoDB servers!".format(shared_count)

Thus eliminating the reduce stage. This is especially useful if you have a shared dictionary which you’re updating from multiple servers. There’s another possible shared datatype called Array, which, as it suggests, is a shared array. Note: One pitfall (that I fell for) is thinking that the "i" in Value("i", 0) is the name of the variable. Actually, its a typecode which stands for “integer”.

There are other ways to do this, however, each of which has its own trade offs:

#	Solution	Advantages	Disadvantages
1	Shared file	Easy to implement and access after	Very slow
2	Shared mongoDB document	Easy to implement	Slow to constantly query for it
3	Multiprocessing Value/Array (this example)	Very fast, easy to implement	On 1 PC only, can’t be accessed after process is killed
4	Memcached Shared Value	Networked aspect is useful for big distributed databases, shared.set() function is already available	TCP could slow you down a bit

A quick solution to OrderedDict’s limitations in Python with O(1) index lookups

Leave a reply

Background to the Problem

I work regularly with gigantic machine learning datasets. One very versatile format, for use in WEKA is the “ARFF” (Attribute Relation File Format). This essentially creates a nicely structured, rich CSV file which can easily be used in Logistic Regression, Decision Trees, SVMs etc. In order to solve the problem of very sparse CSV data, there is a sparse ARFF format that lets users convert sparse lines in each file such as:

f₀	f₁	f₂	f₃	…	f_n
1	0	1	0	…	0

Into a more succint version where you have a list of features and simply specify the feature’s index and value (if any):

@ATTRIBUTE f0 NUMERIC
@ATTRIBUTE f1 NUMERIC
@ATTRIBUTE f2 NUMERIC
@ATTRIBUTE f3 NUMERIC
…
@ATTRIBUTE fn NUMERIC
@DATA
{0 1, 2 1}

i.e. {feature-index-zero is 1, feature-index-two is 1}, simply omitting all the zero-values.

The Implementation Problem

This is easy enough if you have, say 4 features, but what if you have over 1 million features and need to find the index of each one? Searching for a feature in a list is O(n), and if your training data is huge too, then creating the sparse ARFF is going to be hugely inefficient:

features = ['name', 'some_metric', 'an_attribute', 'some_boolean']

#Searching for the existence of a feature is O(n)
>>> 'some_metric' in features
True

#Retrieving the index of a feature in the list is also O(n)
>>> features.index('some_metric')
1

features = ['name', 'some_metric', 'an_attribute', 'some_boolean']

#Searching for the existence of a feature is O(n)

>>> 'some_metric' in features

True

#Retrieving the index of a feature in the list is also O(n)

>>> features.index('some_metric')

I thought I could improve this by using an OrderedDict. This is, very simply, a dictionary that maintains the order of its items – so you can pop() items from the end in a stack-like manner. However, after some research on StackOverflow, this disappointingly this doesn’t contain any efficient way to calculate the index of key:

from collections import OrderedDict
features = ['name', 'some_metric', 'an_attribute', 'some_boolean']
od = OrderedDict()
for f in features:
    od[f] = 0

#Searching for the existence of a feature is O(1)
>>> 'some_metric' in od
True

#Retrieving the index of a feature in the list is still O(n) though!
>>> features.keys().index('some_metric')
1
#keys() has to create an entire list of all the keys in memory to 
#retrieve the index. You could use iterkeys() to improve memory 
#performance, but its still pretty ridiculous.

from collections import OrderedDict

features = ['name', 'some_metric', 'an_attribute', 'some_boolean']

od = OrderedDict()

for f in features:

od[f] = 0

#Searching for the existence of a feature is O(1)

>>> 'some_metric' in od

True

#Retrieving the index of a feature in the list is still O(n) though!

>>> features.keys().index('some_metric')

#keys() has to create an entire list of all the keys in memory to

#retrieve the index. You could use iterkeys() to improve memory

#performance, but its still pretty ridiculous.

The solution

What can we do about this? Enter my favorite thing ever, defaultdicts with lambdas:

from collections import defaultdict
features = ['name', 'some_metric', 'an_attribute', 'some_boolean']
dd = defaultdict(lambda: len(dd))

for f in features:
    dd[f] #no need to give it a value, it just needs to be called

#So now we can do lookups in O(1)
>>> 'some_metric' in dd
True

#And also get its index in O(1)
>>> dd['some_metric']
1

from collections import defaultdict

features = ['name', 'some_metric', 'an_attribute', 'some_boolean']

dd = defaultdict(lambda: len(dd))

for f in features:

dd[f] #no need to give it a value, it just needs to be called

#So now we can do lookups in O(1)

>>> 'some_metric' in dd

True

#And also get its index in O(1)

>>> dd['some_metric']

Assigning items values in addition to the index is fairly straightforward with a slightly modified lambda:

dd = defaultdict(lambda: {'index':len(dd)})

#Then more information can seamlessly added:

dd['some_metric']['info'] = 1
dd['some_attribute']['info'] = 2

#Whilst maintaining the O(1) lookup of the auto-generated index:

>>> dd['some_attribute']['index']
1

dd = defaultdict(lambda: {'index':len(dd)})

#Then more information can seamlessly added:

dd['some_metric']['info'] = 1

dd['some_attribute']['info'] = 2

#Whilst maintaining the O(1) lookup of the auto-generated index:

>>> dd['some_attribute']['index']

Limitations

This is a fun fix, but doesn’t support full dictionary functionality – deleting items won’t reorder the index and you can’t iterate in order through this easily. However, since in creating this ARFF file, there’s no need for deletions or iteration that’s not a problem.

WNYC Radio: “Are Hackathons Worth It?”

Leave a reply

I was recently contacted by Jeff Coltin, a journalist at WNYC Radio, who asked me to participate in a show about hackathons in NYC.

He featured a snippet from our conversation, specifically about problems that the hacker community could solve. I said (vaguely accurate transcription):

“…There are so many problems that hackathons could fix. I think some big issues at the moment in the media, things like the NSA spying scandals and stuff like that. I think one thing the tech community has slightly failed to do is to make encryption really easy. There’s a sort-of inverse relationship between simplicity and security, so the more secure an app, often the more inconvenient it is to use. So we have things like TOR, extra-long passwords (TOR slows down your connection a lot), VPNs and a lot of very secure services are incompatible with mainstream services. So this level of security and privacy that users want or need is just so inconvenient to achieve its really up to the hacker community to make them much easier to use…”

There have been efforts such as Cryptocat but its adoption rate still needs to grow. HTTPS would probably be the best example of seamless encryption but this often fails when people either ignore or are at loss as to what to do when HTTPS certificates are flagged as invalid by the browser.

Cryptography is an incredibly tough field of Computer Science, so creating reliably secure apps is hard. Educating oneself about this can require a fairly super-human effort and I have a lot of respect for people who contribute modules in this field to PyPI. I’m hoping to start the Crypto course on Coursera once I have some more free time, but beating the security-simplicity inverse relationship I mentioned is certainly easier said than done.

Teaching Python at Harvard with Software Carpentry

2 Replies

Mike teaching Hamlet in Python. Photo copyright Chris Erdmann: https://twitter.com/libcce/status/371281901191196672

I’m part of an organization called Software Carpentry in NYC. This uses volunteers to teach programming at varying levels to universities, large governmental organizations and other interested groups of people. I previously taught at Columbia and this past weekend it was held at Harvard, organized by Chris Erdmann, the head librarian at the Harvard-Smithsonian Center for Astrophysics.

Before Software Carpentry, my teaching experience was limited to explaining aspects of programming to friends and family, as well as part of a year spent teaching English and French to children and adults in Japan. Teaching is hard. It’s very easy to be critical of a teacher – I’ve often found myself being so without thinking about the effort and stress behind conveying a complex concept to a group of students all with varying backgrounds and motivations. I’ve come up with a few conclusions about how to optimize teaching style from my last 2 SWC events:

Saturday’s Teacher line-up

Mike Selik on analyzing data and word frequencies in Hamlet
Me on reinforcing concepts of iteration, string formatting, conditionals and the meaning of identation using Codecademy exercises
Erik Bray on git/github and version control
Jessica McKellar on cheating at scrabble with Regular Expressions
R. David Murray to help alongside all the presentations, mainly with the trickier definition-oriented questions

Things that worked well

Humor. Mike sprinkled his tutorial with funny anecdotes which kept the class very lively.
Relevant and interesting subject matter. Hamlet was a good choice, as was the theme of cheating at scrabble due to the librarian-oriented audience. The dictionary brought up several amusing entries for searches like: grep ".*s.*s.*s.*s.*s.*s" words | less
Adding anecdotes to save people googling things. I reckon that a large amount of any programmer’s activities are in simply finding someone who’s done what you want to do before, and slightly modifying things – or connecting up the building blocks. So at the end of talking about the benefits of things like append() vs concatenating with plus signs like first+second , I mentioned things like deque() and format() .

Things to remember for next time

Typing SLOWLY. I work a lot with MongoDB, so end up typing from pymongo import Connection; c = Connection() 20+ times a day into the terminal. This can become so fast, things like that can seem bewildering to newcomers.
Using a high contrast terminal with large font and dimmed lights, to make it super easy to see from the back of the room.

What can advanced programmers get out of teaching such basic things?

You’ll learn a lot from the instructors and student’s questions
Community involvement is a great asset on your resume and shows potential employers that you have the ability/drive to train future co-workers
It helps to have on-hand analogies and anecdotes developed during teaching when explaining technical matters to non-technical people, socially or business-wise.
You’ll meet many like minded people and it feels great to get involved in the community.

What did I learn?

The requests library. I normally use urllib2 to grab html from web pages. Urllib2, it turns out, is simply a more extensible library for HTTP requests as shown in this stackoverflow explanation.
More about Git. I use SVN at work and thus don’t really submit anything to github. Git is HARD. Erik was an excellent instructor and calmly went from the basics right through to the minutiae of things like .gitignore and diff.
What “immutable” really means. I hear this thrown around quite a lot and it basically just means things can’t be assigned to an object. E.g. the . split() of myString.split() can’t become a variable. Very simple.

Review of Data Science for Business (O’Reilly, 2013)

Leave a reply

I’m currently participating in the O’Reilly Blogger Review Program – where bloggers are given ebooks of recent publications.

Data Science for Business fits an interesting gap in the market – managers who want to be able to understand what Data Science is, how to recruit Data Scientists or how to manage a data-oriented team. It says it is also for aspiring Data Scientists, but I would probably recommend Andrew Ng’s Machine Learning course and Codecademy’s intro Python course instead if you’re serious about getting your teeth into the field.

Somewhere between an introduction and an encyclopedia, it gives fairly comprehensive overviews of each sub-field, including distinctions that I hadn’t previously thought of so clearly. The authors are mostly unafraid to explain the maths behind the subjects. It dips into some probability and linear algebra – admittedly with simplified notation. There’s no real mention of implementation (i.e. programming the examples) as one would usually expect with O’Reilly; but most competent readers will now at least know what they’re “looking for” perhaps in terms of packages to install or if they want to try and implement a system from scratch. It is certainly designed for the intelligent, professional and far from popular science.

Whilst it is very thorough and interesting it could touch a nerve among Data Scientists, since should a manager of a Data Scientist really have to read a book such as this – surely in such a position of authority they should know of these techniques already? (an extreme example would be one footnote which even contains a description of what Facebook is, and what it is used for). Often, such unbalanced hierarchies are the cause of much unnecessary stress and complication in the workplace. However, this is often the case so perhaps this will be useful in that context.

I think, overall, I was hoping for a slightly different book – with more in-depth case studies of how to implement existing Data Science knowledge into Business scenarios. Nevertheless, it’s an interesting, intelligent guide in an encyclopedic sense and fairly unique in its clarity of explanation and accessibility – I highly doubt I could write a better guide in that respect. Existing Data Scientists will find many clear analogies to explain their craft to those less technical than themselves and I reckon that by itself justifies taking a look 🙂

When literal_eval fails: using asterisk notation to read in a datetime object

Leave a reply

One great function in python is the ast (Abstract Syntax Tree) library’s literal_eval . This lets you read in a string version of a python datatype:

>>> from ast import literal_eval
>>> # A sample dictionary with some trivial information
>>> myDict = "{'someKey': 1, 'otherKey': 2}"
>>> #Let's parse it using the function
>>> testEval = literal_eval(myDict)
>>> print testEval
{'someKey': 1, 'otherKey': 2}
>>> type(testEval)
<type 'dict'>

>>> from ast import literal_eval

>>> # A sample dictionary with some trivial information

>>> myDict = "{'someKey': 1, 'otherKey': 2}"

>>> #Let's parse it using the function

>>> testEval = literal_eval(myDict)

>>> print testEval

{'someKey': 1, 'otherKey': 2}

>>> type(testEval)

Importing a dictionary such as this is similar to parsing JSON using Python’s json.loads decoder. But it also comes with the shortcoming’s of JSON’s restrictive datatypes, as we can see here when the dictionary contains, for example, a datetime object:

>>> myDict = "{'someKey': 1, 'rightNow': datetime.datetime(2013, 8, 10, 21, 46, 52, 638649)}"
>>>
>>> literal_eval(myDict)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/root/anaconda/lib/python2.7/ast.py", line 80, in literal_eval
    return _convert(node_or_string)
  File "/root/anaconda/lib/python2.7/ast.py", line 63, in _convert
    in zip(node.keys, node.values))
  File "/root/anaconda/lib/python2.7/ast.py", line 62, in <genexpr>
    return dict((_convert(k), _convert(v)) for k, v
  File "/root/anaconda/lib/python2.7/ast.py", line 79, in _convert
    raise ValueError('malformed string')
ValueError: malformed string

>>> myDict = "{'someKey': 1, 'rightNow': datetime.datetime(2013, 8, 10, 21, 46, 52, 638649)}"

>>>

>>> literal_eval(myDict)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

File "/root/anaconda/lib/python2.7/ast.py", line 80, in literal_eval

return _convert(node_or_string)

File "/root/anaconda/lib/python2.7/ast.py", line 63, in _convert

in zip(node.keys, node.values))

File "/root/anaconda/lib/python2.7/ast.py", line 62, in <genexpr>

return dict((_convert(k), _convert(v)) for k, v

File "/root/anaconda/lib/python2.7/ast.py", line 79, in _convert

raise ValueError('malformed string')

ValueError: malformed string

So you might try and write some code to parse the dictionary data-type yourself. This gets very tricky, but eventually you could probably accommodate for all common data-types:

def read_dict(d):
    """Accepts a string containing a dictionary.
    Tries to parse this and returns the dictionary."""
    parsed_dict = {} #The result
    #Remove the {} and split into chunks
    d = d[1:-1].split(', ')
    #iterate through the chunks and try to interpret them
    for kv_pair in d:
        #split up by the central colon
        kv_pair = kv_pair.split(": ")
        #interpret the key and value
        k = whatAmI(kv_pair[0])
        v = whatAmI(kv_pair[1])
        #add to the final parsed dictionary
        parsed_dict[k] = v
    return parsed_dict

def whatAmI(thing):
    """Simple attempt at interpreting a string
    of a datatype. Can deal with Strings and Ints"""
    #remove any inverted commas
    if thing.startswith("'") or thing.startswith('"'):
        thing = thing[1:-1]

    #Now check for data-types (there are way more than this though)
    if thing.isdigit():
        return int(thing) #return the digit
    else:
        return thing #return the string
    #if not recognized by either, then return an error
    return "Corrupted data"

def read_dict(d):

"""Accepts a string containing a dictionary.

Tries to parse this and returns the dictionary."""

parsed_dict = {} #The result

#Remove the {} and split into chunks

d = d[1:-1].split(', ')

#iterate through the chunks and try to interpret them

for kv_pair in d:

#split up by the central colon

kv_pair = kv_pair.split(": ")

#interpret the key and value

k = whatAmI(kv_pair[0])

v = whatAmI(kv_pair[1])

#add to the final parsed dictionary

parsed_dict[k] = v

return parsed_dict

def whatAmI(thing):

"""Simple attempt at interpreting a string

of a datatype. Can deal with Strings and Ints"""

#remove any inverted commas

if thing.startswith("'") or thing.startswith('"'):

thing = thing[1:-1]

#Now check for data-types (there are way more than this though)

if thing.isdigit():

return int(thing) #return the digit

else:

return thing #return the string

#if not recognized by either, then return an error

return "Corrupted data"

But this still doesn’t truly fix our datetime object problem:

>>> read_dict(myDict)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 13, in read_dict
IndexError: list index out of range

>>> read_dict(myDict)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

File "<stdin>", line 13, in read_dict

IndexError: list index out of range

Which is where we get to the crux of this post. I thought at first that I could deal with datetime’s formatting by extracting the class datetime.datetime(2013, 8, 10, 21, 46, 52, 638649) as a tuple by spotting the brackets, then feeding the tuple back into datetime like:

>>> x = (2013, 8, 10, 21, 46, 52, 638649)
>>> parsedDate = datetime(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: an integer is required

>>> x = (2013, 8, 10, 21, 46, 52, 638649)

>>> parsedDate = datetime(x)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

TypeError: an integer is required

But apparently not. The tuple must be extracted – not by a lambda or perhaps list comprehension, but in fact by using asterisk notation:

>>> parsedDate = datetime(*x)
>>> print parsedDate
2013-08-10 21:46:52.638649

>>> parsedDate = datetime(*x)

>>> print parsedDate

2013-08-10 21:46:52.638649

Asterisk ( * ) unpacks an iterable such as x into positional arguments for the function. Simple!

def whatAmI(thing):
    """Simple attempt at interpreting a string
    of a datatype. Can deal with str, int, datetime"""
    #remove any inverted commas
    if thing.startswith("'") or thing.startswith('"'):
        thing = thing[1:-1]

    #Now check for some data-types
    if thing.isdigit():
        return int(thing) #return the digit
    elif thing.startswith('datetime'):
        #get the numbers between the brackets
        thing = thing.split('(')[1].split(')')[0]
        #parse the digits, unpack into datetime and return
        return datetime(*[int(x) for x in thing])
    else:
        return thing #return the string
    #if not recognized by either, then return an error
    return "Corrupted data"

def whatAmI(thing):

"""Simple attempt at interpreting a string

of a datatype. Can deal with str, int, datetime"""

#remove any inverted commas

if thing.startswith("'") or thing.startswith('"'):

thing = thing[1:-1]

#Now check for some data-types

if thing.isdigit():

return int(thing) #return the digit

elif thing.startswith('datetime'):

#get the numbers between the brackets

thing = thing.split('(')[1].split(')')[0]

#parse the digits, unpack into datetime and return

return datetime(*[int(x) for x in thing])

else:

return thing #return the string

#if not recognized by either, then return an error

return "Corrupted data"

Using ACORA to process hundreds of stopwords at once

Leave a reply

“80% of data analysis is spent cleaning data, 20% of it is spent complaining about cleaning data” – Chang She and BigDataBorat

This is one of the best quotes I heard at PyData 2013. When dealing with huge amounts of data, often only a fraction of it is usually relevant to one’s analysis and it can be a total pain trying to clean it. But this is also an essential stage, so let’s make it as painless as possible.

One example is with gigantic log files. Say we’re dealing with a multi-terabyte apache log files as follows:

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-dropdown.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-scrollspy.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-tab.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-tooltip.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-popover.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-button.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-collapse.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-carousel.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-typeahead.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"
127.0.0.1 - - [17/Jul/2013:07:22:39 -0500] "GET /favicon.ico HTTP/1.1" 404 4025 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-dropdown.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-scrollspy.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-tab.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-tooltip.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-popover.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-button.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-collapse.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-carousel.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:38 -0500] "GET /static/js/bootstrap-typeahead.js HTTP/1.1" 304 - "http://127.0.0.1/" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

127.0.0.1 - - [17/Jul/2013:07:22:39 -0500] "GET /favicon.ico HTTP/1.1" 404 4025 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/28.0.1500.71 Safari/537.36"

This is useful data with thousands of lines, and we’d like to analyze it using the big file processing script I mentioned before. However, there are certain lines that you’re not concerned about – so you can write a simple conditional:

with open('mylogfile.txt', 'r') as f:
    for line in f:
        if "some_keyword" not in line:
            do_something()

with open('mylogfile.txt', 'r') as f:

for line in f:

if "some_keyword" not in line:

do_something()

What if you have 2 things that you don’t want in each line?

with open('mylogfile.txt', 'r') as f:
    for line in f:
        if ("some_keyword" not in line) and ("other_keyword" not in line):
            do_something()

with open('mylogfile.txt', 'r') as f:

for line in f:

if ("some_keyword" not in line) and ("other_keyword" not in line):

do_something()

What if you have 3 things that you don’t want in each line?

with open('mylogfile.txt', 'r') as f:
    for line in f:
        line_is_ok = True
        for stopword in ["some_keyword", "other_keyword", "nope"]:
            if stopword in line:
                line_is_ok = False
                break #exit the loop 
        if line_is_ok: #only process line if line_is_ok hasn't been tampered with
            do_something()

with open('mylogfile.txt', 'r') as f:

for line in f:

line_is_ok = True

for stopword in ["some_keyword", "other_keyword", "nope"]:

if stopword in line:

line_is_ok = False

break #exit the loop

if line_is_ok: #only process line if line_is_ok hasn't been tampered with

do_something()

But this is getting super inefficient and a bit silly. Each extra keyword requires yet another pass through the line. With this code basically everything is a worst case scenario.

Bring on ACORA!

ACORA is Stefan Behnel’s library based on the Aho-Corasick string matching algorithm. Without diving too deep into the maths behind it, it basically compiles all the stopwords you have into a single über-stopword, meaning one scan of this stopword over your log-file line will check for all stopwords. For example:

from acora import AcoraBuilder

#create a list of stopwords - these are the entries
#that we'd like to ignore
stopwords = ['.js', '.ico', '.css', '.jpg', ...]

#enter them into a new Acora Builder
stopword_matcher = AcoraBuilder()
for stopword in stopwords:
    stopword_matcher.add(stopword)

#now let it construct the uber-stopword
stopword_matcher = stopword_matcher.build()

#this uses generator which iterates through matches
#it will stop whenever it finds something
for match in stopword_matcher.finditer(line_from_log_file):
    print "Match found: {0}".format(match)

from acora import AcoraBuilder

#create a list of stopwords - these are the entries

#that we'd like to ignore

stopwords = ['.js', '.ico', '.css', '.jpg', ...]

#enter them into a new Acora Builder

stopword_matcher = AcoraBuilder()

for stopword in stopwords:

stopword_matcher.add(stopword)

#now let it construct the uber-stopword

stopword_matcher = stopword_matcher.build()

#this uses generator which iterates through matches

#it will stop whenever it finds something

for match in stopword_matcher.finditer(line_from_log_file):

print "Match found: {0}".format(match)

But how do we integrate this into the line scanner from before? Just like this!

with open('mylogfile.txt', 'r') as f:
    for line in f:
        line_is_ok = True
        for match in stopword_matcher.finditer(line):
            line_is_ok = False
            break #exit the loop 
        if line_is_ok: 
            do_something()

with open('mylogfile.txt', 'r') as f:

for line in f:

line_is_ok = True

for match in stopword_matcher.finditer(line):

line_is_ok = False

break #exit the loop

if line_is_ok:

do_something()

We’ve replaced the entire multiple stopword matching for-loop with a single ACORA matcher.

A note on performance

ACORA is fantastic, but performance may dip if there are only a few stopwords, or only a few lines. It has best performance when you have about 20+ stopwords and at least 1000 or so log file lines to scan through.

Extracting TLDs (top-level domains) – and weird quirks that will upset you

2 Replies

I’ve been using John Kurkowski‘s excellent Python domain extraction library “tldextract” recently. TLDextract can extract the domain name from a URL very easily, for example:

>>> from tldextract import extract
>>> extract('http://davidrenda.com/?p=106')
ExtractResult(subdomain='', domain='davidrenda', tld='com')

>>> from tldextract import extract

>>> extract('http://davidrenda.com/?p=106')

ExtractResult(subdomain='', domain='davidrenda', tld='com')

Why is this useful?

This has many applications – for example, if you want to create a summary of the top domains linking to your site, you might have a very large list of referring URLs:

ref_urls = ["http://www.google.com/somesearch", "http://sub.othersite.com/something", "https://www.google.com/images", "http://xyz.yahoo.com/sample"] #etc etc

1	ref_urls = ["http://www.google.com/somesearch", "http://sub.othersite.com/something", "https://www.google.com/images", "http://xyz.yahoo.com/sample"] #etc etc

And you could write some simple code to output the domain:

from tldextract import extract

def grab_domain(url):
    """returns the domain of a URL"""
    try:
        url = extract(url)
    except Exception:
        raise Exception("This URL doesn't work: \"{0}\"".format(url))
    return '.'.join((url[1], url[2])) #concatenate domain and tld

from tldextract import extract

def grab_domain(url):

"""returns the domain of a URL"""

try:

url = extract(url)

except Exception:

raise Exception("This URL doesn't work: \"{0}\"".format(url))

return '.'.join((url[1], url[2])) #concatenate domain and tld

And use the word frequency calculator from my previous post to compile a list of the top referring domains! See that I’ve modified line 10 to instead add the domain as the key:

from operator import itemgetter
from collections import defaultdict

def domain_frequencies(l):
    """Takes a list 'l' of URLs and returns a list of lists
       where each item is [domain, frequency], sorted
       descending."""
    all_freqs = defaultdict(int) #to temporarily hold values
    for item in l:
        all_freqs[grab_domain(item)] += 1 #add domain to defaultdict
    #convert the dictionary to a list of lists
    all_freqs = [[k,v] for k,v in all_freqs.iteritems()]
    #return a sorted version
    return sorted(all_freqs, key=itemgetter(1), reverse=True)

from operator import itemgetter

from collections import defaultdict

def domain_frequencies(l):

"""Takes a list 'l' of URLs and returns a list of lists

where each item is [domain, frequency], sorted

descending."""

all_freqs = defaultdict(int) #to temporarily hold values

for item in l:

all_freqs[grab_domain(item)] += 1 #add domain to defaultdict

#convert the dictionary to a list of lists

all_freqs = [[k,v] for k,v in all_freqs.iteritems()]

#return a sorted version

return sorted(all_freqs, key=itemgetter(1), reverse=True)

Which returns:

>>> domain_frequencies(ref_urls)
[['google.com', 2], ['yahoo.com', 1], ['othersite.com', 1]]

1 2	>>> domain_frequencies(ref_urls) [['google.com', 2], ['yahoo.com', 1], ['othersite.com', 1]]

Why can’t you just split by fullstops at the third slash and take what’s before?

This is what I tried to do at the start:

def grab_domain(url):
    return url.split('/')[2].split('.')[-2:]

>>> grab_domain("http://www.google.com/something")
>>> ['google', 'com']

def grab_domain(url):

return url.split('/')[2].split('.')[-2:]

>>> grab_domain("http://www.google.com/something")

>>> ['google', 'com']

But since the domain name system is a miasma of top level (e.g. .com), second level (e.g. .gov.uk), standard sub domains (e.g. i.imgur.com) and people with too many fullstops (e.g. www.dnr.state.oh.us) this becomes much more tricky and it becomes impossible to accommodate for everything. So TLDextract actually maintains a local copy of Mozilla’s list of ICANN domains on your system, downloaded from:

http://mxr.mozilla.org/mozilla-central/source/netwerk/dns/effective_tld_names.dat?raw=1

And basically finds matches on the ends of URLs from that. Very nice!

So what’s the problem mentioned in the title?

Unfortunately, the caveat of using Mozilla’s list is that you get some seemingly odd behavior. There are a bunch of sites and companies who have requested that their subdomains are TLDs, and are included in the list, from Amazon:

// Amazon CloudFront : https://aws.amazon.com/cloudfront/
// Requested by Donavan Miller <donavanm@amazon.com> 2013-03-22
cloudfront.net

// Amazon Elastic Compute Cloud: https://aws.amazon.com/ec2/
// Requested by Osman Surkatty <osmans@amazon.com> 2013-04-02
compute.amazonaws.com
us-east-1.amazonaws.com
compute-1.amazonaws.com
z-1.compute-1.amazonaws.com
z-2.compute-1.amazonaws.com
ap-northeast-1.compute.amazonaws.com
ap-southeast-1.compute.amazonaws.com
ap-southeast-2.compute.amazonaws.com
eu-west-1.compute.amazonaws.com
sa-east-1.compute.amazonaws.com
us-gov-west-1.compute.amazonaws.com
us-west-1.compute.amazonaws.com
us-west-2.compute.amazonaws.com

// Amazon Elastic Beanstalk : https://aws.amazon.com/elasticbeanstalk/ 
// Requested by Adam Stein <astein@amazon.com> 2013-04-02
elasticbeanstalk.com

// Amazon CloudFront : https://aws.amazon.com/cloudfront/

// Requested by Donavan Miller <[email protected]> 2013-03-22

cloudfront.net

// Amazon Elastic Compute Cloud: https://aws.amazon.com/ec2/

// Requested by Osman Surkatty <[email protected]> 2013-04-02

compute.amazonaws.com

us-east-1.amazonaws.com

compute-1.amazonaws.com

z-1.compute-1.amazonaws.com

z-2.compute-1.amazonaws.com

ap-northeast-1.compute.amazonaws.com

ap-southeast-1.compute.amazonaws.com

ap-southeast-2.compute.amazonaws.com

eu-west-1.compute.amazonaws.com

sa-east-1.compute.amazonaws.com

us-gov-west-1.compute.amazonaws.com

us-west-1.compute.amazonaws.com

us-west-2.compute.amazonaws.com

// Amazon Elastic Beanstalk : https://aws.amazon.com/elasticbeanstalk/

// Requested by Adam Stein <[email protected]> 2013-04-02

elasticbeanstalk.com

To DynDNS stuff:

is-not-certified.com
is-saved.org
is-slick.com
is-uberleet.com
is-very-bad.org
is-very-evil.org
is-very-good.org
is-very-nice.org
is-very-sweet.org

is-not-certified.com

is-saved.org

is-slick.com

is-uberleet.com

is-very-bad.org

is-very-evil.org

is-very-good.org

is-very-nice.org

is-very-sweet.org

And more… So you’ll trip up if you put in something like:

>>> extract("https://scriptgang.elasticbeanstalk.com/getMagazine.html")
ExtractResult(subdomain='', domain='scriptgang', tld='elasticbeanstalk.com')

1 2	>>> extract("https://scriptgang.elasticbeanstalk.com/getMagazine.html") ExtractResult(subdomain='', domain='scriptgang', tld='elasticbeanstalk.com')

Rather than the expected “.com” as the tld.

Succinct way to build a frequency table of a Python iterable

Leave a reply

This is an interesting and often tackled task in programming, and especially prevalent in NLP and Data Science. Often one has a list of “things” with many repeats and wants to know which ones are the most popular.

Data Examples

my_list = [1,1,1,1,5,5,5,3,2,2,2,3,4,5,5,5,5,5,5,6,6,6,6]

1	my_list = [1,1,1,1,5,5,5,3,2,2,2,3,4,5,5,5,5,5,5,6,6,6,6]

or:

my_sentence = "The cat sat on the mat and read a newspaper"

1	my_sentence = "The cat sat on the mat and read a newspaper"

Which is the most popular number? Which is the most popular letter?

The Code

from collections import defaultdict
from operator import itemgetter

def freq_table(l):
    """Takes a list 'l' and returns a list of lists
       where each item is ['item', frequency], sorted
       descending."""
    all_freqs = defaultdict(int) #to temporarily hold values
    for item in l:
        all_freqs[item] += 1 #add to dictionary
    #convert the dictionary to a list of lists
    all_freqs = [[k,v] for k,v in all_freqs.iteritems()]
    #return a sorted version
    return sorted(all_freqs, key=itemgetter(1), reverse=True)

from collections import defaultdict

from operator import itemgetter

def freq_table(l):

"""Takes a list 'l' and returns a list of lists

where each item is ['item', frequency], sorted

descending."""

all_freqs = defaultdict(int) #to temporarily hold values

for item in l:

all_freqs[item] += 1 #add to dictionary

#convert the dictionary to a list of lists

all_freqs = [[k,v] for k,v in all_freqs.iteritems()]

#return a sorted version

return sorted(all_freqs, key=itemgetter(1), reverse=True)

For our data, we now get:

>>> freq_table(my_list)
[[5, 9], [1, 4], [6, 4], [2, 3], [3, 2], [4, 1]]

1 2	>>> freq_table(my_list) [[5, 9], [1, 4], [6, 4], [2, 3], [3, 2], [4, 1]]

So 5 is the most popular item, with 9 appearances.

>>> freq_table(my_sentence)
[[' ', 9], ['a', 7], ['e', 5], ['t', 4], ['n', 3], ['d', 2], ['h', 2], ['p', 2], ['s', 2], ['r', 2], ['c', 1], ['m', 1], ['o', 1], ['T', 1], ['w', 1]]

1 2	>>> freq_table(my_sentence) [[' ', 9], ['a', 7], ['e', 5], ['t', 4], ['n', 3], ['d', 2], ['h', 2], ['p', 2], ['s', 2], ['r', 2], ['c', 1], ['m', 1], ['o', 1], ['T', 1], ['w', 1]]

So the space is the most popular, followed by a, e and t.