Объединить эффективность сортировки в Python


Я пишу скрипт, который принимает во многих отсортированный .DAT файлы. Я включил образец данных, но набор данных достаточно большой. Желаемый результат-иметь один файл, отсортированный по алфавиту список слов.

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

Используя данные затем * 100000 на 11,000,000 строк без проблем. При работе с большими наборами я хочу разобраться в них, но без сбоев.

Не в Python sort() хорошо подходят для этой работы или я должен быть глядя на что-нибудь еще, что может быть быстрее и эффективнее?

Стоит ли используя модуль многопроцессорной, чтобы помочь справиться с этими задачами? Если да, то что является лучшей реализацией? Исследуя, я обнаружил эту статью, в которой, при работе с большими файлами, может быть аналогичный процесс сортировки большого списка в конце функции.

"Стоимости" этих операций очень важно для задач.

РЕПЛ

    dat1 ='allotment', 'amortization', 'ampules', 'antitheses', 'aquiline', 'barnacle', 'barraged', 'bayonet', 'beechnut', 'bereavements', 'billow', 'boardinghouses', 'broadcasted', 'cheeseburgers', 'civil', 'concourse', 'coy', 'cranach', 'cratered', 'creameries', 'cubbyholes', 'cues', 'dawdle', 'director', 'disallowed', 'disgorged', 'disguise', 'dowries', 'emissions', 'epilogs', 'evict', 'expands', 'extortion', 'festoons', 'flexible', 'flukey', 'flynn',
    'folksier', 'gave', 'geological', 'gigglier', 'glowered', 'grievous', 'grimm', 'hazards', 'heliotropes', 'holds', 'infliction', 'ingres', 'innocently', 'inquiries', 'intensification', 'jewelries', 'juicier', 'kathiawar', 'kicker', 'kiel', 'kinswomen', 'kit', 'kneecaps', 'kristie', 'laggards', 'libel', 'loggerhead', 'mailman', 'materials', 'menorahs', 'meringues', 'milquetoasts', 'mishap', 'mitered', 'mope', 'mortgagers', 'mumps', 'newscasters', 'niggling', 'nowhere', 'obtainable', 'organization', 'outlet', 'owes', 'paunches', 'peanuts', 'pie', 'plea', 'plug', 'predators', 'priestly', 'publish', 'quested', 'rallied', 'recumbent', 'reminiscence', 'reveal', 'reversals', 'ripples', 'sacked', 'safest', 'samoset', 'satisfy', 'saucing', 'scare', 'schoolmasters', 'scoundrels', 'scuzziest', 'shoeshine', 'shopping', 'sideboards', 'slate', 'sleeps', 'soaping', 'southwesters', 'stubbly', 'subscribers', 'sulfides', 'taxies', 'tillable', 'toastiest', 'tombstone', 'train', 'truculent', 'underlie', 'unsatisfying', 'uptight', 'wannabe', 'waugh', 'workbooks',
    'allotment', 'amortization', 'ampules', 'antitheses', 'aquiline', 'barnacle', 'barraged', 'bayonet', 'beechnut', 'bereavements', 'billow', 'boardinghouses', 'broadcasted', 'cheeseburgers', 'civil', 'concourse', 'coy', 'cranach', 'cratered', 'creameries', 'cubbyholes', 'cues', 'dawdle', 'director', 'disallowed', 'disgorged', 'disguise', 'dowries', 'emissions', 'epilogs', 'evict', 'expands', 'extortion', 'festoons', 'flexible', 'flukey', 'flynn',
    'folksier', 'gave', 'geological', 'gigglier', 'glowered', 'grievous', 'grimm', 'hazards', 'heliotropes', 'holds', 'infliction', 'ingres', 'innocently', 'inquiries', 'intensification', 'jewelries', 'juicier', 'kathiawar', 'kicker', 'kiel', 'kinswomen', 'kit', 'kneecaps', 'kristie', 'laggards', 'libel', 'loggerhead', 'mailman', 'materials', 'menorahs', 'meringues', 'milquetoasts', 'mishap', 'mitered', 'mope', 'mortgagers', 'mumps', 'newscasters', 'niggling', 'nowhere', 'obtainable', 'organization', 'outlet', 'owes', 'paunches', 'peanuts', 'pie', 'plea', 'plug', 'predators', 'priestly', 'publish', 'quested', 'rallied', 'recumbent', 'reminiscence', 'reveal', 'reversals', 'ripples', 'sacked', 'safest', 'samoset', 'satisfy', 'saucing', 'scare', 'schoolmasters', 'scoundrels', 'scuzziest', 'shoeshine', 'shopping', 'sideboards', 'slate', 'sleeps', 'soaping', 'southwesters', 'stubbly', 'subscribers', 'sulfides', 'taxies', 'tillable', 'toastiest', 'tombstone', 'train', 'truculent', 'underlie', 'unsatisfying', 'uptight', 'wannabe', 'waugh', 'workbooks'

    dat2 = 'abut', 'actuators', 'advert', 'altitude', 'animals', 'aquaplaned', 'battlement', 'bedside', 'bludgeoning', 'boeing', 'bubblier', 'calendaring', 'callie', 'cardiology', 'caryatides', 'chechnya', 'coffey', 'collage', 'commandos', 'defensive', 'diagnosed', 'doctor', 'elaborate', 'elbow', 'enlarged', 'evening', 'flawed', 'glowers', 'guested', 'handel', 'homogenized', 'husbands', 'hypermarket', 'inge', 'inhibits', 'interloper', 'iowan', 'junco', 'junipers', 'keen', 'logjam', 'lonnie', 'louver', 'low', 'marcelo', 'marginalia', 'matchmaker', 'mold', 'monmouth', 'nautilus', 'noblest', 'north', 'novelist', 'oblations', 'official', 'omnipresent', 'orators', 'overproduce', 'passbooks', 'penalizes', 'pisses', 'precipitating', 'primness', 'quantity', 'quechua', 'rama', 'recruiters', 'recurrent', 'remembrance', 'rumple', 'saguaro', 'sailboard', 'salty', 'scherzo', 'seafarer', 'settles', 'sheryl', 'shoplifter', 'slavs', 'snoring', 'southern', 'spottiest', 'squawk', 'squawks', 'thievish', 'tightest', 'tires', 'tobacconist', 'tripling', 'trouper', 'tyros', 'unmistakably', 'unrepresentative', 'waviest'

    dat3 = 'administrated', 'aggressively', 'albee', 'amble', 'announcers', 'answers', 'arequipa', 'artichoke', 'awed', 'bacillus', 'backslider', 'bandier', 'bellow', 'beset', 'billfolds', 'boneless', 'braziers', 'brick', 'budge', 'cadiz', 'calligrapher', 'clip', 'confining', 'coronets', 'crispier', 'dardanelles', 'daubed', 'deadline', 'declassifying', 'delegating', 'despairs', 'disembodying', 'dumbly', 'dynamically', 'eisenhower', 'encryption', 'estes', 'etiologies', 'evenness', 'evillest', 'expansions', 'fireproofed', 'florence', 'forcing', 'ghostwritten', 'hakluyt', 'headboards', 'hegel', 'hibernate', 'honeyed', 'hope', 'horus', 'inedible', 'inflammation', 'insincerity', 'intuitions', 'ironclads', 'jeffrey', 'knobby', 'lassoing', 'loewi', 'madwoman', 'maurois', 'mechanistic', 'metropolises', 'modified', 'modishly', 'mongols', 'motivation', 'mudslides', 'negev', 'northward', 'outperforms', 'overseer', 'passport', 'pathway', 'physiognomy', 'pi', 'platforming', 'plodder', 'pools', 'poussin', 'pragmatically', 'premeditation', 'punchier', 'puncture', 'raul', 'readjusted', 'reflectors', 'reformat', 'rein', 'relives', 'reproduces', 'restraining', 'resurrection', 'revving', 'rosily', 'sadr', 'scolloped', 'shrubbery', 'side', 'simulations', 'slashing', 'speculating', 'subsidization', 'teaser', 'tourism', 'transfers', 'transnationals', 'triple', 'undermining', 'upheavals', 'vagina', 'victims', 'weird', 'whereabouts', 'wordiness'

    # lines = open(combined_file_name + file_type, 'r').readlines()
    # output = open("intermediate_alphabetical_order.dat", 'w')
    # for line in sorted(lines, key=lambda line: line.split()[0]):
    #         output.write(line)
    # output.close()

    import datetime
    from functools import wraps
    from time import time

    datetme = datetime.datetime.now()
    date = datetme.strftime('%d %b %Y %H:%M:%S ').upper()

    # tuples are used to read in the data to save cost of memory usage
    combined_dat = dat1, dat2, dat3 # * 100000

    results = []

    log = () #TUPLE

    # decorator for speed test.
    def speed_test(f):
        @wraps(f)
        def wrapper(*a, **kw):
            start = time()
            result = f(*a, **kw)
            end = time()
            print('Elapsed time: {} s'.format(round(end - start, 8)))
            return result
        return wrapper

    @speed_test
    def merge_sort_lists(list_of_lists, *a, **kw):
        """takes in a list of lists/tuples and returns a sorted list"""
        try:
            for f in list_of_lists:
                try:
                    for c in f:
                        # recursion for lists in the list of lists... 
                        if isinstance(c, list):
                            merge_sort_lists([c])
                        else:
                            results.append(c)
                except:
                    datetme, ":: Item: {} not added".format(c)
                    # Logging
                        # log.append("file {} not found".format(f))
        except:
            "file {} not found".format(f)
            # Logging
            # log.append("file {} not found".format(f))

        results.sort()

        with open('log.txt', 'a') as f:
            for line in log:
                f.write(line)

    merge_sort_lists(combined_dat)

    # Tests

    def combined_length(combined):
        """calculates the length of a list of lists"""
        com_len = 0

        for i in combined:
            # if isinstance(i, list):
            #     combined_length(i)
            # else:
                com_len += int(len(i))
        return com_len

    com_length = (combined_length(combined_dat))

    res_len = len(results)
    print('\nResult Length: ', res_len, '\nCombined Lists: ', com_length)
    assert(res_len == com_length)


351
4
задан 14 февраля 2018 в 02:02 Источник Поделиться
Комментарии
1 ответ

Мне кажется, что ваше описание проблемы не совпадает с вашим кодом.

Вы заявляете проблему, как "принимает во многих отсортированный .DAT файлы" и необходимости "иметь один файл, отсортированный по алфавиту список слов".

Это слияние, даже не сортировка слиянием. Вы, кажется, пытаются обрабатывать все данные в памяти, которые тоже не надо. Однако, Timsort становится страшно-быстро. Так что это может быть, что загрузка все в памяти, сортировка и разгрузка это самый быстрый вариант. Если общий размер данных не > 1 Гб, или более доступной оперативной памяти, что меньше, это скорее всего правда.

Вариант 1: Timsort США.

def merge_files(outfile, *filenames):
words = []
for filename in filenames:
with open(filename) as f:
words.extend(f.readlines())

words.sort() # NB: in-place sort! Don't call sorted(words)!

with open(outfile, 'w') as out:
map(out.write, words)

Вариант 2: ZOMG! Сколько данных у вас есть??!!?!!

def merge(*iters):
if len(iters) == 1:
return iters[0]

iterlist = []
values = []

# Initialize values[] and also convert iters tuple to list (for del)
for i, it in enumerate(iters):
try:
values.append(next(it))
iterlist.append(it) # Order matter: next() might throw.
except StopIteration:
pass

iters = iterlist

while values:
nextvalue = min(values)
yield nextvalue

try:
i = values.index(nextvalue)
values[i] = next(iters[i])
except StopIteration:
del values[i], iters[i]

def merge_files(outfile, *filenames):
iters = [iter(open(fn)) for fn in filenames]

with open(outfile, 'w') as out:
map(out.write, merge(iters))

Это выглядит как это может сделать хорошая функция в модуле itertools. Это просто необходимо key= вариант, я думаю.

3
ответ дан 14 февраля 2018 в 05:02 Источник Поделиться