Recherche en 2D liste à l'aide de python pour trouver x,position y

J'ai 2D liste et j'ai besoin de rechercher l'index d'un élément. Comme je suis begineer à la programmation, j'ai utilisé la fonction suivante:

def in_list(c):
    for i in xrange(0,no_classes):
        if c in classes[i]:
            return i;

    return -1

Ici des classes est un 2D liste et no_classes indique le nombre de cours que j'ai.e le 1er dimesntion de la liste. -1 est renvoyé lorsque c n'est pas dans le araray. Est-il je peux optimiser la recherche?

  • vous pouvez l'optimiser si vous allez utiliser une structure de données, comme jeu, ou si vous triez vos listes à l'avance, sinon il O(N^2) algorithme et vous ne pouvez pas faire plus vite
  • Parc: pouvez-vous nous donner quelques indications sur l'optimisation de cela?
  • avez-vous des doublons dans vos listes? n'commande de l'élément de questions?
  • pas de doublons...et de l'ordre vraiment n'importe pas
  • C'est une bonne question, mais je pense qu'il serait mieux dans la révision du code de la pile d'échange.
InformationsquelleAutor ranger | 2013-08-04
  1. 3

    Vous n'avez pas besoin de définir no_classes vous-même. Utilisation enumerate():

    def in_list(c, classes):
    for i, sublist in enumerate(classes):
        if c in sublist:
            return i
    return -1
    • Comment procéder en cas de plusieurs occurrences d'un même élément?
    • Compris, vous juste n'avez pas besoin de retourner le moment où vous rencontrez la première occurence
    InformationsquelleAutor Tim Pietzcker
  2. 1

    si l'ordre n'a pas d'importance et vous n'avez pas de doublons dans vos données, je vous suggère de vous tourner 2D liste dans liste de jeux:

    >>> l = [[1, 2, 4], [6, 7, 8], [9, 5, 10]]
>>> l = [set(x) for x in l]
>>> l
[set([1, 2, 4]), set([8, 6, 7]), set([9, 10, 5])]

    Après cela, l'original de votre fonction sera de travailler plus vite, parce que la recherche de l'élément dans un ensemble est constante (alors que la recherche de l'élément de la liste est linéaire), de sorte que vous algorithme devient O(N) et pas de O(N^2).

    Notez que vous ne devez pas le faire dans votre fonction ou il serait converti à chaque fois que la fonction est appelée.

    InformationsquelleAutor Roman Pekar
  3. 0

    Utiliser la liste.index(item)

    a = [[1,2],[3,4,5]]

def in_list(item,L):
    for i in L:
        if item in i:
            return L.index(i)
    return -1

print in_list(3,a)
# prints 1
    • vous devez ajouter essayer sauf si vous souhaitez utiliser l'indice - voir docs - Return the index in the list of the first item whose value is x. It is an error if there is no such item. docs.python.org/2/tutorial/datastructures.html
    • Il n'est pas possible qu'il y ait d'erreur ici parce que j'ai est certainement à l'intérieur de la liste, car il fait partie de la liste qui nous parcourir. Pas besoin d'essayer, sauf qu'ici.
    • oups, ne pas voir cela, merci de modifier la réponse en quelque sorte, afin que je puisse unvote mon -1
    • pas de problème, vous pouvez appuyez simplement sur erreur à nouveau ce qui devrait annuler le downvote.
    • il n'est pas possible de unvote après un certain laps de temps 🙁 sauf si la réponse est édité
    • ok, édité répondre

    InformationsquelleAutor Pawel Miech
  4. 0

    Si votre "2D" de la liste est de forme rectangulaire (même nombre de colonnes pour chaque ligne), vous devez le convertir en un numpy.ndarray et utiliser numpy fonctionnalités pour faire de la recherche:

    a = np.array(c)
i,j = np.where(a==element)

    i et j doit contenir la ligne et de la colonne indices, respectivement.

    Exemple:

    a = np.array([[1,2],
              [3,4],
              [2,6]])
i,j = np.where(a==2)
print i
#array([0, 2])
print j
#array([1, 0]))
    InformationsquelleAutor Saullo G. P. Castro