Hash-Funktion für arrays bzw. double-werte

314159265358979

Es wäre ja denkbar, dass std::less eine Spezialisierung für double hat.

Epsilon-Vergleich habe ich mich geirrt. Jaja, wieder so ein Post, den ich mir hätte sparen können. Ich weiß schon.

knivil

Testo schrieb:

Einfach dein double-Array als byte-Array interpretieren und eine der Hashfunktionen von Wikipedia nehmen.

puh. ist die reihenfolge der elemente gesichert? Also liefert 0.0,1.0 einen anderen schlüssel als 1.0,0.0 ? genau verstehe ich deinen kommentar jetzt nicht?

Weisst du was eine Hashfunktion macht und wie sie sich von einer perfekten Hashfunktion unterscheidet? Natuerlich gibt es keine Garantie, aber wit grosser Wahrscheinlichkeit unterscheiden sie sich. Aber wahrscheinlich solltest du wohl auf std::set oder std::map zurueckgreifen (nach deinen Anforderungen zu urteilen). Deine Frage ueber die Reihenfolge verstehe ich nicht, ein reinterpret_cast<int*> veraendert nicht die Reihenfolge.

314159265358979

knivil schrieb:

Deine Frage ueber die Reihenfolge verstehe ich nicht, ein reinterpret_cast<int*> veraendert nicht die Reihenfolge.

Verletzt aber die strict aliasing rule (Oder wars doch ne andere? Ist doch egal, irgend ne Regel im Standard wird verletzt!). Daher wenn dann reinterpret_cast<char*>

knivil

Bei einem double-Array als Ausgangspunkt hoffe ich einfach, dass es aehnlich wie ein int-Array bzw. int64-Array ausgerichtet ist.

314159265358979

Hoffen ist aber nicht standardkonform

knivil

Dann kuerze es doch ab und zeig mir die entsprechende Stelle ...

Weisst du was eine Hashfunktion macht und wie sie sich von einer perfekten Hashfunktion unterscheidet? Natuerlich gibt es keine Garantie, aber wit grosser Wahrscheinlichkeit unterscheiden sie sich. Aber wahrscheinlich solltest du wohl auf std::set oder std::map zurueckgreifen (nach deinen Anforderungen zu urteilen). Deine Frage ueber die Reihenfolge verstehe ich nicht, ein reinterpret_cast<int*> veraendert nicht die Reihenfolge.

So wie ich das verstehe ist die funktion zuständig für das mapping der objekte und dem hash. also generiert mir einen schlüssel nachdem dann das element abgelegt wird. perfekt ist keine hash-funktion, zumindest im sinne von kollisionsfreiheit.

ich glaube ein minimalbeispiel mit dem reinterpret_cast wäre sinnvoll. Bastelst du schnell was?

camper

knivil schrieb:

Dann kuerze es doch ab und zeig mir die entsprechende Stelle ...

3.10 Lvalues and rvalues [basic.lval] Absatz 15 (bzw. Absatz 10 in n3242)

314159265358979

Sag mal camper, kennst du die Stellen eigentlich auswendig, dass du die immer so schnell hast?

camper

314159265358979 schrieb:

Sag mal camper, kennst du die Stellen eigentlich auswendig, dass du die immer so schnell hast?

Diese eine Stelle: ja - kommt oft genug vor. Bei den meisten anderen Dingen weiß ich mittlerweile aber auch i.d.R. ungefähr, wo sie stehen müssten.

knivil

Habe ich das richtig verstanden:

Es waere in diesem Fall reinterpret_cast<char*> korrekt, so dass kein undefiniertes Verhalten verursacht wird?
Alternativ kann folgendes Union verwendet werden?

union X {
  double in;
  int64_t out;
};

X converter;
converter.in = vec[i]
int64_t value = converter.out;

314159265358979

1.) Richtig.
2.) Falsch, aber ich bin mir nicht 100 % sicher. Warte da lieber noch auf camper

camper

auch das ist UB (wobei gcc über eine Compilererweiterung verfügt, die solches type-punning zulässt, falls ein expliziter Cast verwendet wird - z.B. im Linux-Kernel findet man das oft).
Das Ganze ist UB, weil nach der Zuweisung in dem union ein double-Wert gespeichert ist, und nur dieser dort existiert (9.5/1), der folgende Zugriff folglich über ein lvalue des Typs int64_t auf einen gespeicherten Wert des Typs double zugreift - und genau das wird durch 3.10/15 verboten.
Theoretisch müsste allerdings so etwas wie

union X {
  double in;
  int64_t out;
};

X converter;
converter.in = vec[i];
memmove(&converter.out, &converter.in, sizeof converter);
int64_t value = converter.out;

erlaubt sein, und wenn der Compiler clever ist, optimiert er das memmove weg.

knivil

Du bestaetigst meine eigenen Recherchen. Schade, dass es keine "einfache" Moeglichkeit gibt, standardkonform an das Bitmuster eines doubles zu kommen. Ich habe meist den Uniontrick benutzt, aber er ist wohl gcc-spezifisch.

Bashar

An das Bitmuster kommt man schon, notfalls mit

unsigned char buffer[sizeof double]; 
memcpy(buffer, &meindouble, sizeof double);

Das Problem ist, dass das als Hashkey keine geeignete Grundlage ist, da doubles gleich sein können ( 0.0 == -0.0 ), obwohl das Bitmuster ungleich ist.

da doubles gleich sein können (0.0 == -0.0), obwohl das Bitmuster ungleich ist.

Was? Wieso das denn? Könntest Du das genauer erklären?

Bashar

0.0 und -0.0 sind zwei verschiedene Zahlen mit unterschiedlichem Bitmuster, die aber beim direkten Vergleich mittels == als gleich angezeigt werden. Das ist einfach so. Über die Gründe kann man spekulieren, aber das bringt dich auch nicht weiter.
Denormalisierte Zahlen, NaN und Inf könnten auch Probleme machen.

life

Hier übrigens die Implementierung von boost für floats bzw. doubles:

// Copyright 2005-2009 Daniel James.
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

//  Based on Peter Dimov's proposal
//  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
//  issue 6.18. 

namespace boost
{
    namespace hash_detail
    {
        inline void hash_float_combine(std::size_t& seed, std::size_t value)
        {
            seed ^= value + (seed<<6) + (seed>>2);
        }

        template <class T>
        inline std::size_t float_hash_impl2(T v)
        {
            boost::hash_detail::call_frexp<T> frexp;
            boost::hash_detail::call_ldexp<T> ldexp;

            int exp = 0;

            v = frexp(v, &exp);

            // A postive value is easier to hash, so combine the
            // sign with the exponent and use the absolute value.
            if(v < 0) {
                v = -v;
                exp += limits<T>::max_exponent -
                    limits<T>::min_exponent;
            }

            v = ldexp(v, limits<std::size_t>::digits);
            std::size_t seed = static_cast<std::size_t>(v);
            v -= seed;

            // ceiling(digits(T) * log2(radix(T))/ digits(size_t)) - 1;
            std::size_t const length
                = (limits<T>::digits *
                        boost::static_log2<limits<T>::radix>::value
                        + limits<std::size_t>::digits - 1)
                / limits<std::size_t>::digits;

            for(std::size_t i = 0; i != length; ++i)
            {
                v = ldexp(v, limits<std::size_t>::digits);
                std::size_t part = static_cast<std::size_t>(v);
                v -= part;
                hash_float_combine(seed, part);
            }

            hash_float_combine(seed, exp);

            return seed;
        }

        template <class T>
        inline std::size_t float_hash_impl(T v)
        {
            typedef BOOST_DEDUCED_TYPENAME select_hash_type<T>::type type;
            return float_hash_impl2(static_cast<type>(v));
        }
    }
}

Hashfunktion für Arrays:

// Copyright 2005-2009 Daniel James.
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

//  Based on Peter Dimov's proposal
//  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
//  issue 6.18. 

    template <class T>
    inline void hash_combine(std::size_t& seed, T const& v)
    {
        boost::hash<T> hasher;
        seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }

    template <class It>
    inline std::size_t hash_range(It first, It last)
    {
        std::size_t seed = 0;

        for(; first != last; ++first)
        {
            hash_combine(seed, *first);
        }

        return seed;
    }

    template <class It>
    inline void hash_range(std::size_t& seed, It first, It last)
    {
        for(; first != last; ++first)
        {
            hash_combine(seed, *first);
        }
    }

    template< class T, unsigned N >
    inline std::size_t hash_value(const T (&x)[N])
    {
        return hash_range(x, x + N);
    }

Nexus

Testo schrieb:

Ja, nur ist es im Allgemeinen dumm, in C++ Arrays zu verwenden. Mindestens std::array sollte schon hin

Begründung?

std::array hat gegenüber C-Arrays bei gleicher Performance folgende Vorteile:

Wertsemantik
Keine implizite Konvertierung zu Zeigern
STL-Interface (z.B. begin() , end() , size() )
Unterstützung im Debug-Modus, z.B. Indexprüfungen

std::vector oder andere STL-Container haben gegenüber mit new[] und delete[] verwalteten dynamischen Arrays folgende Vorteile, zusätzlich zu den oben genannten:

Speicherung der Anzahl Elemente
Automatische Freigabe von Speicher und damit Exceptionsicherheit und eindeutige Besitzverhältnisse
Fertige Methoden, die dynamisches Einfügen und Entfernen von Elementen sehr einfach machen

Die manuellen Varianten haben hingegen keine wirklichen Vorzüge. Wenn man sie verwendet, dann sollte das abgekapselt geschehen, z.B. um eine neue Containerklasse zu schreiben. Aber als Normal-User ist man mit STL-Containern eigentlich immer besser beraten.

Danke schonmal für die Antworten.
@Life: Wie sähe denn jetzt eine hash_map Implementierung aus wenn ich die Hash_Funktion aus der von Dir gezeigten Boost-Lib verwenden wollte? Ich sehe da nicht so richtig wie ich das Ding einbinde.

@Nexus: Wie sicher bist Du Dir dass C-Arrays gleich performant sind zu std::arrays? Kannst Du Deine Antwort auch Begründen? (evtl. Tests gemacht?)