Hallo,
ich möchte gerne einen array/vektor o.ä schreiben, wo ich werte
reinschreibe
da möchte ich gerne zahlen und buchstaben reinschreiben.
nummer_1=[1,2,a,b,c]
jetzt möchte ich gerne alle möglichen kombinationen für 4 werte
bekommen:
1,1,1,1
1,1,1,2
1,1,2,1
...
a,b,b,c
...
b,b,c,a
usw.
gibt es da regeln für? oder wie könnte ich da am besten vorgehen?
habe zunächst überlegt es mit for-schleifen zu machen. Das würde ja aber
denke ich mal ewig dauern.
Womit ich das mache, ist eigentlich relativ egal. Am liebsten wäre mir
jedoch c++, da ich das am besten kann.
Gruß
Johannes
rechne erst mal kombinatorisch aus, wieviele verschiedene Kombinationen
es gibt. 26 (kleine) Buchstaben plus 10 Ziffern, ergibt 36
Werteausprägungen.
Für 4 Stellen gibt es also 36 x 36 x 36 x 36 = 1679616 vollständige
Kombinationen. Aber vieleicht willst du ja gar nicht alle möglichen
Kombinationen generieren, sondern nur bestimmte Werte-Kobinationen, dann
wirds natürlich weniger.
"Wohin" willst du denn diese ca. 1.7 Millionen Kombinationen
"schreiben"? In eine Datei?
Deine Ansatz
> habe zunächst überlegt es mit for-schleifen zu machen
geht schon mal in die richtige Richtung. Da du ja wie du schreibst schon
etwas programmieren kannst:
> Am liebsten wäre mir jedoch c++, da ich das am besten kann.
zeig doch einfach mal das, was du schon hast, und was daran nicht geht.
Deine Vermutung
> Das würde ja aber denke ich mal ewig dauern.
ist (abhängig von deiner Ziel-Hardware) vermutlich vollständig
unbegründet. Selbst wenn die Erzeugung und Abspeicherung jeder einzelnen
Kombination ca. 1 ms (Milli-Sekunde) dauert (was für Computer eine
Ewigkeit ist) braucht der gesamte Vorgang keine halbe Stunde - "eine
Ewigkeit" sieht anders für mich aus. Oder hast du bestimmte Zeitvorgaben
(z.B. "muß innerhalb von 10 Sekunden generiert werden")??
Johannes schrieb:> habe zunächst überlegt es mit for-schleifen zu machen.
ja, das ist eigentlich üblich
[c]
int index = 0;
for( int i1 = 0; i1 < 36; ++i1 ) {
for( int i2 = 0; i2 < 36; ++i2 ) {
for( int i3 = 0; i3 < 36; ++i3 ) {
for( int i4 = 0; i4 < 36; ++i4 ) {
nummer_1[index++] = ....
}
}
}
}
[/]
Das würde ja aber
> denke ich mal ewig dauern.
auf einer schnelle CPUs wird es wohl kaum länger als ein paar Sekunden
dauern.
- füll einen Vector mit deinen Werten.
- sortiere diesen
- benutze next_permutation
beliebige andere randomiterable container können auch benutzt werden:
1
#include<iostream>
2
#include<algorithm>
3
#include<string>
4
5
usingnamespacestd;
6
7
intmain(){
8
std::stringstr="abc012";
9
10
cout<<"sorting String '"<<str<<"' :";
11
std::sort(str.begin(),str.end());
12
cout<<" '"<<str<<"' :"<<endl;
13
14
cout<<"permutations: "<<endl;
15
16
do{
17
cout<<str<<endl;
18
}while(next_permutation(str.begin(),str.end()));
19
return0;
20
}
WIchtig ist, es muss eine Sortierfunktion für die elemente
bereitgestellt werden und der COntainer muss muss am Anfang sortiert
sein, sonst kriegst du nicth alle Permutationen
Edit:
Oh ich seh gerade du willst alle Kombinationen - naja nicht richtig
gelesen - ich lass es trotzdem mal stehen.
Wenn du nur die Kombinationen aus den Zeichen im String hast must du
zuerst zählen wie viele verscheiden zeichen du hast und wie viele
Stellen da sind.
Danach rechnest du mit pow(N,M) aus wie viele Kombinationen das sind und
initialisierst dein Array. N verschieden Zeichen, M Anzahl der Stellen
Feld initialisieren und am einfachsten mit for Schleifen füllen.
probiere aber auch den weg über pointer, schaun ob das schneller ist ;)
Johannes schrieb:> Das würde ja aber> denke ich mal ewig dauern.
Das kommt auf deine Definition von "ewig" an.
Selbst wenn du alle Kombinationen als Konstanten in einem Headerfile
ablegt, müssen die beim Programmstart in den Speicher geladen werden.
Das mag dann etwas schneller gehen als deine for-schliefen, aber
unendlich schnell geht das halt nicht.
Die spannende Frage ist allerdings, was du dann mit den Daten anfangen
möchtest.
Oliver
das ist aber schon ziemlich hässlich (abgesehen davon, dass es nicht
funktioniert, weil auf jeder Schleifenebene die entsprechenden Stelle
verändert werden müsste)
1
for(inti1=0;i1<36;++i1){
2
nummer_1[0]=i1;
3
for(inti2=0;i2<36;++i2){
4
nummer_1[1]=i2;
5
for(inti3=0;i3<36;++i3){
6
nummer_1[2]=i3;
7
for(inti4=0;i4<36;++i4){
8
nummer_1[3]=i4;
9
// hier noch output
10
}
11
}
12
}
13
}
aber wie gesagt, das ist ja beschränkt auf eine spezielle breite.
hier eins für variable outputlängen:
Peter II schrieb:>> denke ich mal ewig dauern.
Das liegt in der Natur der Sache, es gibt halt viele Kombinationen und
du willst ja unbedingt jede 1 mal.
Da kann man nichts optimieren, du kannst nur deine Ansprüche
runterschrauben, zumal: Wo willst du die 1.6 Millionen Kombinationen
speichern ?
MaWin schrieb:#
> Peter II schrieb:> >> denke ich mal ewig dauern.
das habe ich nicht geschrieben.
> Wo willst du die 1.6 Millionen Kombinationen> speichern ?
Wir gehen einfach mal davon aus, das jeder PC 10MByte Ram dafür hat.
Tom schrieb:> Nachtrag, um fair zu bleiben:> Das std:endl ist das Problem des C++-Codes. Mit einem "\n" läuft er in> 0.8s ;)
der Code ist auch alles andere als optimal.
schließlich wird im inneren jedes mal ein String gebaut und in eine
Liste geschmissen.
ist aber jetzt kein hübsches c++ mehr.
mit Optimierung übersetzt sollten die Zugriffsoperatoren der std::string
und der std::vector keinen Einfluss haben, die könnte man natürlich auch
noch durch plain-C ersetzen.
Vlad Tepesch schrieb:> hübsches c++
Aktuelles (aber noch unhübscheres) C++ wäre die Formulierung mit
Templates, mit denen der Ergebnisvektor zu Compilezeit ausgefüllt wird.
Dann ird zwar das Compilieren ewig dauern, falls es überhaupt
compilierbar ist (und ewig ist dann wirklich ewig...), aber zur Laufzeit
ist es dann maximal schnell.
Oliver
Vlad Tepesch schrieb:> der Code ist auch alles andere als optimal.
Die neue Variante (mit -O3) läuft bei mir in 0.07s, wobei wahrscheinlich
das Zeilenzählen mit wc -l langsam signifikant wird.
Wieder ein lehrreicher Thread. Dass das std::endl, das jeder für
Zeilenumbrüche benutzt, sich so stark auswirkt, wenn man ernsthafte
Datenmengen nach stdout schreibt, war mir nicht bewusst.
Mein Fazit:
1) Aktuelle Computer/Compiler sind brutal schnell (wenn sie qualifiziert
benutzt werden). 10MByte Daten sind Peanuts und deren Berechnung
passiert in ein paar ms. (von den 70ms nehmen wahrscheinlich die Ausgabe
und Weiterverarbeitung den größten Teil in Anspruch.)
2) Mit Kenntnissen einer dynamischen High-Level-Sprache hat man bei
vielen Problemen eine Lösung in ein paar Augenblicken/Zeilen
heruntergetippt.
Für ein Einweg-Tool, das einmal eine Text-Datei mit den 16 Mio
Kombinationen füllen soll, ist die optimierte C++-Lösung genauso
unpassend wie der Python-Dreizeiler für numerische
Brute-Force-Simulationen.
Tom schrieb:> Wieder ein lehrreicher Thread. Dass das std::endl, das jeder für> Zeilenumbrüche benutzt, sich so stark auswirkt, wenn man ernsthafte> Datenmengen nach stdout schreibt, war mir nicht bewusst.
endl macht ja auch noch ein flush
Mathematisch gesprochen, werden hier für die Menge der vorgegebenen
Zeichen
- alle Variationen mit Wiederholung bzw.
- die Kartesische Potenz
gesucht. Unter diesen Begriffen findet man im Netz weitere Information
und auch Programmcode.
Wenn Python zu langsam ist und C++ zu viel Tipperei bedeutet, kann man
sich natürlich auch mal Haskell anschauen :)
Es gibt dort in den mitgelieferten Bibliotheken zwar keine spezielle
Funktion zur Berechnung der kartesischen Potenz, dafür aber die
allgemeinere Funktion¹ replicateM, die – wenn man sie auf eine Liste
anwendet – genau das Gewünschte tut.
Beispiel:
1
replicateM 2 "abc"
liefert
1
["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
Kompletter Code, der das Gleiche tut wie die von Tom und Vlad geposteten
Programme in Python und C++:
1
import Control.Monad
2
3
symbole = ['0'..'9'] ++ ['a'..'z']
4
ergebnisse = replicateM 4 symbole
5
6
main = putStr $ unlines ergebnisse
Laufzeiten auf meinem Rechner (Ausgabe in /dev/null umgeleitet):
1
Python von Tom 5,216 s
2
C++ von Tom 1,094 s
3
Haskell von mir 0,389 s
4
C++ von Vlad 0,026 s
Das Programm von Vlad liegt nach wie vor weit vorn. Die Ausgabe erst in
einen Puffer zu schreiben und anschließend in einem Rutsch auszugeben,
bringt sehr viel. Gibt man die Ergebnisse jeweils sofort nach ihrer
Berechnung aus (also in 1679616 cout-Aufrufen), werden 0,274 s, also
etwa die zehnfache Zeit benötigt, was aber immer noch sehr schnell ist.
——————————————
¹) Allgemein führt replicateM eine Aktion n-mal in einer Monade aus
und sammelt die Ergebnisse in einer Liste, daher auch der Name.
Yalu X. schrieb:> Laufzeiten auf meinem Rechner (Ausgabe in /dev/null umgeleitet):> Python von Tom 5,216 s> C++ von Tom 1,094 s> Haskell von mir 0,389 s> C++ von Vlad 0,026 s
das "c++ von tom" war auch von mir :) er hatte nur das Alphabet
angepasst, was mich auch zu der Frage führt, die ich vorsichtshalber
stellen wollte:
Ausgabelänge und Alphabet, hast du bei allen gleich gesetzt?
ICh frag nach, weil mir 26ms ziemlich schnell vorkommt.
Angenommen 2GHz *26ms = 52Mio Takte
/ 1.6Mio Kombinationen.
Macht 33 Takte pro Kombination inklusive ausgabe.
Das kommt mir sehr komisch vor.
Vlad Tepesch schrieb:> das "c++ von tom" war auch von mir :)
Stimmt, das hatte ich übersehen.
> Ausgabelänge und Alphabet, hast du bei allen gleich gesetzt?
Ja. Mit wc -l bekomme ich bei deiner schnellen Variante 1679617
angezeigt (1 mehr als 36⁴, weil am Ende mit std::endl noch eine
Leerzeile ausgegeben wird).
> ICh frag nach, weil mir 26ms ziemlich schnell vorkommt.
Jetzt, wo mich darauf hinweist, kommt es mir auch sehr kurz vor :)
> Angenommen 2GHz *26ms = 52Mio Takte> / 1.6Mio Kombinationen.> Macht 33 Takte pro Kombination inklusive ausgabe.> Das kommt mir sehr komisch vor.
Es ist ein Pentium 4 mit 3,2 GHz. Das wären dann immerhin 50 Zyklen.
Dafür rechnet die alte CPU innerhalb eines Zyklus weniger als eine neue.
Ich habe jetzt, um die Auflösung der Zeitmessung zu verbessern, das
Programm zehnmal hintereinander aufgerufen:
Das braucht 264 ms, was mit den 26 ms für 1 Durchlauf gut zusammenpasst.
Vielleicht schummelt das Betriebssystem ja etwas, wenn die Ausgabe nach
/dev/null umgeleitet wird, da sie ja sowieso vernichtet wird. um dies zu
verhindern habe ich
probiert, was immerhin 434 ms, also 82 Zyklen dauert, wobei die
Rechnzeit von cat natürlich mitgezählt wird..
Mit der Umleitung in eine Datei auf einer RAM-Disk
>[Haskell]
Faszinierend.
Mit Zwischenspeichern läuft die Python-Version ca. doppelt so schnell
wie einzelne print().
1
from itertools import product
2
nummer_1=[x for x in '0123456789abcdefghijklmnopqrstuvwxyz']
3
result=[]
4
for a in product(nummer_1, repeat=4):
5
result.append(''.join(a))
6
print('\n'.join(result))
Mit list comprehension (oder generator expression, das nimmt sich
nichts) statt append sind nochmal 25% rauszuholen:
1
from itertools import product
2
nummer_1=[x for x in '0123456789abcdefghijklmnopqrstuvwxyz']
3
result=[''.join(a) for a in product(nummer_1, repeat=4)]
4
print('\n'.join(result))
Das kratzt auf meinem antiken 1.8GHz-Core2Duo fast an der Sekunde (mit
>/dev/null) Angesichts der Geschwindigkeit von Vlads Programm sind diese
Optimierungen aber lächerlich.
und dann setzt du noch vor eine auszusuchende For-Schleife ein
1
#pragma omp parallel for
und schon freuen sich auch die anderen CPU-Kerne über eine halbe Sekunde
Arbeit.
(beachte dabei, dass du die Ausgabe noch threadsicher machen musst, am
besten eine Ausgabedatei pro thread und dann hinterher zusammenhängen)
Mike Beh schrieb:> (beachte dabei, dass du die Ausgabe noch threadsicher machen musst, am> besten eine Ausgabedatei pro thread und dann hinterher zusammenhängen)
wenn man das schöne alte printf verwende würde, gibt es keine Probleme.
Nur bei dem std::cout.
Yalu X. schrieb:> Nein, dein Programm ist wirklich sauschnell :)
Offensichtlich aber auch dank sehr gut optimierenden Compilern
Mike Beh schrieb:> #pragma omp parallel for
Das scheint mir kein standard c++ zu sein. Welche Compiler unterstützen
das unter welchen Voraussetzungen?
Ich wage auch zu bezweifeln, dass das bei obigen code irgendwas bringt,
schließlich hat eine einzelne Iteration fast nix zu tun, ist aber dafür
höchst abhängig von der vorherigen
Vlad Tepesch schrieb:> Das scheint mir kein standard c++ zu sein. Welche Compiler unterstützen> das unter welchen Voraussetzungen?>> Ich wage auch zu bezweifeln, dass das bei obigen code irgendwas bringt,> schließlich hat eine einzelne Iteration fast nix zu tun, ist aber dafür> höchst abhängig von der vorherigen
das ist Teil von OpenMP
http://de.wikipedia.org/wiki/OpenMP
Nutze ich mit Code::Blocks mit dem GNU GCC Compiler.
Ich bin wahrlich keine Leuchte in C++, aber das funktioniert.
Wie hoch die Gewinne ggü. dem bisher dargstellten Code sind weiss ich
nicht, müsste mal jemand mit Zeit und Muße ausprobieren. (dabei mal
bitte die Leistung per taskmanager überwachen, ob wirklich eine
Lastverteilung stattfindet)
Klar lohnt sich der overhead erst ab einer bestimmten Aufgaben-Größe,
aber probieren kanns mans ja auch hier einmal.
Alternativ kann man die Aufgabe händisch in Teile der Größe
Gesamtmenge/(Anzahl CPU-Kerne-1) teilen (hier also die äußerste
for-Schleife) und einzelne Threads dafür starten. Dann kan man auch
gleich die Threads den einzelnen Kernen zuweisen und die
Prozesspriorität hoch setzen.