Ik ben bezig met het programmeren van mijn NAS, waarbij ik elk halfuur snapshots (=soort van back-up) laat maken van mijn bestanden (echter enkel maar wanneer er wijzigingen zijn t.o.v. voorgaande snapshot).
Om te zorgen dat het geheel een beetje beheersbaar blijven, is de laatste 24uur beschermd en worden van de laatste 3mnd maximaal 40 snapshots bewaard.
Nu ben ik op zoek naar een algoritme, wat een goede verdeling van de snapshots waarborgt. Omdat recentere meer waard zijn dan niet-recente snapshots, heb ik besloten een logaritmische verdeling over tijd aan te houden. Waarbij 0 het moment nu is, en het logaritme van het aantal verstreken seconden sinds het maken van de snapshot als waarden genomen wordt.
Één keer per dag draait er een script om te bepalen welke snapshots bewaard moeten worden en welke niet.
Om te bepalen welke snapshots wel en niet bewaard moeten worden, ben ik nu op zoek naar een algoritme die het beste bepaald welke passend zijn bij een goede verdeling.
Nu dacht ik, dit probleem komt eigenlijk neer op:
- Verzameling A (alle logaritmische waarden)
- B = minimale waarde uit verzameling A
- C = maximale waarde uit verzameling A
- N = het aantal te bewaren snapshots (in dit geval 40).
Definieer een lijn: ([1,B] => [N,C])
Selecteer D vervolgens als N-2 waarden uit verzameling A gesorteerd in oplopene volgorde, zodanig dat als ze als punten ingevoegd worden in het assenstelsel van voorgenoemde lijn ([2, D(1)], [3, D(2)], ..., [N-1,D(N-2)]) dat de afstand tussen deze punten en de lijn minimaal is.
Nu is het probleem dat als je dit met een least-squaresmethode doet je over alle combinaties moet itereren. Dat kan soms wel extreem veel combinaties opleveren.
Hierbij heb ik twee vragen:
- Is er een bekend ander probleem in het leven, waarbij een dergelijke vraag gesteld wordt? Zo ja, hoe wordt dit dan opgelost?
- Is er een efficiënter algoritme om dit probleem op te lossen?
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
JWvdVeer
- Artikelen: 0
- Berichten: 1.116
- Lid geworden op: wo 20 mei 2009, 09:36
-
Xilvo
- Moderator
- Artikelen: 0
- Berichten: 10.821
- Lid geworden op: vr 30 mar 2018, 16:51
Re: Subverzameling zo goed mogelijk linair verdeelde waarden
Stel, je hebt een miljoen snapshots verdeeld over de afgelopen 3 maanden.
Je past een methode toe om daaruit 40 snapshots te kiezen zodat die zo goed mogelijk logaritmisch over de tijd verdeeld zijn. De rest gooi je weg. Je hebt een, volgens jouw eisen, nagenoeg perfecte opdeling.
Je komt een dag verder, er zijn er 48 snapshots bijgekomen. Stel, van gisteren wil je 2 snapshots bewaren. Die komen erbij, er moeten dus 2 andere weg Welke? De laatste, de een-na-laatste? en welke andere?
Wat je ook doet, wat je overhoudt heeft lang niet meer die mooie logaritmische verdeling die je eerst had.
Ik zou een veel simpeler schema kiezen. Bijvoorbeeld, van de afgelopen week 2 per dag, van de week ervoor 1 per dag, van de twee weken daarvoor 1 op de twee dagen, enz.
Je kunt bij het opslaan van de snapshot er al een levensduur aanhangen.
Ochtend: 1 week
Avond, oneven dagnummer: 2 weken
Avond, even dagnummer, oneven weeknummer: 4 weken
Zoiets.
Het is maar een voorbeeld, je kunt het aanpassen aan de totale periode en het totaal aantal snapshots dat je wilt bewaren.
Maar het maakt het veel makkelijker te bepalen welke snapshots je na welke tijd weg moet gooien.
Je past een methode toe om daaruit 40 snapshots te kiezen zodat die zo goed mogelijk logaritmisch over de tijd verdeeld zijn. De rest gooi je weg. Je hebt een, volgens jouw eisen, nagenoeg perfecte opdeling.
Je komt een dag verder, er zijn er 48 snapshots bijgekomen. Stel, van gisteren wil je 2 snapshots bewaren. Die komen erbij, er moeten dus 2 andere weg Welke? De laatste, de een-na-laatste? en welke andere?
Wat je ook doet, wat je overhoudt heeft lang niet meer die mooie logaritmische verdeling die je eerst had.
Ik zou een veel simpeler schema kiezen. Bijvoorbeeld, van de afgelopen week 2 per dag, van de week ervoor 1 per dag, van de twee weken daarvoor 1 op de twee dagen, enz.
Je kunt bij het opslaan van de snapshot er al een levensduur aanhangen.
Ochtend: 1 week
Avond, oneven dagnummer: 2 weken
Avond, even dagnummer, oneven weeknummer: 4 weken
Zoiets.
Het is maar een voorbeeld, je kunt het aanpassen aan de totale periode en het totaal aantal snapshots dat je wilt bewaren.
Maar het maakt het veel makkelijker te bepalen welke snapshots je na welke tijd weg moet gooien.
-
JWvdVeer
- Artikelen: 0
- Berichten: 1.116
- Lid geworden op: wo 20 mei 2009, 09:36
Re: Subverzameling zo goed mogelijk linair verdeelde waarden
Dank voor je suggesties. Heb inderdaad even nog over het idee nagedacht. En bedacht dat ook een least squares methode op kan leveren dat je met een aantal dicht op elkaar gemaakte snapshots kan komen te zitten. Uiteindelijk bedacht ik: het gaat uiteindelijk meer om de verschillen in tijd tussen de verschillende snapshots.
Dus:
- A = gesorteerde lijst van logaritmen van het aantal gepasseerde seconden sinds het maken van de snaphots
- B = lijst, zodat B(N)=(A(N)-A(N-1))^2 + (A(N)-A(N+1))^2
- Selecteer snapshot met laagste waarde in lijst B (waarbij 1 en N zijn uitgesloten) en haal deze uit de lijst, verwijder hem als hij niet in de beschermde periode zit.
- Herhaal voorgaande stappen, totdat lijst A maximaal nog aantal elementen bevat dat je theoretisch wilt bewaren.
Dus:
- A = gesorteerde lijst van logaritmen van het aantal gepasseerde seconden sinds het maken van de snaphots
- B = lijst, zodat B(N)=(A(N)-A(N-1))^2 + (A(N)-A(N+1))^2
- Selecteer snapshot met laagste waarde in lijst B (waarbij 1 en N zijn uitgesloten) en haal deze uit de lijst, verwijder hem als hij niet in de beschermde periode zit.
- Herhaal voorgaande stappen, totdat lijst A maximaal nog aantal elementen bevat dat je theoretisch wilt bewaren.
