Est-il rien de plus rapide que le dict()?

J'ai besoin d'un moyen plus rapide pour stocker et accéder à autour de 3 go de k:v paires. Où k est un string ou un integer et v est un np.array() qui peut être de différentes formes.
Est-il un objet, qui est plus rapide que le standard de python dict dans le stockage et la consultation d'un tel tableau? Par exemple, a pandas.DataFrame?

Autant j'ai compris python dict est une mise en œuvre rapide d'une table de hachage, il n'y a rien de mieux que pour mon cas précis?

  • Si votre utilisation de Python 3.5 ou plus bas, alors le dictionnaire construit en Python 3.6 est dit que 20 à 25% plus rapide que l'ancien dictionnaire intégré en Python 3.5. De sorte que vous pouvez obtenir de meilleures performances à l'aide de La dernière version stable de Python.
  • À moins que votre code n'a pas faire autre chose, je serais très surpris si le dictionnaire de l'accès est votre goulot d'étranglement. Avez-vous des informations de profilage montrant ce est le problème?
  • Je pense que dict sont assez rapide. Au lieu de trouver l'alternative, vous pouvez prendre dans l'optimisation reste de ton code 🙂
  • Si votre cas d'utilisation impliqués échange -- si votre structure de données de plus de RAM disponible, alors il serait la meilleure des réponses, mais il n'est pas clair si c'est le cas.
  • c'est dans la configuration de la mémoire, je suis en attente pour la libération de 3.6 en décembre pour ajouter un peu de timing pour la vitesse d'exécution (et il peut effectivement présenter un léger ralentissement si ma compréhension est correcte).
  • mon code ne passe en boucle sur les dict beaucoup de temps
  • c'est pour passée commande dict seulement...
  • Avez-vous besoin d'une boucle pour être plus rapide? Quels sont exactement ce que tu fais avec les données lorsque vous itérer à travers elle? Il n'y a pas de contexte à cette question; "Est-il rien de plus rapide que la dict()?" en fait quoi exactement?
  • en accédant à la k:v paires. Est-il le meilleur objet pour la tâche? Est-il quelque chose de plus rapide, plus efficace en terme de mémoire, etc... bien sûr, le but est de passer en boucle aussi vite que possible.
  • si votre code ne passe en boucle sur les dict, il est facile de le rendre plus rapide -- supprimer la boucle! Mais si votre code ne quelque chose à l'intérieur de la boucle (à dire d'impression, ou trouver le maximum de la valeur, ou quoi que ce soit d'autre que pass), puis si cela prend plus de temps que le dictionnaire de l'accès (et ce sera certainement le cas), l'amélioration de la dict l'accès ne sera pas améliorer votre performance nette du tout. À ce stade, vous allez avoir à montrer un peu de code si vous voulez de vrais conseils.
  • Est-il possible que vous pouvez vectoriser il? Quelles sont les opérations réalisées sur les données? Il est également intéressant de souligner que DataFrames sont beaucoup plus facile et, je crois, plus rapide, éventuellement, d'en magasin.
  • {'some_string':np.array(), ...} comment feriez-vous pour vectoriser ce? Les matrices sont de forme différente.
  • Pourquoi êtes-vous accéder à l'valeurs? Que faites-vous avec eux? Pourquoi ne pas inclure votre code jusqu'à présent?
  • Je ne suis pas en supposant que boucler sur la dict est le goulot d'étranglement de mon code. Cependant, depuis mon code pour accéder à ce dictionnaire de plus de et plus je me demande si il n'y a rien de mieux que le dict. Je ne suis pas intéressé par d'autres moyens d'accélérer mon code.

InformationsquelleAutor alec_djinn | 2016-11-19
  1. 35

    Non, il n'est rien de plus rapide qu'un dictionnaire pour cette tâche et c'est parce que la complexité de son indexation et même l'adhésion de la vérification est d'environ O(1).

    Une fois que vous avez enregistré vos articles dans un dictionnaire, vous pouvez y accéder en un temps constant. Cela dit, le problème n'est pas le processus d'indexation. Mais vous pourriez être en mesure de rendre le processus un peu plus vite en faisant quelques changements dans vos objets et de leurs types. Cela pourrait causer quelques optimisations dans sous le capot de ses activités. Par exemple, si vos cordes (touches) ne sont pas très grandes, vous pouvez stagiaire, afin d'être encaissé en mémoire plutôt que d'être créé comme un objet. Si les clés dans un dictionnaire sont internés, et la recherche de la clé est interné, les comparaisons clés (après hachage) peut être fait par un pointeur comparer au lieu d'une chaîne de comparer. Qui rend l'accès à l'objet très rapidement. Python a fourni un stagiaire() fonction au sein de sys module que vous pouvez utiliser pour cela.

    Entrez la chaîne dans la table des “internés” des chaînes et retourner la situation des internés de la chaîne – qui est la chaîne elle-même ou d'une copie. Stage de chaînes de caractères est utile pour gagner un peu de performance sur recherche dans le dictionnaire...

    Voici un exemple:

    In [49]: d = {'mystr{}'.format(i): i for i in range(30)}

In [50]: %timeit d['mystr25']
10000000 loops, best of 3: 46.9 ns per loop

In [51]: d = {sys.intern('mystr{}'.format(i)): i for i in range(30)}

In [52]: %timeit d['mystr25']
10000000 loops, best of 3: 38.8 ns per loop
    • Alors que je pense que l'OP se dirige dans la mauvaise direction, la performance est plus qu'une grand-O.
    • C'est le genre de truc que je cherchais! Il l'a fait accélérer mon code quelques pour cent. Merci!
    • Belle réponse, mais je pense que l'exemple serait plus clair si les valeurs ont été internés également des chaînes de caractères, plutôt que des nombres entiers (mais ça marche, je suppose parce que les entiers sont internés dans cette gamme, comme un détail d'implémentation)
    • En effet. Ils sont plus petits que 256 😉
    InformationsquelleAutor Kasrâmvd
  2. 3

    Non, je ne pense pas qu'il n'y a rien de plus rapide que dict. La complexité du temps de son indice de vérification est O(1).

    -------------------------------------------------------
Operation    |  Average Case  | Amortized Worst Case  |
-------------------------------------------------------
Copy[2]      |    O(n)        |       O(n)            | 
Get Item     |    O(1)        |       O(n)            | 
Set Item[1]  |    O(1)        |       O(n)            | 
Delete Item  |    O(1)        |       O(n)            | 
Iteration[2] |    O(n)        |       O(n)            | 
-------------------------------------------------------

    PS https://wiki.python.org/moin/TimeComplexity

    InformationsquelleAutor akash karothiya
  3. -4

    Vous pouvez penser de les stocker dans la structure de Données comme Trie donné votre clé est une chaîne de caractère. Même de stocker et de récupérer de Trie vous avez besoin de O(N) où N est la longueur maximale de la clé. Même chose pour calcul de hachage qui calcule le hachage de clé. De hachage est utilisée pour trouver et stocker dans une Table de Hachage. Souvent, nous ne la considérons pas comme le hachage de temps ou de calcul.

    Vous pouvez donner un coup de Trie, Qui devrait être presque à l'égal de la performance, peut-être peu plus vite( si la valeur de hachage est calculé différemment pour dire 

    HASH[i] = (HASH[i-1] + key[i-1]*256^i % BUCKET_SIZE ) % BUCKET_SIZE

    ou quelque chose de similaire en cas de collision, nous avons besoin d'utiliser 256^j'.

    Vous pouvez essayer de les stocker dans Trie et de voir comment il se comporte.

    • La première phrase est un peu trompeuse. Le Big-O notation n'est pas sur la vitesse en général, c'est la manière dont le temps de calcul change lorsque la taille de l'entrée de changements. Alors, O(1) pourrait être terriblement lent ainsi que O(n!).
    • vrai, mais cela ne signifie pas qu'il va être rapide ou rapide que O(n'importe quoi) ou encore la manière la plus rapide parmi tous les Os possible. C'est à propos de la manière dont le montant de travaux de modifications lors de l'entrée changements de taille.
    • ...qui est-à-dire: Dans le monde réel, des facteurs constants de la matière. Un O(1) processus qui prend une constante de temps 1000ms sera souvent un pire choix que un O(n) qui prend 1ns par point d'entrée.
    • O(1) signifie "constante de temps", qui signifie "quelle que soit l'entrée est, le temps de calcul est le même". Sudoku résolution de est à temps constant si nous venons d'examiner toutes les possibilités, mais c'est plus lent que de nombreux algorithmes.
    InformationsquelleAutor sonus21