Incrémenter une valeur en virgule flottante python de la plus petite quantité possible

Question

J'utilise des valeurs à virgule flottante comme clés de dictionnaire.

Parfois, très occasionnellement (et peut-être jamais, mais certainement pas jamais), il y aura des collisions. Je voudrais résoudre ces problèmes en incrémentant la valeur en virgule flottante d'un montant aussi petit que possible. Comment puis-je faire ceci?

En C, je transformerais les morceaux de la mantisse pour y parvenir, mais je suppose que ce n'est pas possible en python.

Answer 1

Incrémenter un python à virgule flottante la valeur par la plus petite quantité possible

Vous n'êtes pas fou, et vous devriez être en mesure de le faire. C'est un courant de défaut de Python bibliothèque de mathématiques, malheureusement, à la fois en Python 2.X et Python3000. Il devrait y avoir un math.nextafter(x,y) en Python, mais il n'y en a pas. Il serait facile d'ajouter, puisque la plupart des compilateurs C avoir les fonctions.

Le nextafter(x,y) des fonctions de revenir le lendemain discrètement différents représentable valeur à virgule flottante suivant x dans la direction de y. Le nextafter() les fonctions sont garantis de travailler sur la plate-forme ou à un retour sensible de la valeur à indiquer que la valeur suivante n'est pas possible.

L' nextafter() fonctions font partie de la norme POSIX et ISO C99 normes et est _nextafter() dans Visual C. C99 conformes à la norme bibliothèques de mathématiques, Visual C, C++, Boost et Java tout mettre en œuvre la norme IEEE recommandé nextafter() de fonctions ou de méthodes. (Je ne sais pas honnêtement si .NET a nextafter(). Microsoft ne se soucient pas beaucoup sur le C99 et POSIX.)

Depuis Python semble aller dans le sens de soutenir la plupart des C99 fonctions mathématiques et de comportements pour le module math, l'exclusion de l' nextafter() est curieux. Heureusement, il existe des solutions de contournement facile.

Aucun des bits se tourner les fonctions ici entièrement ou traiter correctement les cas de bord, tels que les valeurs va bien 0.0, négatif 0,0, subnormals, infinities, les valeurs négatives, plus ou underflows, etc. Voici une implémentation de référence de nextafter() en C pour donner une idée de comment faire le bon peu tourner si c'est votre direction.

Il y a deux solutions pour obtenir de l' nextafter() ou d'autres exclus POSIX fonctions mathématiques en Python:

Utiliser Numpy:

>>> import numpy
>>> numpy.nextafter(0,1)
4.9406564584124654e-324
>>> numpy.nextafter(.1, 1)
0.10000000000000002
>>> numpy.nextafter(1e6, -1)
999999.99999999988
>>> numpy.nextafter(-.1, 1)
-0.099999999999999992

Lien direct vers le système de mathématiques DLL:

import ctypes
import sys
from sys import platform as _platform

if _platform == "linux" or _platform == "linux2":
    _libm = ctypes.cdll.LoadLibrary('libm.so.6')
    _funcname = 'nextafter'
elif _platform == "darwin":
    _libm = ctypes.cdll.LoadLibrary('libSystem.dylib')
    _funcname = 'nextafter'
elif _platform == "win32":
    _libm = ctypes.cdll.LoadLibrary('msvcrt.dll')
    _funcname = '_nextafter'
else:
    # these are the ones I have access to...
    # fill in library and function name for your system math dll
    print "Platform", repr(_platform), "is not supported"
    sys.exit(0)

_nextafter = getattr(_libm, _funcname)
_nextafter.restype = ctypes.c_double
_nextafter.argtypes = [ctypes.c_double, ctypes.c_double]

def nextafter(x, y):
    "Returns the next floating-point number after x in the direction of y."
    return _nextafter(x, y)

assert nextafter(0, 1) - nextafter(0, 1) == 0
assert 0.0 + nextafter(0, 1) > 0.0

Et si vraiment vous voulez vraiment un pur Python solution:

# handles edge cases correctly on MY computer 
# not extensively QA'd...
import math
# 'double' means IEEE 754 double precision -- c 'double'
epsilon  = math.ldexp(1.0, -53) # smallest double that 0.5+epsilon != 0.5
maxDouble = float(2**1024 - 2**971)  # From the IEEE 754 standard
minDouble  = math.ldexp(1.0, -1022) # min positive normalized double
smallEpsilon  = math.ldexp(1.0, -1074) # smallest increment for doubles < minFloat
infinity = math.ldexp(1.0, 1023) * 2

def nextafter(x,y):    
    """returns the next IEEE double after x in the direction of y if possible"""
    if y==x:
       return y         #if x==y, no increment

    # handle NaN
    if x!=x or y!=y:
        return x + y       

    if x >= infinity:
        return infinity

    if x <= -infinity:
        return -infinity

    if -minDouble < x < minDouble:
        if y > x:
            return x + smallEpsilon
        else:
            return x - smallEpsilon  

    m, e = math.frexp(x)        
    if y > x:
        m += epsilon
    else:
        m -= epsilon

    return math.ldexp(m,e)

Évidemment, le Numpy solution est la plus simple.

Answer 2

Tout d'abord, cette "répondre à une collision" est une assez mauvaise idée.

Si elles entrent en collision, les valeurs dans le dictionnaire doit avoir été des listes d'éléments avec une clé commune, et non d'éléments individuels.

Votre "hachage de sondage" algorithme devra boucle à travers plus d'une "petits ajustements" pour résoudre les collisions.

Et séquentielle de hachage sondes sont connus pour être inefficace.

Lire ceci: http://en.wikipedia.org/wiki/Quadratic_probing

Deuxièmement, l'utilisation math.frexp et sys.float_info.epsilon bricoler avec la mantisse et l'exposant séparément.

>>> m, e = math.frexp(4.0)
>>> (m+sys.float_info.epsilon)*2**e
4.0000000000000018

Answer 3

Au lieu d’augmenter la valeur, il suffit d’utiliser un tuple pour la clé en collision. Si vous devez les garder en ordre, chaque clé doit être un tuple, pas seulement les doublons.

Answer 4

Je recommande de ne pas supposer que les flottants (ou les horodatages) seront uniques dans la mesure du possible. Utilisez un itérateur de comptage, une séquence de base de données ou un autre service pour émettre des identificateurs uniques.

Answer 5

import sys
>>> sys.float_info.epsilon
2.220446049250313e-16