эффективно находить элементы в списках ассоциаций Python - PullRequest
1 голос
/ 14 июня 2010

У меня есть набор списков, которые выглядят так:

conditions = [
["condition1", ["sample1", "sample2", "sample3"]],
["condition2", ["sample4", "sample5", "sample6"],
...]

как я могу эффективно и элегантно делать следующие вещи в Python?

  1. Найти все элементы в определенном состоянии?

    например. получить все образцы в условии2. Прямо сейчас я могу сделать:

    for cond in conditions:
      cond_name, samples = cond
      if cond_name == requested_cond:
        return samples
    

    но это неуклюже.

  2. Найти упорядоченное объединение списка условий? Например. ordered_union(["condition1", "condition2"], conditions) должен вернуть:

    ["sample1", "sample2", "sample3", "sample4", "sample5", "sample6"]
    

Как я могу сделать это эффективно в Python? Есть, наверное, умные лайнеры?

Ответы [ 4 ]

6 голосов
/ 14 июня 2010

Это больше похоже на работу для dict:

conditions = {
"condition1": ["sample1", "sample2", "sample3"],
"condition2": ["sample4", "sample5", "sample6"],
...}

Затем вы можете получить "упорядоченный союз", используя

>>> conditions["condition1"]+conditions["condition2"]
['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']

В Python 3.1 или 2.7 выможно сохранить порядок, используя OrderedDict вместо:

from collections import OrderedDict
conditions = OrderedDict([
["condition1", ["sample1", "sample2", "sample3"]],
["condition2", ["sample4", "sample5", "sample6"]]
])

Затем вы можете получить «упорядоченный союз», также для OrderedDicts произвольного размера:

>>> import itertools
>>> [item for item in itertools.chain(*conditions.values())]
['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']
4 голосов
/ 14 июня 2010

Ну, хорошо, если вы вынуждены сохранять эту неуклюжую структуру данных, вы не можете ожидать многого. Однострочный эквивалент вашего первого решения будет выглядеть примерно так:

def samplesof(requested_cond, conditions):
    return next(s for c, s in conditions if c==requested_cond)

а для второго, если вы настаиваете на однострочниках, это будет что-то вроде:

def ordered_union(the_conds, conditions):
    return [s for c in the_conds for s in samplesof(c, conditions)]

Существуют более быстрые способы решения второй проблемы, но все они многострочные, например ::100100

aux_set = set(the_conds)
samples_by_cond = dict((c, s) for c, s in conditions if c in aux_set)
return [s for c in the_conds for s in samples_by_cond[c]]

Обратите внимание, что причина, по которой этот последний подход является более быстрым, заключается в том, что он использует правильные структуры данных (набор и дикт) - к сожалению, он должен создавать их сам, поскольку входящий вложенный список conditions действительно неправильная структура данных.

Не могли бы вы инкапсулировать conditions как переменную-член класса, который строит решающие (правильные, быстрые) вспомогательные структуры данных только один раз? E.g.:

class Sensible(object):
  def __init__(self, conditions):
    self.seq = []
    self.dic = {}
    for c, s in conditions:
      self.seq.append(c)
      self.dic[c] = s
  def samplesof(self, requested_condition):
    return self.dic[requested_condition]
  def ordered_union(self, the_conds):
    return [s for c in the_conds for s in self.dic[c]]

Теперь что быстро и элегантно!

Я предполагаю, что вам нужно self.seq (последовательность условий) для чего-то другого (это определенно не нужно для двух упомянутых вами операций!), И что в этой последовательности и в примерах нет повторений ( какими бы ни были ваши настоящие характеристики, их будет не сложно принять, но вслепую пытаться угадать их, когда вы ничего не упоминаете о них будет очень сложным и бессмысленным;

2 голосов
/ 15 июня 2010

По 1-му вопросу:

>>> dict(conditions)['condition1']
['sample1', 'sample2', 'sample3']

По # 2 (не совсем понятно, что вы подразумеваете под «упорядоченным объединением», поэтому я предполагаю, что «упорядоченные списки объединяются в порядке»):

>>> tmpdict = dict(conditions)
>>> sum( map(tmpdict.get, ["condition1", "condition2"]), [] )
['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']

пс.пример не рекомендуется для правильной критики AM - что из-за проблем с реализацией sum() демонстрирует квадратичное поведение с увеличением размера списка.Вместо этого я предлагаю код ниже:

>>> import operator
>>> tmpdict = dict(conditions)
>>> reduce(operator.iadd, map(tmpdict.get, ["condition1", "condition2"]), [] )
['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']
2 голосов
/ 14 июня 2010

Вам нужно использовать dict (словарь) вместо list. Кроме того, вы можете хранить сэмплы в set, если вам нужны эффективные операции на основе множеств.

conditions = { "condition1" : set(["sample1", "sample2", "sample3"]),
               "condition2" : set(["sample4", "sample5", "sample6"]) }

print conditions["condition2"]
# set(['sample5', 'sample4', 'sample6'])
union = conditions["condition1"].union(conditions["condition2"])
print sorted(union)
# ['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']
...