Непонятная проблема цикла (питон) - PullRequest
3 голосов
/ 25 августа 2010

это похоже на вопрос в сортировка слиянием в python Я повторяю, потому что не думаю, что я объяснил проблему там очень хорошо.

В основном у меня есть серия из примерно 1000 файлов, содержащих доменные имена.в целом данные> 1 гигабайт, поэтому я стараюсь не загружать все данные в оперативную память.каждый отдельный файл был отсортирован с использованием .sort (get_tld), который отсортировал данные по своему TLD (не по своему доменному имени. отсортировал все .com вместе, .orgs вместе и т. д.)

типичныйфайл может выглядеть как

something.ca
somethingelse.ca
somethingnew.com
another.net
whatever.org
etc.org

, но явно длиннее.

Теперь я хочу объединить все файлы в один, сохраняя сортировку так, чтобы в конце один большой файл все еще имел все.coms вместе, .orgs вместе и т. д.

То, что я хочу сделать в основном, это

open all the files
loop:
    read 1 line from each open file
    put them all in a list and sort with .sort(get_tld)
    write each item from the list to a new file

проблема, с которой я столкнулся, это то, что я не могу понять, как зацикливатьсяповерх файлов, которые я не могу использовать с open () как , потому что у меня нет 1 открытого файла для зацикливания, у меня их много.Кроме того, все они имеют переменную длину, поэтому я должен убедиться, что они пройдут самый длинный.

Любой совет очень ценится.

Ответы [ 5 ]

6 голосов
/ 25 августа 2010

Возможность хранить 1000 файлов одновременно - это отдельная проблема, которая зависит от вашей ОС и ее конфигурации; в противном случае вам придется выполнить два шага - объединить группы из N файлов во временные, а затем объединить временные в файл конечного результата (достаточно двух шагов, так как они позволяют объединить всего N в квадрате файлы, если N равно не менее 32, поэтому должно быть возможно объединение 1000 файлов). В любом случае, это отдельная проблема от задачи «объединить N входных файлов в один выходной файл» (это только вопрос того, вызываете ли вы эту функцию один раз или несколько раз).

Общая идея этой функции - сохранить приоритетную очередь (модуль heapq хорош в этом ;-) с небольшими списками, содержащими «ключ сортировки» (текущий TLD, в вашем случае), за которым следует последняя строка чтение из файла, и, наконец, открытый файл, готовый для чтения следующей строки (и что-то отличное между ними, чтобы гарантировать, что нормальный лексикографический порядок не приведет к случайной попытке сравнить два открытых файла, что приведет к ошибке). Я думаю, что некоторый код, вероятно, лучший способ объяснить общую идею, поэтому затем я отредактирую этот ответ, чтобы предоставить код (однако у меня нет времени на тестирование его, поэтому примите его как псевдокод, предназначенный для донести идею; -).

import heapq

def merge(inputfiles, outputfile, key):
  """inputfiles: list of input, sorted files open for reading.
     outputfile: output file open for writing.
     key: callable supplying the "key" to use for each line.
  """
  # prepare the heap: items are lists with [thekey, k, theline, thefile]
  # where k is an arbitrary int guaranteed to be different for all items,
  # theline is the last line read from thefile and not yet written out,
  # (guaranteed to be a non-empty string), thekey is key(theline), and
  # thefile is the open file
  h = [(k, i.readline(), i) for k, i in enumerate(inputfiles)]
  h = [[key(s), k, s, i] for k, s, i in h if s]
  heapq.heapify(h)

  while h:
    # get and output the lowest available item (==available item w/lowest key)
    item = heapq.heappop(h)
    outputfile.write(item[2])

    # replenish the item with the _next_ line from its file (if any)
    item[2] = item[3].readline()
    if not item[2]: continue  # don't reinsert finished files

    # compute the key, and re-insert the item appropriately
    item[0] = key(item[2])
    heapq.heappush(h, item)

Конечно, в вашем случае, в качестве функции key вам понадобится функция, которая извлекает домен верхнего уровня по строке имени домена (с завершающим символом новой строки) - в предыдущем вопросе вы уже указали модулю urlparse как предпочтительнее для манипулирования строками для этой цели. Если вы настаиваете на манипуляции со строками,

def tld(domain):
  return domain.rsplit('.', 1)[-1].strip()

или что-то в этом роде, вероятно, является разумным подходом при этом ограничении.

Если вы используете Python 2.6 или выше, heapq.merge является очевидной альтернативой, но в этом случае вам нужно подготовить итераторы самостоятельно (включая гарантию того, что «объекты открытого файла» никогда не будут сравниваться случайно ...) с аналогичным подходом «украсить / украсить» из того, что я использую в более переносимом коде выше.

3 голосов
/ 25 августа 2010

Вы хотите использовать сортировку слиянием, например, heapq.merge. Я не уверен, позволяет ли ваша ОС одновременно открывать 1000 файлов. Если нет, возможно, вам придется сделать это за 2 или более проходов.

2 голосов
/ 25 августа 2010

Почему бы вам не разделить домены по первой букве, поэтому вы просто разбили бы исходные файлы на 26 или более файлов, которые могли бы называться примерно так: domains-a.dat, domains-b.dat.Затем вы можете полностью загрузить их в ОЗУ, отсортировать их и записать в общий файл.

Итак: 3 входных файла, разбитых на 26+ исходных файлов, 26+ исходных файлов можно загрузить по отдельности, отсортировать в ОЗУ изатем записывается в объединенный файл.

Если 26 файлов недостаточно, я уверен, что вы можете разбить на еще больше файлов ... domains-ab.dat.Дело в том, что файлы дешевы и с ними легко работать (на Python и многих других языках), и вы должны использовать их в своих интересах.

1 голос
/ 25 августа 2010

Ваш алгоритм объединения отсортированных файлов неверен. Вы читаете по одной строке из каждого файла, находите элемент с наименьшим рейтингом среди всех прочитанных строк и записываете его в выходной файл. Повторите этот процесс (игнорируя все файлы, находящиеся в EOF), пока не будет достигнут конец всех файлов.

0 голосов
/ 25 августа 2010
#! /usr/bin/env python

"""Usage: unconfuse.py file1 file2 ... fileN

Reads a list of domain names from each file, and writes them to standard output grouped by TLD.
"""

import sys, os

spools = {}

for name in sys.argv[1:]:
    for line in file(name):
        if (line == "\n"): continue
        tld = line[line.rindex(".")+1:-1]
        spool = spools.get(tld, None)
        if (spool == None):
            spool = file(tld + ".spool", "w+")
            spools[tld] = spool
        spool.write(line)

for tld in sorted(spools.iterkeys()):
    spool = spools[tld]
    spool.seek(0)
    for line in spool:
        sys.stdout.write(line)
    spool.close()
    os.remove(spool.name)
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...