Hvordan finne forskjeller i større datalister, rasktest mulig?

[siDDis]

Eg kom over for nokre månedar sidan noko interessant som eg eigentleg aldri hadde tenkt over før.

Eg hadde ein problemstilling med at to større lister måtte samanliknast, og at eg måtte plukke ut forskjellane mellom dei. Denne operasjon var også kritisk i henhold til tid.

 

Sidan eg programmerte dette i Python og gjor det på den "normale" Python måten for å finne forskjellane, så fant eg fort ut at ytelsen blei heilt elendig.

Her var eg nødt å optimalisere koden, for denne operasjonen tok fleire minuttar på gamle måten. Så kom eg over noko som løyste dette problemet på under 1 sekund, og med å redusere antall kodelinjer også. Så og si alle programmeringspråk har dette innebygd(Og til nettleserar/Javascript). Så derfor tenkte eg å leggja ut utfordringa her.

 

Finn dei forskjellige verdiane i begge listene eg har lagt ut her. Utfør det i det språket du trives best i. Kravet er at algoritmen for å finne forskjellane utfører denne operasjonen på under 1 sekund. Tiden for å laste inn dataen til ein datastruktur tar me ikkje med, bare algoritmen for å finne forskjellane.

[siDDis]

Filene

data1.txt

data2.txt

Oppdaterte filer:

data5.txt

data6.txt

Endret 24. april 2013 av siDDis

[siDDis]

Løysningforslag Python for dei feige

 

 

losningsforslag.py.txt

 

 

Endret 21. april 2013 av siDDis

[Sokkalf™]

Ruby:

data1 = []
data2 = []
f1 = File.open('data1.txt')
f2 = File.open('data2.txt')
f1.each_line do |line|
 data1 << line
end
f2.each_line do |line|
 data2 << line
end
puts Time.now
notindata2 = data1 - data2
notindata1 = data2 - data1
puts "Elementer i data1.txt som ikke finnes i data2.txt :"
puts notindata2
puts "Elementer i data2.txt som ikke finnes i data1.txt :"
puts notindata1
puts Time.now

 

Kjøring:

2013-04-21 15:19:50 +0200

Elementer i data1.txt som ikke finnes i data2.txt :

1687926652

1431419379

950390868

42710819

514627089

1427948303

Elementer i data2.txt som ikke finnes i data1.txt :

5687926652

7431779379

1950390868

22710819

627089

42798303

2013-04-21 15:19:53 +0200

 

Tok visst litt lengre tid enn i Python. Ble fryktelig spent på hva du hadde gjort for å få det til å gå så fort, men i bunn og grunn var det jo så og si samme løsningen.

[siDDis]

Interessant, med bare lister

Eg prøvde med Set i Ruby, men det var faktisk bittelitt treigare

Kanskje Ruby 2 er betre? Eg prøvde Ruby 1.9.3

[jag007]

Lagde et lite shellscript, for å løse dette:

#!/bin/ksh
file1=$1
file2=$2
sort <$file1 > 1.txt
sort <$file2 > 2.txt
time comm -3 1.txt 2.txt | sort

 

Tidsforbruk:

real 0m0.153s

user 0m0.144s

sys 0m0.009s

 

Output som for andre resultat.

Men ser at programmet "comm", er ganske raskt.

Tar jeg med tinde det tar å sortere filene først, så tar hele operasjonen lengre tid (rett under 1.5 sekunder).

 

OSX 10.8.3, med CPU i7 2,3 GHz

 

/Jan

[siDDis]

Stiligt, det visste eg ikkje om. Minuset er at du må sortere først, men er det sortert så går det jo himla fort

[Sokkalf™]

"diff"-kommandoen er også temmelig kjapp her.

[zotbar1234]

Stiligt, det visste eg ikkje om. Minuset er at du må sortere først, men er det sortert så går det jo himla fort

 

Ifølge dine egne vilkår telles ikke sorteringstiden.

[Gjest Slettet+9871234]

Stiligt, det visste eg ikkje om. Minuset er at du må sortere først, men er det sortert så går det jo himla fort

 

Da er radix eller telle sortering raksest om de kan brukes siden de går i lineær tid. Boblesortering går i kvadratisk tid, mens de fleste andre sorteringsalgoritmer går i n log(n) tid.

[Sokkalf™]

C:

#include <stdio.h>
#include <string.h>
unsigned char *readFile(char *filename)
{
   int filesize, i;
   unsigned char *buffer = NULL;
   FILE *f;
   f = fopen(filename, "r");
   fseek(f, 0L, SEEK_END);
   filesize = ftell(f);
   buffer = malloc((sizeof(char) + 1) * filesize);
   fseek(f, 0L, SEEK_SET);
   fread(buffer, sizeof(char), filesize, f);
   buffer[filesize + 1] = '\0';
   fclose(f);
   for (i = 0; i < filesize; i++)
if (buffer[i] == '\n')
 buffer[i] = '\0';
   return buffer;
}
unsigned char *diffArray(unsigned char *a, unsigned char *b)
{
   while (*a && *b) {
unsigned int len_a = strlen(a);
unsigned char substr_a[len_a];
memcpy(substr_a, a, len_a);
substr_a[len_a] = '\0';
int len_b = strlen(b);
unsigned char substr_b[len_b];
memcpy(substr_b, b, len_b);
substr_b[len_b] = '\0';
int result = strcmp(substr_a, substr_b);
if (result < 0)
 printf("< %s\n> %s\n", substr_a, substr_b);
if (result > 0)
 printf("> %s\n< %s\n", substr_a, substr_b);
a += len_a + 1;
b += len_b + 1;
   }
   return " ";
}
int main()
{
   unsigned char *file1, *file2;
   file1 = readFile("data1.txt");
   file2 = readFile("data2.txt");
   diffArray(file1, file2);
   free(file1);
   free(file2);
   return 0;
}

$ time ./diffdata

< 1687926652

> 5687926652

< 1431419379

> 7431779379

> 950390868

< 1950390868

> 42710819

< 22710819

< 514627089

> 627089

< 1427948303

> 42798303

real 0m0.137s

user 0m0.121s

sys 0m0.015s

 

Jeg hater C.

[Gjest Slettet+9871234]

Men du kan C?

[Sokkalf™]

Nei, egentlig ikke.

 

Brukte et par timer på dette, men tok det som en anledning til å lære meg litt mer. Kjekt å kunne litt.

 

Går fort som fy når det funker. Kræsjer spektakulært når det ikke funker..

 

Edit: "kan" er forsåvidt rimelig subjektivt til tider. Har vært borti folk som sier de "kan" C som kan mindre enn meg - men jeg føler meg ikke fortrolig nok med språket til å si at jeg kan det. Litt for mye prøving og feiling på meg til at jeg kan si det.

Endret 22. april 2013 av Sokkalf™

[Gjest Slettet+9871234]

Du kjenner denne

 

http://users.powerne...ndr2/index.html

 

med løsninger på oppgaver fra boken?

 

Any man who reads too much and uses his own brain too little falls into lazy habits of thinking.

 

 

Education is what remains after one has forgotten what one has learned in school.

 

http://www.brainyquo...t_einstein.html

Endret 22. april 2013 av Slettet+9871234

[Sokkalf™]

Ja, jeg hadde den boken da jeg studerte - men har dessverre mistet den.

[Gjest Slettet+9871234]

Du finner den som PDF dokument på nettet om du gjør det riktige søket. Hint

 

tittel + .pdf

 

Merk der er et punktum foran pdf.

 

Du finner første og andre utgave.

 

Har også litt sans for denne: http://www.acceleratedcpp.com/

 

Jobber for øvrig med PostgreSQL for øyeblikket og fant denne

 

http://www.sai.msu.s...doc/intro.shtml

 

interessante ressursen på nettet. Noen ganger er det mye raskere å sammenligne, sortere, søke etc. direkte i en database.

 

Relatert: OpenFTS

 

OpenFTS (Open Source Full Text Search engine) is an advanced PostgreSQL-based search engine that provides online indexing of data and relevance ranking for database searching. Close integration with database allows use of metadata to restrict search results.

Endret 22. april 2013 av Slettet+9871234

[zotbar1234]

Edit: "kan" er forsåvidt rimelig subjektivt til tider. Har vært borti folk som sier de "kan" C som kan mindre enn meg - men jeg føler meg ikke fortrolig nok med språket til å si at jeg kan det. Litt for mye prøving og feiling på meg til at jeg kan si det.

 

sizeof(char) er meningsløs, da den er stipulert til 1.

[Lycantrophe]

sizeof(char) er meningsløs, da den er stipulert til 1.

Vel, ja. Den er fortsatt ok å bruke til tider, synes jeg, ettersom det (ofte) signaliserer hva du vil gjøre; eksplisitt påpeke den ene byten.

[Sokkalf™]

Ble uansett litt surr der ser jeg, gikk litt fort i svingene. (Allokerer en byte char mer enn nødvendig).

Ellers en del annet som er rotete og inkonsekvent, jeg ga meg ganske fort da det virket.

 

 

Men ja, det var for å illustrere at jeg skulle putte inn en char på slutten, nullkarakteren.

Endret 23. april 2013 av Sokkalf™

[Lycantrophe]

Da er radix eller telle sortering raksest om de kan brukes siden de går i lineær tid. Boblesortering går i kvadratisk tid, mens de fleste andre sorteringsalgoritmer går i n log(n) tid.

Ja, men disse forventer ting av input vi ikke kan anta.

 

Sokkalf: forventer ikke programmet ditt at input er sortert allerede?

Endret 23. april 2013 av Lycantrophe