[hashing / fingerprinting] Snel hash algoritme

[Juup]

Peoples,

Om geheugen te besparen wil ik van alle URLs in een hele lange lijst (± 1 GB totaal) een fingerprint maken. Ik heb we al een algoritme (zal het posten als ik op m'n werk zit) maar dat is LANGZAAAAAM, ongeveer 2 URLs per seconde ofzo (ultra sparc IIi op 440 MHz).

Weet iemand een snellere hashfunctie?

Edit1: Ik doe het in Perl (slechte taal voor dit soort dingen, ik weet het) maar de taal maakt niet zo veel uit.

[lordsnow]

Je bedoelt zeker harde-schijf ruimte... toch?

Ik ben wel nieuwsgiering.. mischien wil je wat meer uitleggen wat 't probleem is?

Je wilt de grote van het bestand verkleinen, en het doorzoeken van dit bestand snel houden?

Hoe groot is de samenhang van de URLs? Mischien is een lichte vorm van text compressie een uitkomst?

[Alarmnummer]

deze komt van de URL class (eigelijk komt ie van de URLStreamHandler class) van Java. Maar met Perl zul je wel hetzelfde kunnen.

code:

 /**
     * Provides the default hash calculation. May be overidden by handlers for
     * other protocols that have different requirements for hashCode
     * calculation.
     * @param u a URL object
     * @return an <tt>int</tt> suitable for hash table indexing
     */
    protected int hashCode(URL u) {
      int h = 0;

      // Generate the protocol part.
      String protocol = u.getProtocol();
      if (protocol != null)
        h += protocol.hashCode();

      // Generate the host part.
    InetAddress addr = getHostAddress(u);
    if (addr != null) {
        h += addr.hashCode();
    } else {
        String host = u.getHost();
        if (host != null)
          h += host.toLowerCase().hashCode();
      }

      // Generate the file part.
      String file = u.getFile();
    if (file != null)
        h += file.hashCode();

      // Generate the port part.
    if (u.getPort() == -1)
        h += getDefaultPort();
    else
        h += u.getPort();

      // Generate the ref part.
      String ref = u.getRef();
    if (ref != null)
        h += ref.hashCode();

    return h;
    }

Deze moet vast wel meer dan 2 per seconden aan kunnen

[Alarmnummer]

kun je er geen database onder hangen ipv een enorme file? Die zijn voor dit soort dingen geboren

[Juup]

Okee meer info:
Het is werkgeheugen, geen HD stuff. Ik zou wel een DB kunnen gebruiken, maar dan verplaats ik het probleem alleen want dan heb ik een DB server nodig met veel geheugen. Ik moet CONTINUE (10x per seconde) bij nieuwe URLs checken of ik ze al gehad heb. Nu heb ik wel een lichte compressie omdat ik weet hoe de URL's er ongeveer uitzien. Ik wil MEER comprimeren.

Op dit moment gebruikt mijn Perl array van ~ 10^6 elementen meer dan 1.5GB werkgeheugen. Dat is meer dan 1kB per URL! Terwijl een URL maximaal 256 Byte is.

[Juup]

Op zaterdag 19 januari 2002 12:29 schreef Alarmnummer het volgende:
deze komt van de URL class (eigelijk komt ie van de URLStreamHandler class) van Java. Maar met Perl zul je wel hetzelfde kunnen.

code:

 /**
     * Provides the default hash calculation. May be overidden by handlers for
     * other protocols that have different requirements for hashCode
     * calculation.
     * @param u a URL object
     * @return an <tt>int</tt> suitable for hash table indexing
     */
    protected int hashCode(URL u) {
      int h = 0;

      // Generate the protocol part.
      String protocol = u.getProtocol();
      if (protocol != null)
        h += protocol.hashCode();

      // Generate the host part.
    InetAddress addr = getHostAddress(u);
    if (addr != null) {
        h += addr.hashCode();
    } else {
        String host = u.getHost();
        if (host != null)
          h += host.toLowerCase().hashCode();
      }

      // Generate the file part.
      String file = u.getFile();
    if (file != null)
        h += file.hashCode();

      // Generate the port part.
    if (u.getPort() == -1)
        h += getDefaultPort();
    else
        h += u.getPort();

      // Generate the ref part.
      String ref = u.getRef();
    if (ref != null)
        h += ref.hashCode();

    return h;
    }

Deze moet vast wel meer dan 2 per seconden aan kunnen

Ben ik nu blind of zie ik hier *DE* hashfunctie niet tussen staan?