高级解决方案：
- 解析输入，将“[token] +X +Y”行输出到 N 个输出文件中的 1 个（这些“分片”输出文件中的每一个都足够小，可以在内存中处理。）
- [对于每个文件] 将其读入内存，输出带有“[token] [count1] [count2] ...”行的排序文件
- 在查询时，对正确的文件进行二分搜索
详细信息：这是第 1 步的 Python 伪代码）
NUM_SHARDS = 1000 # big enough to make each file fit in memory
output_files = [open("file" + str(n), "w") for n in xrange(NUM_SHARDS)]
for token in input_stream:
shard_id = hash(token) % NUM_SHARDS
output_files[shard_id].write(token + " +0 +1\n")
# TODO: output the correct +X and +Y as needed
这是第 2 步的 Python 伪代码）
input_files = [open("file" + str(n)) for n in xrange(NUM_SHARDS)]
for file in input_files:
counts = {} # Key: token Value: { "count1": 0, "count2": 1 }
# read the file, and populate 'counts'
for line in file:
(token, count1, count2) = line.split(" ")
# make sure we have a value for this token
counts.setdefault(token, { "count1": 0, "count2": 0 })
counts[token]["count1"] += int(count1)
counts[token]["count2"] += int(count2)
# TODO: compute those floats, and stuff those inside 'counts' also
# now write 'counts' out to a file (in sorted order)
output_file = open(file.name + ".index", "w")
for token, token_counts in sorted(counts.items()):
output_file.write(token + " " + token_counts["counts1"] + " " + token_counts["counts2"] + "\n")
# TODO: also write out those floats in the same line
这是第 3 步的一些 Python 代码）：
# assume 'token' contains the token you want to find
shard_id = hash(token) % NUM_SHARDS
filename = "file" + str(shard_id) + ".index"
binary_search(token, open(filename), 0, os.path.getsize(filename))
# print out the line in 'file' whose first token is 'token'
# begin/end always point to the start of a line
def binary_search(token, file, begin, end):
# If we're close, just do brute force
if end - begin < 10000:
file.seek(begin)
while file.tell() < end:
line = file.readline()
cur_token = line.strip().split(" ")[0]
if cur_token == token:
print line
return True
return False # not found
# If we're not close, pivot based on a line near the middle
file.seek((begin + end) / 2)
partial_line = file.readline() # ignore the first fractional line
line = file.readline()
cur_token = line.strip().split(" ")[0]
if cur_token == token:
print line
return True
elif cur_token < token:
return binary_search(token, file, file.tell(), end)
else: # cur_token > token
return binary_search(token, file, begin, file.tell() - len(line))