TypeError при использовании сортировки слиянием на больших объемах данных (python)

Anthony B спросил: 13 октября 2017 в 06:40 в: python

Итак, я хочу сделать тест и сравнить скорость обработки разных алгоритмов на массивах разных размеров. У меня есть следующий скрипт, который должен использовать mergeSort для входных массивов размером 10, 100, 1000, 10000, 100000, 1000000:

import sys
import time
import randomdef 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))

Ошибка:

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

Я понятия не имею, что вызывает эту проблему. Этот алгоритм прямо с учебного сайта и отлично работал с небольшими списками. Я считаю, что первоначальный вызов функции также является правильным. Входные данные - это просто файл, где каждая строка представляет собой случайное целое число. Вот сценарий, который я использовал для создания этих сценариев:

import math
import randomfor 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()

И да, я вручную удалил лишнюю новую строку в конец каждого файла. Любая помощь приветствуется.

0 ответов