CODEWITHSUNDEEP
pythonmergesort
Anthony B
Anthony B

Reputation: 55

TypeError when using mergesort on large amounts of data (python)

So, I want to make a benchmark and compare different algorithm's processing speed on different size arrays. I have the following script which is supposed to use mergeSort on size 10, 100, 1000, 10000, 100000, 1000000 input arrays:

import sys
import time
import random

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r- m

    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)

    # Copy data to temp arrays L[] and R[]
    for i in range(0 , n1):
        L[i] = arr[l + i]

    for j in range(0 , n2):
        R[j] = arr[m + 1 + j]

    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray

    while i < n1 and j < n2 :
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,l,r):
    if l < r:

        # Same as (l+r)/2, but avoids overflow for
        # large l and h
        m = (l+(r-1))/2

        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)

data = []
L10 = []
L100 = []
L1000 = []
L10000 = []
L100000 = []
L1000000 = []
inf = open("10.txt", "r")
inputData = inf.readlines()
for line in inputData:
    L10.append(int(line.rstrip()))
data.append(L10)

inf = open("100.txt", "r")
inputData = inf.readlines()
for line in inputData:
    L100.append(int(line.rstrip()))
data.append(L100)

inf = open("1000.txt", "r")
inputData = inf.readlines()
for line in inputData:
    L1000.append(int(line.rstrip()))
data.append(L1000)

inf = open("10000.txt", "r")
inputData = inf.readlines()
for line in inputData:
    L10000.append(int(line.rstrip()))
data.append(L10000)

inf = open("100000.txt", "r")
inputData = inf.readlines()
for line in inputData:
    L100000.append(int(line.rstrip()))
data.append(L100000)

inf = open("1000000.txt", "r")
inputData = inf.readlines()
for line in inputData:
    L1000000.append(int(line.rstrip()))
data.append(L1000000)

for numList in data:
    start = time.time()
    mergeSort(numList, 0, len(numList)-1)
    end = time.time()
    print("Sort time for {} size list: {}".format(len(numList), end - start))

The error:

Traceback (most recent call last):
  File "C:\Users\witcher\Documents\NJIT\CS 288\mergesort.py", line 110, in <module>
    mergeSort(numList, 0, len(numList)-1)
  File "C:\Users\witcher\Documents\NJIT\CS 288\mergesort.py", line 58, in mergeSort
    mergeSort(arr, l, m)
  File "C:\Users\witcher\Documents\NJIT\CS 288\mergesort.py", line 58, in mergeSort
    mergeSort(arr, l, m)
  File "C:\Users\witcher\Documents\NJIT\CS 288\mergesort.py", line 58, in mergeSort
    mergeSort(arr, l, m)
  File "C:\Users\witcher\Documents\NJIT\CS 288\mergesort.py", line 60, in mergeSort
    merge(arr, l, m, r)
  File "C:\Users\witcher\Documents\NJIT\CS 288\mergesort.py", line 10, in merge
    L = [0] * (n1)
TypeError: can't multiply sequence by non-int of type 'float

I have no idea what causes this issue. This algorithm is directly from a tutorial website and worked perfectly fine with small lists. I believe the initial function call is correct as well. The input data is just a file where every line is a random integer, here is the script I used to create those scripts:

import math
import random

for num in [10, 100, 1000, 10000, 10000, 100000, 1000000]:
    outf = open(str(num)+".txt", "w")
    for i in range(num):
        outf.write(str(random.randint(1,999))+"\n")
outf.close()

And yes, I manually removed the extra newline at the end of each file. Any help is appreciated.

Upvotes: 0

Views: 53

Answers (1)

bow
bow

Reputation: 2563

Looks like you're on Python 3? I'm guessing the error stems from this line:

m = (l+(r-1))/2

In Python 3, this division will create a float (as opposed to just regular ints -- the behavior in Python 2). If you want to create ints still, you can use:

m = (l+(r-1)) // 2

This is a floor division and will give you an int, which should work for your use case.

Upvotes: 2

Related Questions