Блог

Контекст: У меня немного странная проблема: давайте рассмотрим 2 кортежа, один из которых является подмножеством другого размера N-1.

 node = (40, 50, 60, 80)
adj_node = (40, 50, 60)
  

Как вы можете видеть, я ссылаюсь на эти комбинации как на узлы из сетевого графика. Префикс adj_ обозначает adjacent . Алгоритм раскрашивает график, то есть находит альтернативное значение для каждого узла. Суффикс alt_ будет означать alternative .

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

 def compute_deviation_between_node_alternative_and_adj_node_alternative(node,
                                            node_alt, adj_node, adj_node_alt):
"""
4 tuples in input, the node, the node alternative, the adjacent node, and 
the adjacent node alternatives.
"""
# Compute
return deviation
  

Давайте рассмотрим следующий ввод:

 node = (40, 50, 60, 80)
node_alt = (39, 48, 59, 87)
adj_node = (40, 50, 60)
adj_node_alt = (42, 55, 59)
  

Каждое значение из узла или из adj_node заменяется альтернативным значением в пределах диапазона допуска /- 10%. Таким образом, 40 становится 39 альтернативным в узле и 42 в соседнем node_alternative.
Альтернативы могут быть не упорядочены. т. Е. node_alt могли бы быть (48, 39, 87, 59) .
Диапазон допусков может перекрываться, например, для 60 , оба 55 и 59 находятся в пределах диапазона допусков.

Проблемная часть кода: Шаг, который я пытаюсь реализовать, — это то, что я назвал шагом идентификации: выясните, какое альтернативное значение соответствует какому входному значению. Для этого я вычисляю расстояние между значениями и возвращаю идентификатор (или idx), в котором находится альтернативное значение.

 tolerances = [0.1 if x <= 100 else 0.2 for x in node]
distance = dict()
alt_identification = dict()
for k, x in enumerate(node):
    distance[k] = [abs(elt-1) for elt in [alt_x/x for alt_x in node_alt]]
    alt_identification[x] = list(np.where([elt <= tolerances[k] 0.00001 for elt in distance[k]])[0])
  

В приведенном выше примере вывод является:

 alt_identification
Out[67]: {40: [0], 50: [1], 60: [2], 80: [3]}
  

То же самое делается для альтернативы смежного узла.

 distance = dict()
adj_alt_identification = dict()
for k, x in enumerate(node):
    distance[k] = [abs(elt-1) for elt in [alt_x/x for alt_x in adj_node_alt]]
    adj_alt_identification[x] = list(np.where([elt <= tolerances[k] 0.00001 for elt in distance[k]])[0])
  

Вывод:

 adj_alt_identification
Out[66]: {40: [0], 50: [1], 60: [1, 2], 80: []}
  

Проблема: у меня есть разные сценарии, которые могут возникнуть.

Сценарий 1: каждое значение было идентифицировано с одним альтернативным значением. Например, это относится к тому, node где находится вывод {40: [0], 50: [1], 60: [2], 80: [3]} .

Сценарий 2: Некоторые из входных значений идентифицируются с 2 или более различными возможными альтернативными значениями. Это может произойти из-за перекрытия диапазона допуска. например

 adj_node = (40, 50, 60)
adj_node_alt = (42, 55, 54)
  

Оба 55 и 54 включены в диапазон допусков из 50 и 60 .
Вывод будет (если узел есть (40, 50, 60, 80) ):

adj_alt_identification Out[66]: {40: [0], 50: [1, 2], 60: [1, 2], 80: []}

Сценарий 3: это имеет место в предыдущем примере для adj_alt :

 adj_node = (40, 50, 60)
adj_node_alt = (42, 55, 59)
  

55 и 59 включены в диапазон допусков 60 .
Только 55 включено в диапазон допуска 50 .

Текущий результат равен:

 adj_alt_identification
Out[66]: {40: [0], 50: [1], 60: [1, 2], 80: []}
  

Вывод corret определит, что 60 не может принять значение 55 , поскольку оно уже принято 50 . Таким образом, вывод должен быть:

 adj_alt_identification
Out[66]: {40: [0], 50: [1], 60: [2], 80: []}
  

Если у кого-нибудь есть какие-либо идеи о том, как улучшить этот код, и о том, как получить правильный вывод в каждом сценарии, я бы с удовольствием услышал об этом 🙂 Я чувствую, что мой процесс идентификации неуклюж и неэффективен…

Текущий код, приводящий к правильному выводу: это беспорядок и явно неэффективный…

 def traceback(tuple_node, tuple_node_alt):
    """
    Compute which value from tuple_node_alt comes from which value from tuple_node.
    tuple_node is the input
    tuple_node_alt is the "output"
    """
    # Compute the tolerances based on the node
    tolerances = [0.1 if f <= 100 else 0.2 for f in tuple_node]

    # Traceback
    distance = dict()
    alt_identification = dict()
    for k, x in enumerate(tuple_node):
        distance[k] = [abs(elt-1) for elt in [alt_x/x for alt_x in tuple_node_alt]]
        alt_identification[x] = list(np.where([elt <= tolerances[k] 0.00001 for elt in distance[k]])[0])

    len_values = {key: len(val) for key, val in alt_identification.items()}

    if all([x <= 1 for x in len_values.values()]):
        return alt_identification
    else:
        for key, value in alt_identification.items():
            if len(value) <= 1:
                continue
            else:
                other_values = [val for k, val in alt_identification.items() if k != key]
                if value in other_values:
                   continue
                else:
                    for val in other_values:
                        set1 = set(value)
                        intersec = set1.intersection(set(val))
                        if len(intersec) == 0:
                            continue
                        else:
                            alt_identification[key] = [v for v in value if v not in intersec]

    return alt_identification