Doubletten in List Of Hashes finden

am 25.08.2006 00:07:00 von MH

Hi *, ich habe eine List Of Hashes und suche nun Doubletten in den Has=
hes,=0Ad.h. alle, bei denen der Wert zum Key "xyz" (case ignore) gleich ist=
Am=0AEnde haette ich am liebsten einen Hash mit den doppelten Werten al=
s Key=0Aund dem Zaehler, wie oft er vorkam, als Wert. Quell-LoH: =
@loh =3D (=0A { "key01" =3D> "Val01",=0A "key02" =3D> "val02",=0A "k=
ey03" =3D> "val03",=0A ... },=0A { "key01" =3D> "val11",=0A "key02" =
=3D> "val12",=0A "key03" =3D> "val13",=0A ... },=0A { "key01" =3D> "=
VAL01",=0A "key02" =3D> "val22",=0A "key03" =3D> "val23",=0A ... }=
,=0A { "key01" =3D> "Val11",=0A "key02" =3D> "val32",=0A "key03" =3D=
> "val33",=0A ... },=0A); Zielhash: %h =3D (=0A val01 =3D> 2=
=0A val11 =3D> 2,=0A); Klar kann man das mit einer Schleife ala =
for $i ( 0 .. $#loh ) {=0A} machen. Allerdings dauert das bei 500.000 =
Eintraegen uferlos lange.=0AGibt es eine schnellere - effizientere - besser=
e Methode? Das Ganze muss unter Perl 5.8.4 bis 5.8.8 laufen. TIA.=
Ciao.=0AMichael.=0A--=20
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/

Re: Doubletten in List Of Hashes finden

am 25.08.2006 20:45:16 von Slaven Rezic

mh@mike.franken.de (Michael Hirmke) writes:

> Hi *,
>
> ich habe eine List Of Hashes und suche nun Doubletten in den Hashes,
> d.h. alle, bei denen der Wert zum Key "xyz" (case ignore) gleich ist. Am
> Ende haette ich am liebsten einen Hash mit den doppelten Werten als Key
> und dem Zaehler, wie oft er vorkam, als Wert.
>
> Quell-LoH:
>
> @loh = (
> { "key01" => "Val01",
> "key02" => "val02",
> "key03" => "val03",
> ... },
> { "key01" => "val11",
> "key02" => "val12",
> "key03" => "val13",
> ... },
> { "key01" => "VAL01",
> "key02" => "val22",
> "key03" => "val23",
> ... },
> { "key01" => "Val11",
> "key02" => "val32",
> "key03" => "val33",
> ... },
> );
>
> Zielhash:
>
> %h = (
> val01 => 2
> val11 => 2,
> );
>
> Klar kann man das mit einer Schleife ala
>
> for $i ( 0 .. $#loh ) {
> }

Marginal schneller dürfte es sein, wenn du über die Element direkt
iterierst.

> machen. Allerdings dauert das bei 500.000 Eintraegen uferlos lange.
> Gibt es eine schnellere - effizientere - bessere Methode?
>

Wie sieht dein Code genau aus?

--
Slaven Rezic - slaven rezic de

tknotes - A knotes clone, written in Perl/Tk.
http://ptktools.sourceforge.net/#tknotes

Re: Doubletten in List Of Hashes finden

am 27.08.2006 23:17:08 von Slaven Rezic

Re: Doubletten in List Of Hashes finden

am 28.08.2006 00:32:00 von MH

Slaven Rezic [slaven@rezic.de] schrieb:

[...]
>> for $i ( 0 .. $#loh ) {
>> }

>Marginal schneller dürfte es sein, wenn du über die Element direkt
>iterierst.

Hmja, aber wirklich nur marginal.

>> machen. Allerdings dauert das bei 500.000 Eintraegen uferlos lange.
>> Gibt es eine schnellere - effizientere - bessere Methode?
>>

>Wie sieht dein Code genau aus?

Hm, das Teil ist riesig.
Der fragliche Teil sieht so aus:

for $i ( 0 .. $#{ $loh } ) {
# ------------------------------------------------------------ ----
$s =3D $loh->[ $i ]{ lc( $k ) ) };
if( $s ) {
# ------------------------------------------------------------ --
$h{ lc( $s ) }++;
# ...
# ------------------------------------------------------------ --
} else {
# ------------------------------------------------------------ --
$s =3D "not_found";
$loh->[ $i ]{ lc( $k ) ) } =3D $s;
# ------------------------------------------------------------ --
} # // Ende unless( .. )
# ------------------------------------------------------------ ----
} # // Ende for( .. )

>--
>Slaven Rezic - slaven rezic de

Danke und ciao.
Michael.
--=20
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/

Re: Doubletten in List Of Hashes finden

am 28.08.2006 23:44:35 von Slaven Rezic

mh@mike.franken.de (Michael Hirmke) writes:

> Slaven Rezic [slaven@rezic.de] schrieb:
>

[...]

>
> >Code. Du k.ntest lexikalische Variablen verwenden. Diese drften
> >(ebenfalls nur marginal) schneller sein. Vielleicht auch exists()
> >verwenden, um die Existenz eines Hash-Keys zu prfen.
>
> exist auf den Hash-Key heisst aber nicht, dass sein Value nicht undef
> sein koennte, oder?
>

exists() liefert wahr, solange das Schlüssel-Wert-Paar existiert, auch
wenn der Wert undef ist.

Gruß,
Slaven

--
Slaven Rezic - slaven rezic de

tkrevdiff - graphical display of diffs between revisions (RCS, CVS or SVN)
http://ptktools.sourceforge.net/#tkrevdiff

Re: Doubletten in List Of Hashes finden

am 29.08.2006 00:33:00 von MH

Slaven Rezic [slaven@rezic.de] schrieb:

[...]=0A
>Wo kommt $k her? Egal, ich sehe nicht unbedingt etwas Verwerfliches im

Das ist eine Variable, die halt auf einen Key im Hash verweist, den ich
auf Doubletten pruefen will.

>Code. Du k.ntest lexikalische Variablen verwenden. Diese drften
>(ebenfalls nur marginal) schneller sein. Vielleicht auch exists()
>verwenden, um die Existenz eines Hash-Keys zu prfen.

exist auf den Hash-Key heisst aber nicht, dass sein Value nicht undef
sein koennte, oder?

>Gru?=0A> Slaven

Ciao.
Michael.
--=20
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/

Re: Doubletten in List Of Hashes finden

am 29.08.2006 21:16:00 von Horst Knobloch

Michael Hirmke wrote:

> ich habe eine List Of Hashes und suche nun Doubletten in den Hashes,
> d.h. alle, bei denen der Wert zum Key "xyz" (case ignore) gleich ist. Am
> Ende haette ich am liebsten einen Hash mit den doppelten Werten als Key
> und dem Zaehler, wie oft er vorkam, als Wert.
>
[Grosser Hash mit Doubletten]

Du schreibst leider nicht wie der Hash überhaupt generiert
wird. Vieleicht ist ja möglich schon beim erstellen des
Hash ebenfalls deine Statistik über Doubletten zu erstellen.
Dann brauchst du nicht hinter das mühsam wieder rauszufrickeln.

Ciao, Horst
--
When pings go wrong (It hurts me too) E.Clapton/E.James/P.Tscharn

Re: Doubletten in List Of Hashes finden

am 29.08.2006 22:35:13 von ekkehard.horner

Michael Hirmke wrote:
> Horst Knobloch [horschti2@gmx.de] schrieb:
>=20
> [...]
>=20
>=20
>>Du schreibst leider nicht wie der Hash überhaupt generiert
>>wird. Vieleicht ist ja möglich schon beim erstellen des
>>Hash ebenfalls deine Statistik über Doubletten zu erstellen.
>>Dann brauchst du nicht hinter das mühsam wieder rauszufrickeln.
>=20
>=20
> Die LoH entsteht durch Einlesen einer .csv-Datei, was wiederum ein Modu=
l
> macht. Da kann ich vermutlich nichts drehen.
> Ich habe es aber jetzt anderweitig geschafft, das ein wenig zu
> optimieren, indem ich zwei andere Schleifen danach gemerged habe.
>=20
Koennte man nicht aus der .csv-Datei mit DBI und "SELECT DISTINCT .."
bzw. "SELECT .. GROUP BY ..." die interessierenden Information
rausfischen?

Re: Doubletten in List Of Hashes finden

am 29.08.2006 23:58:47 von Thomas Jahns

mh@mike.franken.de (Michael Hirmke) writes:
> Slaven Rezic [slaven@rezic.de] schrieb:
>
> [...]
> >> for $i ( 0 .. $#loh ) {
> >> }
>
> >Marginal schneller dürfte es sein, wenn du über die Element direkt
> >iterierst.
>
> Hmja, aber wirklich nur marginal.
>
> >> machen. Allerdings dauert das bei 500.000 Eintraegen uferlos lange.
> >> Gibt es eine schnellere - effizientere - bessere Methode?
> >>
>
> >Wie sieht dein Code genau aus?
>
> Hm, das Teil ist riesig.
> Der fragliche Teil sieht so aus:
>
> for $i ( 0 .. $#{ $loh } ) {
> # ------------------------------------------------------------ ----
> $s = $loh->[ $i ]{ lc( $k ) ) };
> if( $s ) {
> # ------------------------------------------------------------ --
> $h{ lc( $s ) }++;
> # ...
> # ------------------------------------------------------------ --
> } else {
> # ------------------------------------------------------------ --
> $s = "not_found";
> $loh->[ $i ]{ lc( $k ) ) } = $s;
> # ------------------------------------------------------------ --
> } # // Ende unless( .. )
> # ------------------------------------------------------------ ----
> } # // Ende for( .. )

Da wird wohl vielfach über die Werte im Hash gegangen (es fehlt ein Tick
zu viel, als daß ich das mit Bestimmtheit sagen könnte).

Wenn die Werte aus einem festgelegten Bereich stammen wäre es das
einfachste, diese in Zahlen umzuwandeln und ein Array damit zu
indizieren, so aber könnte folgendes helfen:

use strict;
use warnings;
use Data::Dumper;

my @loh = (
{ "key01" => "Val01",
"key02" => "val02",
"key03" => "val03",
},
{ "key01" => "val11",
"key02" => "val12",
"key03" => "val13",
},
{ "key01" => "VAL01",
"key02" => "val22",
"key03" => "val23",
},
{ "key01" => "Val11",
"key02" => "val32",
"key03" => "val33",
},
);

{
my %valPosMap;
for(my $i=0; $i <@loh; ++$i)
{
my ($key, $val);
while(($key, $val) = each %{$loh[$i]})
{
if(exists($valPosMap{lc $val}))
{
push(@{$valPosMap{lc $val}}, [ $i, $key ]);
}
else
{
$valPosMap{lc $val} = [ [ $i, $key ] ];
}
}
}
my (%dupMap, $revkey, $revval);
while(($revkey, $revval) = (each %valPosMap))
{
$dupMap{$revkey} = scalar(@$revval) if(@$revval > 1);
}
print(Data::Dumper->Dumper(\%dupMap));
}

Das durchläuft jedes Element der List-of-Hashes nur genau einmal.
Vielleicht hilft's.

Thomas Jahns
--
"Computers are good at following instructions,
but not at reading your mind."
D. E. Knuth, The TeXbook, Addison-Wesley 1984, 1986, 1996, p. 9

Re: Doubletten in List Of Hashes finden

am 30.08.2006 00:05:00 von MH

Horst Knobloch [horschti2@gmx.de] schrieb:

[...]

>Du schreibst leider nicht wie der Hash überhaupt generiert
>wird. Vieleicht ist ja möglich schon beim erstellen des
>Hash ebenfalls deine Statistik über Doubletten zu erstellen.
>Dann brauchst du nicht hinter das mühsam wieder rauszufrickeln.

Die LoH entsteht durch Einlesen einer .csv-Datei, was wiederum ein Modul
macht. Da kann ich vermutlich nichts drehen.
Ich habe es aber jetzt anderweitig geschafft, das ein wenig zu
optimieren, indem ich zwei andere Schleifen danach gemerged habe.

>Ciao, Horst

Danke und ciao.
Michael.
--=20
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/

Re: Doubletten in List Of Hashes finden

am 31.08.2006 01:00:55 von Helmut Wollmersdorfer

Michael Hirmke wrote:

> Die LoH entsteht durch Einlesen einer .csv-Datei, was wiederum ein Modul
> macht. Da kann ich vermutlich nichts drehen.

Naja, die Frage ist, was der Zweck Deines Programmes ist. Wenn es nur um
das Zählen der Doubletten geht, kannst Du die csv-Datei ganz einfach
zeilenweise einlesen und in ein Hash zählen. Läuft bei 30 Mio.
Log-Zeilen täglich kreuz und quer statistisch ausgewertet in viele HoH
bzw. HoHoH recht gut.

Helmut Wollmersdorfer

Re: Doubletten in List Of Hashes finden

am 31.08.2006 01:10:46 von MH

ekkehard.horner [ekkehard.horner@arcor.de] schrieb:

[...]
>Koennte man nicht aus der .csv-Datei mit DBI und "SELECT DISTINCT .."
>bzw. "SELECT .. GROUP BY ..." die interessierenden Information
>rausfischen?

Ich fuerchte, das wird bei 500.000 Datensaetzen schon heftig, bei der
Endzahl von ca. 4-5 Mio nahezu unmoeglich.

Aber danke fuer den Hinweis.

Ciao.
Michael.
--=20
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/

Re: Doubletten in List Of Hashes finden

am 31.08.2006 01:10:46 von MH

Thomas Jahns [thomas.jahns01@lycos.de] schrieb:

[...]
>Wenn die Werte aus einem festgelegten Bereich stammen wäre es das
>einfachste, diese in Zahlen umzuwandeln und ein Array damit zu
>indizieren, so aber könnte folgendes helfen:

Leider stammen die Werte aus keinem festgelegten Bereich und koennen
auch nicht sinnvoll in Zahlen umgewandelt werden.

[...]
>Das durchläuft jedes Element der List-of-Hashes nur genau einmal.
>Vielleicht hilft's.

Trotz allem danke fuer den sehr interessanten Ansatz!

>Thomas Jahns

Ciao.
Michael.
--=20
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/

Re: Doubletten in List Of Hashes finden

am 31.08.2006 01:10:46 von MH

Michael Hirmke [mh@mike.franken.de] schrieb:

>Hi *,

[...]
>machen. Allerdings dauert das bei 500.000 Eintraegen uferlos lange.
>Gibt es eine schnellere - effizientere - bessere Methode?

Danke an alle fuer die wirklich prima Tips.
Allerdings habe ich mich wohl selbst vertan - die uferlose Laufzeit kam
nicht durch Probleme mit Schleifen o.ae. zustande, sondern durch die
schiere Speichermenge, die dabei benoetigt wurde. Ich habe den Rechner
jetzt von 2 auf 8 GB RAM aufgeruestet und es dadurch geschafft, die
Laufzeit auf 10 bis 20% der urspruenglichen Dauer zu druecken. Der
Prozess, der diese Auswertungen macht, benoetigt insgesamt ueber 7 GB an
RAM!

Ciao.
Michael.
--
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/

Re: Doubletten in List Of Hashes finden

am 31.08.2006 08:50:16 von Steffen Panning

Michael Hirmke wrote:

[...]

Ich habe den Rechner
> jetzt von 2 auf 8 GB RAM aufgeruestet und es dadurch geschafft, die
> Laufzeit auf 10 bis 20% der urspruenglichen Dauer zu druecken. Der
> Prozess, der diese Auswertungen macht, benoetigt insgesamt ueber 7 GB an
> RAM!
>
> Ciao.
> Michael.

Hallo Michael,

bist du sicher, dass die List of Hashes diesen gigantischen
Speicherverbrauch produziert?
Das erscheint mir unrealistisch, selbst wenn ich 4_000_000 eintraege im
Stil von abcdef => 'abcdef' annehme (dh kurzer string mappt auf kurzen
string).

Ich habe das auf meinem Rechner nachgestellt und dabei den schlimmsten
Fall angenommen: Eine liste von 4_000_000 Hashes mit einem Key Value
Paar. Das bedeutet, dass die Speichermenge fuer die Verwaltung der
Datencontainer im vergleich zu den eigentlichen Nutzdaten
ueberproportional hoch ist.

Der einfache Test:
perl -e 'for(1..4_000_000){ push @bar, { 'abcdefgh' => 'abcdefgh' }}
print "sleeping\n";sleep'

Das Programm 'top' zeigt bei mir anschliessend einen Speicherverbrauch
(VIRT) von 663 MB

Das ist weit von 7GB entfernt, obwohl in meinem Beipiel sehr viel
Speicher fuer die Verwaltung drauf geht.

Der extrem hohe Speicherverbrauch muss also an einer anderen Stelle
entstehen.

greets Steffen

Re: Doubletten in List Of Hashes finden

am 31.08.2006 12:04:00 von MH

Steffen Panning [ps607@t-online.de] schrieb:

>Michael Hirmke wrote:

[...]
>Hallo Michael,

>bist du sicher, dass die List of Hashes diesen gigantischen
>Speicherverbrauch produziert?

Ja.

>Das erscheint mir unrealistisch, selbst wenn ich 4_000_000 eintraege im
>Stil von abcdef => 'abcdef' annehme (dh kurzer string mappt auf kurzen
>string).

Der LoH hat nicht nur ein Key-Value-Paar jeweils, sondern 200-300!
Und die Strings sind teilweise bis 2048 Zeichen lang.
Ich habe im Beispiel nur alles auf das Minimum reduziert, um die
Situation darzustellen. Aus diesem LoH und einem zweiten baue ich eine
sehr komplexe Struktur im Speicher zusammen - eigentlich sowas wie ein
hohoholoh :) Darin sind mehrere auch untereinander verlinkte Strukturen
enthalten.
Um es mal so zu sagen - ich halte nach Durchlauf des Ganzen ein
komplettes Active Directory und ein komplettes Exchange 5.5 Verzeichnis
im Speicher.

[...]

>Der extrem hohe Speicherverbrauch muss also an einer anderen Stelle
>entstehen.

Hm, ich fuerchte nein.

>greets Steffen

Thx.
Ciao.
Michael.
--
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/

Re: Doubletten in List Of Hashes finden

am 03.09.2006 02:04:18 von Thomas Jahns

mh@mike.franken.de (Michael Hirmke) writes:
> Allerdings habe ich mich wohl selbst vertan - die uferlose Laufzeit kam
> nicht durch Probleme mit Schleifen o.ae. zustande, sondern durch die
> schiere Speichermenge, die dabei benoetigt wurde. Ich habe den Rechner
> jetzt von 2 auf 8 GB RAM aufgeruestet und es dadurch geschafft, die
> Laufzeit auf 10 bis 20% der urspruenglichen Dauer zu druecken. Der
> Prozess, der diese Auswertungen macht, benoetigt insgesamt ueber 7 GB an
> RAM!

Das erscheint mir aber doch irgendwie unelegant, hast Du mal erwogen,
das in C oder einer ähnlichen Sprache mittels eigenem Speichermanagement
(z.B. via mmap) zu kodieren? Das verlangt natürlich sich vorher über
mögliche Optimierungen bezügl. Lokalität Gedanken zu machen, aber falls
dieser Prozeß öfter läuft könnte sich das trotzdem lohnen. Denn wenn Du
7GB Speicher tatsächlich per Random-Access nutzt, ist die Hauptbremse
noch nicht einmal der Speicher sondern die Tatsache, daß die
Cache-Hierarchie ungenügend genutzt wird.

Da x Stunden Programmiererzeit heutzutage aber in vielen Fällen wohl
mehr kosten als ein paar GB Speicher, könnte das auch vergebene
Liebesmüh sein.

Thomas Jahns
--
"Computers are good at following instructions,
but not at reading your mind."
D. E. Knuth, The TeXbook, Addison-Wesley 1984, 1986, 1996, p. 9

Re: Doubletten in List Of Hashes finden

am 04.09.2006 12:39:00 von MH

Thomas Jahns [thomas.jahns01@lycos.de] schrieb:

[...]
>Das erscheint mir aber doch irgendwie unelegant, hast Du mal erwogen,
>das in C oder einer (nlichen Sprache mittels eigenem Speichermanagement

habe ich - allerdings ist es dort wesentlich komplexer zu realisieren.
Ich kann zwar C und C++, aber ich schaetze die Entwicklungszeit auf
sicher das Dreifache und zudem existiert ja das Perl-Script jetzt
bereits in voller Schoenheit, d.h. diese Entwicklungszeit muesste man
dann auch noch draufrechnen.

[...]
>Da x Stunden Programmiererzeit heutzutage aber in vielen F,len wohl
>mehr kosten als ein paar GB Speicher, k.nte das auch vergebene
>Liebesmh sein.

Nehme ich leider auch an. Fuer 1000 Euro entwickelt mir das sicher
keiner.

>Thomas Jahns

Danke und ciao.
Michael.
--=20
Michael Hirmke | Telefon +49 (911) 557999
Wilhelm-Spaeth-Strasse 52 | FAX +49 (911) 557664
90461 Nuernberg | E-Mail mailto:mh@mike.franken.de
| WWW http://www.hirmke.de/