Geek Answers Handbook

Is there any way to simplify this "n-way merge" in python

So, now I hardcoded 4 if / elif / else statements. Is there a more dynamic way to do this? For example, if I wanted to do 10 or eve 40 merge?

#4-way merge sort, sorted page files
outfile="fullsorted.txt"
of=open(outfile,"w")
f1=open("temp0-sorted.txt","r")
f2=open("temp1-sorted.txt","r")
f3=open("temp2-sorted.txt","r")
f4=open("temp3-sorted.txt","r")

f1_line=f1.readline()
f2_line=f2.readline()
f3_line=f3.readline()
f4_line=f4.readline()

while len(f1_line)>0 and len(f2_line)>0 and len(f3_line)>0 and len(f4_line)>0:
  if f1_line < f2_line and f1_line < f3_line and f1_line < f4_line and len(f1_line)>0:
    of.write(f1_line)
    f1_line=f1.readline()
  elif f2_line < f3_line and f1_line < f4_line and len(f2_line)>0:
    of.write(f2_line)
    f2_line=f2.readline()
  elif f3_line < f4_line and len(f3_line)>0:
    of.write(f3_line)
    f3_line=f3.readline()
  else:
    of.write(f4_line)
    f4_line=f4.readline()

of.close()
+4
source share
3 answers

Just use heapq.merge:

import heapq

#4-way merge sort, sorted page files
outfile="fullsorted.txt"

with open("temp0-sorted.txt","r") as f1,\
     open("temp1-sorted.txt","r") as f2,\
     open("temp2-sorted.txt","r") as f3,\
     open("temp3-sorted.txt","r") as f4,\
     open(outfile,"w") as of:
    of.writelines(heapq.merge(f1, f2, f3, f4))
+5
source

Using your own code template, add it to this approach:

outfile="fullsorted.txt"
of=open(outfile,"w")
files = ["temp0-sorted.txt", "temp1-sorted.txt","temp2-sorted.txt","temp3-sorted.txt"]

filehandles = [open(f, "r") for f in files]

lines = [f.readline() for f in filehandles]

while len(filehandles) > 0:
    smallest = min(lines)
    smallestposition = lines.index(smallest)
    of.write(smallest)
    lines[smallestposition] = filehandles[smallestposition].readline()
    if lines[smallestposition] == "":
        filehandles[smallestposition].close()
        filehandles.pop(smallestposition)
        lines.pop(smallestposition)

of.close()

Please note that this will merge all the files, and does not stop as soon as one file ends.

+1
source

, :

sorted_files=[]

strings=[]
for i in xrange(files+1):
  sorted_files.append(open("temp"+str(i)+"-sorted.txt","r"))
  strings.append(sorted_files[i].readline())

print len(sorted_files)
print strings
eofs=0
while eofs != 1:
  small_str=min(filter(lambda x: x != "", strings))
  str_index=strings.index(small_str)
  of.write(small_str)
  strings[str_index]=sorted_files[str_index].readline()
  if all(i =="" for i in strings):
    eofs=1

6,5 (~ 700), 500000 , , ( ) , , 128 ( 2- , ), 16 :

real    15m54.375s
user    15m52.096s
sys 0m3.000s

script , , , , . , .

0

More articles:


All Articles