import os
import random
from array import array
def get_sampling_params(filename):
'''redefine to fit data'''
filesize = os.path.getsize(filename)
num_of_chunks = 500
size_of_chunk = filesize/(100*num_of_chunks)
seek_positions = [random.randint(0,(filesize-size_of_chunk)) for i
in xrange(num_of_chunks)]
epsilon = 2
return seek_positions, size_of_chunk, epsilon
def sample_chunks_gen(filename, seek_positions, size_of_chunk):
'''yields array of floats'''
def _array_from_file_chunk(input_file, seek_position, size_of_chunk):
input_file.seek(seek_position)
buf_str = input_file.read(size_of_chunk)
first_endl = buf_str.find('\n')
last_endl = buf_str.rfind('\n')
return array('f', map(float,
buf_str[(first_endl+1):][:(last_endl+1)].splitlines()))
with open(filename, 'rb') as input_file:
for seek_position in seek_positions:
yield _array_from_file_chunk(input_file, seek_position,
size_of_chunk)
def select(data, positions, start=0, end=None):
'''For every n in *positions* find nth rank ordered element in *data*
inplace select'''
if not end: end = len(data) - 1
if end < start:
return []
if end == start:
return [data[start]]
pivot_rand_i = random.randrange(start,end)
pivot_rand = data[pivot_rand_i] # get random pivot
data[end], data[pivot_rand_i] = data[pivot_rand_i], data[end]
pivot_i = start
for i in xrange(start, end): # partitioning about the pivot
if data[i] < pivot_rand:
data[pivot_i], data[i] = data[i], data[pivot_i]
pivot_i += 1
data[end], data[pivot_i] = data[pivot_i], data[end]
under_positions, over_positions, mid_positions = [],[],[]
for position in positions:
if position == pivot_i:
mid_positions.append(position)
elif position < pivot_i:
under_positions.append(position)
else:
over_positions.append(position)
result = []
if len(under_positions) > 0:
result.extend(select(data, under_positions, start, pivot_i-1))
if len(mid_positions) > 0:
result.extend([data[position] for position in mid_positions])
if len(over_positions) > 0:
result.extend(select(data, over_positions, pivot_i+1, end))
return result
def get_interval_endpoints(data, position, epsilon):
'''return interval endpoints'''
values = select(data, [position-epsilon, position+epsilon])
return min(values), max(values)
def reduce_endpoints(endpoints):
'''return min and max of all endpoints'''
first_endpoint = min(endpoints, key=lambda x: x[0])
last_endpoint = max(endpoints, key=lambda x: x[1])
return first_endpoint[0], last_endpoint[1]
def fill_interval(filename, endpoints, size_of_chunk=64*1024):
'''return count of values before interval, interval, data len'''
with open(filename, 'rb') as input_file:
first_endpoint = endpoints[0]
last_endpoint = endpoints[1]
seek_position = 0
interval = array('f')
iappend = interval.append
pre_count = 0
count = 0
input_file.seek(seek_position)
buf_str = input_file.read(size_of_chunk)
while buf_str:
last_endl = buf_str.rfind('\n')
buf_arr = array('f', map(float,
buf_str[:(last_endl+1)].splitlines()))
count = count + len(buf_arr)
for value in buf_arr:
if value <= first_endpoint:
pre_count = pre_count + 1
elif last_endpoint <= value:
pass
else:
iappend(value)
seek_position = seek_position + (last_endl+1)
input_file.seek(seek_position)
buf_str = input_file.read(size_of_chunk)
return interval, count, pre_count
def find_value(filename, position, sampling_func=get_sampling_params):
'''find value in file'''
seek_positions, size_of_chunk, epsilon = sampling_func(filename)
s_chunks_iter = sample_chunks_gen(filename, seek_positions, size_of_chunk)
s_endpoints = map(lambda x:
get_interval_endpoints(x, position, epsilon),
s_chunks_iter)
endpoints = reduce_endpoints(s_endpoints)
interval, count, pre_count = fill_interval(filename, endpoints)
print len(interval)
results = select(interval, [position - pre_count])
return results[0]
if __name__ == '__main__':
import optparse
parser = optparse.OptionParser()
parser.add_option(
'-f','--file',
dest='filename',
)
parser.add_option(
'-p','--position',
dest='position',
type='int'
)
options, args = parser.parse_args()
print repr(find_value(options.filename, options.position))
