Daily Programmer #245 Hard - Python Solution

ipsort.py

import numpy as np
import time
from collections import Counter

from numba import jit

def to_int(ip_str):
	ip = map(int, ip_str.strip().split("."))
	return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + (ip[3])

def to_ip(intip):
	a = intip >> 24 & 0xFF
	b = intip >> 16 & 0xFF
	c = intip >>  8 & 0xFF
	d = intip       & 0xFF
	return "%i.%i.%i.%i" % (a,b,c,d)

@jit(nopython=True, cache=True)
def find_quiery_index(start,end,length,query):
	small_index = None
	small_size = 9223372036854775807
	for i in xrange(length):
		if start[i] <= query and query <= end[i]:
			if (end[i]-start[i]) < small_size:
				small_index = i
				small_size = end[i] - start[i]

	return small_index

def main():
	with open("query10k.txt", "r") as query_file:
		qf_len = sum(1 for i in query_file)
		query_integers = np.empty(qf_len, dtype=np.int32)
		query_file.seek(0,0)
		for i in xrange(qf_len):
			query_integers[i] = to_int(query_file.readline().strip())


	with open("ips1mil.txt", "r") as whois_file:
		lines = [line.strip().split(" ", 2) for line in whois_file]
		range_start = np.empty(len(lines), dtype=np.int32)
		range_end = np.empty(len(lines), dtype=np.int32)
		range_str = len(lines)*[None]
		for i in xrange(len(lines)):
			range_start[i] = to_int(lines[i][0])
			range_end[i] = to_int(lines[i][1])
			range_str[i] = lines[i][2]

	names = []
	calc_time = time.time()
	for ints in query_integers:
		index = find_quiery_index(range_start, range_end, len(range_start), ints)
		if index is not None:
			names.append(range_str[index])
		else:
			names.append("<unknown>")
	print("--- Main Calc: %s seconds ---" % (time.time() - calc_time))

	c = Counter(names)
	print "\n".join(["%i - %s" % (val, name) for name,val in c.most_common()])
		
if __name__ == "__main__":
	start_time = time.time()
	main()
	print("------- Total: %s seconds ---" % (time.time() - start_time))