Intersection of "viel" arrays :-)

[Slobo]

hi,

Ziel: In mehreren Arrays nach gemeinsamen Elementen suchen (Intersection).

In Perlfaq4 habe ich Einleitung gefunden die beschreibt
wie man gemeinsame Elemente ZWEI Arrays findet.

Habe auch versucht dieses zu adaptieren das es ein Array
liefert mit gemensamen Elementen -> fehlgeschlagen.

Habe auch gedacht eine Funktion zu basteln die
als Input einige Parameter kriegt - der Aufruf wurde ungef.
so aussehen:

&liefere_mir_gemensame_elemente($x,@array1,@array2,...)
wo
$x = "$a $a1 $a2 $a3 ...";
währe, und $a (der Anzahl der Arrays), $a1, $a2 ...
(der Elementenanzahl des Arrays @array1, @array2 ...)

Die Funktion wurde dann mehrere (zweier-Vergleiche) machen, abbrechen (FALSCH) wenn der @intersection-array irgendwann mal leer wird (ohne die Gesamtzahl der benötigten Vergleiche zu ereichen), oder denn array
zurückliefern (WAHR).

Das ganze währe fast ein neues Modul (Array::Intersect) ;-)

Habe aufgehört (ist zu hoch für mich - zur Zeit) :-(

Habe auch ein Modul mit verwandtem Thema gefunden
(Bit::Vector) - der vergleicht aber bits und nicht
Listen bzw. Arrays.

Ich habe viellecht ganz falsches Ansatz verfolgt -
vielleicht liege ich ganz nah - ICH WEIS ES NICHT.

Ideen ? Oder Lösungen ?

bye

Slobo

[Frank Schönmann]

hi!

Ziel: In mehreren Arrays nach gemeinsamen Elementen suchen (Intersection).

Ok, es war nicht ganz einfach, aber ich habe eine Lösung gefunden :)

=== cut ===
#!/usr/bin/perl

@a = ("eins", "zwei", "drei", "vier", "fuenf");
@b = ("zwei", "drei", "fuenf");
@c = ("eins", "drei", "fuenf");
@d = ("drei");

print &intersect(@a, @b, @c, @d);

sub intersect
{
  for (@{scalar shift})
  {
    $union[0]{$_} = 1;
  }

while (@_)
  {
    $i++;
    for (@{scalar shift})
    {
      if ($union[$i-1]{$_}) { $union[$i]{$_} = 1; }
    }
  }

return keys %{$union[$i]};
}
=== cut ===

Die Funktion &intersect erwartet mindestens zwei Arrays als Referenzen (!), es können aber auch beliebig viele weitere sein (s.o.). Zurückgeliefert wird eine Liste der Elemente, die in jedem der angegebenen Arrays vorkommen. Ich hoffe, du kannst damit was anfangen...

Fehlermeldungen und Optimierungsvorschläge sind willkommen :)

bye, Frank!

[Slobodan]

hi,
»»Ich hoffe, du kannst damit was anfangen...

und wie !

Schon mal nachgedacht ein Modul für CPAN zu schreiben
(wenn schon nicht passiert) ? :-)

Ich habe aber trotzdem eine Frage die mich beschäftigt:
Wie weis die Funktion &intersect wo die Grenze zwischen
einzelnen Arrays in @_ ist (weil das auch ein
Array ist). Macht das die Anweisung "@{scalar shift}" ?
Wenn ja, wie ?

Viel Dank,

Slobo

P.S. Hofe nicht zu viel Kopfweh bereitet zu haben :)

[Frank Schönmann]

hi!

Schon mal nachgedacht ein Modul für CPAN zu schreiben
(wenn schon nicht passiert) ? :-)

Ist noch nicht passiert ;) Aber ein Modul, das nur aus einer einzigen Funktion besteht?

Ich habe aber trotzdem eine Frage die mich beschäftigt:
Wie weis die Funktion &intersect wo die Grenze zwischen
einzelnen Arrays in @_ ist (weil das auch ein
Array ist). Macht das die Anweisung "@{scalar shift}" ?
Wenn ja, wie ?

Das Problem hatte ich anfangs, es war allerdings auch das größte ;) Tatsächlich liefert shift nämlich auch bei übergebenen Arrays nicht das gesamte Array, sondern nur ein einziges Element. Deshalb werden der Funktion ja jetzt nicht mehr Arrays als Parameter übergeben, sondern Referenzen auf Arrays, die allerdings nur einen Skalar darstellen. Mit "@{scalar shift}" werden die Referenzen de-referenziert und ich erhalte das Array, dessen Referenz ich übergeben habe. Referenzen sind sowas ähnliches wie Pointer in C.

Das "scalar shift" wird sichergestellt, dass nur ein Skalar aus der Parameterliste gezogen wird, ob das wirklich nötig ist, weiß ich gar nicht so genau, aber es ist zumindest nicht verkehrt :-)
Evtl. sollte man die Variablen, die in der Funktion verwendet werden - zumindest $i - mit "my" lokal anlegen, damit es nicht zu evtl. Problemen kommt, wenn die Variablen schon früher im Skript verwendet wurden und dann in der Funktion falsch initialisiert sind.

Alle Klarheiten beseitigt? :)

bye, Frank!

[Slobodan]

hi!

Ist noch nicht passiert ;) Aber ein Modul, das nur aus einer einzigen Funktion besteht?

Wenn etwas so wertvoll ist wie die paar Zeilen (in der Tat sind es nicht viele) denke ich das nichts dagegen Spricht. Ausserdem können ja noch welche Funktionen (array- und hashhandling) gebraucht werden. Wer weis :)

Alle Klarheiten beseitigt? :)

Nicht ganz ;-) Ein anderes Problem:

Wie übergebe ich der Funktion mehrere Arrays wenn ihr Anzahl erst zur Laufzeit bekannt wird.

Referenzen - ich weis, aber werden die denn, die
Referenzen die schon in dem Aufruf sind, stören ?
Vielleicht eine dumme Frage - aber <so spät nachts>
blicke ich nicht mehr durch :)

Wie müsste dan der Funktionsafruf lauten wenn ich
alle zu übergebende Arrays in einem Hash habe (keys)?

Kompliziert das die Sache ?

bye
slobo

[Frank Schönmann]

hi!

Wie übergebe ich der Funktion mehrere Arrays wenn ihr Anzahl erst zur Laufzeit bekannt wird.

Genau dafür ist sie ausgelegt. Du kannst der Funktion soviele Arrays übergeben wie du willst...

Referenzen - ich weis, aber werden die denn, die
Referenzen die schon in dem Aufruf sind, stören ?
Vielleicht eine dumme Frage - aber <so spät nachts>
blicke ich nicht mehr durch :)

Leider verstehe ich die Frage auch nicht... Welche Referenzen sollen welche Referenzen in welchem Aufruf stören?

Wie müsste dan der Funktionsafruf lauten wenn ich
alle zu übergebende Arrays in einem Hash habe (keys)?

Die Funktion erwartet Arrays, also gib ihr Arrays ;) Zur Zeit musst du jedes Array, das im Hash ist, einzeln angeben. Aber du findest dafür sicher eine einfache Lösung. Mir fällt so spät nichts mehr ein ;)

bye, Frank!

[Slobodan]

hi,

Die Funktion erwartet Arrays, also gib ihr Arrays ;) Zur Zeit musst du jedes Array, das im Hash ist, einzeln angeben. Aber du findest dafür sicher eine einfache Lösung. Mir fällt so spät nichts mehr ein ;)

nach dem man ein wenig geschlaffen hat, kommen einem
Ideen und richtige Ansätze "fast" von aleine :)

Wie gesagt ich hatte Hash zu verfügung und müsste das
irgendwie an die Funktion übergeben.

Hier der (vielleicht nicht ganz so gute) Abschluss:

--------------- code ---------------
#!perl.exe -w

#print "Content-type: text/html\n\n";

nehmen wir an - wir haben vier Arrays

@a = ("eins", "zwei", "drei", "vier", "fuenf", "acht");
@b = ("zwei", "drei", "fuenf", "acht");
@c = ("eins", "drei", "fuenf", "acht");
@d = ("drei", "acht");
#@d = ("two", "five"); # für nicht erfolgreiche Suche
#######################

wir wollen nicht die Arrays an die Funktion

übergeben, sondern Hash der die Arrays enhält

für den Beispiel lese ich die Arrays erstmal in ein Hash

$anzahl_der_arrays = 4;
for($akt_lista = 1; $akt_lista <= $anzahl_der_arrays; $akt_lista++) {
if($akt_lista == 1) { push @{ $hash{$akt_lista} }, @a; }
if($akt_lista == 2) { push @{ $hash{$akt_lista} }, @b; }
if($akt_lista == 3) { push @{ $hash{$akt_lista} }, @c; }
if($akt_lista == 4) { push @{ $hash{$akt_lista} }, @d; }
}

und jetzt füllen wir den Array @aufruf (Funktionsaufruf) mit Daten

foreach $schluessell (keys %hash) {
push @aufruf, @{ $hash{$schluessell} };
}
@results = &intersect(@aufruf);

if(@results) {
print "<br>Intersection:<b> @results</b>\n";
} else {
print "<br>Leider gab es keine gemeinsamkeiten.\n";
}

sub intersect {

hier vielleicht

local $i;

for (@{scalar shift}) {
    $union[0]{$_} = 1;
  }
  while (@_) {
    $i++;
    for (@{scalar shift}) {
      if ($union[$i-1]{$_}) { $union[$i]{$_} = 1; }
    }
  }
  return keys %{$union[$i]};
}
--------------- code end ------------

biss dann

Slobo

[Michael Schröpl]

und jetzt füllen wir den Array @aufruf (Funktionsaufruf) mit Daten

foreach $schluessell (keys %hash) {
push @aufruf, @{ $hash{$schluessell} };
}
@results = &intersect(@aufruf);

Genau so etwas muß es sein.

Die Funktion erwartet eine Parameterliste, die sie mit shift abarbeitet. Jeder Wert der Parameterliste ist dann eine Referenz auf einen Array.

*Wie* Du es schaffst, diese Liste zu versurgen, ist allerdings Deine Sache. Ich vermute, Du könntest auch den Hash als Parameter an eine weitere Funktion übergeben, welche dann das "foreach" durchführt und mit "return" die Liste der Referenzen zurückliefert.

Der Aufruf sähe dann so aus, falls diese zusätzliche Funktion z. B. "loop" hieße:
    @results = &intersect (&loop (%hash));
Das hätte den Vorteil, daß Du die temporäre Variable "@aufruf" nur innerhalb der Funktion "loop" verwendest und dort lokal deklarieren kannst, ohne die Umwelt zu beeinflussen.