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

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?)

volkard

Testo schrieb:

@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?)

Das ist eine Binsenweisheit.

life

Testo schrieb:

@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.

http://www.boost.org/doc/libs/1_47_0/doc/html/hash/tutorial.html

Das 2. Beispiel sieht für dich passend aus.

Das ist eine Binsenweisheit.

Soll jetzt nicht aggressiv wirken. Ich will nur etwas lernen:
Nur weil es jeder sagt heißt es nicht dass es stimmt. Wenn alle aus dem fenster springen springe ich nicht unbedingt aus dem fenster.

Könnte es sein, dass die STL mit ihren containern im worst case nen tick langsamer als C-Arrays ist? Allerdings ist der tick so klein dass es wohl gar nicht ins gewicht fällt?

SeppJ

Testo schrieb:

Könnte es sein, dass die STL mit ihren containern im worst case nen tick langsamer als C-Arrays ist? Allerdings ist der tick so klein dass es wohl gar nicht ins gewicht fällt?

Im Worst-Case dürfen die tatsächlich langsamer sein. Worst-Case ist hier aber kein Anwenungsfall sondern eine Worst-Case Implementierung. Die darf theoretisch nämlich beliebig viel Unsinn machen, sogar Warteschleifen einbauen. Die Container in der Standardbibliothek von MSVC sind so ein Fall wo alle paar Wochen hier jemand mit einem Benchmark auftaucht der beweist, wie viel schneller die C-Methoden doch sind. Dabei haben sie bloß nicht das Handbuch ihres Compilers gelesen, bei dem noch irgendwelche tollen Flags gesetzt werden müssen, damit die Container keine Laufzeitprüfungen machen.
Ist das jedoch ohne überflüssige Sicherheitsvorkehrungen implementiert, dann ist vector exakt so schnell wie ein dynamisches Array und array exakt so schnell wie ein statisches Array. Ich schreibe exakt, denn das ist es wirklich. vector ist intern ein dynamisches Array, array ist intern ein statisches Array, beide haben bloß ein abstrahiertes Interface und das gibt es in C++ gratis (zumindest wenn man die Compileroptimierungen einschaltet).

Die anderen Container (list, set, map, ...) haben wiederum ganz andere Eigenschaften und hängen normale Arrays entweder weit ab oder sind viel langsamer, je nachdem was man mit ihnen macht.

volkard

Testo schrieb:

Könnte es sein...

Wenn ich doch nur jemanden kennen würde, der die Zeit und Muße hat, das mal genau zu messen. Starke Fehlereinflüsse sind:

Anderer Prozess kommt dran. Abhilfe: Oft messen, 1000-mal und den schnellstan Lauf nehmen, nicht wie immer vorgeschlagen den Durchschnitt.

Nicht -march=native und -O3 haben oder Compiler kennt Deinen Prozessor nicht gut genug und aligned Schleifen, Funktionseintritte oder Variablen nicht gut. Abhilfe: Auch mal mit anderer Funktionsreihenfolge compilieren und mit einer SInnlostätigkeit davor.

Der Compiler optimiert alles weg. Abhilfe: Es muß was berechnet werden, das alle Schritte miteinbezueht, und das Ergebnis muß am Ende ausgegeben werden.

Und natürlich fehlerprüfungen von MSVC.

Damit kann man Testcode auf 5 signifikante Stellen ausmessen. Kein Witz, ich habe regelmäßig 5 stabile Stellen.