Optimale Platzausnutzung

N

Nornagest

0
Mal wieder eine Aufgabe die auf indi zurückgeht (sry, dass ich etwas lange zum posten gebraucht hab :) )

Also es geht darum ein Programm zu schreiben, dass mehrere Verzeichnisse so auswählt, dass eine vorher festgelegte Speicherplatzmenge optimal ausgenutzt wird, um z.B. bei einem Backup nicht 1/4 einer CD leer zu lassen.
Es soll folgendermaßen funktionieren:
Angenommen man möchte ein Backup eines bestimmten Laufwerkes oder Verzeichnisses machen, dass natürlich mehrere Unterverzeichisse hat, gibt man den Pfad und den verfügbaren Speicherplatz ein und das Programm wählt dann die Unterverzeichnisse so aus, dass der Speicherplatz optimal genutzt wird.

Ich hoffe jemand findet eine Lösung dafür
mfg
Nornagest
 
Wär schön, wenn jemand eine PHP-Lösung schreiben könnte. :D
 
Hmm, wenn du wirklich ein Backup ziehen willst und den Platz auf den Datenträgern optimal ausnutzen willst, würde ich es anders machen, nämlich eine Kombination von tar und split:

Man erzeuge ein virtuelles File, in dem alle zu archivierenden Files mit Verzeichnisinformationen drinne sind, wie tar halt, und teile dieses dann portionsweise auf die Datenträger auf, wie split halt. Auf den Datenträgern vermerkt man noch die laufende Nummer, um die Reihenfolge nachher sicherstellen zu können, und fertig ist die Laube. Platzausnutzung 100%.

In Pseudocode:
Code: 
Sub SchreibeByte(byte)
  if anzbytes > datenträgergröße
      if anzdatenträger > 0
         CloseAltenDatenträger()
      endif
      neuenDatenträgerAnfordern()
      anzdatenträger++
      schreibe_byte(anzdatenträger)    // für die Reihenfolge !!!
      anzbytes=1
   endif
  anzbytes++
  schreibe_byte(byte)
EndSub

Sub leseByteAusFiles
   if anzreadbytes > dateilänge
      if ÖffneNächstesFileAusListe() = FALSE
         noch_bytes_einzulesen=FALSE
         return -1
      endif
      anzreadbytes=0
      SchreibeKennsatzMitDateiinformationen()
   endif
   return lese_ein_byte()
EndSub

Main()
   anzdatenträger=0
   anzreadbytes=0
   dateilänge=-1
   anzbytes=datenträgergröße+1
   noch_bytes_einzulesen=TRUE

   while noch_bytes_einzulesen
      byte=leseByteAusFiles()
      if byte > -1
         SchreibeByte(byte)
      endif
   wend
   CloseAltenDatenträger()
END

Oder schwebte dir als Aufgabe vor, eine gegebene Menge von Zahlen (Dateigrößen) so aufzuteilen, daß man sie in möglichst wenigen Einheiten bestimmter Größe (Datenträgern) unterbringen kann?
 
Hmm, wenn du wirklich ein Backup ziehen willst und den Platz auf den Datenträgern optimal ausnutzen willst, würde ich es anders machen, nämlich eine Kombination von tar und split:
Zum Vergrößern anklicken....

Keine Gute Idee. Es war genauso gedacht, wie es Nornagest in der Aufgabenstellung schrieb. :))
 
Na gut,

hier ein Proggi, welches verschiedene Größen auf Datenträgern verteilt. Das Auslesen der Directories, schreiben des Backups, Lizenzzahlungen an Microsoft wegen Verwendung von Leerzeichen und Kommentaren im Quellcode schenke ich mir, da es ja um den reinen Verteilalgorithmus geht. Dieser hier verteilt stur, was noch drauf paßt

Code: 
# include <stdio.h>
# include <stdlib.h>

int main(int argc, char **argv)
{
   /* Die Groessen der betroffenen Dateien */
	int daten[32]={47,112,18,3,4,1,933,144,332,223,47,2,2,11,15,64,57,58,
	               432,32,543,47,98,85,7,765,344,500,117,235,711,23};
   /* Das Fassungsvermoegen eines Datentraegers */
	int fassungsvermoegen=1000;

	int t;
	int anz, anzdat=0;

                 /* Passen alle Files ueberhaupt auf einen Datentrageger? */
	for(anz=0, t=0; t<32; t++){
		if(daten[t]>fassungsvermoegen) anz++;
	}
	if(anz>0){                     /* Nein? Dann raus                      */
		printf("%d Daten passen nicht auf einen Datentraeger!!!\n", anz);
		return(1);
	}
	for(;;){                       /* Bis alle wech sind                   */
		for(anz=0, t=0; t<32; t++){ /* Noch Daten zu verteilen da?          */
			if(daten[t]>0) anz++;
		}
		if(anz==0) break;           /* Nein, Fertig.                        */
		for(anz=0, t=0; t<32; t++){
			if(daten[t]>0){
				if(daten[t]<=(fassungsvermoegen-anz)){ /* Passt noch rauf?    */
					printf("%d\n", daten[t]);           /* Nehmen,...          */
					anz+=daten[t];   
					daten[t]=0;                         /* und markieren.      */
				}
			}
		}
		printf("%d ==========( voll )===========\n", anz); /* Einer voll    */
		anzdat++;
	}
	printf("Fertig, %d Datentraeger belegt.\n", anzdat);
	return(0);
}
 
Ich weiss nicht, ob ich die Aufgabe richtig verstanden habe, aber hier meine Lösung in C#.NET :

Class1.cs
Code: 
using System;
using System.IO;
using System.Collections;
using System.Windows.Forms;	//NUR für den FolderBrowserDialog


namespace Platzausnutzung
{
	class Class1
	{
		internal static DirectoryInfo dir;	//Um Ordnerinformationen auszulesen
		internal static ArrayList Dirs= new ArrayList(0);	//ArrayList für Ordnernamen
		private static ArrayList DirSizes = new ArrayList(0);	//ArrayList für Ordnergröße
		private static long temp;	
		private static long temp2;
		private static FolderBrowserDialog OrdnerWahl = new FolderBrowserDialog();	//zum komfortablen Ordner auswählen
		

		
		static void Main()
		{
			long maximal;	//lokale Variable für den Maximalwert des Speichers
			
			OrdnerWahl.Description = "Bitte einen Ordner auswählen, von dem ein Backup gemacht werden soll";
			OrdnerWahl.ShowNewFolderButton = false;
			if(OrdnerWahl.ShowDialog() == DialogResult.OK)	//Ordnerauswahl
				dir = new DirectoryInfo(OrdnerWahl.SelectedPath);

			Console.Write("Bitte den Maximalspeicherplatz des Backups eingeben (in KB): ");
			maximal = Convert.ToInt64(Console.ReadLine());	//Maximalgröße eingeben
			
				FileSystemInfo[] ordner = dir.GetFileSystemInfos();
		
			foreach (System.IO.FileSystemInfo obj in ordner)
			{
				
				if (obj.GetType().ToString() == "System.IO.DirectoryInfo")	//Auf weitere Unterordner prüfen
				{
					temp2 = FileMethoden.hatUnterverzeichnis((DirectoryInfo) obj);
					Dirs.Add("(directory) " +obj.Name + " -> "+ temp2 +"KB ");
					DirSizes.Add(temp2);
					
					FileMethoden.i = 0;
				}
				else	//Wenn keine weiten Unterordner vorhanden, die Größe der Dateien zusammenrechnen
				{
					FileInfo Datei = new FileInfo(obj.FullName);
					temp += Datei.Length;
				}
			}

			Dirs.Add("(files) Dateien -> " + temp/1024 + "KB");	//Dateigröße im Root Ordner in die ArrayList einfügen

			Console.WriteLine("\n\n Die folgenden Verzeichnisse wurden ausgewählt: \n");
			FileMethoden.DatenVerteilen(DirSizes, maximal);	//Methode um die "richtigen" Verzeichnisse auszuwählen
			
			Console.ReadLine();
			
		}
	}
}

FileMethoden.cs
Code: 
using System;
using System.IO;
using System.Collections;

namespace Platzausnutzung
{
	internal class FileMethoden
	{
		internal static long i = 0;	// temp Variable
		private static long temp = 1;	//temp Variable
		
		
		internal static long hatUnterverzeichnis(DirectoryInfo dir) //Die Größe des übergebenen Verzeichnisses prüfen
		{
			
			FileSystemInfo[] ordner = dir.GetFileSystemInfos();
			foreach (System.IO.FileSystemInfo obj in ordner)
			{
				if (obj.GetType().ToString() == "System.IO.DirectoryInfo")
				{
					FileMethoden.hatUnterverzeichnis((DirectoryInfo) obj);	//Rekursiver Methodenaufruf
				}
				else
				{
					FileInfo datei = new FileInfo(obj.FullName);
					i += (datei.Length / 1024);	//Byte in KB
				}

			}
			return (i);

		}

		internal static void DatenVerteilen(ArrayList daten, long maxi) //Dateien verteilen
		{
			for (int i = 0; i != daten.Count; i++)	//Schauen ob es Ordner gibt, die absolut nicht passen
			{
				if((long)daten[i] > maxi)
				{
					daten.RemoveAt(i);
					Class1.Dirs.RemoveAt(i);
					i--;
				}
			}
			for (int i = 0; i != daten.Count; i++)	//Nacheinandern die ArrayList auslesen und wenn
			{										//noch Platz vorhanden ist Ordner hinzufügen
				if(temp > maxi)
				{
					temp -= (long)daten[i-1];
					break;
				}
				else
				{
					temp += (long)daten[i];
					if(temp < maxi)
						Console.WriteLine(Class1.Dirs[i].ToString());
				}

			}
			Console.WriteLine("\n Gesamtspeicherplatz: "+temp.ToString() + "KB");

												  
		} 
	}

}

Habe System.Windows.Forms nur wegen dem BrowserDialog eingebunden, da es mir doch bei öfterem Benutzen auf die Nerven geht immer den kompletten Pfad in die Eingabeaufforderung einzugeben.

Das Programm unterstützt nur die 1. Ebene von Unterordnern des ausgewählten Verzeichnisses, da ich mir nicht die Mühe machen wollte weitere Ebenen einzeln zu unterstützen, da es meiner Meinung auch Unsinn ist, denn diese Ordner sind dann meistens für die darüberliegenden Ebenen unerlässlich und ein alleiniges Backup bringt nicht viel.

Ich habe natürlich nicht die 'optimale' Platzausnutzung implementiert, da dieser Algorithmus doch sehr viel Arbeit wäre (Rucksack-Prinzip), ich habe es ähnlich wie as3jg implementiert.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben