Beste art um Kombinationen zu programmieren?
Moin!
Was ist die effizienteste Methode, wenn man mit Kombinationen programmieren will? Und welche Programmiersprache?
Ist eine Datenbank das schnellste?
Ich kenne mich leider kaum aus...
Ich kann es ja kurz anreissen, was ich machen will.
Es sollen zb 100 textdatein geladen werden. In diesen sind circa à 300.000 zeilen mit zahlen. Insgesamt gibt es aber nur 500.000 verschiedene zahlen. Nun möchte ich das immer 15 Datein zusammengefügt werden.
Wenn zb 6 Datein die volle Zahl von 500.000 erreichen, wird dort nicht weiter kombiniert.
Ich möchte so heraus finden, welche 15 Datein unter 500.000 bleiben.
Ich hoffe es ist verständlich in abgespeckter form😁
Lg!
Können die Zahlen sortiert werde oder muss deren Reihenfolge erhalten bleiben?
Handelt es sich um ganze Zahlen (Integer) ?
Vorzeichen?
Ja ich kann sie vorher alphabetisch sortieren und es sind keine doppelten in einer Textdatei.
Also besser wäre das auf zeilen zu machen, eine Zahl = eine Zeile.
PS:
Sind die Zahlen in Textform aufgelistet (menschlich lesbar/decimal) , oder im Binärformat?
Wie groß ist die größte Zahl?
Eine Zahl sieht zb so aus: [01][02][43] das wäre dann eine 010243. Ich wollte keine konkrete Hilfe, deswegen habe ich es nicht so ausgeführt!😋
4 Antworten
Mache ich also mal mit beim lustigen Raten…
Du hast Dateien die Zahlen enthalten. Über alle Dateien hinweg gibt es 300.000 eindeutige Zahlen. Du möchtest jetzt eine Datei lesen (Datei_1), und bestimmen, welche eindeutigen Zahlen drinnen sind. Danach liest Du die nächste (Datei_2) und bestimmst, welche eindeutigen Zahlen sie enthält, die nicht in Datei_1 enthalten sind… Das tust Du so lange, bis Datei_1,…,Datei_n insgesamt alle unterschiedlichen Zahlen enthalten. Damit wird Datei_1,…,Datei_n eine Gruppe von Dateien. Jetzt beginnt das gleiche Spiel mit Datei_(n+1), Datei_(n+2) und so fort.
Sehr viele Sprachen können so etwas, beispielsweise Python.
die Kombinationen gehen ja in die zich zich zich Milliarden!
Wieso? 1-15 bilden eine Gruppe, 16-30 die zweite, 31-45, 46-60, 61-75, 76-90, 91-100. Ich komme da nur auf 7 Dateien mit jeweils maximal 500.000 Zeilen. Das ist doch nix besonderes und läuft in weniger als einer Minute durch.
Oder du hast dich falsch ausgedrückt und meinst etwas anderes.
Interessanter wird es, wenn man ein Optimalitätskriterium hat. Dafür müsste man einen Index aufbauen.
Es geht ja um Kombinationen, nicht um feste Gruppen, 1-15 war nur ein Beispiel.
Nach dem kombinieren von 1-15 kommt 1-14 + 16, dann 1-14 +17 Etc..
Aber das fällt alles weg, wenn 1-10 schon voll sind.
Nehmen wir also an, Du möchtest, dass die Dateiengruppen von 15 Dateien in dem Sinne optimal sein sollen, dass sie jeweils die maximale Zahl von Zahlen enthalten (einige vollständig, andere unvollständig), dann musst Du einen Index aufbauen. Der Index enthält, welche Zahl in welchen Dateien vorhanden ist. Damit kannst Du dann sehr schnell die Frage beantworten, wie viele Dateiengruppen Du maximal erstellen kannst, die alle Zahlen enthalten. Du kannst auch “fail first” suchen, d.h. Du nimmst die Zahl, die am seltensten vorkommt, nimmst die erste Datei, die diese enthält, und dann suchst Du dazu jeweils die Datei, die den geringsten Überlapp hat. So gehst Du vor, bis Du eine Gruppe voll hast. Dann nimmst Du das nächste unbenutzte Dokument in der Liste.
Das würde vielleicht zu einer “guten” Lösung führen. Insgesamt halte ich das Problem für NP-hart.
trivial
ich mach mir nicht die Mühe [01][02][43] erst in eine Zahl umzuwandeln is sortiere einfach di strings Du willst ja ohnehin nur wissen vieviel Elemente übrig bleiben....
Mit Millionen Datenzeilen aus Dateien zu agiern ist in jeder Sprache eine "Hausnummer" Was das Programm im Speicher tut, ist weniger das Problem als das Lesen der Dateien!
Iteriere über die gewünschten Dateien
- füge alle Zeilen der aktuellen Datei einem Buffer hinzu.
- sortiere die Zeilen ohne Duplikate (je nach Sprache: "sort unique" , ".Distinct(), etc )
- prüfe mit Array.Count/List.Count oder ~.Size (verschieden in jeder Sprache) wieviel Elemente (Zeilen) in der Liste sind
- Sind es weniger Elemente als der vorgegebene Wert merkst du Dir die bisher gelesenen in einem 2. Buffer und machst mit der nächsten Datei weiter
- ist die Vorgabe überschritten kannst ist die Sache erledigt
..den 2.Buffer kannst du dann in in eine Datei deiner Wahl schreiben oder was auch immer.
mal das Auswerden eines Blocks von 15 Dateien
Statt nutzlosem Pseudocode...
Quick&Dirty in Powershel (Get-Content ist nicht unbedingt ein Rennpferd beim Lesen von großen Dateien , aber für ne Demo übersichtlicher) :
$StopFlag=$False
$BaseNum=0
$WriteBuffer=@()
$BaseNum..($BaseNum+14)|
?{$StopFlag -eq $False}| #solange keine Abbruchbedingung
%{$ReadBuffer=@()}{
$FileName='file{0:d3}.txt'-f $_ #zu lesenden Dateinamen aus de jeweils übergenebeb Dateinummer zusammenbasteln (file000.txt, file000.txt ...usw)
Write-Host "Fuege $FileName zum Buffer"
$ReadBuffer+=Get-Content $FileName -ReadCount 0
$ReadBuffer=$ReadBuffer|Sort-Object -Unique
Write-Host "Einzigartige Strings in ReadBuffer: $($ReadBuffer.Count)" -fo blue
if ($ReadBuffer.Count -lt 500000) {
Write-Host "ubernehme ReadBuffer in WriteBuffer" -fo green
$WriteBuffer=$ReadBuffer #in 2.Buffer...Kopieren
}
else {
$StopFlag=$True # Loop abbbrechen
Write-Host "Maximum Strings ueberschritten" -fo red
Write-Host "ReadBuffer verworfen" -fo red
}
}
$writebuffer.count
Ich glaube, wenn du dein Problem verständlich formulieren kannst, ist die Lösung nicht mehr fern.
Es sollen zb 100 textdatein geladen werden. In diesen sind circa à 300.000 zeilen mit zahlen. Insgesamt gibt es aber nur 500.000 verschiedene zahlen. Nun möchte ich das immer 15 Datein zusammengefügt werden.
Also 300.000 Zahlen pro Datei? Nach welchen Kriterien sollen jetzt 15 Dateien zusammengefügt werden? Wie sieht so eine Zusammenfügung aus?
Sie werden einfach zusammen gefügt. So als würde man alle Zeilen aller 15 Datein in eine rein tun ,doppelte zeilen werden überschreiben
Nun möchte ich das immer 15 Datein zusammengefügt werden.
Wenn zb 6 Datein die volle Zahl von 500.000 erreichen, wird dort nicht weiter kombiniert.
Was immer du damit bezwecken magst ...
Du nimmst also Datei 1 mit 300.000 Zahlen, fügst aus Datei 2 alle Zahlen zu, die nicht bereits drin sind, dann Datei 3 usw. bis du entweder Datei 15 verwendet hast oder die Zieldatei 500.000 Zahlen enthält? Wenn das bei Datei 10 erreicht ist, werden 11-15 ignoriert?
Stellst du an das Format der Zieldatei irgendwelche Anforderungen? Oder enthält sie einfach nur Zahlen?
Ja genau, so wie du es beschrieben hast.
Die zieldatei soll einfach nur zahlen wieder geben, also das was in den zeilen steht.
Ja genau, so wie du es beschrieben hast.
Die zieldatei soll einfach nur zahlen wieder geben, also das was in den zeilen steht.
Es sind nämlich nicht die zahlen von 1-500.000 sondern zb von 1mio - 5mio. Die Anzahl werden durch eine Datei vorgegeben. Deswegen wäre es am besten, wenn eine zusatz Datei als Vorlage dafür dient, was der " rahmen" ist.
Also quasi den Rahmen der 500.000 stellt, deswegen ist es besser das auf zeilen Ebene zu machen.
Mir ist immer noch nicht klar, was Du willst.
Du hast offenbar eine Menge D={ D_1, D_2, ... } von Dateien, die je als eine Menge D_i von Zeilen gesehen werden können. Du kennst die Menge Z aller möglichen Zeilen. Und Du suchst jetzt nach Gruppen aus 15 Dateien, deren Vereinigung nicht Z ist. Brauchst Du da:
- eine beliebige solche Gruppe?
- alle möglichen Gruppen? Das könnten sehr viele sein!
- eine Zerlegung aller Dateien in solche Gruppen? Dann bleibt aber immer ein Rest, weil 100 nicht durch 15 teilbar ist.
Ich würde solche Datenmengen in Python verarbeiten und für jede Zeile eine Menge der Dateien verwalten, die diese Zeile enthalten. Diese Mengen kann man effizient als Integer abbilden, wobei jedes Bit einer Datei entspricht:
from os import listdir
# lineinfo: line --> files (as Bit-Set)
lineinfo = { (line, 0) for line in open("all.txt") }
index = 1 # 2, 4, 8, ... 2^n
datainfo = {} # index --> filename
for data in listdir("input"):
datainfo[index] = data
for line in open(data):
lineinfo[line] |= index # total count
index *= 2
Wenn danach irgendeine Zeile in höchstens 85 (=100−15) Dateien vorkommt, sind beliebige 15 Dateien aus dem Rest eine mögliche Lösung. Andernfalls (wenn alle Zeilen mindestens 86-mal vorkommen) gibt es keine Lösung:
for line, lineset in lineinfo.items():
int count = 0
int idx = 1
while idx<index:
if not lineset & idx:
count += 1
if count >= 15:
int idx = 1
while idx<index:
if not lineset & idx:
print( datainfo[idx], end=", " )
break
Etwas schwieriger wird es, alle möglichen Gruppen zu enumerieren. Eigentlich zählt jede Gruppe von 15 Dateien (wie oben) für jede Zeile. Allerdings werden dabei Gruppen mehrfach gezählt, wenn in deren Vereinigung zwei oder mehr Zeilen fehlen. Es ist sicher nicht praktikabel, sich alle schon berechneten Gruppen zu merken, um Doubletten zu vermeiden, denn das sind viel zu viele.
Prinzipiell kann man erst mal alle Zeilen ignorieren, die in 86 oder mehr Dateien vorkommen (weil die in jeder Gruppe vorkommen), und dann die Dateien aussortieren, die in der Schnittmenge der übrigen Zeilen liegen. Das dürfte die Datenmenge gewaltig verkleinern.
Wie man aber genau vorgeht, hängt davon ab, ob Du zwei verschiedene Dateigruppen mit gleicher Vereinigungmenge unterscheiden willst:
- Wenn nicht, kannst Du iterativ für jede interessante Zeile z_i alle Lösungen finden, die z_i nicht enthalten und danach nur Lösungen betrachten, die z_1 bis z_i enthalten. Das sollte eigentlich recht flott gehen.
- Falls doch, müsste man noch etwas knobeln, um nicht über alle möglichen 15-er-Gruppen iterieren zu müssen ...
Ja circa 300.000 könnte aber auch mehr oder weniger sein.
Der Rest passt.
Wie baut man sowas auf? Den die Kombinationen gehen ja in die zich zich zich Milliarden!