Python - чистый подход к этой проблеме?

Question

У меня проблемы с выбором лучшей структуры данных для решения проблемы.

Проблема заключается в следующем:

1. У меня есть вложенный список идентификационных кодов, где подсписки имеют разную длину.

   li = [['abc', 'ghi', 'lmn'], ['kop'], ['hgi', 'ghy']]
   

2. У меня есть файл с двумя записями в каждой строке; идентификационный код и номер.

   abc      2.93  
   ghi      3.87  
   lmn      5.96  
   

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

В какую структуру данных следует читать файл с числами?

Кроме того, как бы вы перебрали указанную структуру данных для возврата i.d. с наибольшим номером, который соответствует i.d. в подсписке?

Спасибо, S: -)

Answer 1

Вы можете прочитать файл в словарь (string => int), а затем использовать понимание списка, чтобы получить максимальный идентификационный код из каждого подсписка.

d = {}
with open("data", 'rb') as data:
  for line in data:
    key, val = line.split(' ')
    d[key] = float(val)

ids = [max(sublist, key=lambda k: d[k]) for sublist in li]

Для Python 2.4 используйте:

ids = []
for sublist in li:
  subnums = map(lambda x: d[x], sublist)
  ids.append(sublist[subnums.index(max(subnums))])

Как уже отмечалось, это O (n).

Answer 2

Мое решение предполагает, что вам нужен только самый высокий номер, а не идентификатор, связанный с ним.

Я бы прочитал коды идентификации и цифры в словаре, как это было предложено Мэтью

NEW_LIST = []
ID2NUM = {}
with file('codes') as codes:
  for line in codes:
    id, num = line.rstrip().split()
    ID2NUM[id] = num

Я добавил несколько чисел, чтобы у каждого идентификатора было значение.Мой ID2NUM выглядит следующим образом:

{'abc': 2.9300000000000002,
 'ghi': 3.8700000000000001,
 'ghy': 1.2,
 'hgi': 0.40000000000000002,
 'kop': 4.3499999999999996,
 'lmn': 5.96}

Затем обрабатывает список li:

for l in li:
  NEW_LIST.append(max([d[x] for x in l]))

>>> NEW_LIST
[5.96, 4.3499999999999996, 1.2]

Чтобы записать новый список в файл, по одному в строке:

with file('new_list', 'w') as new_list:
  new_list.write('\n'.join(NEW_LIST))

Answer 3

Как насчет хранения каждого подсписка в виде двоичного дерева поиска? Вы получите в среднем O (log n) результатов поиска.

Другой вариант - использовать max-heaps, и вы получите O (1) для получения максимального значения.