Требуется более эффективное решение для вложенного цикла - PullRequest
Новая
       7

Требуется более эффективное решение для вложенного цикла

0 голосов
/ 03 марта 2010

Я пытаюсь сравнить два файла. Я перечислю два содержимого файла: 

 File 1                           File 2

"d.complex.1"                     "d.complex.1"

  1                                 4
  5                                 5
  48                                47
  65                                21

d.complex.10                    d.complex.10

  46                                5
  21                                46
 109                               121
 192                               192

В каждом файле всего 2000 d.complex. Я пытаюсь сравнить оба файла, но проблема в том, что значения, перечисленные в d.complex.1 в первом файле, должны быть проверены со всеми записями d.complex 2000 во втором файле, и если они не совпадают, они быть распечатанным. Например, в вышеуказанных файлах в file1 d.complex.1 номер 48 отсутствует в file2 d.complex.1; так что этот номер должен быть сохранен в списке (распечатать позже). С другой стороны, тот же самый d.complex.1 должен сравниваться с d.complex.10 из file2, и поскольку 1, 48 и 65 отсутствуют, их необходимо добавить в список.

Метод, который я выбрал для достижения этой цели, состоял в том, чтобы использовать множества, а затем сделать пересечение. Код, который я написал, был: 

first_complex=open( "file1.txt", "r" )
first_complex_lines=first_complex.readlines()
first_complex_lines=map( string.strip, first_complex_lines )
first_complex.close()

second_complex=open( "file2.txt", "r" )
second_complex_lines=second_complex.readlines()
second_complex_lines=map( string.strip, second_complex_lines )
second_complex.close()


list_1=[]
list_2=[]

res_1=[]
for line in first_complex_lines:
    if line.startswith( "d.complex" ):
        res_1.append( [] )
    res_1[-1].append( line )

res_2=[]
for line in second_complex_lines:
    if line.startswith( "d.complex" ):
        res_2.append( [] )
    res_2[-1].append( line )
h=len( res_1 )
k=len( res_2 )
for i in res_1:
   for j in res_2:
       print i[0]
       print j[0]
       target_set=set ( i )
       target_set_1=set( j )
       for s in target_set:
           if s not in target_set_1:
               print s

Приведенный выше код дает вывод, подобный этому (просто пример): 

1
48
65
d.complex.1.dssp
d.complex.1.dssp

46
21

109 d.complex.1.dssp d.complex.1.dssp d.complex.10.dssp

Хотя приведенный выше ответ верен, я хочу более эффективный способ сделать это, кто-нибудь может мне помочь? Также печатаются два файла d.complex.1.dssp вместо одного, что тоже нехорошо.

Я хотел бы иметь: 

d.complex.1
d.complex.1 (name from file2)
   1
   48
   65

d.complex.1
d.complex.10 (name from file2)
   1
   48
   65

Я так новичок в python, поэтому моя концепция выше может быть ошибочной. Также я никогда раньше не пользовался сетами :(. Кто-нибудь может мне здесь помочь?

Ответы [ 2 ]

1 голос
/ 03 марта 2010

Уже есть хороший ответ @MattH, сфокусированный на деталях Python по вашей проблеме, и, хотя его можно улучшить в нескольких деталях, улучшения принесут вам лишь несколько процентных пунктов эффективности - стоит, но не очень.

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

Важная часть: примерно, какой диапазон чисел будет присутствовать в файле, и примерно, сколько чисел в разделе "d.complex.N"? Вы уже сказали нам, что будет около 2000 строф на файл (и это, конечно, также важно), и создается впечатление, что в каждом файле они будут упорядочены непрерывным увеличением N - 1, 2, 3 и так далее (это так?).

Ваш алгоритм строит две карты строфы-> числа (не с максимальной эффективностью, но ответ @ MattH фокусируется на улучшении), так что неизбежно ему нужны N squared проверки строфы-строфы - так как N равно 2000, это нужно 4 миллиона таких проверок.

Рассмотрим создание перевернутых карт, чисел-> строф - если диапазон чисел и типичный размер (количество чисел в) строфе разумно ограничены, они будут более компактными. Например, если числа находятся в диапазоне от 1 до 200, а в строфах около 4 чисел, это означает, что число обычно будет в (2000 * 4) / 200 -> 40 строфах, поэтому в таких сопоставлениях будет 200 записей по 40 строф в каждой. Требуется только 200 квадратов (40000) проверок, а не 4 миллиона, чтобы получить объединенную информацию для каждого числа (тогда, в зависимости от точной потребности в формате вывода, форматирование этой информации может потребовать очень существенных усилий снова - если вам абсолютно необходимо как конечный результат 4 миллиона «секций-пар» в качестве выходных данных, тогда, конечно, нет способа избежать 4 миллионов «выходных операций, что неизбежно будет очень дорогостоящим).

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

Помните, чтобы процитировать Фред Брукс :

Покажите мне свои блок-схемы и скрыть ваши таблицы, и я буду продолжать быть мистифицированным. Покажи мне свои столы и Мне обычно не нужны ваши блок-схемы; они будут очевидны.

Брукс писал в 60-х годах (хотя его сборник «Мифический человеко-месяц» был опубликован позже, в 70-х годах), откуда странное использование «блок-схем» (где мы будем говорить код или алгоритмы) и «таблицы» (где мы бы сказали, данные или структуры данных) - но общая концепция все еще остается в силе: организация и характер ваших данных во всех видах программ, ориентированных на обработку данных (таких как ваша ), может быть даже более важным, чем организация кода, тем более что он ограничивает последний; -).

1 голос
/ 03 марта 2010

Указатели:

  • Используйте списочные или генераторные выражения для упрощения обработки данных. Более читабельно
  • Просто сгенерируйте наборы один раз.
  • Используйте функции, чтобы не повторяться, особенно выполняя одно и то же задание дважды.

Я сделал несколько предположений относительно ваших входных данных, вы можете попробовать что-то вроде этого. 

def parsefile(filename):
  ret = {}
  cur = None
  for line in ( x.strip() for x in open(filename,'r')):
    if line.startswith('d.complex'):
      cur = set()
      ret[line] = cur
    if not cur or not line.isdigit():
      continue
    cur.add(int(line))
  return ret

def compareStructures(first,second):
  # Iterate through key,value pairs in first
  for firstcmplx, firstmembers in first.iteritems():
    # Iterate through key,value pairs in second
    for secondcmplx, secondmembers in second.iteritems():
      notinsecond = firstmembers- secondmembers
      if notinsecond:
        # There are items in first that aren't in second
        print firstcmplx
        print secondcmplx
        print "\n".join([ str(x) for x in notinsecond])

first = parsefile("myFirstFile.txt")
second = parsefile("mySecondFile.txt")

compareStructures(first,second)

Отредактировано для исправлений .. показывает, насколько я полагаюсь на запуск кода для его проверки :) Спасибо, Алекс

...