Optimalis darabolo algoritmus

Sziasztok!

Egy algoritmus tokeletesiteseben kernem a segitsegeteket. A gyakorlati
problema tulajdonkeppen az lenne, hogy adott egy konyvtarhierarchia es
ugy akarod szetdarabolni CD/DVD-re iras elott, hogy minel
optimalisabban kihasznalhasd az adathordozok kapacitasat.

A tokeletes megoldasban az ISO9660 fajlrendszer felepitest is
figyelembe kellene venni ezert eleg mely ismeretet igenyelne a
teruleten. Egyelore csak a kovetkezo egyszerusitett specifikacion
gondolkodtam:

Bemenet:

- Egesz szamok halmaza. A szamok a fajlok meretet
reprezentaljak. Feltetelezzuk hogy mindegyik fajl merete nagyobb,
mint nulla. Gyakorlatban az ures fajlokat nem vesszuk bele a
bemenetbe.

- Maximalis darabmeret. Ez gyakorlatban az adathordozo kapacitasa.

Kimenet:

- Olyan fajlcsoportok halmazai, amelyekben egy-egy csoport osszmerete
alulrol konvergal a darabmerethez. Tehat a csoportmeret kisebb, vagy
egyenlo mint a darabmeret es ezek kulonbsege minel kisebb.

Konstrualtam egy mukodo, de nem optimalis algoritmust es irtam hozza
egy Python tesztprogramot:

[code:1:7ab67daa4d]#!/usr/bin/env python

"""Test program: Optisplit algorithm, version 1."""

import random
import sys

FILES_NUM = 100 # the number of files to generate.
MIN_FILE_SIZE = 3*10**8 # minimum filesize.
MAX_FILE_SIZE = 10**9 # maximum filesize.
SLICE_SIZE = 5*10**9 # the size of slices

def have_proper_file(free_space):
"""Have there a file with a size that is less or equal than free_space?"""
length = len(files)

if length == 0: # we have no files left.
return 0
elif length == 1: # we have only one file left. check it.
return files[0] <= free_space
else: # we have so many files. check them.
return min(*files) <= free_space

def pop_max(max):
"""Pop the greatest file size that is less or equal than max."""
bottom = 0
upper = len(files)-1
index = 0 # in case of bottom == upper

while bottom != upper:
index = (bottom+upper)/2

if max > files[index]:
if upper - bottom == 1: # special case
return files.pop(bottom)

bottom = index
else:
upper = index

return files.pop(index)

# generate random file sizes

files = []

for i in range(0, FILES_NUM):
size = random.randint(MIN_FILE_SIZE, MAX_FILE_SIZE)
files.append(size)

files.sort()

# print generated input and some statistics

print 'Number of files: ' + str(FILES_NUM)
print 'Minimum filesize: ' + str(MIN_FILE_SIZE)
print 'Maximum filesize: ' + str(MAX_FILE_SIZE)
print 'Average filesize: ' + str(sum(files)*1.0/FILES_NUM)
print 'Slice size: ' + str(SLICE_SIZE)
print

# group the files into slices.

slices = []

while files:
slice = []
free_space = SLICE_SIZE

while have_proper_file(free_space):
file = pop_max(free_space)
slice.append(file)
free_space -= file

slices.append(slice)

# slice statistics.

slice_stats = map(lambda slice: sum(slice)*100.0/SLICE_SIZE, slices)
average_fill = sum(slice_stats[0:-1]) / (len(slices)-1)

# print results.

for slice_index in range(len(slices)):
print 'slice ' + str(slice_index+1) + ': ' +\
str(slice_stats[slice_index]) + '% fill with ' +\
str(len(slices[slice_index])) + ' files.'

print
print 'Average fill (not counted the last slice): ' + str(average_fill)
[/code:1:7ab67daa4d]

Az algoritmus ugy kepez csoportokat a fajlok halmazabol, hogy elkezd
egy csoportot, amelyet sorban feltolt leheto legnagyobb elerheto
fajlokkal, amelyek meg belefernek a csoportba. Ezeket a fajlokat
sorban kiveszi a kozosbol. Ha nincs mar olyan kicsi fajl, amely
beleferne az aktualis csoportba, uj csoportot kezd es ugyanenilyen
modon tolti fel a kovetkezot, amig van fajl a kozosben.

A tesztprogram szerint a megadott tesztadatokkal (lasd a
kodban) a darabok kitoltottsege (az utolso darabot nem szamitva) eleg jo,
de meg igy sem optimalis:

[code:1:7ab67daa4d]Number of files: 100
Minimum filesize: 300000000
Maximum filesize: 1000000000
Average filesize: 638961674.94
Slice size: 5000000000

slice 1: 96.1392765% fill with 5 files.
slice 2: 99.94811224% fill with 6 files.
slice 3: 99.99905108% fill with 6 files.
slice 4: 99.9878866% fill with 6 files.
slice 5: 99.971893% fill with 7 files.
slice 6: 99.99468824% fill with 7 files.
slice 7: 96.47377092% fill with 7 files.
slice 8: 99.93813048% fill with 8 files.
slice 9: 97.43366466% fill with 8 files.
slice 10: 99.95500118% fill with 9 files.
slice 11: 95.59641194% fill with 9 files.
slice 12: 99.85980006% fill with 11 files.
slice 13: 92.62566298% fill with 11 files.

Average fill (not counted the last slice): 98.7748072417
[/code:1:7ab67daa4d]

Az is erdekelne hogy milyen tesztadatokat javasoltok. Gyakorlaias
szempontok alapjan valasztottam az aktualis adatokat. (DVD meret,
multimedia fajlok...)

Van egy olyan erzesem, hogy a hatekonyabb algoritmusok drasztikusan
magasabb futasi idovel rendelkeznek, igy tobb megoldas is erdekel.

Ezt az algoritmust Midnight Commander-rel is osszehegesztenem
menukiterjeszteskent, igy sokak altal lenne hasznalhato.

Elore is koszonom a segitsegeteket!

Kosz szepen a sok segitseget mindenkitol! Nem gondoltam volna, hogy ennyi hozzaszolas szuletik.

Ahogy olvastam a postokat, egyre inkabb tudatosult bennem, hogy milyen harmatgyenge vagyok algoritmuselmeletbol. Gaz, de meg az NP-teljes fogalmat is ugy kellett eloszednem. A genetikus programozasrol hallottam mar, de gyakorlatlag meg semmit nem tudok rola.

Babszemnek koszonom a refernciakat. At fogom nezni oket.

Bar ez az egyszeru moho megoldas is, mint mondtatok kozel optimalis eredmenyt ad, nem akarok itt megallni. Jo erv, hogy azt az 1-2 plusz DVD-t meg se erzi a penztarcank, de ha optimalisabban is meg lehet oldani es kevesebb lemezbol is ki lehet jonni, akkor miert ne.

Utana akarok menni a dolognak mindenkeppen es errol majd tajekoztatlak is benneteket majd ha tobb idom lesz.

pete: Koszi a dicseretet. A koncepcio szerintem is rulez, de az UC a jelenlegi formajaban majdnem hasznalhatatlan. Csak a panelben navigalhatsz. Raadasul nem Python lesz a vege, hanem mint mar mondtam neked C# (Mono). Szoval meg sok viz lefolyhat a Dunan, mire tenyleg megtanulok mindent hozza (interfesz alapu programozas/tervezes - C#, XML, fajlrendszer anatomia meg egy rakas API) es hasznalhatova erik.
Apropo, ideje lenne mar frissitenem a honlapom ide vonatkozo reszet, mert ha jol emlekszem akkor meg a Perl-ben akartam megirni is arrol szovegeltem 1000-rel.