Opened by styx-cc at 2018-07-18 02:03
User since
2006-05-20
533 Artikel
BenutzerIn
2006-05-20
533 Artikel
BenutzerIn
Ich versuche es etwas anders mit einem Beispiel:
Nehmen wir die Reihe: a2 b3 c4 d3
oder 2 * 3 * 4 * 3 oder 1*2^1 * 1*3^1 * 1*4^1 * 1*3^1
An pos. a gibt es 2 Möglichkeiten, an pos. b 3 Möglichkeiten, usw. daraus ergeben sich insgesamt 72 Möglichkeiten.
Wenn ich das korrekt verstanden habe sind das alle Variation mit Wiederholung in lexikographischer Ordnung (klein nach groß, wohlsortiert?), sicher bin ich nicht.
Wie kann ich diese Aufgabe auf Beispielsweise 3 CPUs, ungeachtet der Reihenfolge, gleichmäßig verteilen?
Mein Ansatz, ich teile die Anzahl der Kombinationen durch die Anzahl der CPUs, 72/3 = 24,
jede CPU muss also 24 Kombinationen berechnen die folgende Tabelle teilt die Arbeit auf:
Daraus folgt, n1 oder CPU1 rechnet die Kombinationen von 1 1 1 1 bis 1 2 4 3:
n2 oder CPU2 von 1 3 1 1 bis 2 1 4 3:
Und n3 oder CPU3 von 2 2 1 1 bis 2 3 4 3:
Im Prinzip brauche ich etwas wie:
my @start_end_points = split_variations([2, 3, 4, 3], 3); # kombination, anzahl cpus
Und split Variations gibt sowas wie [ [1111,1243], [1311, 2143], [2211, 2343] ] zurück.
Nach meiner Methode oben müsst ich dafür durch alle Kombinationen durchgehen, um zu ermitteln wer welchen Teil abzuarbeiten hat. Das ist bei sehr großen Variation ungünstig, zumal jede CPU seinen Teil anschließend noch mal durchgeht und nach verschiedenen Bedingungen eine Kombination zulässt oder verwirft.
Eine Idee die ich gerade habe ist, man könnte nur den Anteil der ersten CPU errechnen und weiß ja dann, da alle CPUs gleich viel zu tun haben sollen, in welchem Abstand die Kombination zu verteilen sind:
n1 oder CPU1 von 1 1 1 1 bis 1 2 4 3
n2 oder CPU2 von 1 3 1 1 bis 2 1 4 3
n3 oder CPU3 von 2 2 1 1 bis 2 3 4 3
Da ist ja ein Muster zu erkennen, was sich seit n1 wiederholt, weil der Abstand gleich bleibt. Ich kann das nur weder in Perl noch in Mathe ausdrücken.
Ich vermute es geht in die Richtung mod n und/ooder Faktorzerlegung.
Vielen Dank fürs lesen.
Edit:
Ich sehe gerade, dass die for-schleifen für CPU2 von 1 3 1 1 bis 2 1 4 3 nicht ganz korrekt sind, was wohl am Überschlag liegt bzw. daran, dass jede Reihe/Variation ein eigenes Stellenwertsystem mit sich bringt?
Last edited: 2018-07-18 21:16:28 +0200 (CEST)
Nehmen wir die Reihe: a2 b3 c4 d3
oder 2 * 3 * 4 * 3 oder 1*2^1 * 1*3^1 * 1*4^1 * 1*3^1
An pos. a gibt es 2 Möglichkeiten, an pos. b 3 Möglichkeiten, usw. daraus ergeben sich insgesamt 72 Möglichkeiten.
Wenn ich das korrekt verstanden habe sind das alle Variation mit Wiederholung in lexikographischer Ordnung (klein nach groß, wohlsortiert?), sicher bin ich nicht.
Code: (dl
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/perl -w
use strict;
my $i = 0;
for my $w (1..2) {
for my $x (1..3) {
for my $y (1..4) {
for my $z (1..3) {
$i++;
print "$w $x $y $z\n";
}
}
}
}
print $i ."\n";
styx@desktop:~$ perl permute_test.pl
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
1 1 2 2
1 1 2 3
1 1 3 1
1 1 3 2
1 1 3 3
1 1 4 1
1 1 4 2
1 1 4 3
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 2 3
1 2 3 1
1 2 3 2
1 2 3 3
1 2 4 1
1 2 4 2
1 2 4 3
1 3 1 1
1 3 1 2
1 3 1 3
1 3 2 1
1 3 2 2
1 3 2 3
1 3 3 1
1 3 3 2
1 3 3 3
1 3 4 1
1 3 4 2
1 3 4 3
2 1 1 1
2 1 1 2
2 1 1 3
2 1 2 1
2 1 2 2
2 1 2 3
2 1 3 1
2 1 3 2
2 1 3 3
2 1 4 1
2 1 4 2
2 1 4 3
2 2 1 1
2 2 1 2
2 2 1 3
2 2 2 1
2 2 2 2
2 2 2 3
2 2 3 1
2 2 3 2
2 2 3 3
2 2 4 1
2 2 4 2
2 2 4 3
2 3 1 1
2 3 1 2
2 3 1 3
2 3 2 1
2 3 2 2
2 3 2 3
2 3 3 1
2 3 3 2
2 3 3 3
2 3 4 1
2 3 4 2
2 3 4 3
72
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
1 1 2 2
1 1 2 3
1 1 3 1
1 1 3 2
1 1 3 3
1 1 4 1
1 1 4 2
1 1 4 3
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 2 3
1 2 3 1
1 2 3 2
1 2 3 3
1 2 4 1
1 2 4 2
1 2 4 3
1 3 1 1
1 3 1 2
1 3 1 3
1 3 2 1
1 3 2 2
1 3 2 3
1 3 3 1
1 3 3 2
1 3 3 3
1 3 4 1
1 3 4 2
1 3 4 3
2 1 1 1
2 1 1 2
2 1 1 3
2 1 2 1
2 1 2 2
2 1 2 3
2 1 3 1
2 1 3 2
2 1 3 3
2 1 4 1
2 1 4 2
2 1 4 3
2 2 1 1
2 2 1 2
2 2 1 3
2 2 2 1
2 2 2 2
2 2 2 3
2 2 3 1
2 2 3 2
2 2 3 3
2 2 4 1
2 2 4 2
2 2 4 3
2 3 1 1
2 3 1 2
2 3 1 3
2 3 2 1
2 3 2 2
2 3 2 3
2 3 3 1
2 3 3 2
2 3 3 3
2 3 4 1
2 3 4 2
2 3 4 3
72
Wie kann ich diese Aufgabe auf Beispielsweise 3 CPUs, ungeachtet der Reihenfolge, gleichmäßig verteilen?
Mein Ansatz, ich teile die Anzahl der Kombinationen durch die Anzahl der CPUs, 72/3 = 24,
jede CPU muss also 24 Kombinationen berechnen die folgende Tabelle teilt die Arbeit auf:
Code: (dl
)
1
2
3
4
5
6
n=3 a2 b3 c4 d3 = 72 (72/n = anzahl pro n (24))
n1) 1-1 1-2 1-4 1-3 = 24
n2) 1-1 3-3 1-4 1-3 = 12
n2) 2-2 1-1 1-4 1-3 = 12 n2) von 1 3 1 1 bis 2 1 4 3
n3) 2-2 2-3 1-4 1-3 = 24
Daraus folgt, n1 oder CPU1 rechnet die Kombinationen von 1 1 1 1 bis 1 2 4 3:
Code: (dl
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/perl -w
use strict;
my $i = 0;
for my $w (1..1) {
for my $x (1..2) {
for my $y (1..4) {
for my $z (1..3) {
$i++;
print "$w $x $y $z\n";
}
}
}
}
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
1 1 2 2
1 1 2 3
1 1 3 1
1 1 3 2
1 1 3 3
1 1 4 1
1 1 4 2
1 1 4 3
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 2 3
1 2 3 1
1 2 3 2
1 2 3 3
1 2 4 1
1 2 4 2
1 2 4 3
24
1 1 1 2
1 1 1 3
1 1 2 1
1 1 2 2
1 1 2 3
1 1 3 1
1 1 3 2
1 1 3 3
1 1 4 1
1 1 4 2
1 1 4 3
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 2 3
1 2 3 1
1 2 3 2
1 2 3 3
1 2 4 1
1 2 4 2
1 2 4 3
24
n2 oder CPU2 von 1 3 1 1 bis 2 1 4 3:
Code: (dl
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#!/usr/bin/perl -w
use strict;
my $i = 0;
for my $w (1..1) {
for my $x (3..3) {
for my $y (1..4) {
for my $z (1..3) {
$i++;
print "$w $x $y $z\n";
}
}
}
}
for my $w (2..2) {
for my $x (1..1) {
for my $y (1..4) {
for my $z (1..3) {
$i++;
print "$w $x $y $z\n";
}
}
}
}
print $i ."\n\n";
1 3 1 1
1 3 1 2
1 3 1 3
1 3 2 1
1 3 2 2
1 3 2 3
1 3 3 1
1 3 3 2
1 3 3 3
1 3 4 1
1 3 4 2
1 3 4 3
2 1 1 1
2 1 1 2
2 1 1 3
2 1 2 1
2 1 2 2
2 1 2 3
2 1 3 1
2 1 3 2
2 1 3 3
2 1 4 1
2 1 4 2
2 1 4 3
24
1 3 1 2
1 3 1 3
1 3 2 1
1 3 2 2
1 3 2 3
1 3 3 1
1 3 3 2
1 3 3 3
1 3 4 1
1 3 4 2
1 3 4 3
2 1 1 1
2 1 1 2
2 1 1 3
2 1 2 1
2 1 2 2
2 1 2 3
2 1 3 1
2 1 3 2
2 1 3 3
2 1 4 1
2 1 4 2
2 1 4 3
24
Und n3 oder CPU3 von 2 2 1 1 bis 2 3 4 3:
Code: (dl
)
1
2
3
4
5
6
7
8
9
10
for my $w (2..2) {
for my $x (2..3) {
for my $y (1..4) {
for my $z (1..3) {
$i++;
print "$w $x $y $z\n";
}
}
}
}2 2 1 1
2 2 1 2
2 2 1 3
2 2 2 1
2 2 2 2
2 2 2 3
2 2 3 1
2 2 3 2
2 2 3 3
2 2 4 1
2 2 4 2
2 2 4 3
2 3 1 1
2 3 1 2
2 3 1 3
2 3 2 1
2 3 2 2
2 3 2 3
2 3 3 1
2 3 3 2
2 3 3 3
2 3 4 1
2 3 4 2
2 3 4 3
24
2 2 1 2
2 2 1 3
2 2 2 1
2 2 2 2
2 2 2 3
2 2 3 1
2 2 3 2
2 2 3 3
2 2 4 1
2 2 4 2
2 2 4 3
2 3 1 1
2 3 1 2
2 3 1 3
2 3 2 1
2 3 2 2
2 3 2 3
2 3 3 1
2 3 3 2
2 3 3 3
2 3 4 1
2 3 4 2
2 3 4 3
24
Im Prinzip brauche ich etwas wie:
my @start_end_points = split_variations([2, 3, 4, 3], 3); # kombination, anzahl cpus
Und split Variations gibt sowas wie [ [1111,1243], [1311, 2143], [2211, 2343] ] zurück.
Nach meiner Methode oben müsst ich dafür durch alle Kombinationen durchgehen, um zu ermitteln wer welchen Teil abzuarbeiten hat. Das ist bei sehr großen Variation ungünstig, zumal jede CPU seinen Teil anschließend noch mal durchgeht und nach verschiedenen Bedingungen eine Kombination zulässt oder verwirft.
Eine Idee die ich gerade habe ist, man könnte nur den Anteil der ersten CPU errechnen und weiß ja dann, da alle CPUs gleich viel zu tun haben sollen, in welchem Abstand die Kombination zu verteilen sind:
n1 oder CPU1 von 1 1 1 1 bis 1 2 4 3
n2 oder CPU2 von 1 3 1 1 bis 2 1 4 3
n3 oder CPU3 von 2 2 1 1 bis 2 3 4 3
Da ist ja ein Muster zu erkennen, was sich seit n1 wiederholt, weil der Abstand gleich bleibt. Ich kann das nur weder in Perl noch in Mathe ausdrücken.
Ich vermute es geht in die Richtung mod n und/ooder Faktorzerlegung.
Vielen Dank fürs lesen.
Edit:
Last edited: 2018-07-18 21:16:28 +0200 (CEST)
Pörl.