Bienvenue sur IndexError.

Ici vous pouvez poser des questions sur Python et le Framework Django.

Mais aussi sur les technos front comme React, Angular, Typescript et Javascript en général.

Consultez la FAQ pour améliorer vos chances d'avoir des réponses à vos questions.

Combinaisons de listes enum et bitstring : optimisation possible du code ?

+3 votes

Exercice de style: montrez-moi comment je peux faire plus court (?) et surtout mieux.

Voici un programme qui sort les combinaisons possibles d'arrangement de bits d'un mot dit de 'qualité' d'un protocole de communication (IEC 61850, mais on s'en fout un peu).

Les deux octets [12 bits sur 16 d'un mot] de 'qualité' sont composés soit de 'enumerate', c'est à dire d'informations qui sont exclusivement 1 parmi n (une seule peut être True et les autres sont forcément False) et de 'bitstring' qui sont des informations qui peuvent être False ou True, toutes en même temps ou seulement une partie d'elles, ou encore aucune.

Les enumerates ne peuvent PAS être toutes à False (ou '0') : il y en a forcément une à True (ou '1').
La bitstring peut être tout à False ('0') ou tout à True ('1') ou une partie True seulement.
(je me répète, pardon)

Les enumerate sont les listes "valid" et "source".
Les bitstrings sont "others" et "detailed_qual".

Le but est de trouver toutes les combinaisons possibles des ces octets de "qualité".
Il y a 12 bits et bizarrement ça me trouve 8192 possibilités alors que 2^12 fait 4096. je me dit qu'il faut compter aussi l'ensemble vide ce qui ferait 2^13 possibilités mais mon cerveau disjoncte un peu ^^.

Valid = 1 bit (1 parmi n ; n=4)
source = 1 bit (1 parmi n ; n=2)
others = 2 bits (bitdtring)
detailed_qual = 8 bits (bitstring)
Soit 12 bits en tout.

On peut avoir "Valid + Process" tout court jusqu'à "Valid + process + Overflow + OutOfRange + BadRef + Oscillatory + Failure + OldData + Inconsistent + Inaccurate + Test + Op.Blocked" avec tous les états intermédiaires.

Les valeurs cumulées sont calculées (non complètement indiquées ici et hors sujet).

exemples de retour :

  • Valid + Process 0x0
  • Test + Op.Blocked + Overflow + OutOfRange + BadRef + Oscillatory + \
    Failure + OldData + Inconsistent + Inaccurate + Test + Op.Blocked + \
    Questionable + Process 0x3ff

etc. je n'en mets que 2.


Ma question :

La fonction "getcombiwith_enum()" prend un max de temps (quelques secondes) d'après un profilage (mais elle est déjà chargée de toutes les combinaisons). Est-ce que je m'y prend bien pour analyser les infos ou est-ce que :
1) je pourrais faire plus court,
2) ou être plus rapide avec une autre écriture.

Pour getallcombination() j'ai lâchement pomper sur internet mais pour format_combination() je sens que je peux faire mieux. Une idée ?

Suis ouvert à toute critique.


import itertools
import pathlib

# ### VARIABLES ###
# --- Enumerates - 1 amongst n
valid = [('Valid', '0x0000'),
         ('Invalid', '0x0001'),
         ('Reserved', '0x0002'),
         ('Questionable', '0x0003')]
source = [('Process', '0x0000'),
          ('Substituted', '0x0400')]

# --- 'bitstring'
# all remaining bits
others = [('Test', '0x00'),
          ('Op.Blocked', '0x00')]

# Detailed Quality - bitstring : any of those can be set
detailed_qual = [('Overflow', '0x0004'),
                 ('OutOfRange', '0x0008'),
                 ('BadRef', '0x0010'),
                 ('Oscillatory', '0x0020'),
                 ('Failure', '0x0040'),
                 ('OldData', '0x0080'),
                 ('Inconsistent', '0x0100'),
                 ('Inaccurate', '0x0200')]

# list of 'to be combined': Test, OpBlocked and Detailed Quality are not
# mutually exclusive. They can be added to get a larger list to process.
to_be_combined = others + detailed_qual

def get_combi_with_enum(a_list, an_enumerate):
    """
    Returns all possible combinations from a_list coupled with a '1 amongst
    n' list of items.
    """
    ret_list = []
    for list_item in a_list:
        list_text, list_val = list_item
        for item_enum in an_enumerate:
            txt_enum, val_enum = item_enum
            # If list_item is not empty
            if len(list_text) > 0:
                txt_res = list_text + " + " + txt_enum
                val_res = list_val + int(val_enum, 16)
                ret_list.append([txt_res, val_res])
            else:
                txt_res = txt_enum
                val_res = int(val_enum, 16)
                ret_list.append([txt_res, val_res])

    return ret_list


def get_all_combination(a_list):
    """
    Return a list of all combination of the input `a_list` list.

    It returns a non-ordered combination, i.e. only AB will appear, not BA.
    That function is NOT supposed to be used with an enumerate.

    """
    if not a_list:
        raise Exception("A list shall be supplied")

    # -- Searching for all combinations
    all_combination = []

    # Calculates all combinations
    for l in range(0, len(a_list) + 1):
        for subset in itertools.combinations(a_list, l):
            # print(list(subset), len(subset))
            all_combination.append(list(subset))

    # then format the resulting list so that all text within a subset is
    # merged into one with " + " in between and all values are summed up.
    ret_list = format_combination(all_combination)
    return ret_list


def format_combination(list_comb):
    # --- Formats the list : format the text in the form of
    # 'xxx + yyy + zzz + ...' and also sum up the values.

    # temporary elements
    temp_txt = []
    temp_val = []
    # First element in item_list ? If yes, we don't add " + " in string.
    first = True
    # Returned list
    ret_list = []

    # Processes elements: Text and Val
    for item_list in list_comb:
        for item in item_list:
            item_text, item_val = item
            # if first time we add a text / value, we don't want to add
            # the " + " string. We decode the string to hex.
            if first:
                temp_txt = item_text
                temp_val = int(item_val, 16)
                first = False
            else:
                # Builds text member by adding all text part of the
                # item_list separated with a " + ". Also add the
                # hexadecimal-to-decimal converted value to existing
                # value.
                temp_txt += " + " + item_text
                temp_val += int(item_val, 16)
        # Records the new member to the existing list
        ret_list.append([temp_txt, temp_val])
    return ret_list


def main():
# For my information : endianness of the computer we are.
#    debug = True
#    if debug:
#        import sys
#        print("Endianness here = {} endian".format(sys.byteorder))

    # Gets all combinations from the bitstring
    combi_bitstring = get_all_combination(to_be_combined)

    # Gets additional combinations with 'Validity'
    with_validity = get_combi_with_enum(combi_bitstring, valid)
    # Get final combination with 'Source'
    final_combi = get_combi_with_enum(with_validity, source)

    print("Il y a {} combinaisons possible.".format(len(final_combi)))

    # -- Saving information to file
    my_path = pathlib.Path('.')
    my_file = my_path / "61850combi.txt"

    print("Saving to file <{}> ...".format(my_file), end='', flush=True)
    # with my_file.open('w') as f:
    #     for item in final_combi:
    #         print("{}\t{}".format(item[0], hex(item[1])), file=f)
    print(" Done.")


if __name__ == "__main__":
    main()
demandé 18-Avr-2015 par Agagax (182 points)

pourquoi codes-tu les valeurs unitaires en hexa?

Les valeurs indiquées sont celles de la norme. Afin de me repérer plus facilement, j'ai trouvé préférable d'entrer les mêmes, c'est à dire les valeurs hexa. Au lieu de mettre 1, j'ai mis ce que dis la norme : "0x01". De plus, ça permet de garder le même type de notation et pour les valeurs faibles (0x01) et pour les grandes valeurs (0x200 et plus).

Il est vrai que j'aurai pu coder le double-octet lui-même en indiquant quel bit est à "1" (genre "13" pour indiquer que c'est le 14e bit qui correspond à la valeur en regard).

Cela dit, les valeurs ne sont pas un problème en soit -- d'ailleurs elles ne sont pas toutes entrées. Il est bien entendu que si ma notation est complètement déconnante par rapport à ce que je pourrais gagner avec une autre notation, je veux bien changer.

Néanmoins, ce sont surtout mes multiples for ... for ... if ... qui me disent qu'il doit y avoir à la fois plus simple et plus efficace (tant en lecture qu'en temps de process). Mon but ultime, est de produire un code plus lisible et plus concis qu'il ne l'est. L'exemple pompé de get_all_combination() me paraît nettement plus élégant et rapide que ce que j'avais conçu au départ (je ne connaissais pas itertools alors forcément j'avais pondu un truc assez euh ... caca).

J'avoues que j'ai la flemme de faire une réponse entière là donc je met juste une suggestion en comment : check itertools.combinations.

Il doit y avoir des erreurs de transcription dans les valeurs hexa (je pense à source et others).

Si toutes les valeurs étaient correctes, ce serait beaucoup plus simple de proposer quelque chose d'efficace. Le principe est d'utiliser les opérateurs bitwise pour séparer les informations et travailler avec.

Aussi, ton compte pour atteindre 12 bits est faux, et d'ailleurs ces données ne peuvent pas tenir sur 12 bits. 8192 est le bon résultat, puisque il y a 10 bits de bitstring et 1 parmi 4 et encore 1 parmi 2, cela fait : 2^10 * 4 * 2 = 8192.

1 Réponse

0 votes

Bon ce ne sera certainement pas complet ni optimisé, mais voilà déjà quelques pistes.

La fonction format_combination n'utilise pas les outils fournis avec les dictionnaires ni ceux des strings, c'est un peu dommage. On peut la réduire avec quelques feintes:

def format_combination(list_comb):
  ret_list = [] #the other variables don't need an init
  for item_list in list_comb:
    item_list =  dict(item_list) # change for a dictionnary 
    temp_txt = '+'.join(item_list.keys()) # concatenate keys
    temp_val = eval('+'.join(item_list.values)()) # add values
    ret_list.append([temp_txt, temp_val])
  return ret_list

Pour getcombiwith_enum je pense qu'on peut faire la même chose mais je n'ai pas réussi à pousser le truc jusqu'au bout.

def get_combi_with_enum(a_list, an_enumerate):
  ret_list = []
  for list_item in a_list:
    list_text, list_val = list_item
    for item_enum in an_enumerate:
      txt_res, val_res = item_enum
      val_res = int(val_res,16)
      if list_text:
        txt_res = list_text + " + " + txt_res
        val_res = list_val + val_res
      ret_list.append([txt_res, val_res])
  return ret_list
répondu 20-Avr-2015 par furankun (1,434 points)
edité 6-Mai-2015 par furankun

(je sais, eval c'est caca)

tu peux supprimer ton 'eval' en utilisant sum()

Il y a aussi cette astuce vue il n'y a pas longtemps pour séparer list_comb en deux listes:

text_items, val_items = zip(*list_comb)

Plutôt que de passer par un dict pour en séparer les clés et les valeurs.

Dans get_combi_with_enum(): il est d'usage de faire l'unpacking directement dans les lignes de for.

....
for (list_text, list_val) in a_list:
    for (txt_res, val_res) in an_enumerate:
        ...

yay cool! bon du coup pour sum() on est obligés de passer par une liste, on ne peut plus le faire directement sur l'array de valeurs:

temp_text, temp_val = zip(*list_comb)
temp_text = '+'.join(temp_text)
temp_val = sum((int(elmt,16) for elmt in temp_val))

Parfait. Tu peux même économiser une paire de parenthèses:

temp_val = sum(int(elmt, 16) for elmt in temp_val)

A noter que l'expression dans sum() n'est pas une liste mais un générateur.

...