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

[Gjest Slettet+9871234]

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

 

Jeg er klar over det og skrev

 

Da er radix eller telle sortering raksest om de kan brukes, siden de går i lineær tid.

 

Se også:

 

Sorting in linear time?

 

Wikipeida: Sorting algorithm

 

Hva med bøttesortering?

Endret 23. april 2013 av Slettet+9871234

[Lycantrophe]

Jeg er fullstendig klar over hvordan sortering fungerer. Også i lineær tid. Du skrev ingenting om de ikke ville fungere her (hint: det gjør de ikke.)

 

Dersom input alltid er heltall vil radix fungere. Dette er uspesifisert, men ut ifra datasettet kan det virke rimelig.

[Sokkalf™]

Nei, jeg kjørte det på de to filene som ligger vedlagt i posten til siDDis, umodifisert.

 

Edit: Det forutsetter nok dog at datasettene er like store (ihvertfall i antall linjer).

Endret 23. april 2013 av Sokkalf™

[Lycantrophe]

Sokkalf:

Nei, jeg kjørte det på de to filene som ligger vedlagt i posten til siDDis, umodifisert.

Vil ikke den da bare finne ulike som er ved siden av hverandre? Er dette gitt av problemet?

 

Hva med bøttesortering?

Bucket Sort er også verdiløs om vi ikke kan anta noe om uniform distrubsjon.

[Sokkalf™]

Sokkalf:

 

Vil ikke den da bare finne ulike som er ved siden av hverandre? Er dette gitt av problemet?

 

Jo, den finner ulike som er ved siden av hverandre, og på hvilken side ulikheten er - om det er gitt av problemet, tja, det er ihvertfall en mindre fullverdig løsning enn eksemplene gitt i Python og Ruby - men det løser jo forsåvidt problemet i dette tilfellet.

[Lycantrophe]

Jeg har ikke studert datasettene, bare lest problemstillingen. Og den sier ikke noe om rekkefølgen er signifikant.

 

Men jeg antar den ikke er det, ettersom jeg ser Set er foreslått som en løsning. Fra det virker det som om programmet ditt ikke egentlig løser problemet.

Endret 23. april 2013 av Lycantrophe

[GeirGrusom]

edit: foo

Endret 23. april 2013 av GeirGrusom

[Gjest Slettet+9871234]

Jeg har ikke studert datasettene, ...

 

Det har heller ikke jeg, men noen nevnte sortering og da sa jeg hva som er raskest gitt visse forutsetninger. Så vidt jeg husker er lister i Python ganske effektive.

 

Men innlastning av data og datastrukturereing må da bety noe.

 

Da tenker jeg med en gang streaming (splitting av filene) og innlasting av data i biter (jfr. flette sortering). Dagens maskiner med Gb minne har kanskje ikke noe problem med de relativt små filene i eksemplet. Hva med filer på noen TB?

[Lycantrophe]

Men hva er relevansen til hva som kunne løst problemet gitt en veldig spesifikk input når input ikke har den garantien?

 

Den asymptotisk raskeste måten å gjøre dette generelt er løsningen som først foreslått: traverser den ene listen og sett i en hash. Traverser deretter den andre listen og gjør et oppslag i hashen på om elementet er der eller ikke.

 

Du har deretter noen valg på hvordan du skal finne matchingen den "andre" veien. Asymptotisk vil dette også bli lineært, men jeg tipper sortering i mange tilfeller vil gi deg vel så gode resultater. Dette forutsetter at du bruker en god sorteringsalgoritme, selvfølgelig.

[GeirGrusom]

Men hva er relevansen til hva som kunne løst problemet gitt en veldig spesifikk input når input ikke har den garantien?

 

Den asymptotisk raskeste måten å gjøre dette generelt er løsningen som først foreslått: traverser den ene listen og sett i en hash. Traverser deretter den andre listen og gjør et oppslag i hashen på om elementet er der eller ikke.

 

Du har deretter noen valg på hvordan du skal finne matchingen den "andre" veien. Asymptotisk vil dette også bli lineært, men jeg tipper sortering i mange tilfeller vil gi deg vel så gode resultater. Dette forutsetter at du bruker en god sorteringsalgoritme, selvfølgelig.

 

Går vel an å traversere begge listene samtidig (forutsett at begge listene er sortert)?

 

if(*a != *b++)
 yield b[-1];
else
 a++;

Endret 24. april 2013 av GeirGrusom

[Lycantrophe]

Javisst, men det kan vi ikke (uten videre) forutsette. Da må vi også ta hensyn til sorteringen, n log(n), som vil bli den asymptotiske kjøretiden.

 

Tipper den allikevel er raskere på en del datasett. Derfor jeg spesifiserte asymptotisk.

Endret 24. april 2013 av Lycantrophe

[GeirGrusom]

Javisst, men det kan vi ikke (uten videre) forutsette. Da må vi også ta hensyn til sorteringen, n log(n), som vil bli den asymptotiske kjøretiden.

 

Tipper den allikevel er raskere på en del datasett. Derfor jeg spesifiserte asymptotisk.

Ettersom lastetiden ikke er en del av oppgaven, så ser jeg ikke problemet med å sortere datasettet på forhånd.

[Lycantrophe]

For all del, men det er jo en del av problemløsningstiden spør du meg.

[snippsat]

notindata2 = data1 - data2

Hmm artig hvordan fungerer dette i Ruby?,tenker da på Python hvor man må først brukes set() for så og gjøre data1 - data2.

Bruker Ruby hash eller er det gjort på annen måte.

Vanlig måte og skrive dette på i Python uten og bruke set().

>>> lst1 = ["car", "apple", "door"]
>>> lst2 = ["door", "house", "car"]
>>> [x for x in lst1 if x not in lst2]
['apple']

Da tenker jeg at lst1 - lst2 vil gi samme resultat i Ruby?

 

Har sett litt på oppgaven i Python og målt litt tid,ser ut som løsning du har er bra @siDDis.

Prøvd i PyPy uten at det ble raskere,mye avhenger nok av I/O sin lese hastighet her.

 

Kan jo for gøy skrive det på en linje med og kalle difference,men tiden blir jo dårligere da man må kalle motsatt for og få resultalt fra begge datasett.

print set(open("data1.txt").readlines()).difference(set(open("data2.txt").readlines()))

 

Da tenker jeg med en gang streaming (splitting av filene) og innlasting av data i biter (jfr. flette sortering). Dagens maskiner med Gb minne har kanskje ikke noe problem med de relativt små filene i eksemplet. Hva med filer på noen TB?

For og svare på dette med bruk av Python.

Er den store filen line basert kan man lese lese linje for line som en (lazy generator).

with open('really_big_file.dat') as f:
#Read only line by line into memory
for line in f:
	process_data(line)

Man kan lage en generator for og splitte opp filen og lese stykke for stykke.

Ja "kode tag" systemet på hw fungere jo ikke,så det blir litt blandet formatering av koden.

def read_in_chunks(file_object, chunk_size=1024):
"""generator to read a file piece by piece"""
while True:
	data = file_object.read(chunk_size)
	if not data:
		break
	yield data

with open('really_big_file.dat') as f:
for piece in read_in_chunks(f):
	process_data(piece)

[Paull]

Et C#-eksempel uten forhåndssortering (er ikke så drevet i linq, så finnes sikkert optimaliseringer):

 

var items1 = File.ReadLines(@"E:\temp\testdata\data1.txt").Select<string, Int64>(Int64.Parse).ToList();
var items2 = File.ReadLines(@"E:\temp\testdata\data2.txt").Select<string, Int64>(Int64.Parse).ToList();
var onlyinFirst = items1.Except(items2).ToList<Int64>();
var onlyinSecond = items2.Except(items1).ToList<Int64>();
Console.WriteLine("Items only in data1.txt: {0}", onlyinFirst.Count());
onlyinFirst.ForEach(k => Console.WriteLine(k));
Console.WriteLine("Items only in data2.txt: {0}", onlyinSecond.Count());
onlyinSecond.ForEach(k => Console.WriteLine(k));

 

Tok totalt 1,2 sekunder der 739ms var loading, og 539ms var sammenligning av items.

 

Komplett kode med timing-funksjoner:

 

 

using System;
using System.Diagnostics;
using System.IO;
using System.Linq;
namespace DataSort
{
class Program
{
	static void Main(string[] args)
	{
		Stopwatch loadtimer = new Stopwatch();
		Stopwatch compareTimer = new Stopwatch();
		Stopwatch completeTimer = new Stopwatch();
		loadtimer.Start();
		completeTimer.Start();
		var items1 = File.ReadLines(@"E:\temp\testdata\data1.txt").Select<string, Int64>(Int64.Parse).ToList();
		var items2 = File.ReadLines(@"E:\temp\testdata\data2.txt").Select<string, Int64>(Int64.Parse).ToList();
		loadtimer.Stop();
		compareTimer.Start();
		var onlyinFirst = items1.Except(items2).ToList<Int64>();
		var onlyinSecond = items2.Except(items1).ToList<Int64>();
		compareTimer.Stop();
		Console.WriteLine("Load Elapsed Ticks: {0}, Ticks/s: {1}, Milliseconds: {2}", loadtimer.ElapsedTicks, Stopwatch.Frequency, (((double)1000.0) * (double)loadtimer.ElapsedTicks / Stopwatch.Frequency));
		Console.WriteLine("Comparison Elapsed Ticks: {0}, Milliseconds: {1}", compareTimer.ElapsedTicks, (((double)1000.0) * (double)compareTimer.ElapsedTicks / Stopwatch.Frequency));
		Console.WriteLine("Items only in data1.txt: {0}", onlyinFirst.Count());
		onlyinFirst.ForEach(k => Console.WriteLine(k));
		Console.WriteLine("Items only in data2.txt: {0}", onlyinSecond.Count());
		onlyinSecond.ForEach(k => Console.WriteLine(k));
		completeTimer.Stop();
		Console.WriteLine("Total MilliSeconds: {0}", completeTimer.ElapsedMilliseconds, loadtimer.ElapsedMilliseconds);
		Console.ReadLine();
	}
}
}

 

Endret 24. april 2013 av Paull

[siDDis]

Siden det er diskusjon om sortering, tall osv så var egentleg mitt eksempel tatt med hensyn at man ikke helt visste kva dataten faktisk var. Så eg har oppdatert datasettene og sortert dei heilt ferdig som tekststrenger.

Så kan dykk heller konsentrera dykk om algoritmen

 

data5.txt

data6.txt

 

Skal teste C eksempelet så fort eg får tid, for det verka jo som bra saker! Men kanskje Set i stdlib er betre?

http://www.cplusplus.com/reference/set/set/

http://www.cplusplus.com/reference/algorithm/set_difference/

[Paull]

Med mer eller mindre samme C#-kode (4 linjer endret), tok lesing av filer 914ms og sammenligningen 788ms.

 

De fire endrede linjene er:

 

var items1 = File.ReadLines(@"E:\temp\testdata\data5.txt", System.Text.Encoding.ASCII).ToList();

var items2 = File.ReadLines(@"E:\temp\testdata\data6.txt", System.Text.Encoding.ASCII).ToList();

og

var onlyinFirst = items1.Except(items2).ToList();

var onlyinSecond = items2.Except(items1).ToList();

Endret 24. april 2013 av Paull

[Lycantrophe]

Dataene er sortert, sa du?

 

$ time ./a.out

> /home/olav/Documents/103375239.doc

< /home/olav/Documents/gameofthrones.doc

< /home/olav/Documents/.hiddenpornofiles/nudepic1.jpg

< /home/olav/Documents/.hiddenpornofiles/nudepic2.jpg

< /home/olav/Documents/.hiddenpornofiles/nudepic3.jpg

< /home/olav/Documents/.hiddenpornofiles/nudepic4.jpg

< /home/olav/Documents/porn.doc

> /home/olav/file753898663.txt

> /home/olav/file75400904.txt

> /home/olav/file75535687.txt

> /home/olav/file755566055.txt

> /home/olav/file75574336.txt

< /home/olav/Music

< /home/olav/Pictures

< /home/olav/.profile.conf

< /home/olav/raid

< /home/olav/.ssh/id_pub.rsa

< /usr/local/etc/989929161.conf

< /usr/local/etc/98994238.conf

< /usr/local/etc/989950314.conf

< /usr/local/etc/99962676.conf

< /usr/local/etc/nginx.conf

< /usr/local/etc/postgresql.conf

< /usr/local/etc/smb.conf

 

real 0m0.083s

user 0m0.068s

sys 0m0.012s

 

Inkludert innlesning. Er et par antagelser jeg ikke kan gjøre, så blir noen sjekker for mye. Men men. Mistenker at mesteparten her sitter i IO.

 

#include <fstream>
#include <iostream>

static inline void helper( std::ifstream& file1,
    std::ifstream& file2,
    std::string& line1,
    std::string&line2, bool right ) {

   const char* arrow = right ? "> " : "< ";
   while( line1 < line2 && file1.good() ) {
    std::cout << arrow << line1 << "\n";
    std::getline( file1, line1 );
   }  

   if( line1 == line2 ) return;

   if( !file1.good() ) return;
   helper( file2, file1, line2, line1, !right );
}

int main() {
   std::string line1, line2;
   std::cout.sync_with_stdio( false );
   std::ifstream file1( "data5.txt" );
   std::ifstream file2( "data6.txt" );

   while( file1.good() && file2.good() ) {
    std::getline( file1, line1 );
    std::getline( file2, line2 );

    if( line1 == line2 ) continue;
    if( line1 < line2 )
	    helper( file1, file2, line1, line2, true );
    else helper( file2, file1, line2, line1, false );
   }  

   while( file1.good() ) {
    std::cout << "> " << line1 << "\n";
    getline( file1, line1 );
   }  

   while( file2.good() ) {
    std::cout << "< " << line2 << "\n";
    getline( file2, line2 );
   }  

   std::cout.flush();
}

[Paull]

D'oh, leste feil, trodde det stod "sortert helt tilfeldig som strenger".

[Lycantrophe]

Det står det.