Opgelost Programmeeropgave

In De Bilt werd de volgende oplossing genoemd:

for i = 1 to 1000000
do
lees de hele input file
om te controleren of i erin voorkomt
if antwoord = 'nee'
then
print i
fi
done

Verbeterde versie:

maak een hulp bestand met de getallen 1 t/m 1000000 in records van vaste lengte.
open de input en het hulp bestand
while getal = read( input)
do
seek record getal in het hulp bestand
en vervang het getal door NUL bytes
done
sluit de bestanden
filter alle NUL bytes uit het hulp bestand (bijv. met het 'tr' commando)
je houdt dan alle getallen over die niet in de input voorkomen.

Hint
In de Bilt werden logaritmen op grondtal 2 genoemd; realiseer je dat 2log(1000000) = 10 (bijna).

Via deze link bestanden opgave vindt je een zip-file met het inputbestand (met 1.000.001 - 80 getallen) en de 80 getallen die er niet in staan

Sorry. 2log(1000000) = 20, natuurlijk.

Nog een suggestie, die ik maar QuickCheck zal noemen:

Loop het invoerbestand af en schrijf de getallen naar twee hulpbestanden, zodanig dat de getallen kleiner dan het gemiddelde (500.000) in het ene bestand komen en de rest in het andere. Tel ondertussen het aantal elementen in elk deel. Als een van de hulpbestanden het maximale aantal elementen heeft, verwijder dat dan.

Roep de procedure recursief aan op de overblijvende hulpbestanden met het berekende minimum en maximum als parameter (als minimum en maximum gelijk zijn ben je klaar). Als je een hulpbestand overhoudt met 0 elementen, dan print je alle getallen tussen het minimum en maximum en verwijdert dat bestand.

Dit is geen sorteren, maar het effekt is het zelfde.

Een soort quicksort, maar dan op disk. Zal best wel werken.

Ik denk meer de volgende kant op:
- lees het bestand in, 10 getallen per keer
- sorteer ze en schrijf afwisselend een reeks van 10 weg op bestand A en bestand B
- lees vervolgens bestand A en B in en voeg de reeksen van 10 samen tot reeksen van 20 en schrijf die afwisselend weg op bestand C en D
- voeg op de zelfde manier C en D samen op E en F met reeksen van 40
- herhaal dit totdat je 1 reeks krijgt
- dan is het bestand gesorteerd en kun je vrij gemakkelijk de ontbrekende getallen bepalen
Aangezien in iedere run de grootte van de reeksen verdubbelt en het aantal halveert ben je in 20 runs door het sorteerprocess heen
Knuth spendeert in TAOCP hoofdstuk 5.4 aan external sorting

Ik heb ondertussen achterhaald waar het oorspronkelijke probleem vandaan komt en ik heb ook mijn toenmalige oplossing achterhaald.
Die werkt vrij snel (< 3 seconden) maar schrijft wel 1730 tijdelijke bestanden weg....
En dat op een echte harddisk (dwz geen SSD).
Mijn oplossing destijds was ongeveer die van Dan the Man
- verdeel het oorspronkelijke bestand in twee bestanden
- bestand 1: alles in de range 1..500000
- bestand 2: alles in de range 500.001 -- 1.000.000
Verwerk (via recursie) vervolgens de twee bestanden.
Omdat ik weet hoeveel regels in de bestanden terecht komen kan ik het verwerken van bestanden die net zoveel regels bevatten als de range groot is skippen. Dat levert plm. 800 bestanden op die niet verder verwerkt hoeven te worden.
Dit kan omdat duplicaten niet voorkomen.

Het oorspronkelijke probleem komt uit het boek van Jon Bentley (Programming Pearls (1999) --nog steeds een aanrader en het is ondertussen op internet) te vinden.

Het testbestand wijkt af van de specificatie van het probleem: het bevat zowel de getallen 0 als 1000000:-(

Het probleem is als 'opgelost' gemarkeerd; hierbij een poging om een oplossing te vinden.... Om te beginnen verander ik het probleem maar zodat het draait om getallen van 6 cijfers (000.000 tot en met 999.999) -- zie mijn vorige opmerking.

Dan verzon ik iets wat je kunt doen met een array van 10 gehele getallen en dat het bestand regel voor regel inlezen, eventuele voorloopnullen aanbrengen en tellen hoe vaak je de cijfers 0 t/m 9 aantrof. Noem het cijfer dat het minste voorkwam c.

De volgende doorgang splits lees je het invoerbestand weer in en schrijft de getallen naar een zevental hulpbestanden: het eerste bestand ontvangt de getallen waar op de eerste positie een c voorkomt,... en het zesde bestand de getallen met dat cijfer op de zesde positie; het zevende bestand krijgt de getallen waar dat cijfer helemaal niet in voorkomt. Sommige getallen komen inderdaad in meerdere bestanden.

In de derde stap kijk je hoe groot de hulpbestanden zijn (zonder ze te lezen), vergeleken met het aantal dat ze zouden hebben als alle getallen van 000.000 t/m 999.999 in de invoer voorkwamen. Als dat aantal gelijk is, kun je het hulpbestand verwijderen, anders moet je het recursief verder doorzoeken.

De recursie is de vierde stap: daarbij gebruik je een array van 1 bits (booleans, flags) die initieel 0 zijn, waarin je het c-e element op 1 zet. De eerste stap wijzigen we zodanig dat cijfers waarvoor het bitmasker een 1 bevat moeten worden overgeslagen. Als alle bits in het masker op 1 staan moet de recursie stoppen. We hebben nog een extra parameter die initieel ook 000.000 is, maar waarvan je het i-e cijfer vervangt door een c. Als de recursie klaar is, zit je met een leeg hulpbestand en druk je die parameter af, die een ontbrekend getal moet zijn.

Na de recursieve aanroep moet je nog de hulpbestanden verwijderen.

Discussie: als je alle bestanden twee keer doorleest hoef je minder hulpbestanden te maken dan wanneer je gewoon bij het eerste cijfer begint. In dat geval hoef je elk bestand maar één keer door te lezen. Wat is efficiënter?

Hierbij de hierboven aangeduide "oplossing" in de vorm van Java code. Het is niet de meest snelle, maar gebruikt inderdaad een array van 10 integers (en een array met de namen van de tijdelijke bestanden). Om een nette uitvoer te krijgen moet je de getallen sorteren en duplicaten verwijderen.

Hierbij mijn oplossing
#! /usr/bin/perl

use strict;

use constant RANGESIZE => 10;
use constant DEBUGPRINT => 0;


# argumenten: N filenaam
# de file bevat unieke getallen in de range 0..N
# geef de missende getallen met zo weinig mogelijk geheugengebruik
# (niet inlezen, geen bitmap maken)
# en zonder de file te sorteren met een externe sort

my $N=shift;
my $file=shift;
our $TempFileSeqNbr=0;



OnderzoekFile($file,0,$N);
print STDERR "$TempFileSeqNbr tijdelijke files gemaakt\n" if DEBUGPRINT;

sub OnderzoekFile
{
my $file=shift;
my $lower=shift;
my $upper=shift;

print "$file $lower $upper\n" if DEBUGPRINT;

if ($upper+1-$lower <= RANGESIZE) {
LeesHeleFile($file,$lower,$upper);
return;
}
my $pivot=int(($lower+$upper) / 2);
my $lcnt=0;
my $hcnt=0;
my $lfile=GeefTempFile();
my $hfile=GeefTempFile();

# open de inputfile
open(INPUT,"<$file" or die "Open error on $file\n";

# open de outputfiles
open(LOW ,">$lfile" or die "Open error on $lfile for output\n";
open(HIGH,">$hfile" or die "Open error on $hfile for output\n";
while(<INPUT> {
chomp();
my $nbr=$_;
if ($nbr <= $pivot) {
print LOW "$nbr\n";
$lcnt++;
} else {
print HIGH "$nbr\n";
$hcnt++;
}
}
close INPUT;
close LOW;
close HIGH;


print "$lfile=$lcnt $hfile=$hcnt\n" if DEBUGPRINT;
OnderzoekFileEnDelete($lfile,$lcnt,$lower,$pivot);
OnderzoekFileEnDelete($hfile,$hcnt,$pivot+1,$upper);

}
sub OnderzoekFileEnDelete
{
my ($file,$cnt,$lower,$upper)=@_;
unless ($upper - $lower + 1 == $cnt) {
OnderzoekFile($file,$lower,$upper)
} else {
print "Onderzoek $file ($lower - $upper - $cnt) onnodig\n" if DEBUGPRINT;
}
unlink $file;
}
sub LeesHeleFile
{
my ($file,$lower,$upper)=@_;
my @nbr=((0) x ($upper-$lower+1));
open(INPUT,"<$file" or die "Open error on $file\n";
while(<INPUT> {
chomp();
my $nbr=$_;
die "$nbr klopt niet met range $lower .. $upper in file $file\n"
if $nbr < $lower || $nbr > $upper;
$nbr[$nbr-$lower]=1;

}
close INPUT;
for my $i (0..$#nbr) {
printf ">>> %d\n",$i+$lower
unless $nbr[$i];
}
}
sub GeefTempFile
{
$TempFileSeqNbr++;
return sprintf("ch0201-%04d.tmp",$TempFileSeqNbr);
}

De bijbehorende output is
>>> 0
>>> 35669
>>> 108293
>>> 126816
>>> 235522
>>> 266142
>>> 296793
>>> 395810
>>> 429365
>>> 522180
>>> 526613
>>> 540421
>>> 547737
>>> 551175
>>> 601002
>>> 633031
>>> 667441
>>> 731248
>>> 785671
>>> 804030
Door DEBUGPRINT op 1 te zetten krijg je allerlei extra informatie

Johans Perl programma kostte hier 6 s rekentijd, mijn Javaprogramma 4 s, en mijn C programma 2 seconden.

Wat ik er niet bij vermeld heb is dat je om de zelfde uitvoer te krijgen, de uitvoer van mijn programma's nog moet sorteren ( ./arglist bestand | sort -n -u onder Linux).

Als je naar de listing van Johans programma kijkt, dan zie je een optimalisatie die hij eerder niet vermeldde: de functie LeesHeleFile() wordt aangeroepen voor invoerbestanden van ten hoogste 10 getallen en die gebruikt een array van 10 getallen om de hele file in te lezen en te testen. Het idee achter Open Source is dat je broncode mag kopiëren. Ik heb Johans truc zelf ook toegepast, waardoor het aantal tijdelijke bestanden daalde van 6691 naar 4173 en de looptijd ongeveer een seconde korter werd.

Als ik Johans programma test dan produceert het 1.748 tijdelijke bestanden i.p.v. 1.730. Het kost ruim 6 seconden, wat zou betekenen dat zijn PC dubbel zo snel is. Johans programma leest 954 bestanden en gooit de rest meteen weg, zodat het in totaal 7.823.408 getallen test. Na vertaling van Perl in Java kost het nog maar 3 seconden.

Mijn programma produceert 4.173 tijdelijke bestanden en verwerkt er 1.392 en leest in totaal 9.563.573 getallen, omdat alle bestanden twee keer worden doorgelezen en doet daar 4 seconden over. Johans versie is dus sneller!

In onderstaand artikel kun je het nog eens rustig nalezen....
https://static-programmeren.hcc.nl/images/Artikelen/arglistig-artikel.pdf