Re: [PERL] Smart måde at checke på?

[Christian Borup <sslug@sslug>]

Carsten Svaneborg wrote:

> Jeg har ca. 6800 patentkoder af formen EP01234567.
>
> Jeg vil gerne lavet et filter således at det læser en liste
> af kendte patent koder fra en fil, og fra stdin læser en strøm,
> der også indeholder patent koder, og filtret skal udskrive til
> stdout alle de patentkoder i stdin, der IKKE var i filen.
> Dvs. nye patenter. Antallet af input er formodeligt i størrelses
> ordnen 10k patent koder. Så der er mange af dem!

Størrelsen af input betyder ikke alverden, da der ikke er noget i dit
brev der tyder på at du får brug for at læse dem alle ind på en gang.

> Hvad er den mest praktiske måde at implementere dette på?

Med en hash...

> Antallet er stort, så jeg vil nødigt lave et array og så
> traversere arrayet for hver input, det lyder også for let.
> Ditto ville det være kedeligt at lime dem sammen til en
> stor streng, og så bruge et regulært udtryk i en stor streng
>
> Min idee var at lave en træstruktur fordi så bør jeg erstatte
> O(N) med O(logB(N)) scaling for et eller andet B~10.

Hashes er hurtigere end O(log N), i princippet er de vel O(1)...
Læg de eksisterende patentkoder ind i en hash, og check på om
patentkoderne fra input filen eksisterer i hash'en efterhånden som du
læser dem ind.
Jeg mener her bare en hash alá: $hash{"EP01234567"}= 1;

> Jeg har dog nogle problemer med at hitte ud af hvordan
> man kan lave træ strukturer i Perl.
>
> Jeg har rodet med autovivification som:
>
> my %hash;
>
> $hash{'E'}{'P'}{'0'}{'1'}.... = 1;
>
> Dette bør give en hash af en hash af en ..
> Problemet er bare at noder ikke kan have information og
> subnoder samtidigt.
>
> Fx. vil
> $hash{'E'}{'P'}{'0'}  = 2;
>
> slette noden med 1 i ovenover fordi EPO01... er en submode af EP0.

Hvis du gerne vil vide noget om træstrukturer i perl, så skriv endelige
tilbage, men de er ikke den bedste løsning på dit konkrete problem.

./borup