Suche 'erweiterte' Funktionen für Listen

[Brainsucker]

Hallo,

das was ich suche ist etwas kompliziert zu beschreiben. Daher war ich mir auch nicht ganz sicher was ich als Threadüberschrift wählen soll.


Naja hier mal ein konkretes Beispiel was ich vorhabe:

Ich habe eine ellen lange Liste an Dateien mit unterschiedlichsten Größen (zwischen 6-14 MB). Nun will ich diese Dateien auf CDs brennen (aber nicht über Python).

Der Grund wofür ich hier Python brauche ist folgender:
Da handelsübliche CDs meißt auf 700 MB begrenz sind und ich diese so gut wie möglich ausnutzen will, will ich mir über Python ein Programm schreiben, dass die Dateigrößen aller dieser Dateien möglich genau so berechnet, dass die 700 MB der CD so gut wie möglich ausgenutzt werden.

Als beispiel:
Angenommen ich habe eine liste von 50 Dateien, soll mir Python eine neue Liste erstellen mit allen möglichen kombinationen der verfügbaren Dateien (dann müsste ich wohl eine Liste erhalten mit 2^50 Values).
Wenn dann eine Kombination gefunden wurde, die möglichst genau an die 700 MB heran kommt, sollen diese Dateien die diese Kombination ergeben in ein anderes Verzeichniss kopiert werden (das müsste mit shutil kein Problem darstellen).
Wichtig ist: Wenn eine Datei in einer Kombination bereits Verwendet wurde, soll sie kein zweites Mal verwendet werden.

Da diese 'Progrämmchen' wohl eine sehr hohe Rechenleistung erfordert, wäre der einsatz von Threads wohl sehr sinnvoll.
Außerdem wäre eine Graphische Oberfläche mit TKinter auch nicht schlecht. Aber dass reicht dann irgendwann noch, wenn die oben beschriebene Hauptfunktion steht^^


MfG Stefan

[Hyperion]

Das entspricht dem Knappsackproblem. Evtl. gibt es da schon (Backup)-Tools, die dafür Lösungen anbieten.

[Brainsucker]

Hey,

Danke für das Stichwort. Werd mich da mal durchlesen eventuell hilft es mir weiter.

[JonasR]

Also ich hätte die Liste jetzt Rückwärts sortiert heißt [höchste Zahl, ..., niedrigste Zahl] und dann wäre ich die Liste durch gegangen und hätte immer das größte Element der sortierten Liste einer neuen angehängt wenn es kleiner als 700 ist.

Denke in Python ist es einfacher zu verstehen...

Code: Alles auswählen

>>> t_list = []
>>> for i in xrange(50):
	t_list.append(random.randint(1,50))

	
>>> t_list.sort()
>>> t_list.reverse()
>>> a = []
>>> for key, value in enumerate(t_list):
	if sum(a) + value <= 700:
		a.append(value)

		
>>> a
[50, 50, 49, 49, 46, 45, 44, 44, 43, 42, 42, 41, 41, 40, 40, 34]
>>> sum(a)
700

Ich weiß es ist recht unsauber aber es soll ja nur ein Denkanstoß sein
Natürlich fehlt noch ein großer Teil des Programms aber du musst ja auch etwas machen

Edit: das enumerate ist übrigens für ein geplantes 'pop' schon drin

[deets]

@JonasR

Du solltest mal den Link von Hyperion lesen. Das von dir geschriebene Programm ist viel zu primitiv, und die perfekte Loesung viel zu komplex, um sie auch nur fuer kleine n zu berechnen. Da muss man schon mit cleveren Heuristiken ran, nicht mit ner simplen Schleife...

[BlackJack]

@JonasR: Mal ein einfaches Beispiel, die Grössen: 3, 3, 3, 3, 2, 2, 2, 2 und wir gehen mal von einer CD-Grösse von 10 aus. Du würdest diese Verteilung bekommen:
CD 1: 3 3 3
CD 2: 3 2 2 2
CD 3: 2

Man käme aber eigentlich mit 2 CDs aus:
CD 1: 3 3 2 2
CD 2: 3 3 2 2

[Brainsucker]

Also ich hätte die Liste jetzt Rückwärts sortiert heißt [höchste Zahl, ..., niedrigste Zahl] und dann wäre ich die Liste durch gegangen und hätte immer das größte Element der sortierten Liste einer neuen angehängt wenn es kleiner als 700 ist.

Denke in Python ist es einfacher zu verstehen...

Code: Alles auswählen

>>> t_list = []
>>> for i in xrange(50):
	t_list.append(random.randint(1,50))

	
>>> t_list.sort()
>>> t_list.reverse()
>>> a = []
>>> for key, value in enumerate(t_list):
	if sum(a) + value <= 700:
		a.append(value)

		
>>> a
[50, 50, 49, 49, 46, 45, 44, 44, 43, 42, 42, 41, 41, 40, 40, 34]
>>> sum(a)
700

Ich weiß es ist recht unsauber aber es soll ja nur ein Denkanstoß sein
Natürlich fehlt noch ein großer Teil des Programms aber du musst ja auch etwas machen

Edit: das enumerate ist übrigens für ein geplantes 'pop' schon drin

hmm hey sorry aber dein script is leider nicht wirklich hilfreich.

Als erstes brauche ich wohl eine liste von allen möglichen kombinationen. (Ich vermute mal hier laufe ich schon in die gefahr in ein MemoryError zu enden.)

Als nächsten schritt müsste ich alle dateigrößen zusammen zählen (das ist wohl kein problem) und dann die erste liste die kleiner als die besagten 700 MB ist auswählen und kopieren. Dann geht das ganze Spiel wieder von vorne los allerdings diesmal ohne die dateien die beim ersten mal bereits verwendet wurden.


Irgendwie ahne ich es schon, dass das wieder auf eine while schleife hinausläuft ^^

[deets]

@BrainSucker

Ne Liste aller moeglichen Kombinationen ist ja wie du gesagt hast 2**50. Wenn du zum bewerten nur einer einzigen dieser Moeglichkeiten eine Nanosekunde braeuchtest, dann wuerde dein Programm ca. 35 Jahre rechnen...

Code: Alles auswählen

>>> ns = 1.0 / 10**6
>>> ns
1e-06
>>> ns * 2 ** 50
1125899906.842624
>>> ns * 2 ** 50 / (3600.0 * 24)
13031.24892178963
>>> ns * 2 ** 50 / (3600.0 * 24) / 365.0
35.70205184051953

Da hilft dann auch multi-threading nicht mehr weiter...

[Brainsucker]

@BrainSucker

Ne Liste aller moeglichen Kombinationen ist ja wie du gesagt hast 2**50. Wenn du zum bewerten nur einer einzigen dieser Moeglichkeiten eine Nanosekunde braeuchtest, dann wuerde dein Programm ca. 35 Jahre rechnen...

Code: Alles auswählen

>>> ns = 1.0 / 10**6
>>> ns
1e-06
>>> ns * 2 ** 50
1125899906.842624
>>> ns * 2 ** 50 / (3600.0 * 24)
13031.24892178963
>>> ns * 2 ** 50 / (3600.0 * 24) / 365.0
35.70205184051953

Da hilft dann auch multi-threading nicht mehr weiter...

Ouhh kagge^^

Das mit den 50 Dateien war ja nur beispielhaft. In wirklichkeit handelt es sich ja grademal um knappe 800 Dateien (hier wäre die liste dann ca. 2**800 lang)

Hmm dann brauche ich wohl tatsächlich eine andere lösung.

[Hyperion]

Naja, das Problem haben ja schon viele Leute beackert... ich würde da jetzt wirklich denken, dass es da schon Ansätze gibt. Und wenn nicht, finden sich sicherlich Ansätze, wie man eine nette Heuristik implementieren könnte.

Ach ja, bitte zitiere doch nicht stumpf immer alles aus einem Vorgängerposting. Zitiere doch nur den Teil, zu dem Du etwas sagen willst. Alles andere bläht den Thread nur auf und trägt nicht zum Verständnis bei.

[Brainsucker]

ich würde da jetzt wirklich denken, dass es da schon Ansätze gibt. Und wenn nicht, finden sich sicherlich Ansätze, wie man eine nette Heuristik implementieren könnte.

Das ist wohl wahr.

Hier habe ich was nettes gefunden:

http://www.google.com/codesearch#GzfXS- ... psack%20py

Ich denke dieser Schnipsel trifft den nagel auf den kopf

[Brainsucker]

Hallo Leute,


Ich brauche nocheinmal ein wenig hilfestellung.

Der Knapsack ist prinzipiell genau das was ich suche. Allerdings ist der 'Wert' in meinem Fall überflüssig, da jede Datei gleich Behandelt werden soll. Das einzige, das in meinem Fall zählt ist allein die Dateigröße. Somit könnte man sich ja ein wenig rechenzeit ersparen.
Außerdem funktioniert dieser knapsack nicht mit floats (ich musste die Dateigrößen von Bits in MegaBytes umwandeln, da ich sonst in einen MemoryError laufe).

[JonasR]

@BlackJack wenn man das ganze jedoch mal Maßstabsgetreu nachstellt, kommt man mit meiner Rechnung sehr wohl auf ein annehmbares Ergebnis. Ich habe meine Rechnung schon auf diesen Fall abgezielt
Vom Kosten/Nutzen-Faktor ist mein Script denke ich mal dem vorzuziehen, was der Brainsucker gerade versucht

Hier mal zum Prüfen meiner recht hochnäsigen These

Code: Alles auswählen

import random

t_list = []
for i in xrange(800):
    t_list.append(random.randint(6, 14))

t_list.sort()
t_list.reverse()

result_list = []
while t_list:
    t_list_temp = list(t_list)
    result_temp = []
    for value in t_list_temp:
        if (sum(result_temp) + value) <= 700:
            result_temp.append(value)
            t_list.remove(value)
        else:
            if value == min(t_list_temp):
                break
    print sum(result_temp)
    result_list.append(result_temp)
##print result_list
print len(result_list)

Edit: Ich weiß übrigens nicht warum ich die liste 't_list' genannt habe oO

[Brainsucker]

Edit: Ich weiß übrigens nicht warum ich die liste 't_list' genannt habe oO

Der Name der Variable ist mir genau so egal, wie es dem Strom egal ist, welche Farbe die Ader hat durch die er fließt!^^

Hmm ich werde diese version mal in der prasxis anwenden. mal sehn wie mein resultat aussieht

[JonasR]

Edit: Ich weiß übrigens nicht warum ich die liste 't_list' genannt habe oO

Der Name der Variable ist mir genau so egal, wie es dem Strom egal ist, welche Farbe die Ader hat durch die er fließt!^^

Hmm ich werde diese version mal in der prasxis anwenden. mal sehn wie mein resultat aussieht

Naja Variablen sollten IMO schon sinnvolle Namen haben, damit man leicht erkennen kann was drin ist, ohne den Quellcode zu durchforsten. Aber das kann man bei einem solchen Snippet ja vielleicht vernachlässigen.

[BlackJack]

@JonasR: Wieso war meines nicht massstabsgetreu? Du brauchst nur ein paar Verzeichnisse mit entsprechend grossen Dateien. Zum Beispiel Filme von Youtube, Datendateien von Spielen, oder verlustfrei komprimierte Musik, und es können mehr CDs heraus kommen als nötig wären.

@Brainsucker: Du könntest beide Werte gleich setzen. Wenn Dir das tatsächlich zu viel Speicher verbraucht, kannst Du den Speicherverbrauch der Matrix zwei mal halbieren. Einmal in dem Du den Algorithmus umschreibst, dass nur einer der beiden, dann ja gleichen Werte verwendet wird. Dann wird die Matrix symmetrisch, d.h. man muss nur noch die Hälfte davon tatsächlich speichern.

An Gleitpunktzahlen wirst Du das nicht anpassen können. Du kannst höchstens schauen wie weit Du die Einheit runter setzen kannst. Und ab wann das überhaupt noch Sinn macht. Ich denke eine Grössenordnung sollte man herunter gehen können, also die Grösseneinheit auf 100 KB setzen.

[JonasR]

...Dateien mit unterschiedlichsten Größen (zwischen 6-14 MB)... Da handelsübliche CDs meißt auf 700 MB begrenz sind...

Was später noch dazu kam sind die 800 Datein die aber in dem Falle egal sind.

Es ist nämlich schon ein Unterschied ob ich Datein zwischen 2-3 MB auf 10 MB packen will oder 6-14 MB auf 700.

[EyDu]

Zum Multiple Knapsack Problem sollte es eigentlich genug Approximationen mit garantierten Schranken geben. Ich würde mal behaupten, dass es, wie oben schon vorgeschlagen, ausreichen sollte die Dateien absteigend der Größe nach zu sortieren und dann immer auf die CD zu packen auf der noch am wenigsten Platz verfügbar ist. Wenn ich darauf tippen sollte, was der Worst Case wäre, dann würde ich darauf tippen, dass maximal doppelt so viele CDs verwendet werden würden wie durch das Optimum möglich. Ob das bei nicht-künstlichen Daten eintritt würde ich aber bezweifeln.

[JonasR]

Oo Zeug mir mal deine Rechnung... Bei den Gegebenheiten komme ich auf maximal eine CD dazu.
Meine gibts morgen schreibe gerade vom Handy

[JonasR]

Also gehen wir mal davon aus alle Files sind 13 MB groß damit wir immer einen maximalen Freiraum auf der CD haben.
Es würden auf 700MB 53,85 Files passen, also reale 53 Files. (700 / 13)
Die CD wäre bis auf 11 MB ausgelastet. (13 * 53)
An ausgelasteten CDs wird es am Ende 15 Stück geben mit insgesamt 795 Files. (800 / 53) und (15 * 53)
Eine CD hätte also noch 5 Files mit insgesamt 65 MB.

Ich weiß es ist eine ziemlich künstliche Rechnung, aber ich denke es zeigt, das selbst wenn ich auf jeder CD, aufgrund schlechter Sortierung, noch eine Gewisse Menge an Platz freihabe, ist der Maximal zusätzlich benötigte Platz bei solch kleinen Dateigrößen zu vernachlässigen.