SaladTomatOnion Le blog qui mange trois fruits et légumes

16Août/160

Vérifier qu’une liste est une sous-liste d’une autre en python

Voici une petite recette "force brute" pour vérifier qu'une liste est une sous-liste d'une autre. Je n'utilise pas les fonctions d'intersection des sets, car je considère mes listes avec leur ordre, et la possibilité de doublons.

Je prends donc une fenêtre glissante de la longueur de ma sous-liste potentielle, et je superpose la sous-liste au contenu de la fenêtre courante pour vérifier l'égalité. Pour ce faire, je hache ma plus grande liste en morceaux en commençant à chaque itération une case plus loin, tout simplement, et tout brutalement.

Voici le code:

def is_sublist(sublist, superlist):
    '''
    Checks whether 'sublist' is a sublist of 'superlist'.
    Both arguments must be typed list or tuple.
    '''
    if not isinstance(sublist, (list, tuple)) or not isinstance(sublist, (list,tuple)):
        raise TypeError("Both 'sublist' and 'superlist' must be lists or tuples.")
    # Return early if candidate sublist is longer than superlist
    if len(sublist) > len(superlist):
        return False
    else:
        for chunk in (superlist[i:i+len(sublist)] for i in range(0, len(superlist)-len(sublist)+1)): 
            if chunk == sublist:
                return True
        return False

On se rend compte que dans le pire cas (pas de correspondance ou la correspondance est à la fin), je vais avoir à parcourir ma sur-liste entièrement, voire plus que ça, selon l'implémentation du slicing (parcours jusqu'à l'index de départ, puis parcours jusqu'à l'index de fin de la tranche). Il faudrait que je vérifie la dite implémentation en CPython pour en avoir le cœur net.

Ceci dit, pour les autres cas que le pire, notons que j'ai utilisé un générateur (superlist[i:…] for i in …) et non une liste (avec des parenthèses et non des crochets), de façon à ne retourner les tranches qu'au moment où l'on en a besoin. La même ligne avec des crochets [] constituerait la liste entière avant d'itérer, alors que là je crée mes tranches au fur et à mesure que j'avance.

Je n'ai pas encore réfléchi à une méthode plus optimale, mais vu que je souhaite rester dans le cas général (non ordonné, avec des doublons possibles, etc.), j'ai l'impression qu'on ne pourra pas faire moins complexe. Si vous avez une idée, n'hésitez pas à laisser un commentaire.

8Août/160

Un moteur de recherche descriptif pour retrouver un film

Un nouveau site pour quand on ne se souvient plus du titre d'un film!

Ça se passe à cette adresse: http://www.whatismymovie.com/.

La particularité du site est qu'il peut simplement retrouver un film partant d'une description en langage naturel (en anglais). Apparemment, le moteur d'indexation est une IA capable d'analyser automatiquement le contenu visuel des films pour en tirer des informations sur les personnages, l'action, les lieux, etc.

Selon ma source, c'est une startup finlandaise basée à l'université de Oulu qui est à l'origine du moteur de recherche.

J'ai fait quelques essais, et ça semble marcher plutôt pas mal!

L'article source, sur Independant UK (en anglais): http://www.independent.co.uk/[...]nd-films-a6936651.html

8Août/160

Le clavier au bout des doigts

tap1

Aujourd'hui, on tapote discrètement. Je suis tombé sur ce projet d'un nouveau type de clavier sans fil, appelé TAP. C'est un "wearable", comme on dit, et pourrait être très intéressant pour le mobile. Le principe m'a l'air assez novateur, car ils essayent de sortir des paradigmes habituels pour les outils de saisie de texte.

5Août/160

Facebook remplit automatiquement une description des photos

C'est totalement par hasard que j'ai remarqué, sur Facebook web, que la propriété alt des balises <img/> était pré-remplie, et ce, apparemment, de façon automatique.

Pas étonnant: Facebook a une équipe R&D qui travaille dur à mettre en place des IA et des algorithmes d'apprentissage profond.

Avec l'inspecteur de page de mon navigateur, j'ai pu en voir les résultats. Voici deux exemples.

4Août/160

Déformations de texture pour thermoformage

Aujourd'hui, on ne choisit pas entre le dessert et le (thermo)formage.

Je viens de tomber sur cette vidéo qui explique un procédé industrialisable pour créer des plastiques thermoformés avec des textures précises.

Dans le principe, ils créent un moule de thermoformage avec de l'impression 3D, et dans le même temps calculent la déformation à appliquer à la texture pour l'imprimer à plat sur la feuille de plastique, de façon à ce qu'elle colle aux reliefs une fois le formage terminé. Le résultat est vraiment sympa. Selon eux, les couleurs sont plus vives et plus précises que via l'impression 3D couleur ou la peinture hydrographique des modèles nus.

C'est à voir ici:

C'est un papier signé Christian Schüller et al., ETH Zurich, IGL et Disney Research.

À propos! l'année dernière on avait vu un principe similaire pour l'hydrographie. Je ne me lasse pas de regarder cette vidéo, c'est fascinant.