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

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

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.