[Vari] Contest 7: Il Lotto

[Vincenzo1968]

autore (compilatore): tempo (piccoli ~50MB) / tempo (grandi ~90MB) - rapporto

cionci (GCC): 6058ms / 11930ms - 1.97
cionci (VS): 5753ms / 11461ms - 1.99
repne (GCC): 1563ms / 3186ms - 2.03
repne (VS): 1541ms / 3006ms - 1.95

Vista x86-64
Intel T9300 @ 2.50GHz
4.00GB RAM

I file che hai linkato pero erano abbastanza grandini... anche i piccoli. :fagiano:

Edit: VS = Visual Studio 2008, GCC = GCC 4.3.2-tdm-1

Si, per piccoli intendevo più piccoli di quelli più grossi :D

Me lo faresti un favore? puoi zippare i file più grossi e metterli sul sito per il download?

[||ElChE||88]

Me lo faresti un favore? puoi zippare i file più grossi e metterli sul sito per il download?
http://www.usaupload.net/d/57zzs7n2dvx
:O:D

[Vincenzo1968]

:O:D

Si, quello l'ho già provato e mi dà errore quando tento di decomprimerlo. Dicevo se puoi fare un'altra 'zippata' e mettermela a disposizione. Grazie ;)

edit:

http://www.guidealgoritmi.it/images/ImgForums/ErroreZip2.jpg

[||ElChE||88]

Si, quello l'ho già provato e mi dà errore quando tento di decomprimerlo. Dicevo se puoi fare un'altra 'zippata' e mettermela a disposizione. Grazie ;)

edit:

Rizippandolo il file esce esattamente identico. E quello nel link funziona bene (provato su 2 PC). :fagiano:
Se non ti funzionano ne 7z ne zip il problema è nel tuo computer...

[Vincenzo1968]

Rizippandolo il file esce esattamente identico. E quello nel link funziona bene (provato su 2 PC). :fagiano:
Se non ti funzionano ne 7z ne zip il problema è nel tuo computer...

Evidentemente.

Vedo che repne, per il momento, non risponde. Spero sia solo per impegni suoi personali e non per le polemiche che ci sono state. Vorrei creare manualmente, con i codici che ha postato lei, i file grossi. Qualcuno sa come si debbono impostare i parametri all'inizio dei file?

[Vincenzo1968]

Ho creato, utilizzando i sorgenti di repne, due nuove coppie di file. Il file dati più piccolo è circa 44 MB mentre quello più grande è circa 88 MB.

Questa è la nuova classifica:

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica07.jpg


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional
Service Pack 3

[Vincenzo1968]

Ho rifatto delle altre prove dopo aver riavviato la macchina:

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica08.jpg

Adesso, come rapporto, i due programmi si equivalgono, in linea coi risultati di ElChE.

I file li ho creati impostando questi parametri nei file postati da repne:

Per i file piccoli:

#define RUOTE 250
#define ESTRAZIONI 4000
#define LUNG_NOME_RUOTE 16
#define OUTPUT_FILE_NAME "LOTTO.D1"
#define VALORI 6
#define Y_MIN 1980
#define RANGE_Y 40.0



#define FIND 10000
#define MIN_G 4
#define MAX_G 5
#define OUTPUT_FILE_NAME "LOTTO.D2"


Per i file grandi:

#define RUOTE 250
#define ESTRAZIONI 8000
#define LUNG_NOME_RUOTE 16
#define OUTPUT_FILE_NAME "LOTTO.D1"
#define VALORI 6
#define Y_MIN 1980
#define RANGE_Y 40.0



#define FIND 20000
#define MIN_G 4
#define MAX_G 5
#define OUTPUT_FILE_NAME "LOTTO.D2"


Nel Sedgewick(Robert Sedgewick - Algoritmi in C - Terza edizione italiana) leggo(pag. 48) che l'influenza della duplicazione dell'input sul tempo di calcolo è data dalla seguente tabella:

http://www.guidealgoritmi.it/images/ImgForums/Complessita.jpg

Ora, poiché in entrambi i casi, raddoppiando l'input, i tempi di esecuzione aumentano, all'incirca, di un fattore 4, si può dire che entrambi gli algoritmi hanno una complessità = O(N^2) ?

[Vincenzo1968]

Ehm Cionci,

le prove le ho fatte senza guardare il contenuto dei file di output. Adesso stavo provando l'output a video:

http://www.guidealgoritmi.it/images/ImgForums/OutputCionci2.jpg

:mad:

[cionci]

Devi mettere nuovamente f.clear() fra f.close e f.open.

[Vincenzo1968]

Devi mettere nuovamente f.clear() fra f.close e f.open.

Infatti:

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica09.jpg


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3


:mad: :mad: :mad: <--- membri del Tribunale della "Santa" Inquisizione.

[gugoXX]

Onde evitare il cilicio e quell'orrenda veste della vergogna,
ho scritto una versione C# provando un algoritmo diverso da quelli provati finora, che penso sostanzialmente siano sempre gli stessi (e che anche io avevo scritto),
che pero' si e' verificato essere parzialmente vincente.
In pratica non avevo voglia di passare attraverso le combinazioni senza ripetizione perche' il replicare i dati tante volte mi portava a mangiare davvero tantissima memoria.

Sulla carta questo nuovo algoritmo e' buono, ma non posso spendere troppo tempo per ottimizzare.
Ho qualche idea, ma se dimezzo e' gia' tanto.

Ottengo 644ms sul mio vecchio file grosso, e purtroppo 34sec sul file grosso di Repne, e in piu' non so se c'e' un baco o meno perche' su questo file ho trovato solo 30044 estrazioni verificate su 5623 target risultanti.


Start
Load Time: 37ms
Parse Estrazioni: 369ms
Parse Target: 5ms
SEARCH
Search time: 233ms
Found: target 209
Found: totestr 263
TOTAL Time: 644ms
--End--



Start
Load Time: 812ms
Parse Estrazioni: 4742ms
Parse Target: 12ms
SEARCH
Search time: 28408ms
Found: target 5621
Found: totestr 30041
TOTAL Time: 33974
--End--


Inoltre ho dovuto sforzarmi un po' per effettuare il parse dei file di testo. Il codice in C# per il parse erano proprio 2 righe, ma dato che non e' possibile giocare con byte alti/byte bassi,le performance erano bruttine
Allora ho messo di mezzo il Marshaling, e per il parsing di ogni stringa di valori ho messo di mezzo una libreria C++
In piu', per rosicare qualcosa ho abilitato il parallelismo, ma essendo che su 10.000 target ce ne sono piu' di 5000 che si riescono a trovare, i conflitti tra i thread sono alti, e quindi sono dovuto andare di Interop (classe helper di sistema Framework per gestire le operazioni matematiche semplici monoatomiche sincronizzate)
Diciamo che ho speranza con questo stesso codice di poter battere Repne tra un paio d'anni, quando avremo 8 core sul proc e non solo 2 :D

[gugoXX]

Codice C# (Serve la libreria di Parallel Threading)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.InteropServices;
using System.IO;
using System.Threading;
using System.Diagnostics;

namespace Contest7Bis
{
class Program
{
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
// LOAD
sw.Start();
Console.WriteLine("Start");
//string[] EstrazioniLines = File.ReadAllLines(@"C:\temp\LOTTO.D1");
//string[] TargetLines = File.ReadAllLines(@"C:\temp\LOTTO.D2");
string[] EstrazioniLines = File.ReadAllLines(@"C:\temp\LottoDataDifficile.txt");
string[] TargetLines = File.ReadAllLines(@"C:\temp\LottoFindDifficile.txt");
sw.Stop();
long loadtime = sw.ElapsedMilliseconds;
Console.WriteLine("Load Time: {0}ms", sw.ElapsedMilliseconds);

//PARSE
// Parse Estrazioni
Console.Write("Parse Estrazioni: ");
sw.Start();
Lotto lot = new Lotto();
lot.LoadEstrazioni(EstrazioniLines);
sw.Stop();
long finestr = sw.ElapsedMilliseconds;
Console.WriteLine("{0}ms", finestr-loadtime);
//Parse Target
Console.Write("Parse Target: ");
sw.Start();
lot.LoadTarget(TargetLines);
sw.Stop();
long fintarg = sw.ElapsedMilliseconds;
Console.WriteLine("{0}ms",fintarg-finestr);

//SEARCH
Console.WriteLine("SEARCH");
sw.Start();
var res = lot.Search(Console.Out,false);
sw.Stop();
long finsearch=sw.ElapsedMilliseconds;
Console.WriteLine("Search time: {0}ms", finsearch - fintarg);

Console.WriteLine("Found: target {0}", res.TotalFound);
Console.WriteLine("Found: totestr {0}",res.EstrFound);
Console.WriteLine("TOTAL Time: {0}ms", finsearch);

//ToBeSearched tbs = new ToBeSearched();
//Console.WriteLine("Read and Parse: Target");
//var mm = tbs.Load(@"C:\temp\LOTTO.D2");

Console.WriteLine("--End--");
Console.ReadKey();
}
}

public class Lotto
{
/// <summary>
/// Library e' un Dizionario che, a fronte dei valori trovati in almeno un'estrazione
/// Restituisce quali estrazioni hanno avuto esattamente questi valori
/// (Potrebbe essere che 2 estrazioni hanno estratto esattamente gli stessi numeri)
/// (Se questa remota ipotesi e' verificabile a priori, si puo' magniare qualcosa)
/// </summary>
Dictionary<ulong, List<Token>> Library = new Dictionary<ulong, List<Token>>();

/// <summary>
/// Splitter e' un'array di 90 celle le cui celle sono Hashtable di estrazioni
/// Per ciascun numero 1-90 memorizzo quali sono le estrazioni che lo comprendono
/// </summary>
Dictionary<ulong, bool>[] Splitter = new Dictionary<ulong,bool>[91];

/// <summary>
/// Ottimizzazione, e' l'array corrispondente allo Splitter
/// Sarebbe superfluo, ma entra in gioco per ottimizzazione
/// Ha lo stesso contenuto informativo di Splitter.
/// </summary>
ulong[][] BaseSearch = new ulong[91][];

/// <summary>
/// La lista delle combinazioni da ricercare (eqv al file target)
/// </summary>
List<Helper.Parsed> Targets;

public Lotto()
{
}

/// <summary>
/// Parso i Target, riempiendo la lista dei Target
/// </summary>
/// <param name="p_Targets"></param>
public void LoadTarget(string[] p_Targets)
{
var tgs = p_Targets.Skip(1).Select(t => Helper.ParseStringComma(t));
Targets = tgs.ToList();
}

/// <summary>
/// Parso le Estrazioni, riempiendo le strutture per la ricerca
/// </summary>
/// <param name="Estrazioni"></param>
public void LoadEstrazioni(string[] Estrazioni)
{
var estr = Estrazioni.Skip(2).Select(t => Token.Parse(t));

for (byte t = 1; t <= 90; t++)
{
Splitter[t] = new Dictionary<ulong, bool>();
}

foreach (Token tk in estr)
{
List<Token> memo;
ulong img = tk.Image;
if (!Library.TryGetValue(img, out memo))
{
memo = Library[img] = new List<Token>();
}
memo.Add(tk);

foreach (byte b in tk.Values)
{
Splitter[b][tk.Image] = true;
}
}

for (int t = 1; t < 91; t++)
{
BaseSearch[t] = Splitter[t].Keys.ToArray();
}
}

/// <summary>
/// Risultato della ricerca, indica quante combinazioni sono state trovate
/// E la quantita' totale di Estrazioni soddisfacenti
/// </summary>
public struct Result
{
public int TotalFound;
public int EstrFound;
}

/// <summary>
/// Algoritmo
/// </summary>
/// <param name="tw">
/// E' il textwriter su cui effettuare lo spool.
/// Puo' essere la Console o un File indifferentemente
/// </param>
/// <param name="SpoolOut">true se si intende spoolare i risultati parziali</param>
/// <returns>Un Result</returns>
public Result Search(TextWriter tw,bool SpoolOut)
{
unsafe
{
int TotFound = 0;
int MinF = 0;
//foreach(var v in Targets)
Parallel.ForEach(Targets, v =>
{
bool headst = true;
byte[] ts = v.Values;
int tslen = ts.Length;

Dictionary<ulong,bool>[] ns = new Dictionary<ulong,bool>[tslen];
for (int qp = 1; qp < tslen; qp++)
{
ns[qp] = Splitter[ts[qp]];
}

ulong[] bs = BaseSearch[ts[0]];
int nv = bs.Length;

for(int qp=0;qp<nv;qp++)
{
ulong estr = bs[qp];

bool fnd = true;
for (int t = 1; t < tslen; t++)
{
if (!ns[t].ContainsKey(estr))
{
fnd = false;
break;
}
}
if (fnd)
{
var ToPrint = Library[estr];
int ta = ToPrint.Count;
Interlocked.Add(ref MinF, ta);
if (SpoolOut)
{
if (headst)
tw.WriteLine("--{0}--", v.Input);

ToPrint.ForEach(Console.WriteLine);
}

if (headst)
{
Interlocked.Increment(ref TotFound);
headst = false;
}
}
}
});
Result res = new Result();
res.TotalFound = TotFound;
res.EstrFound = MinF;
return res;
}
}

}

/// <summary>
/// Classe che modella un'estrazione
/// DataRuota - e' la sottostringa comprendente la data e la ruota di riferimento
/// ValoriLen - indica quanti valori sono stati estratti in quella data
/// (L'algoritmo funziona anche se per ciascuna estrazione non si estrae sempre
/// lo stesso numero di valori. Non richiesto)
/// str - e' la sottostringa dei valori estratti
/// Values - E' l'array dei byte corrispondenti ai valori estratti
/// Image - E' il compattamento dei valori estratti in un unico intero 64bit
/// Pertanto l'algoritmo funziona solamente se la quantita' dei
/// valori estratti per ciascuna ruota non e' maggiore di 8
/// </summary>
public class Token
{
public string DataRuota;
public int ValoriLen;
string str;
public byte[] Values;
public ulong Image;


public override string ToString()
{
return string.Format("{0} - {1}", DataRuota, str);
}

public static Token Parse(string str)
{
int pos = str.LastIndexOf(' ');
Token ret = new Token();
ret.DataRuota = str.Substring(0, pos);
ret.str = str.Substring(pos + 1);

//string[] rr = s2.Split(new char[] { ',' });
//byte[] ff = rr.Select(t => byte.Parse(t)).ToArray();
var vals = Helper.ParseStringComma(ret.str);

//ret.Valori = vals;
ret.ValoriLen = vals.Len;
ret.Values = vals.Values;
ret.Image = vals.Image;
return ret;
}
}

/// <summary>
/// Classe Helper di Marshaling verso il C++
/// </summary>
public static class Helper
{
[DllImport("Supporter.dll")]
public static extern Spanner GetFromString(string str, int ln);

public struct Spanner
{
public byte b0;
public byte b1;
public byte b2;
public byte b3;
public byte b4;
public byte b5;
public byte b6;
public byte b7;

public ulong Image;

public int len;
};

public struct Parsed
{
public byte[] Values;
public ulong Image;
public int Len;
public string Input;
}

private static byte[] buffer = new byte[8];
public static Parsed ParseStringComma(string input)
{
var rspan = Helper.GetFromString(input, input.Length);

buffer[0] = rspan.b0;
buffer[1] = rspan.b1;
buffer[2] = rspan.b2;
buffer[3] = rspan.b3;
buffer[4] = rspan.b4;
buffer[5] = rspan.b5;
buffer[6] = rspan.b6;
buffer[7] = rspan.b7;

int mlen = rspan.len;
Parsed ret = new Parsed();
byte[] ff = ret.Values = new byte[mlen];
for (int t = 0; t < mlen; t++)
ff[t] = buffer[t];

ret.Image = rspan.Image;
ret.Len = rspan.len;
ret.Input = input;

return ret;
}
}

}


Codice C++, da inserire in un progetto di tipo C++ della stessa soluzione.

// This is the main DLL file.

#include "stdafx.h"
#include "Supporter.h"

#define DllExport __declspec( dllexport )


typedef unsigned char BYTE;

typedef struct
{
BYTE b0;
BYTE b1;
BYTE b2;
BYTE b3;
BYTE b4;
BYTE b5;
BYTE b6;
BYTE b7;
__int64 Image;
int len;
} Spanner;

// Prende la stringa comma separated, i cui valori sono compresi tra 1-90
// Cerca i singoli caratteri di ciascun numero (al massimo 2)
// Li compatta in un byte
// Prende i byte e li compatta in un intero 64bit
// Restituisce anche la quantita' di valori trovati (1-8)
DllExport Spanner GetFromString(char* mstr,int len)
{
Spanner ret;
int oi=0;
int nl=0;
char ch0;
char ch1;
int ln=0;
BYTE* tp = (BYTE*)&ret;
for(int t=0;t<=len;t++)
{
char th;
if ( (t==len) || ( (th = mstr[t]) ==',') )
{
if (nl==1)
{
*tp=(ch0-0x30);
}
else
{
BYTE bv0 = ch0-0x30;
BYTE bv1 = ch1-0x30;
BYTE res;
__asm
{
mov ah,bv0
mov al,bv1
aad // EQV BV0*10+BV1
mov res,al
}
*tp=res;
}
tp++;
nl=0;
ln++;
}
else
{
if (nl==0) ch0=th;
else ch1=th;
nl++;
}
}
for(int u=ln;u<8;u++)
{
*tp=0;
tp++;
}

ret.len=ln;
int* LoInt = (int*)&ret.b0;
int* HiInt = (int*)&ret.b4;

int* ImP = (int*)&ret.Image;
*ImP = *LoInt;
ImP++;
*ImP = *HiInt;

return ret;
}


Occorrera' inserire nel progetto C# il riferimento alla libreria DLL del C++
e occorrera' anche pubblicare la funzione GetFromString della libreria C++ sull'opportuno file .def che enumera le funzioni esposte delle DLL
Il mio progetto C++ si chiama "Supporter", la DLL su chiamera' "Supporter.dll" e il file def si chiamera' "Supporter.def"

LIBRARY "Supporter"
EXPORTS
GetFromString

[Vincenzo1968]

Onde evitare il cilicio e quell'orrenda veste della vergogna,
ho scritto una versione C# provando un algoritmo diverso da quelli provati finora, che penso sostanzialmente siano sempre gli stessi (e che anche io avevo scritto),
che pero' si e' verificato essere parzialmente vincente.
In pratica non avevo voglia di passare attraverso le combinazioni senza ripetizione perche' il replicare i dati tante volte mi portava a mangiare davvero tantissima memoria.

Sulla carta questo nuovo algoritmo e' buono, ma non posso spendere troppo tempo per ottimizzare.
Ho qualche idea, ma se dimezzo e' gia' tanto.

Ottengo 644ms sul mio vecchio file grosso, e purtroppo 34sec sul file grosso di Repne, e in piu' non so se c'e' un baco o meno perche' su questo file ho trovato solo 30044 estrazioni verificate su 5623 target risultanti.


Start
Load Time: 37ms
Parse Estrazioni: 369ms
Parse Target: 5ms
SEARCH
Search time: 233ms
Found: target 209
Found: totestr 263
TOTAL Time: 644ms
--End--



Start
Load Time: 812ms
Parse Estrazioni: 4742ms
Parse Target: 12ms
SEARCH
Search time: 28408ms
Found: target 5621
Found: totestr 30041
TOTAL Time: 33974
--End--


Inoltre ho dovuto sforzarmi un po' per effettuare il parse dei file di testo. Il codice in C# per il parse erano proprio 2 righe, ma dato che non e' possibile giocare con byte alti/byte bassi,le performance erano bruttine
Allora ho messo di mezzo il Marshaling, e per il parsing di ogni stringa di valori ho messo di mezzo una libreria C++
In piu', per rosicare qualcosa ho abilitato il parallelismo, ma essendo che su 10.000 target ce ne sono piu' di 5000 che si riescono a trovare, i conflitti tra i thread sono alti, e quindi sono dovuto andare di Interop (classe helper di sistema Framework per gestire le operazioni matematiche semplici monoatomiche sincronizzate)
Diciamo che ho speranza con questo stesso codice di poter battere Repne tra un paio d'anni, quando avremo 8 core sul proc e non solo 2 :D

Il cilicio non c'entra. Quello lo usano(anche oggi) i membri dell'Opus Dei. Il sambenito è invece merito della "Santa" Inquisizione(abolita da tempo, per fortuna).
A proposito, il codice dov'è? Se non lo posti, mi comunica il Mons., ti aspetta un bellissimo autodafé, altro che sambenito :Perfido:

[gugoXX]

Il cilicio non c'entra. Quello lo usano(anche oggi) i membri dell'Opus Dei. Il sambenito è invece merito della "Santa" Inquisizione(abolita da tempo, per fortuna).
A proposito, il codice dov'è? Se non lo posti, mi comunica il Mons., ti aspetta un bellissimo autodafé, altro che sambenito :Perfido:

Bene, il codice l'ho messo, quindi l'ho scampata, qualunque cosa l'autodafé sia.
Ma il tuo codice dov'e'? :D

[Vincenzo1968]

Bene, il codice l'ho messo, quindi l'ho scampata, qualunque cosa l'autodafé sia.
Ma il tuo codice dov'e'? :D

Io, essendo un familiare della "Santa" Inquisizione, sono esonerato da qualsiasi punizione :ciapet:
No, a parte gli scherzi, fra un po' arriva(uno o due mesi ;))

Ho compilato il tuo codice. Ecco come l'ho riazzizzato:

File Supporter.h

#ifndef _MyDll_H
#define _MyDll_H

#ifdef DLL_EXPORTS
#define DllExport __declspec(dllexport)
#else
#define DllExport __declspec(dllimport)
#endif

#ifdef __cplusplus
extern "C" {
#endif

typedef unsigned char BYTE;

typedef struct
{
BYTE b0;
BYTE b1;
BYTE b2;
BYTE b3;
BYTE b4;
BYTE b5;
BYTE b6;
BYTE b7;
__int64 Image;
int len;
} Spanner;

DllExport Spanner WINAPI GetFromString(char* mstr,int len);

#ifdef __cplusplus
}
#endif

#endif // _MyDll_H


File Supporter.cpp

#include <windows.h>

#define DLL_EXPORTS
#include "Supporter.h"

//#define DllExport __declspec( dllexport )

// Prende la stringa comma separated, i cui valori sono compresi tra 1-90
// Cerca i singoli caratteri di ciascun numero (al massimo 2)
// Li compatta in un byte
// Prende i byte e li compatta in un intero 64bit
// Restituisce anche la quantita' di valori trovati (1-8)
DllExport Spanner WINAPI GetFromString(char* mstr,int len)
{
Spanner ret;
int oi=0;
int nl=0;
char ch0;
char ch1;
int ln=0;
BYTE* tp = (BYTE*)&ret;
for(int t=0;t<=len;t++)
{
char th;
if ( (t==len) || ( (th = mstr[t]) ==',') )
{
if (nl==1)
{
*tp=(ch0-0x30);
}
else
{
BYTE bv0 = ch0-0x30;
BYTE bv1 = ch1-0x30;
BYTE res;
__asm
{
mov ah,bv0
mov al,bv1
aad // EQV BV0*10+BV1
mov res,al
}
*tp=res;
}
tp++;
nl=0;
ln++;
}
else
{
if (nl==0) ch0=th;
else ch1=th;
nl++;
}
}
for(int u=ln;u<8;u++)
{
*tp=0;
tp++;
}

ret.len=ln;
int* LoInt = (int*)&ret.b0;
int* HiInt = (int*)&ret.b4;

int* ImP = (int*)&ret.Image;
*ImP = *LoInt;
ImP++;
*ImP = *HiInt;

return ret;
}


File Contest07Gugo.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.InteropServices;
using System.IO;
using System.Threading;
using System.Diagnostics;

namespace Contest7Bis
{
class Program
{
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
// LOAD
sw.Start();
Console.WriteLine("Start");
//string[] EstrazioniLines = File.ReadAllLines(@"C:\temp\LOTTO.D1");
//string[] TargetLines = File.ReadAllLines(@"C:\temp\LOTTO.D2");
string[] EstrazioniLines = File.ReadAllLines(@"C:\temp\LottoDataDifficile.txt");
string[] TargetLines = File.ReadAllLines(@"C:\temp\LottoFindDifficile.txt");
sw.Stop();
long loadtime = sw.ElapsedMilliseconds;
Console.WriteLine("Load Time: {0}ms", sw.ElapsedMilliseconds);

//PARSE
// Parse Estrazioni
Console.Write("Parse Estrazioni: ");
sw.Start();
Lotto lot = new Lotto();
lot.LoadEstrazioni(EstrazioniLines);
sw.Stop();
long finestr = sw.ElapsedMilliseconds;
Console.WriteLine("{0}ms", finestr-loadtime);
//Parse Target
Console.Write("Parse Target: ");
sw.Start();
lot.LoadTarget(TargetLines);
sw.Stop();
long fintarg = sw.ElapsedMilliseconds;
Console.WriteLine("{0}ms",fintarg-finestr);

//SEARCH
Console.WriteLine("SEARCH");
sw.Start();
var res = lot.Search(Console.Out,false);
sw.Stop();
long finsearch=sw.ElapsedMilliseconds;
Console.WriteLine("Search time: {0}ms", finsearch - fintarg);

Console.WriteLine("Found: target {0}", res.TotalFound);
Console.WriteLine("Found: totestr {0}",res.EstrFound);
Console.WriteLine("TOTAL Time: {0}ms", finsearch);

//ToBeSearched tbs = new ToBeSearched();
//Console.WriteLine("Read and Parse: Target");
//var mm = tbs.Load(@"C:\temp\LOTTO.D2");

Console.WriteLine("--End--");
Console.ReadKey();
}
}

public class Lotto
{
/// <summary>
/// Library e' un Dizionario che, a fronte dei valori trovati in almeno un'estrazione
/// Restituisce quali estrazioni hanno avuto esattamente questi valori
/// (Potrebbe essere che 2 estrazioni hanno estratto esattamente gli stessi numeri)
/// (Se questa remota ipotesi e' verificabile a priori, si puo' magniare qualcosa)
/// </summary>
Dictionary<ulong, List<Token>> Library = new Dictionary<ulong, List<Token>>();

/// <summary>
/// Splitter e' un'array di 90 celle le cui celle sono Hashtable di estrazioni
/// Per ciascun numero 1-90 memorizzo quali sono le estrazioni che lo comprendono
/// </summary>
Dictionary<ulong, bool>[] Splitter = new Dictionary<ulong,bool>[91];

/// <summary>
/// Ottimizzazione, e' l'array corrispondente allo Splitter
/// Sarebbe superfluo, ma entra in gioco per ottimizzazione
/// Ha lo stesso contenuto informativo di Splitter.
/// </summary>
ulong[][] BaseSearch = new ulong[91][];

/// <summary>
/// La lista delle combinazioni da ricercare (eqv al file target)
/// </summary>
List<Helper.Parsed> Targets;

public Lotto()
{
}

/// <summary>
/// Parso i Target, riempiendo la lista dei Target
/// </summary>
/// <param name="p_Targets"></param>
public void LoadTarget(string[] p_Targets)
{
var tgs = p_Targets.Skip(1).Select(t => Helper.ParseStringComma(t));
Targets = tgs.ToList();
}

/// <summary>
/// Parso le Estrazioni, riempiendo le strutture per la ricerca
/// </summary>
/// <param name="Estrazioni"></param>
public void LoadEstrazioni(string[] Estrazioni)
{
var estr = Estrazioni.Skip(2).Select(t => Token.Parse(t));

for (byte t = 1; t <= 90; t++)
{
Splitter[t] = new Dictionary<ulong, bool>();
}

foreach (Token tk in estr)
{
List<Token> memo;
ulong img = tk.Image;
if (!Library.TryGetValue(img, out memo))
{
memo = Library[img] = new List<Token>();
}
memo.Add(tk);

foreach (byte b in tk.Values)
{
Splitter[b][tk.Image] = true;
}
}

for (int t = 1; t < 91; t++)
{
BaseSearch[t] = Splitter[t].Keys.ToArray();
}
}

/// <summary>
/// Risultato della ricerca, indica quante combinazioni sono state trovate
/// E la quantita' totale di Estrazioni soddisfacenti
/// </summary>
public struct Result
{
public int TotalFound;
public int EstrFound;
}

/// <summary>
/// Algoritmo
/// </summary>
/// <param name="tw">
/// E' il textwriter su cui effettuare lo spool.
/// Puo' essere la Console o un File indifferentemente
/// </param>
/// <param name="SpoolOut">true se si intende spoolare i risultati parziali</param>
/// <returns>Un Result</returns>
public Result Search(TextWriter tw,bool SpoolOut)
{
unsafe
{
int TotFound = 0;
int MinF = 0;
//foreach(var v in Targets)
Parallel.ForEach(Targets, v =>
{
bool headst = true;
byte[] ts = v.Values;
int tslen = ts.Length;

Dictionary<ulong,bool>[] ns = new Dictionary<ulong,bool>[tslen];
for (int qp = 1; qp < tslen; qp++)
{
ns[qp] = Splitter[ts[qp]];
}

ulong[] bs = BaseSearch[ts[0]];
int nv = bs.Length;

for(int qp=0;qp<nv;qp++)
{
ulong estr = bs[qp];

bool fnd = true;
for (int t = 1; t < tslen; t++)
{
if (!ns[t].ContainsKey(estr))
{
fnd = false;
break;
}
}
if (fnd)
{
var ToPrint = Library[estr];
int ta = ToPrint.Count;
Interlocked.Add(ref MinF, ta);
if (SpoolOut)
{
if (headst)
tw.WriteLine("--{0}--", v.Input);

ToPrint.ForEach(Console.WriteLine);
}

if (headst)
{
Interlocked.Increment(ref TotFound);
headst = false;
}
}
}
});
Result res = new Result();
res.TotalFound = TotFound;
res.EstrFound = MinF;
return res;
}
}

}

/// <summary>
/// Classe che modella un'estrazione
/// DataRuota - e' la sottostringa comprendente la data e la ruota di riferimento
/// ValoriLen - indica quanti valori sono stati estratti in quella data
/// (L'algoritmo funziona anche se per ciascuna estrazione non si estrae sempre
/// lo stesso numero di valori. Non richiesto)
/// str - e' la sottostringa dei valori estratti
/// Values - E' l'array dei byte corrispondenti ai valori estratti
/// Image - E' il compattamento dei valori estratti in un unico intero 64bit
/// Pertanto l'algoritmo funziona solamente se la quantita' dei
/// valori estratti per ciascuna ruota non e' maggiore di 8
/// </summary>
public class Token
{
public string DataRuota;
public int ValoriLen;
string str;
public byte[] Values;
public ulong Image;


public override string ToString()
{
return string.Format("{0} - {1}", DataRuota, str);
}

public static Token Parse(string str)
{
int pos = str.LastIndexOf(' ');
Token ret = new Token();
ret.DataRuota = str.Substring(0, pos);
ret.str = str.Substring(pos + 1);

//string[] rr = s2.Split(new char[] { ',' });
//byte[] ff = rr.Select(t => byte.Parse(t)).ToArray();
var vals = Helper.ParseStringComma(ret.str);

//ret.Valori = vals;
ret.ValoriLen = vals.Len;
ret.Values = vals.Values;
ret.Image = vals.Image;
return ret;
}
}

/// <summary>
/// Classe Helper di Marshaling verso il C++
/// </summary>
public static class Helper
{
[DllImport("Supporter.dll")]
public static extern Spanner GetFromString(string str, int ln);

public struct Spanner
{
public byte b0;
public byte b1;
public byte b2;
public byte b3;
public byte b4;
public byte b5;
public byte b6;
public byte b7;

public ulong Image;

public int len;
};

public struct Parsed
{
public byte[] Values;
public ulong Image;
public int Len;
public string Input;
}

private static byte[] buffer = new byte[8];
public static Parsed ParseStringComma(string input)
{
var rspan = Helper.GetFromString(input, input.Length);

buffer[0] = rspan.b0;
buffer[1] = rspan.b1;
buffer[2] = rspan.b2;
buffer[3] = rspan.b3;
buffer[4] = rspan.b4;
buffer[5] = rspan.b5;
buffer[6] = rspan.b6;
buffer[7] = rspan.b7;

int mlen = rspan.len;
Parsed ret = new Parsed();
byte[] ff = ret.Values = new byte[mlen];
for (int t = 0; t < mlen; t++)
ff[t] = buffer[t];

ret.Image = rspan.Image;
ret.Len = rspan.len;
ret.Input = input;

return ret;
}
}

}


Fortunatamente, in occasione del contest 5, avevo già scaricato le parallel extensions ;)

Fra un po' aggiorno la classifica.

[gugoXX]

Io, essendo un familiare della "Santa" Inquisizione, sono esonerato da qualsiasi punizione :ciapet:
No, a parte gli scherzi, fra un po' arriva(uno o due mesi ;))

Ho compilato il tuo codice. Ecco come l'ho riazzizzato:

..cut..


Va benissimo, fammi sapere come gira sotto un AMD.

Davvero, mi piacerebbe provare fra qualche anno come si attestano le differenze C - C# quando c'e' di mezzo il multithreading.
Il C standard non ha nulla per il parallelismo vero?

E conta che "forse" c'e' un errore, dato che i miei risultati sono diversi da quelli che ho trovato qualche pagina fa.

Se avessi l'elenco completo dei risutlati potrei cercare un facile debug. Ora non posso proprio, sto montando mobili dell'Ikea perche' ovviamente a mia moglie non andava bene nulla di quello che avevo da scapolo.

E poi vuole un gatto.
“Non capisco perche' ami tanto i gatti.
I gatti sono indipendenti, non ascoltano mai, non vengono mai quando li si chiama,
amano restare fuori tutta la notte e, quando sono a casa,
tutto quello che vogliono e' essere lasciati tranquilli a fare i catsi propri.

In altre parole, tutte le caratteristiche che di me odia sono quelle che ama di un gatto”

[Vincenzo1968]

Se ne esce senza dare nessun errore(ma nemmeno nessun output):

http://www.guidealgoritmi.it/images/ImgForums/ErroreGugo.jpg

I tempi registrati, però, sono favolosi: 0 secondi ;)

Tutti i file, eseguibile, dll e dati, sono nella stessa cartella. :confused:

edit: come non detto avevo fatto una minchiata. Fra un po' la classifica.

[gugoXX]

Se ne esce senza dare nessun errore(ma nemmeno nessun output):

http://www.guidealgoritmi.it/images/ImgForums/ErroreGugo.jpg

I tempi registrati, però, sono favolosi: 0 secondi ;)

Tutti i file, eseguibile, dll e dati, sono nella stessa cartella. :confused:

Non saprei.
Se vuoi aggiusto la linea di comando, cosi' puoi dare i file di input da fuori...
Per il resto sarebbe dovuto comunque uscire almeno un'eccezione direi.
Ma hai messo sia C# che C++ tutto nella stessa soluzione?
Se vuoi zippo il sorgente e te lo passo...

[Vincenzo1968]

Non saprei.
Se vuoi aggiusto la linea di comando, cosi' puoi dare i file di input da fuori...
Per il resto sarebbe dovuto comunque uscire almeno un'eccezione direi.
Ma hai messo sia C# che C++ tutto nella stessa soluzione?
Se vuoi zippo il sorgente e te lo passo...

No no, avevo risolto(ho editato il post precedente, forse non ci hai fatto caso).

Purtroppo, sulla mia macchina, dopo cinque minuti non dà ancora l'output e tutto il sistema risulta bloccato.
M'è toccato riavviare e, dunque, autodafé:

http://it.wikipedia.org/wiki/Autodaf%C3%A9

http://it.encarta.msn.com/encyclopedia_761555403/Autodaf%C3%A9.html

Else potrebbe aggiornare la classifica sulla sua macchina ché dispone di un bel po' di ram.

[gugoXX]

No no, avevo risolto(ho editato il post precedente, forse non ci hai fatto caso).

Purtroppo, sulla mia macchina, dopo cinque minuti non dà ancora l'output e tutto il sistema risulta bloccato.
M'è toccato riavviare e, dunque, autodafé:

http://it.wikipedia.org/wiki/Autodaf%C3%A9

http://it.encarta.msn.com/encyclopedia_761555403/Autodaf%C3%A9.html

Else potrebbe aggiornare la classifica sulla sua macchina ché dispone di un bel po' di ram.

Prova per curiosita' a togliere la parte di parallelismo.
Dovrebbe esserci solo un Parallel.Foreach
Sarebbe gia' la seconda (o terza?) volta che il parellismo da problemi sulla tua macchina, e quindi sarei propenso a pensare che questa Beta non sia stata fatta molto bene o almeno non bene per gli AMD

E' sufficiente scommentare il ciclo sopra (e togliere una parentesi un po' piu' in basso)

[Vincenzo1968]

Prova per curiosita' a togliere la parte di parallelismo.
Dovrebbe esserci solo un Parallel.Foreach
Sarebbe gia' la seconda (o terza?) volta che il parellismo da problemi sulla tua macchina, e quindi sarei propenso a pensare che questa Beta non sia stata fatta molto bene o almeno non bene per gli AMD

E' sufficiente scommentare il ciclo sopra (e togliere una parentesi un po' piu' in basso)

Prima ho scritto Else, volevo dire Elche ;)

Nel contest 5, le parallel extensions, non mi hanno dato nessun problema. Anzi, il tuo codice è risultato più veloce. Quindi non credo che sia questo. Mo provo, comunque.

[gugoXX]

In effetti ho controllato e sul file grosso sto mangiando 1GB di memoria fisica e 1GB di memoria virtuale. Che pappone, ma dov'e' che si perde non lo so...
Avrei detto almeno 4-5 volte piu' piccolo.

[Vincenzo1968]

Ho installato Python e Psyco. C'è qualcuno che conosce bene questo linguaggio e vuole partecipare al contest? (DanieleC88?).

[||ElChE||88]

Prima ho scritto Else, volevo dire Elche ;)
:D
Ora sono un po' occupato con un progetto, appena ho un attimo lo provo sul mio portatile. :)

[cdimauro]

Ho installato Python e Psyco. C'è qualcuno che conosce bene questo linguaggio e vuole partecipare al contest? (DanieleC88?).
Io lo conosco bene e ti posso dare una mano se ci sono delle cose che non ti sono chiare, ma non partecipo al contest.

[Vincenzo1968]

Io lo conosco bene e ti posso dare una mano se ci sono delle cose che non ti sono chiare, ma non partecipo al contest.

ehm Cdimauro,

ti ringrazio ma io non lo conosco per niente. Vediamo se Daniele ha voglia di partecipare.

x Elche: grazie ;)

[DanieleC88]

Vediamo se Daniele ha voglia di partecipare.
Uhm, ma io di Python conosco solo le basi! :D
Be' quando ho visto il contest ormai avevate già raggiunto soluzioni ottimali, quindi non ho nemmeno letto cosa si dovrebbe fare... ti faccio sapere.

[Vincenzo1968]

Uhm, ma io di Python conosco solo le basi! :D
Be' quando ho visto il contest ormai avevate già raggiunto soluzioni ottimali, quindi non ho nemmeno letto cosa si dovrebbe fare... ti faccio sapere.

Cogli la palla al balzo: Cdimauro s'è offerto per dare una mano. ;) (tempestalo di messaggi privati :D)

M'è venuta un'idea. Per far rientrare tutti gli altri in gioco, mi creo, con i sorgenti di repne, due coppie di file di dimensione minore rispetto agli attuali. Vediamo cosi di far rientrare tutti i linguaggi di programmazione nella classifica. ;)

[||ElChE||88]

x Elche: grazie ;)
Ehm... una domanda:
Come si compila la parte in c++? Mi dice che manca un entry point (mai compilato DLL, c'è qualcosa di speciale che devo fare?

[Vincenzo1968]

Ehm... una domanda:
Come si compila la parte in c++? Mi dice che manca un entry point (mai compilato DLL, c'è qualcosa di speciale che devo fare?

Da qui (http://www.guidealgoritmi.it/public/Contest07Gugo.zip) puoi scaricare il progetto per Visual Studio 2008. Devi solo compilare. Ho messo anche, nella cartella Binari, gli eseguibili exe e dll per win32.

Prima di compilare scarica e installa le parallel extension per C#. Vedo di trovare il link e te lo posto( se non muoio prima; sto scoppiando: mi sono appena sbafàto mezzo chilo di polipetti che si squagliavano in bocca, bolliti e conditi con sale, pepe nero, olio, limone e prezzemolo e una spigola che pareva nuotasse ancora nel mare).
:)

[Vincenzo1968]

Ecco il link:

http://www.microsoft.com/downloads/details.aspx?FamilyId=348F73FD-593D-4B3C-B055-694C50D2B0F3&displaylang=en

[||ElChE||88]

Compilato, ma:

BadImageFormatException
An attempt was made to load a program with an incorrect format. (Exception from HRESULT: 0x8007000B)

:boh:

Edit: Risolto, compilava un pezzo in x86 e l'altro in x64.

[||ElChE||88]

Quello di gugoXX occupa 600MB di RAM con i file "piccoli", 1300MB con i file grandi. :eek:

autore (compilatore): tempo (piccoli ~50MB) / tempo (grandi ~90MB) - rapporto

cionci (C++ - GCC): 6058ms / 11930ms - 1.97
cionci (C++ - VS): 5753ms / 11461ms - 1.99
repne (C - GCC): 1563ms / 3186ms - 2.03
repne (C - VS): 1541ms / 3006ms - 1.95
gugoXX (C# / C++ - VS): 38577ms / 98240ms - 2.54

Vista x86-64
Intel T9300 @ 2.50GHz
4.00GB RAM

VS = Visual Studio 2008, GCC = GCC 4.3.2-tdm-1

[DanieleC88]

4.00GB RAM
Quanto sto invidiando la tua RAM, stasera non riesco a fare nulla per quanto mi swappa tutto... :asd:

[gugoXX]

Scusate, ci sono per caso delle altre versioni di file grandi?
A me con quello che pensavo essere il piu' grande ci mette 33secondi (e ho solo 2GB di ram), come mai tutta questa differenza?
Elche, Ma il tuo e' un dual core o core singolo?

[Vincenzo1968]

Scusate, ci sono per caso delle altre versioni di file grandi?
A me con quello che pensavo essere il piu' grande ci mette 33secondi (e ho solo 2GB di ram), come mai tutta questa differenza?
Elche, Ma il tuo e' un dual core o core singolo?

Ecco i due link:

File piccoli:
http://www.usaupload.net/d/1fzh7nkp97s

File grossi:
http://www.usaupload.net/d/pjpovf64vku
;)

[Vincenzo1968]

Oppure puoi crearteli a piacere con i sorgenti che ha postato repne:

LOTTO.D1:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define RUOTE 250
#define ESTRAZIONI 4000
#define LUNG_NOME_RUOTE 16
#define OUTPUT_FILE_NAME "LOTTO.D1"
#define VALORI 6
#define Y_MIN 1980
#define RANGE_Y 40.0

int main(void)

{
FILE *output_file_handle;
time_t t;
int m,g,a;
unsigned long i,j,k,l;
char nome_ruote[RUOTE][LUNG_NOME_RUOTE+1],table_lotto[90];
double g_mese[12]={31.0,28.0,31.0,30.0,31.0,30.0,31.0,31.0,30.0,31.0,30.0,31.0};

srand((unsigned)time(&t));

for(i=0;i<RUOTE;i++)
{
for(j=0;j<LUNG_NOME_RUOTE;j++)
nome_ruote[i][j]=(rand()*26.0)/(RAND_MAX+1.0)+'A';
nome_ruote[i][j]=0;
}

if((output_file_handle=fopen(OUTPUT_FILE_NAME,"wt"))==NULL)
{
fprintf(stderr,"Non riesco a creare il file " OUTPUT_FILE_NAME "\n");
return 1;
}

fprintf(output_file_handle,"Ruote %d\n",RUOTE);
fprintf(output_file_handle,"Valori %d\n",VALORI);

for(i=0;i<(RUOTE*ESTRAZIONI);i++)
{
m=(rand()*12.0)/(RAND_MAX+1.0)+1;
g=(rand()*g_mese[m-1])/(RAND_MAX+1.0)+1;
a=(rand()*RANGE_Y)/(RAND_MAX+1.0)+Y_MIN;
fprintf(output_file_handle,"%.2d/%.2d/%.4d %s ",g,m,a,nome_ruote[i%RUOTE]);
for(j=0;j<90;j++)
table_lotto[j]=0;
for(j=0;j<VALORI;j++)
{
k=(rand()*(90.0-j))/(RAND_MAX+1.0)+1;
l=0;
do
{
if(table_lotto[l++]==0)
k--;
} while (k);
table_lotto[l-1]=1;
fprintf(output_file_handle,"%d",l);
if(j!=(VALORI-1))
fprintf(output_file_handle,",");
}
fprintf(output_file_handle,"\n");
}

if(fclose(output_file_handle))
{
fprintf(stderr,"Errore interno: 001\n");
return 1;
}

return 0;
}


LOTTO.D2:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define FIND 10000
#define MIN_G 4
#define MAX_G 5
#define OUTPUT_FILE_NAME "LOTTO.D2"

int main(void)

{
FILE *output_file_handle;
time_t t;
char table_lotto[90];
unsigned long i,j,k,l,m;

srand((unsigned)time(&t));

if((output_file_handle=fopen(OUTPUT_FILE_NAME,"wt"))==NULL)
{
fprintf(stderr,"Non riesco a creare il file " OUTPUT_FILE_NAME "\n");
return 1;
}

fprintf(output_file_handle,"Find %d\n",FIND);

for(i=0;i<FIND;i++)
{
for(j=0;j<90;j++)
table_lotto[j]=0;
m=(rand()*(MAX_G-MIN_G+1))/(RAND_MAX+1.0);
for(j=0;j<(MIN_G+m);j++)
{
k=(rand()*(90.0-j))/(RAND_MAX+1.0)+1;
l=0;
do
{
if(table_lotto[l++]==0)
k--;
} while (k);
table_lotto[l-1]=1;
fprintf(output_file_handle,"%d",l);
if(j!=(MIN_G+m-1))
fprintf(output_file_handle,",");
}
fprintf(output_file_handle,"\n");
}

if(fclose(output_file_handle))
{
fprintf(stderr,"Errore interno: 001\n");
return 1;
}

return 0;
}

[gugoXX]

estensione 7z?
Cos'e' uno scherzo? Potevate usare zoo, Schiper, Ace o KGB...
:fagiano:

Quelli grandi iniziano con?

Ruote 250
Valori 6
01/12/2010 HXXZLVFGBQTQVXVH 31,36,81,11,85,47
22/10/1982 UYEEEIKQBCBQARBS 36,78,80,73,15,27
24/05/1988 EMEXAARYADAVOCIV 32,30,24,6,61,73

Hihi... ho trovato un 30 febbraio hihi
Lo dicevo che il lotto e' pilotato

[Vincenzo1968]

estensione 7z?
Cos'e' uno scherzo? Potevate usare zoo, Schiper, Ace o KGB...
:fagiano:

Quelli grandi iniziano con?

Ruote 250
Valori 6
01/12/2010 HXXZLVFGBQTQVXVH 31,36,81,11,85,47
22/10/1982 UYEEEIKQBCBQARBS 36,78,80,73,15,27
24/05/1988 EMEXAARYADAVOCIV 32,30,24,6,61,73

Hihi... ho trovato un 30 febbraio hihi
Lo dicevo che il lotto e' pilotato

Quelli grandi non lo so. Io ho avuto difficoltà nello scompattarli e me li sono creati con i sorgenti di repne(dimensione circe 88 MB).
Devi chiedere a Elche.

[||ElChE||88]

Elche, Ma il tuo e' un dual core o core singolo?
Il T9300 è un dual core (Penryn - per portatili).
Quelli grandi iniziano con?

Ruote 250
Valori 6
01/12/2010 HXXZLVFGBQTQVXVH 31,36,81,11,85,47
22/10/1982 UYEEEIKQBCBQARBS 36,78,80,73,15,27
24/05/1988 EMEXAARYADAVOCIV 32,30,24,6,61,73
No.

Ruote 250
Valori 6
15/05/1980 SMOTOKJSEWAXWLCA 77,14,47,42,67,21
04/01/1984 GNCFNADNXFCICHUS 3,32,55,84,16,85
14/03/2001 EPZZSPDSTZXMMZVH 85,28,53,17,90,68

E' grande 90MB.
Quello che dici tu è grande 46MB (è quello da 38 sec).
A me con quello che pensavo essere il piu' grande ci mette 33secondi (e ho solo 2GB di ram), come mai tutta questa differenza?
Che processore hai?
Comunque non c'è differenza tra 2GB e 4GB di RAM, il picco di consumo del programma è di 1.3GB con i file da 90MB.

[gugoXX]

Certo, ora ho capito.
Mi ero tarato su quello che pensavo essere il file grande, e che invece e' piccolo.
Ho un 3GHz dual core e 2GB.

Vedremo se mi verra' in mente qualcos'altro.
Volevo provare un algoritmo diverso, ma non e' vincente (almeno per altri 2/3 anni)

[songoge]

Certo, ora ho capito.
Mi ero tarato su quello che pensavo essere il file grande, e che invece e' piccolo.
Ho un 3GHz dual core e 2GB.

Vedremo se mi verra' in mente qualcos'altro.
Volevo provare un algoritmo diverso, ma non e' vincente (almeno per altri 2/3 anni)

Lo volevi fare GPGPU?

Fate contest anche con Cuda? Sarebbe interessante vedere la differenza con una compilazione in cuda.

[gugoXX]

Lo volevi fare GPGPU?

Fate contest anche con Cuda? Sarebbe interessante vedere la differenza con una compilazione in cuda.

No, l'ho semplicemente fatto multicore, ma anche la prima versione era cosi' e con performance non cosi' penose. Vediamo, forse mi sta venendo in mente qualcosa per ridurre.

[songoge]

No, l'ho semplicemente fatto multicore, ma anche la prima versione era cosi' e con performance non cosi' penose. Vediamo, forse mi sta venendo in mente qualcosa per ridurre.

Ma anche la programmazione GPGPU è multicore. In particolare ho dato un'occhiata a cuda. Volevo utilizzarlo per costruire un motore IA, ma ho dovuto rimandare a tempi migliori perchè in questo periodo devo finire un'altro proggetto. A prima vista mi sembra troppo incasinato il sistema per gestire più processi. Forse è meglio attendere le schede multicore di intel basate su singoli core x86 (non ricordo il nome).

[Vincenzo1968]

Quello di gugoXX occupa 600MB di RAM con i file "piccoli", 1300MB con i file grandi. :eek:

autore (compilatore): tempo (piccoli ~50MB) / tempo (grandi ~90MB) - rapporto

cionci (C++ - GCC): 6058ms / 11930ms - 1.97
cionci (C++ - VS): 5753ms / 11461ms - 1.99
repne (C - GCC): 1563ms / 3186ms - 2.03
repne (C - VS): 1541ms / 3006ms - 1.95
gugoXX (C# / C++ - VS): 38577ms / 98240ms - 2.54

Vista x86-64
Intel T9300 @ 2.50GHz
4.00GB RAM

VS = Visual Studio 2008, GCC = GCC 4.3.2-tdm-1

Per rilevare l'occupazione di memoria usi tools particolari come, per esempio, Performance Monitor Tool presente in Windows o lo fai da codice? In quest'ultimo caso, puoi postare un esempio?

[||ElChE||88]

Per rilevare l'occupazione di memoria usi tools particolari come, per esempio, Performance Monitor Tool presente in Windows o lo fai da codice? In quest'ultimo caso, puoi postare un esempio?
Uso Process Explorer, niente di complicato. Purtroppo la mia conoscenza delle API Windows è quasi nulla...

[cionci]

Ma i tempi li hai ottenuti utilizzando le ottimizzazioni ?

[Vincenzo1968]

Uso Process Explorer, niente di complicato. Purtroppo la mia conoscenza delle API Windows è quasi nulla...

cioè questo?:

http://technet.microsoft.com/en-us/sysinternals/bb896653.aspx

[Vincenzo1968]

Ohé, ho misurato le performance di Repne e Cionci con Process Explorer:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3


Repne:
http://www.guidealgoritmi.it/images/ImgForums/ProcessExplorerRepne.jpg

Cionci:
http://www.guidealgoritmi.it/images/ImgForums/ProcessExplorerCionci.jpg

Le misure sono effettuate utilizzando il file più grosso(circa 88 MB).

[cionci]

Vincenzo, prova questo, dovrebbe essere un po' più veloce (sul mio il 25%), soprattutto se il tuo compilatore non ottimizza bene la STL dovrebbe rendere meglio. Ora guardo di togliere tutti i vector senza perdere prestazioni, e vi devo dire che su GCC 4.2 è davvero difficile, soprattutto nel caso in cui non si sappia a priori la dimensione da allocare. Proverò con un'allocazione a blocchi.
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstring>
#include <ctime>

using namespace std;

//#define DATAFILENAME "LottoDataDifficile.txt"
//#define SEARCHFILENAME "LottoFindDifficile.txt"

#define DATAFILENAME "LOTTO.D1"
#define SEARCHFILENAME "LOTTO.D2"


class MyBitSet
{
unsigned int bits[3];
public:
MyBitSet()
{
bits[0] = bits[1] = bits[2] = 0;
}

void set(unsigned int n)
{
bits[n >> 5] |= 1 << (n & 0x1F);
}

bool test(MyBitSet & other)
{
return ((other.bits[0] & bits[0]) == other.bits[0]) &&
((other.bits[1] & bits[1]) == other.bits[1]) &&
((other.bits[2] & bits[2]) == other.bits[2]);
}
};


void parseNumbersString(const string &numbers, int *v, MyBitSet & bits)
{
unsigned int i = 0;
int items = 0;
while (i < numbers.size())
{
if (numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if (numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}
v[items] = item;
bits.set(item);
++items;
}
++i;
}
}


class Drawing
{
MyBitSet bits;
string text;
int *v;

public:
Drawing(int numeberCount, const string &city, const string &date, const string &numbers)
{
text = date;
text.append(" ");
text.append(city);
text.append(" ");
text.append(numbers);

v = new int[numeberCount];
parseNumbersString(numbers, v, bits);
}

const string & toString()
{
return text;
}

bool isMatching(MyBitSet &toBeTested)
{
return bits.test(toBeTested);
}

int getNumber(int i)
{
return v[i];
}
};


class Database
{
vector<Drawing *> drawings[91][91];
int numberCount;
int *v;
public:
Database(int numberCount): numberCount(numberCount)
{
v = new int[numberCount];
}

void insertDrawing(Drawing * drawing)
{
for (int i = 0; i < numberCount; ++i)
{
for (int j = 0; j < numberCount; ++j)
{
if (j != i)
{
drawings[drawing->getNumber(i)][drawing->getNumber(j)].push_back(drawing);
}
}
}
}

void printDrawings(const string &numbers)
{
MyBitSet bits;
parseNumbersString(numbers, v, bits);

vector<Drawing *> &l = drawings[v[0]][v[1]];

bool print = false;

//for(vector<Drawing*>::iterator it = l.begin(); it != l.end(); it++)
for(unsigned int i = 0; i < l.size(); ++i)
{
if (l.at(i)->isMatching(bits))
{
if(!print)
{
print = true;
cout << "-- " << numbers << " --" << endl;
}

cout << l.at(i)->toString() << endl;
}
}
}
};


int main()
{
ifstream f(DATAFILENAME);

string date, city, numbers;

if (f.fail())
{
cout << "Errore apertura file dati" << endl;
return 1;
}

getline(f, numbers);
getline(f, numbers, ' ');

int numberCount;
f >> numberCount;

if (f.fail())
{
cout << "Errore parametri file dati" << endl;
return 1;
}

Database db(numberCount);

getline(f, numbers);

while (1)
{
getline(f, date, ' ');
if (f.eof() || f.fail()) break;
getline(f, city, ' ');
getline(f, numbers);
Drawing * d = new Drawing(numberCount, city, date, numbers);
db.insertDrawing(d);
}

f.close();
f.clear();
f.open(SEARCHFILENAME);

if (f.fail())
{
cout << "Errore apertura file di ricerca" << endl;
return 1;
}

int count;
getline(f, date, ' ');
f >> count;

if (f.fail())
{
cout << "Errore parametri file di ricerca" << endl;
return 1;
}

getline(f, numbers);
for (int i = 0; i < count; ++i)
{
getline(f, numbers);

db.printDrawings(numbers);
}

return 0;
}

[Vincenzo1968]

Si, è più veloce:

http://www.guidealgoritmi.it/images/ImgForums/OutputCionci3.jpg

[Vincenzo1968]

Anche il codice di repne risulta più veloce togliendo l'output non necessario(la stampa, cioè, della memoria allocata/deallocata e dei tempi di esecuzione):

http://www.guidealgoritmi.it/images/ImgForums/OutputRepne.jpg


#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include <mem.h>
#include <malloc.h>

#define N_CLK 10
#define N_MAGIC 3
#define MAX_N_DIM 10
#define MAX_N 90
#define E_ZN 3
#define DATA_LEN 3
#define Y_ZERO 1900

//#define INPUT_FILE_NAME_D1 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrossoNew\\LOTTO.D1"
//#define INPUT_FILE_NAME_D2 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrossoNew\\LOTTO.D2"

#define INPUT_FILE_NAME_D1 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoEnorme\\LOTTO.D1"
#define INPUT_FILE_NAME_D2 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoEnorme\\LOTTO.D2"


int Get_Number(char *,long *);

int main()
{
//clock_t clk[N_CLK];
char *buffer_file_d1, *buffer_file_d2, *buffer_file_tmp, *end_buffer_file;
char *st_arry, *st_arry_tmp, **rt_name;
char *magic[N_MAGIC] = {"Ruote", "Valori", "Find"};
char f_elem[MAX_N];

FILE *input_file_handle_d1, *input_file_handle_d2;
int i, j, k, l, m, n;
int mem_name = 0, e_find, find, element, sp, rt_name_size;
int disp, disp_t, n_estr = 0;
int input_file_size_d1, input_file_size_d2, ruote, valori, *e_arry, *l_arry;

int table_disp[20][3] = {
{0,1,2},
{0,1,3},
{0,1,4},
{0,1,5},
{0,2,3},
{0,2,4},
{0,2,5},
{0,3,4},
{0,3,5},
{0,4,5},
{1,2,3},
{1,2,4},
{1,2,5},
{1,3,4},
{1,3,5},
{1,4,5},
{2,3,4},
{2,3,5},
{2,4,5},
{3,4,5}
};

//clk[0] = clock();

if((input_file_handle_d1 = fopen(INPUT_FILE_NAME_D1,"rb")) == NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME_D1 "\n");
return 1;
}

if(fseek(input_file_handle_d1,0L,SEEK_END))
{
fprintf(stderr,"Errore interno: 001\n");
return 1;
}

if((input_file_size_d1 = ftell(input_file_handle_d1)) == -1)
{
fprintf(stderr,"Errore interno: 002\n");
return 1;
}

if(fseek(input_file_handle_d1,0L,SEEK_SET))
{
fprintf(stderr,"Errore interno: 003\n");
return 1;
}

if((buffer_file_d1 = malloc(input_file_size_d1)) == NULL)
{
fprintf(stderr,"Memoria insufficiente (001 : %d Byte)\n",input_file_size_d1);
return 1;
}
//else
// printf("001 - Allocati: %d Byte\n",input_file_size_d1);

if(fread(buffer_file_d1,input_file_size_d1,1,input_file_handle_d1) == 0)
{
fprintf(stderr,"Errore interno: 004\n");
return 1;
}

if(fclose(input_file_handle_d1))
{
fprintf(stderr,"Errore interno: 005\n");
return 1;
}

end_buffer_file = buffer_file_d1 + input_file_size_d1;

if(memcmp(magic[0],buffer_file_d1,strlen(magic[0])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (001)\n");
return 1;
}

buffer_file_d1 += strlen(magic[0]);
if((ruote = Get_Number(buffer_file_d1,(long *)&buffer_file_d1)) == 0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (002)\n");
return 1;
}

if( (rt_name=malloc(ruote*sizeof(int))) == NULL )
{
fprintf(stderr,"Memoria insufficiente (002 : %d Byte)\n",ruote*sizeof(int));
return 1;
}
//else
// printf("002 - Allocati: %d Byte\n",ruote*sizeof(int));

if(memcmp(magic[1],buffer_file_d1,strlen(magic[1])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (003)\n");
return 1;
}

buffer_file_d1 += strlen(magic[1]);
if((valori = Get_Number(buffer_file_d1,(long *)&buffer_file_d1)) == 0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (004)\n");
return 1;
}

buffer_file_tmp = buffer_file_d1;

while(buffer_file_tmp<end_buffer_file)
{
if((*buffer_file_tmp==0x0A)||(*buffer_file_tmp==0x0D))
{
n_estr++;
buffer_file_tmp++;
if((*buffer_file_tmp == 0x0A) || (*buffer_file_tmp == 0x0D))
buffer_file_tmp++;
}
else
buffer_file_tmp++;
}

if( n_estr % ruote )
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (005)\n");
return 1;
}
else
{
if((st_arry = malloc(n_estr*(DATA_LEN+valori))) == NULL)
{
fprintf(stderr,"Memoria insufficiente (003 : %d Byte)\n",n_estr*(DATA_LEN+valori));
return 1;
}
//else
// printf("003 - Allocati: %d Byte\n",n_estr*(DATA_LEN+valori));
n_estr /= ruote;
}

for(disp_t = valori, i = valori-1; i > (valori-E_ZN); i--)
disp_t*=i;
for(i=2;i<=E_ZN;i++)
disp_t/=i;

if((l_arry = malloc(disp_t*n_estr*ruote*(sizeof(int) << 1))) == NULL)
{
fprintf(stderr,"Memoria insufficiente (004 : %d Byte)\n",disp_t*n_estr*ruote*(sizeof(int)<<1));
return 1;
}
//else
// printf("004 - Allocati: %d Byte\n",disp_t*n_estr*ruote*(sizeof(int) << 1));

for(j = 1, disp = i = 0; i <E_ZN; i++, j *= MAX_N)
disp += (MAX_N-i-1) * j;

if((e_arry = malloc(++disp*sizeof(int))) == NULL)
{
fprintf(stderr,"Memoria insufficiente (005 : %d Byte)\n",disp*sizeof(int));
return 1;
}
//else
// printf("005 - Allocati: %d Byte\n",disp*sizeof(int));

memset(e_arry, 0, disp*sizeof(int));

for(st_arry_tmp = st_arry, element = sp = i = 0; i < n_estr; i++)
{
for( j = 0; j < ruote; j++ )
{
st_arry[0] = Get_Number(buffer_file_d1,(long *)&buffer_file_d1);
st_arry[1] = Get_Number(buffer_file_d1,(long *)&buffer_file_d1);
st_arry[2] = Get_Number(buffer_file_d1,(long *)&buffer_file_d1) - Y_ZERO;

buffer_file_d1++;
if(sp==0)
{
buffer_file_tmp = buffer_file_d1;
while (*buffer_file_tmp++ != ' ');
rt_name_size = buffer_file_tmp-buffer_file_d1;
*(buffer_file_tmp-1)=0;
if((rt_name[j] = malloc(rt_name_size)) == NULL)
{
fprintf(stderr,"Memoria insufficiente (006 : %d Byte)\n",rt_name_size);
return 1;
}
mem_name += rt_name_size;
memcpy(rt_name[j],buffer_file_d1,rt_name_size);
buffer_file_d1+=rt_name_size;
}
else
while (*buffer_file_d1++ != ' ');

for(k=0;k<valori;k++)
st_arry[DATA_LEN + k] = Get_Number(buffer_file_d1, (long *)&buffer_file_d1);

do
{
l = 0;
for(k = 0; k < (valori-1); k++)
{
if(st_arry[DATA_LEN+k] > st_arry[DATA_LEN+k+1])
{
l = st_arry[DATA_LEN+k];
st_arry[DATA_LEN+k] = st_arry[DATA_LEN+k+1];
st_arry[DATA_LEN+k+1] = l;
l = 1;
}
}
} while (l);

for(k = 0;k < disp_t; k++)
{
for(m = st_arry[DATA_LEN+table_disp[k][0]]-1,l = 1; l < E_ZN; l++)
m = m*MAX_N+st_arry[DATA_LEN+table_disp[k][l]]-1;

if(e_arry[m])
l_arry[1] = e_arry[m];
else
l_arry[1] = -1;
e_arry[m] = (int)l_arry;
*l_arry = element;
l_arry += 2;
}
element++;

st_arry+=DATA_LEN+valori;
}
if( sp == 0 )
{
//printf("006 - Allocati: %d Byte\n", mem_name);
sp = 1;
}
}

st_arry = st_arry_tmp;

free(buffer_file_d1);
//printf("007 - Deallocati: %d Byte\n",input_file_size_d1);

//clk[1] = clock();

if((input_file_handle_d2 = fopen(INPUT_FILE_NAME_D2,"rb")) == NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME_D2 "\n");
return 1;
}

if(fseek(input_file_handle_d2,0L,SEEK_END))
{
fprintf(stderr,"Errore interno: 006\n");
return 1;
}

if((input_file_size_d2 = ftell(input_file_handle_d2)) == -1)
{
fprintf(stderr,"Errore interno: 007\n");
return 1;
}

if(fseek(input_file_handle_d2,0L,SEEK_SET))
{
fprintf(stderr,"Errore interno: 008\n");
return 1;
}

if((buffer_file_d2 = malloc(input_file_size_d2)) == NULL)
{
fprintf(stderr,"Memoria insufficiente (007 : %d Byte)\n",input_file_size_d2);
return 1;
}
//else
// printf("008 - Allocati: %d Byte\n\n",input_file_size_d2);

if(fread(buffer_file_d2,input_file_size_d2,1,input_file_handle_d2) == 0)
{
fprintf(stderr,"Errore interno: 009\n");
return 1;
}

if(fclose(input_file_handle_d2))
{
fprintf(stderr,"Errore interno: 010\n");
return 1;
}

if(memcmp(magic[2],buffer_file_d2,strlen(magic[2])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D2 " non corretto - (001)\n");
return 1;
}

buffer_file_d1 += strlen(magic[0]);

if((find = Get_Number(buffer_file_d2,(long *)&buffer_file_d2)) == 0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D2 " non corretto - (002)\n");
return 1;
}

for(i = 0; i < find; i++)
{
for(j = 0; j < MAX_N; j++)
{
f_elem[j] = Get_Number(buffer_file_d2,(long *)&buffer_file_d2);
if(*buffer_file_d2 != ',')
break;
}

do
{
l = 0;
for(k = 0; k < j; k++)
{
if(f_elem[k] > f_elem[k+1])
{
l = f_elem[k];
f_elem[k] = f_elem[k+1];
f_elem[k+1] = l;
l = 1;
}
}
} while (l);

for(e_find = 0, m = f_elem[0]-1, l = 1; l < E_ZN; l++)
m = m*MAX_N+f_elem[l]-1;
if(e_arry[m])
{
l_arry = (int *)e_arry[m];
do
{
element = *l_arry;

for(k = element*(DATA_LEN+valori), l = E_ZN; l <= j; l++)
{
for( n = m = 0; m < valori; m++ )
{
if( st_arry[DATA_LEN + m + k] == f_elem[l] )
n = 1;
}
if(n == 0)
break;
}

if( l == (j+1) )
{
if( e_find == 0 )
{
printf("-- ");
for(k = 0; k <= j; k++)
{
printf("%d",f_elem[k]);
if(k!=j)
printf(",");
}
printf(" --\n");
e_find = 1;
}
printf("%.2d/%.2d/%.4d %s ",
st_arry[element*(DATA_LEN+valori)],
st_arry[element*(DATA_LEN+valori)+1],
st_arry[element*(DATA_LEN+valori)+2]+Y_ZERO,
rt_name[element%ruote]);
for( k = 0; k < valori; k++ )
{
printf("%d", st_arry[element*(DATA_LEN+valori)+DATA_LEN+k]);
if(k != (valori-1))
printf(",");
}
printf("\n");
}

l_arry = (int *)*(l_arry+1);
} while ((int)l_arry != -1);
}
}

//clk[2] = clock();

//printf("\n*** Tempo per caricamento dati e creazione strutture: %7.3f secondi\n",(double)(clk[1]-clk[0])/CLK_TCK);
//printf("\n*** Tempo per ricerca della soluzione difficile: %7.3f secondi\n",(double)(clk[2]-clk[1])/CLK_TCK);
//printf("\n*** Tempo totale per l'intera elaborazione: %7.3f secondi\n",(double)(clk[2]-clk[0])/CLK_TCK);

return 0;
}

int Get_Number(char *buffer, long *offset)
{
int rnum = -1, i = 0;
char numero[MAX_N_DIM];

for(;;buffer++)
{
if((*buffer == 0x0A) || (*buffer == 0x0D))
{
buffer++;
break;
}
if((*buffer>='0')&&(*buffer<='9'))
{
do
{
numero[i++] = *buffer++;
} while ((*buffer >= '0') && (*buffer <= '9'));
numero[i]=0;
rnum = atoi(numero);
if((*buffer == 0x0A) || (*buffer == 0x0D))
buffer++;
break;
}
}
if((*buffer == 0x0A) || (*buffer == 0x0D))
buffer++;

*offset = (long)buffer;

return(rnum);
}

[Vincenzo1968]

http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica10.jpg


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3

[Vincenzo1968]

Questa è la classifica di Elche ma con i vecchi file. Si dovrebbe aggiornare con la nuova versione di Cionci e con le modifiche che ho apportato al codice di repne.

http://www.guidealgoritmi.it/images/ImgForums/Contest07ClassificaElche03.jpg


Vista x86-64
Intel T9300 @ 2.50GHz
4.00GB RAM


P.S. Elche, visto che disponi di un bel po' di ram, potresti provare a prendere i tempi dei codici di Magix e Vicius ;)

[cionci]

Ho provato a togliere i vector dal repository. Sul mio PC ho addirittura un peggioramento da 3.4 a 3.5 secondi :eek: Eppure faccio l'inserimento (che è il collo di bottiglia in O(1)). Ho cercato di mantenere una struttura la più leggera possibile, eppure i miglioramenti non ci sono stati rispetto al vector.
Prova a vedere Vincenzo se magari il tuo compilatore è più sensibile anche in questo caso alla STL. Dovrebbe essere sceso di un po' anche il consumo di ram.

#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

//#define DATAFILENAME "LottoDataDifficile.txt"
//#define SEARCHFILENAME "LottoFindDifficile.txt"

#define DATAFILENAME "/home/cionci/Contest7/bin/Release/LOTTO.D1"
#define SEARCHFILENAME "/home/cionci/Contest7/bin/Release/LOTTO.D2"


class MyBitSet
{
unsigned int bits[3];
public:
MyBitSet()
{
bits[0] = bits[1] = bits[2] = 0;
}

void set(unsigned int n)
{
bits[n >> 5] |= 1 << (n & 0x1F);
}

bool test(MyBitSet & other)
{
return ((other.bits[0] & bits[0]) == other.bits[0]) &&
((other.bits[1] & bits[1]) == other.bits[1]) &&
((other.bits[2] & bits[2]) == other.bits[2]);
}
};


void parseNumbersString(const string &numbers, int *v, MyBitSet & bits)
{
unsigned int i = 0;
int items = 0;
while (i < numbers.size())
{
if (numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if (numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}
v[items] = item;
bits.set(item);
++items;
}
++i;
}
}


class Drawing
{
MyBitSet bits;
string text;
int *v;

public:
Drawing(int numeberCount, const string &city, const string &date, const string &numbers)
{
text = date;
text.append(" ");
text.append(city);
text.append(" ");
text.append(numbers);

v = new int[numeberCount];
parseNumbersString(numbers, v, bits);
}

const string & toString()
{
return text;
}

bool isMatching(MyBitSet &toBeTested)
{
return bits.test(toBeTested);
}

int getNumber(int i)
{
return v[i];
}
};

const unsigned int Bits = 9;
const unsigned int DataSize = 1 << Bits;
const unsigned int IndexMask = DataSize - 1;

class MyList
{
struct DataElement
{
Drawing * data[DataSize];
DataElement * next;

DataElement(): next(NULL)
{
}
};

int insertCounter;
int size;
int readCounter;

DataElement * first;
DataElement * last;
DataElement * current;

public:
MyList(): insertCounter(0), size(DataSize), readCounter(0)
{
current = last = first = new DataElement();
}

void insert(Drawing * d)
{
if(insertCounter == size)
{
last -> next = new DataElement();
last = last->next;
size += DataSize;
}
last->data[insertCounter++ & IndexMask] = d;
}

Drawing * getNext()
{
Drawing * tmp = current->data[readCounter++ & IndexMask];
if(!(readCounter & IndexMask))
{
current = current->next;
}
return tmp;
}

bool hasNext()
{
return readCounter < insertCounter;
}

void reset()
{
readCounter = 0;
current = first;
}
};

class Database
{
MyList drawings[91][91];
int numberCount;
int *v;
public:
Database(int numberCount): numberCount(numberCount)
{
v = new int[numberCount];
}

void insertDrawing(Drawing * drawing)
{
for (int i = 0; i < numberCount; ++i)
{
for (int j = 0; j < numberCount; ++j)
{
if (j != i)
{
drawings[drawing->getNumber(i)][drawing->getNumber(j)].insert(drawing);
}
}
}
}

void printDrawings(const string &numbers)
{
MyBitSet bits;
parseNumbersString(numbers, v, bits);

MyList &l = drawings[v[0]][v[1]];

bool print = false;

while(l.hasNext())
{
Drawing * d = l.getNext();
if (d->isMatching(bits))
{
if(!print)
{
print = true;
cout << "-- " << numbers << endl;
}

cout << d->toString() << endl;
}
}
l.reset();
}
};


int main()
{
ifstream f(DATAFILENAME);

string date, city, numbers;

if (f.fail())
{
cout << "Errore apertura file dati" << endl;
return 1;
}

getline(f, numbers);
getline(f, numbers, ' ');

int numberCount;
f >> numberCount;

if (f.fail())
{
cout << "Errore parametri file dati" << endl;
return 1;
}

Database db(numberCount);

getline(f, numbers);

while (1)
{
getline(f, date, ' ');
if (f.eof() || f.fail()) break;
getline(f, city, ' ');
getline(f, numbers);
Drawing * d = new Drawing(numberCount, city, date, numbers);
db.insertDrawing(d);
}

f.close();
f.clear();
f.open(SEARCHFILENAME);

if (f.fail())
{
cout << "Errore apertura file di ricerca" << endl;
return 1;
}

int count;
getline(f, date, ' ');
f >> count;

if (f.fail())
{
cout << "Errore parametri file di ricerca" << endl;
return 1;
}

getline(f, numbers);
for (int i = 0; i < count; ++i)
{
getline(f, numbers);

db.printDrawings(numbers);
}

return 0;
}

[cionci]

Come faccio a semplificare l'inserimento più di così ??? :stordita:
void insert(Drawing * d)
{
if(insertCounter == size)
{
last -> next = new DataElement();
last = last->next;
size += DataSize;
}
last->data[insertCounter++ & IndexMask] = d;
}

[Vincenzo1968]

Invece, da me, i tempi migliorano di molto:

http://www.guidealgoritmi.it/images/ImgForums/OutputCionci4.jpg

ma peggiora il rapporto: 12.55

Che faccio? Se inserisco questi nuovi dati in classifica balzi all'ultimo posto e il sambenito non te lo toglie più nessuno :Perfido:

[||ElChE||88]

P.S. Elche, visto che disponi di un bel po' di ram, potresti provare a prendere i tempi dei codici di Magix e Vicius ;)
Ora ci provo. :O

[VICIUS]

Ora ci provo. :O
Sarà interessante vedere quante settimane impiegherà la versione ruby per terminare :asd:

[Vincenzo1968]

Ora ci provo. :O

Ricordati anche di ricompilare le nuove versioni di Repne e Cionci.

Da qui (http://www.guidealgoritmi.it/public/MagixVicius.zip) puoi scaricare i sorgenti di Magix e Vicius.

P.S. quelli di Magix sono quattro file .java che fanno parte di un unico progetto.

[Vincenzo1968]

Sarà interessante vedere quante settimane impiegherà la versione ruby per terminare :asd:

Non è detto. La tua ultima versione, sui file piccoli, era abbastanza veloce. Mi dava problemi di memoria su quelli grossi ;)

[||ElChE||88]

Ma quanto è lento il download di Ruby? :cry:
Va a 1.2kb/s... è "leggermente" umiliante per una 100Mbit. :muro:

Edit: niente, il file continua a corrompersi...
Ri-edit: risolto, ora testo

[magix2003]

Io sinceramente lascerei stare la mia versione... semplicemente dubito che terminerà!

[||ElChE||88]

Io sinceramente lascerei stare la mia versione... semplicemente dubito che terminerà!
Infatti, dopo tre quarti d'ora sono giunto alla stessa conclusione. :fagiano:
Anche quella di VICIUS non sembra dare segni di vita. :fagiano:

Edit: lascio stare pure quella, in 25 minuti ha fatto 1/5 delle ricerche (file piccolo).
Ora aggiorno le solite.

[VICIUS]

Infatti, dopo tre quarti d'ora sono giunto alla stessa conclusione. :fagiano:
Anche quella di VICIUS non sembra dare segni di vita. :fagiano:

Edit: lascio stare pure quella, in 25 minuti ha fatto 1/5 delle ricerche (file piccolo).
Ora aggiorno le solite.
Hai misurato l'utilizzazione della ram? Mi piacerebbe sapere a quanto è arrivato il processo della vm.

[||ElChE||88]

autore (compilatore): tempo (piccoli ~50MB) / tempo (grandi ~90MB) - rapporto

cionci (C++ - GCC): 5388ms / 10845ms - 2.01
cionci - no vector (C++ - GCC): 5054ms / 10003ms - 1.98
cionci (C++ - VS): 7245ms / 14212ms - 1.96
cionci - no vector (C++ - VS): 5599ms / 10942ms - 1.95
repne (C - GCC): 1636ms / 3155ms - 1.93
repne (C - VS): 1490ms / 2941ms - 1.97
gugoXX (C# / C++ - VS): 35315ms / 90019ms - 2.55


Vista x86-64
Intel T9300 @ 2.50GHz
4.00GB RAM

VS = Visual Studio 2008, GCC = GCC 4.3.2-tdm-1


Non ho la più pallida idea sul perché la versione VS di cionci (con i vector) impieghi più tempo delle altre. Ho provato a ricompilarla varie volte ma il risultato è sempre quello. :fagiano:

Hai misurato l'utilizzazione della ram? Mi piacerebbe sapere a quanto è arrivato il processo della vm.
Sui 500MB...

[cionci]

Non ho la più pallida idea sul perché la versione VS di cionci (con i vector) impieghi più tempo delle altre. Ho provato a ricompilarla varie volte ma il risultato è sempre quello. :fagiano:
Te lo dico io...l'ottimizzazione del compilatore di MS per i Vector non è scandalosa...di più.

Ad entrambi: provate ad aumentare la dimensione del vettore preallocato...

const unsigned int Bits = 9; <---mettetelo a 10 o 11

Quasi raddoppia o quadruplica la memoria utilizzata. Cosa mi dite sull'utilizzo di memoria ? Io posso fare male i conti perché ho gli indirizzi a 64 bit ;)

[Vincenzo1968]

Eqque qua:

Classifica per rapporto tra i due tempi di esecuzione:

http://www.guidealgoritmi.it/images/ImgForums/Contest07ClassificaElche04.jpg

Classifica per tempi di esecuzione:

http://www.guidealgoritmi.it/images/ImgForums/Contest07ClassificaElche05.jpg

La macchina è questa:


Vista x86-64
Intel T9300 @ 2.50GHz
4.00GB RAM

[||ElChE||88]

const unsigned int Bits = 9; <---mettetelo a 10 o 11

Quasi raddoppia o quadruplica la memoria utilizzata. Cosa mi dite sull'utilizzo di memoria ? Io posso fare male i conti perché ho gli indirizzi a 64 bit ;)
Sul mio sistema l'utilizzo resta uguale identico (280MB per i file "piccoli").

[cionci]

Sul mio sistema l'utilizzo resta uguale identico (280MB per i file "piccoli").
In effetti l'utilizzo dovrebbe aumentare solo per file troppo piccoli. Aumenta la dimensione dei blocchi, quindi anche del primo blocco allocato con contenitore vuoto. In ogni caso dovrebbe ssere più veloce con 11 o addirittura salendo a 12 (4096 byte per blocco).

[Vincenzo1968]

Ohé,

ho notato che l'eseguibile win32 che ha postato repne è più veloce di quello che ho compilato io col visual studio:

Tempi sui file grandi:
http://www.guidealgoritmi.it/images/ImgForums/outputRepne2.jpg

Il file si può scaricare da qui:

http://www.usaupload.net/d/1bppcml2wbw

e credo che sia compilato col watcom ;)

[rеpne scasb]

■

[^TiGeRShArK^]

tnx x la spiegazione :p

[banryu79]

Nulla di speciale dici? Me cojoni :sofico:
Hai delle invidiabilissime (almeno da parte mia) capacità analitiche e matematiche!

Perdonate la nubbiaggine che mi affligge, ma perchè è veloce? Che tipo di complessità ha?

[cionci]

repne: ma se la sequenza da ricercare è lunga 2 elementi come può venire trovata se si indicizza usandone tre ?

[rеpne scasb]

■

[rеpne scasb]

■

[rеpne scasb]

■

[okay]

Non ti fare impressionare, ti assicuro che non e' complesso ed implementarlo e' semplice. Prova a scrivere, nel linguaggio di programmazione che preferisci, il software che risolve il contest 7 con questo algoritmo. Se vuoi, nei limiti del tempo che ho disposizione, posso seguirti passo passo, chiarendoti i punti che trovi oscuri.

grande, grande rep... ciao è proprio bello leggerti... ritorno indietro nel tempo... ciao cionci ciao a tutti...;)

[^TiGeRShArK^]

Non ti fare impressionare, ti assicuro che non e' complesso ed implementarlo e' semplice. Prova a scrivere, nel linguaggio di programmazione che preferisci, il software che risolve il contest 7 con questo algoritmo. Se vuoi, nei limiti del tempo che ho disposizione, posso seguirti passo passo, chiarendoti i punti che trovi oscuri.

io alla fine stavo facendo qualcosa di simile..
ma l'usare 3 numeri come chiave anzichè tutti e 6 i numeri delle estrazioni non mi era proprio venuto in mente.. :fagiano:

[banryu79]

Non ti fare impressionare, ti assicuro che non e' complesso ed implementarlo e' semplice. Prova a scrivere, nel linguaggio di programmazione che preferisci, il software che risolve il contest 7 con questo algoritmo. Se vuoi, nei limiti del tempo che ho disposizione, posso seguirti passo passo, chiarendoti i punti che trovi oscuri.
Proverò (stasera non posso, sono già impegnato fino a tardi) ma ho capito cosa vuoi dire; quello che ti invidio nn è l'esperienza col linguaggio ma proprio le conoscenze matematiche.
Copiare è un conto, con davanti la spiegazione poi... ben diverso è pensare da zero a una soluzione.
Ma forse appunto sono un po' "cucco" io a stupirmi che conosciate la matematica, solo perchè io non l'ho studiata :p

[rеpne scasb]

■

[rеpne scasb]

■

[banryu79]

Se senti di voler imparare la matematica, fallo subito! :)
Lo sto già facendo da un paio di settimane ;)

[cionci]

repne, un'ultima osservazione, ma se la quantità dei numeri estratti per ogni ruota cambia, mettiamo che diventino 7, allora devi variare table_disp manualmente ?

[rеpne scasb]

■

[dierre]

Che figata i contest, devo preparare due esami che poi ho finito, se ad anno nuovo ancora li fate partecipo. (Se mi ci metto ora rischio di non studiare :P )

[Vincenzo1968]

Che figata i contest, devo preparare due esami che poi ho finito, se ad anno nuovo ancora li fate partecipo. (Se mi ci metto ora rischio di non studiare :P )

Ciao Dierre,

attento che è come il vizio del fumo: una volta preso, poi è difficile smettere.

Questi i link ai contest precedenti:

Contest 1 (http://www.hwupgrade.it/forum/showthread.php?t=1784948)

Contest 2 (http://www.hwupgrade.it/forum/showthread.php?t=1785752)

Contest 3 (http://www.hwupgrade.it/forum/showthread.php?t=1787500)

Contest 4 (http://www.hwupgrade.it/forum/showthread.php?t=1791293)

Contest 5 (http://www.hwupgrade.it/forum/showthread.php?t=1799059)

Contest 6 (http://www.hwupgrade.it/forum/showthread.php?t=1850150)

Contest 7 (http://www.hwupgrade.it/forum/showthread.php?t=1839674)

;)

[Vincenzo1968]

Giusta osservazione. Questo e' vero, per pigrizia non ho scritto l'algoritmo che crea table_disp in modo automatico al variare di V. Il codice che ho postato non funzionerebbe se V=7, pero' modificarlo per adattarlo a V=7 e' abbastanza semplice e richiederebbe pochi minuti. Ben piu' complesso e' creare table_disp "al volo" al variare di V.

Ciao Repne,

sto tentando di modificare il tuo codice in modo da creare al volo la tabella table_disp.
C'è qualche algoritmo che permetta di generare, in modo efficiente, le combinazioni?

[cionci]

for(int i = 0; i < n-1; ++i)
for(int j = i + 1; j < n; ++j)

dovrebbe bastare ;)

[rеpne scasb]

■

[Vincenzo1968]

for(int i = 0; i < n-1; ++i)
for(int j = i + 1; j < n; ++j)

dovrebbe bastare ;)

Grazie mille ;)

A occhio(ma di matematica non ne so niente: proprio il niente che è niente) mi sembra abbia una complessità O(n^2); un ciclo for annidato all'interno di un altro.

Ho detto una cavolata? :confused: (molto probabilmente si).

Se non ricordo male, avevo letto, da qualche parte, qualche tempo fa, di un algoritmo con complessità O(n x Lg n) per la generazione di combinazioni.

[cionci]

Basta per Z=2. Ma se Z=5? Z=17 e V=35?
Eh sì...per Z > 2 in effetti diventa complesso.
Io l'avevo fatto in C++ sfruttando le permutazioni.

[cionci]

Comunque sì, è O(n^2)...anche se è più basso di n^2. Il calcolo esatto è:

n! / 2! * (n-2)! = (n * (n - 1)) / 2

[cionci]

Eh sì...per Z > 2 in effetti diventa complesso.
Io l'avevo fatto in C++ sfruttando le permutazioni.
Ecco il codice:
class SimpleCombination
{
unsigned int count;
vector<int> markers;
vector<int> values;
bool hasNextCombination;

public:
SimpleCombination(const vector<int> &values, unsigned int count): count(count), values(values)
{
for(unsigned int i = 0; i < values.size(); ++i)
{
markers.push_back((i < count) ? 1 : 0);
}

next_permutation(markers.begin(), markers.end());
hasNextCombination = true;
}

bool hasNext()
{
return hasNextCombination;
}

void nextCombination(vector<int> & combination)
{
combination.clear();
for(unsigned int i = 0; i < values.size(); i++)
{
combination.push_back(values.at(i) * markers.at(i));
}
hasNextCombination = next_permutation(markers.begin(), markers.end());
}
};

[Vincenzo1968]

Ma qualche link o libro che tratti degli algoritmi combinatori?

Non riesco a ricordare dove ho letto quelle informazioni e non ho voglia di spulciarmi una per una tutte le centomila pagine(molte delle quali assolutamente inutili) che vengono fuori da una ricerca su google.

:)

[rеpne scasb]

■

[rеpne scasb]

■

[Vincenzo1968]

Da qualche parte ho una libreria in C che utilizza una funzione ricorsiva per calcolare le combinazioni di k elementi presi n alla volta. Se la ritrovo te la passo.

Grazie mille ;)

Nel frattempo ho trovato il codice dell'algoritmo di cui parlavo(ma non il link dal quale l'ho preso):


#include <stdio.h>
#include <stdlib.h>

void combinations (int v[], int start, int n, int k, int maxk)
{
int i;

/* k here counts through positions in the maxk-element v.
* if k > maxk, then the v is complete and we can use it.
*/
if (k > maxk)
{
/* insert code here to use combinations as you please */
for (i = 1; i <= maxk; i++)
printf ("%i ", v[i]);
printf ("\n");
return;
}

/* for this k'th element of the v, try all start..n
* elements in that position
*/
for (i = start; i <= n; i++)
{
v[k] = i;
/* recursively generate combinations of integers
* from i+1..n
*/
combinations (v, i+1, n, k+1, maxk);
}
}

int main (int argc, char *argv[])
{
int v[100], n, k;

if (argc != 3)
{
printf ("Usage: %s n k\n", argv[0]);
return 1;
}
n = atoi (argv[1]);
k = atoi (argv[2]);

/* generate all combinations of n elements taken
* k at a time, starting with combinations containing 1
* in the first position.
*/
combinations (v, 1, n, 1, k);

return 0;
}


Edit: ho trovato anche il link ;) :

http://www.cs.utsa.edu/~dj/ut/utsa/cs3343/lecture25.html

[Vincenzo1968]

Per il momento ho aggiunto la funzione combinations, modificata, al codice di Repne:


void combinations (int **pTable, int v[], int start, int n, int k, int maxk)
{
static int x = 0;
int i;

/* k here counts through positions in the maxk-element v.
* if k > maxk, then the v is complete and we can use it.
*/
if (k > maxk)
{
/* insert code here to use combinations as you please */
for (i = 1; i <= maxk; i++)
{
//printf ("%i ", v[i]);
pTable[x][i] = v[i] - 1;
}
//printf ("\n");
x++;
return;
}

/* for this k'th element of the v, try all start..n
* elements in that position
*/
for (i = start; i <= n; i++)
{
v[k] = i;
/* recursively generate combinations of integers
* from i+1..n
*/
combinations (pTable, v, i+1, n, k+1, maxk);
}
}

[Vincenzo1968]

Ohé,

ho bisogno di sapere come si calcola il numero di combinazioni.
Per esempio, quante combinazioni si ottengono con sei numeri presi a quattro a quattro?

http://www.hwupgrade.it/forum/customavatars/avatar246559_1.gif

[Vincenzo1968]

Ohé,

ho bisogno di sapere come si calcola il numero di combinazioni.
Per esempio, quante combinazioni si ottengono con sei numeri presi a quattro a quattro?

http://www.hwupgrade.it/forum/customavatars/avatar246559_1.gif

Credo di esserci riuscito:


int NumCombinations(int n, int k)
{
int x, y, z = 0;

y = n;
for ( x = n - 1; x > n - k; x-- )
y *= x;

z = k;
for ( x = k-1; x >= 2; x-- )
z *= x;

return y/z;
}


Chiamando la funzione con n = 5 e k = 4 il numero di combinazioni restituito è uguale a 5.
Chiamandola invece con n = 5 e k = 3 il numero di combinazioni è 10.
Giusto?

[rеpne scasb]

■

[rеpne scasb]

■

[Vincenzo1968]

Si

Ciao Repne,

grazie per la conferma.

Ho modificato il tuo codice in modo da creare la tabella al volo, ma mi va in crash.

Questo è il codice:


#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define N_CLK 10
#define N_MAGIC 3
#define MAX_N_DIM 10
#define MAX_N 90
#define E_ZN 4
#define DATA_LEN 3
#define Y_ZERO 1792
#define OUTPUT_BUFFER_LEN 10000000

//#define INPUT_FILE_NAME_D1 "LOTTO.D1"
//#define INPUT_FILE_NAME_D2 "LOTTO.D2"

//#define INPUT_FILE_NAME_D1 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrossoNew\\LOTTO.D1"
//#define INPUT_FILE_NAME_D2 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrossoNew\\LOTTO.D2"

#define INPUT_FILE_NAME_D1 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoEnorme\\LOTTO.D1"
#define INPUT_FILE_NAME_D2 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoEnorme\\LOTTO.D2"

/*
#if E_ZN==2
#define TABLE_C table_disp[15][E_ZN]={{0,1},{0,2},{0,3},{0,4},{0,5},{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}}
#elif E_ZN==3
#define TABLE_C table_disp[20][E_ZN]={{0,1,2},{0,1,3},{0,1,4},{0,1,5},{0,2,3},{0,2,4},{0,2,5},{0,3,4},{0,3,5},{0,4,5},{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}}
#elif E_ZN==4
#define TABLE_C table_disp[15][E_ZN]={{0,1,2,3},{0,1,2,4},{0,1,2,5},{0,1,3,4},{0,1,3,5},{0,1,4,5},{0,2,3,4},{0,2,3,5},{0,2,4,5},{0,3,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}
#endif
*/

int Get_Number(char **);
void combinations(int **pTable, int v[], int start, int n, int k, int maxk);
int NumCombinations(int n, int k);

int main()
{
int ** table_disp = NULL;
int numcomb;
int x;
int v[1000];

clock_t clk[N_CLK];
char a,*buffer_file_d1,*buffer_file_d2,*buffer_file_tmp,*end_buffer_file,*output_buffer,*output_buffer_tmp,*st_arry,*st_arry_tmp,**rt_name,*magic[N_MAGIC]={"Ruote","Valori","Find"},f_elem[MAX_N];
FILE *input_file_handle_d1,*input_file_handle_d2;
int i,j,k,l,sol=0,m,n,m1,n1,mem_name=0,e_find,find,element,sp,rt_name_size,disp,disp_t,n_estr=0,input_file_size_d1,input_file_size_d2,ruote,valori,*e_arry,*l_arry,*l_arry_base,k1[E_ZN][MAX_N];

//int TABLE_C;

clk[0]=clock();

for(m1=1,n1=E_ZN;n1>=1;n1--,m1++)
{
for(l=0,k1[E_ZN-n1][m1-1]=0,i=m1;i<=(MAX_N-n1);i++)
{
for(k=1,j=1;j<n1;j++)
k*=(MAX_N-j-i);
for(j=1;j<n1;j++)
k/=j;
l+=k;
k1[E_ZN-n1][i]=l;
}
}

if((input_file_handle_d1=fopen(INPUT_FILE_NAME_D1,"rb"))==NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME_D1 "\n");
return 1;
}

if(fseek(input_file_handle_d1,0L,SEEK_END))
{
fprintf(stderr,"Errore interno: 001\n");
return 1;
}

if((input_file_size_d1=ftell(input_file_handle_d1))==-1)
{
fprintf(stderr,"Errore interno: 002\n");
return 1;
}

if(fseek(input_file_handle_d1,0L,SEEK_SET))
{
fprintf(stderr,"Errore interno: 003\n");
return 1;
}

if((buffer_file_d1=malloc(input_file_size_d1))==NULL)
{
fprintf(stderr,"Memoria insufficiente (001 : %d Byte)\n",input_file_size_d1);
return 1;
}
else
printf("001 - Allocati: %d Byte\n",input_file_size_d1);

if(fread(buffer_file_d1,input_file_size_d1,1,input_file_handle_d1)==0)
{
fprintf(stderr,"Errore interno: 004\n");
return 1;
}

if(fclose(input_file_handle_d1))
{
fprintf(stderr,"Errore interno: 005\n");
return 1;
}

end_buffer_file=buffer_file_d1+input_file_size_d1;

if(memcmp(magic[0],buffer_file_d1,strlen(magic[0])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (001)\n");
return 1;
}

buffer_file_d1+=strlen(magic[0]);
if((ruote=Get_Number(&buffer_file_d1))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (002)\n");
return 1;
}
buffer_file_d1+=2;

if((rt_name=malloc(ruote*sizeof(int)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (002 : %d Byte)\n",ruote*sizeof(int));
return 1;
}
else
printf("002 - Allocati: %d Byte\n",ruote*sizeof(int));

if(memcmp(magic[1],buffer_file_d1,strlen(magic[1])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (003)\n");
return 1;
}

buffer_file_d1+=strlen(magic[1]);
if((valori=Get_Number(&buffer_file_d1))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (004)\n");
return 1;
}
buffer_file_d1+=2;

buffer_file_tmp=buffer_file_d1;


// Allocare qui
// valori, E_ZN

numcomb = NumCombinations(valori, E_ZN);

//table_disp = (int**)calloc(pArray->side + 1, sizeof(int*));
table_disp = (int**)malloc(numcomb*sizeof(int*));
if ( table_disp != NULL )
{
for ( x = 0; x < numcomb; x++ )
{
table_disp[x] = (int*)malloc(E_ZN*sizeof(int));
if ( table_disp[x] == NULL )
{
printf("Memoria insufficiente.\n");
return 1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return 1;
}

combinations(table_disp, v, 1, valori, 1, E_ZN);

while (buffer_file_tmp<end_buffer_file)
{
if(*buffer_file_tmp==0x0D)
{
n_estr++;
buffer_file_tmp+=2;
}
else
buffer_file_tmp++;
}

if(n_estr%ruote)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (005)\n");
return 1;
}
else
{
if((st_arry=malloc(n_estr*(DATA_LEN+valori)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (003 : %d Byte)\n",n_estr*(DATA_LEN+valori));
return 1;
}
else
printf("003 - Allocati: %d Byte\n",n_estr*(DATA_LEN+valori));
n_estr/=ruote;
}

for(disp_t=valori,i=valori-1;i>(valori-E_ZN);i--)
disp_t*=i;
for(i=2;i<=E_ZN;i++)
disp_t/=i;

if((l_arry=malloc(disp_t*n_estr*ruote*sizeof(int)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (004 : %d Byte)\n",disp_t*n_estr*ruote*(sizeof(int)<<1));
return 1;
}
else
printf("004 - Allocati: %d Byte\n",disp_t*n_estr*ruote*sizeof(int));

l_arry_base=l_arry;

for(disp=1,i=MAX_N;i>(MAX_N-E_ZN);i--)
disp*=i;
for(i=2;i<=E_ZN;i++)
disp/=i;

if((e_arry=calloc(disp*sizeof(int),1))==NULL)
{
fprintf(stderr,"Memoria insufficiente (005 : %d Byte)\n",disp*sizeof(int));
return 1;
}
else
printf("005 - Allocati: %d Byte\n",disp*sizeof(int));

for(st_arry_tmp=st_arry,sp=i=0;i<n_estr;i++)
{
for(j=0;j<ruote;j++)
{
st_arry[0]=Get_Number(&buffer_file_d1);
st_arry[1]=Get_Number(&buffer_file_d1);
st_arry[2]=Get_Number(&buffer_file_d1);

buffer_file_d1++;
if(sp==0)
{
buffer_file_tmp=buffer_file_d1;
while (*buffer_file_tmp++!=' ');
rt_name_size=buffer_file_tmp-buffer_file_d1;
*(buffer_file_tmp-1)=0;
if((rt_name[j]=malloc(rt_name_size))==NULL)
{
fprintf(stderr,"Memoria insufficiente (006 : %d Byte)\n",rt_name_size);
return 1;
}
mem_name+=rt_name_size;
memcpy(rt_name[j],buffer_file_d1,rt_name_size);
buffer_file_d1+=rt_name_size;
}
else
while (*buffer_file_d1++!=' ');

for(k=0;k<valori;k++)
st_arry[DATA_LEN+k]=Get_Number(&buffer_file_d1);

do
{
l=0;
for(k=0;k<(valori-1);k++)
{
if(st_arry[DATA_LEN+k]>st_arry[DATA_LEN+k+1])
{
l=st_arry[DATA_LEN+k];
st_arry[DATA_LEN+k]=st_arry[DATA_LEN+k+1];
st_arry[DATA_LEN+k+1]=l;
}
}
} while (l);

for(k=0;k<disp_t;k++)
{
for(m=k1[0][st_arry[DATA_LEN+table_disp[k][0]]-1],l=1;l<E_ZN;l++)
m+=k1[l][st_arry[DATA_LEN+table_disp[k][l]]-1];

l_arry[0]=e_arry[m];
e_arry[m]=(int)l_arry++;
}

st_arry+=DATA_LEN+valori;
}
if(sp==0)
{
printf("006 - Allocati: %d Byte\n",mem_name);
sp=1;
}
}

st_arry=st_arry_tmp;

buffer_file_d1=end_buffer_file-input_file_size_d1;

free(buffer_file_d1);
printf("007 - Deallocati: %d Byte\n",input_file_size_d1);

clk[1]=clock();

if((input_file_handle_d2=fopen(INPUT_FILE_NAME_D2,"rb"))==NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME_D2 "\n");
return 1;
}

if(fseek(input_file_handle_d2,0L,SEEK_END))
{
fprintf(stderr,"Errore interno: 006\n");
return 1;
}

if((input_file_size_d2=ftell(input_file_handle_d2))==-1)
{
fprintf(stderr,"Errore interno: 007\n");
return 1;
}

if(fseek(input_file_handle_d2,0L,SEEK_SET))
{
fprintf(stderr,"Errore interno: 008\n");
return 1;
}

if((buffer_file_d2=malloc(input_file_size_d2))==NULL)
{
fprintf(stderr,"Memoria insufficiente (007 : %d Byte)\n",input_file_size_d2);
return 1;
}
else
printf("008 - Allocati: %d Byte\n",input_file_size_d2);

if(fread(buffer_file_d2,input_file_size_d2,1,input_file_handle_d2)==0)
{
fprintf(stderr,"Errore interno: 009\n");
return 1;
}

if(fclose(input_file_handle_d2))
{
fprintf(stderr,"Errore interno: 010\n");
return 1;
}

if((output_buffer=malloc(OUTPUT_BUFFER_LEN))==NULL)
{
fprintf(stderr,"Memoria insufficiente (008 : %d Byte)\n",input_file_size_d2);
return 1;
}
else
printf("009 - Allocati: %d Byte\n\n",OUTPUT_BUFFER_LEN);

output_buffer_tmp=output_buffer;

if(memcmp(magic[2],buffer_file_d2,strlen(magic[2])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D2 " non corretto - (001)\n");
return 1;
}

buffer_file_d2+=strlen(magic[2]);

if((find=Get_Number(&buffer_file_d2))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D2 " non corretto - (002)\n");
return 1;
}

for(i=0;i<find;i++)
{
for(j=0;j<MAX_N;j++)
{
f_elem[j]=Get_Number(&buffer_file_d2);
if(*buffer_file_d2!=',')
break;
}

do
{
l=0;
for(k=0;k<(E_ZN-1);k++)
{
if(f_elem[k]>f_elem[k+1])
{
l=f_elem[k];
f_elem[k]=f_elem[k+1];
f_elem[k+1]=l;
l=1;
}
}
} while (l);

for(e_find=0,m=k1[0][f_elem[0]-1],l=1;l<E_ZN;l++)
m+=k1[l][f_elem[l]-1];

l_arry=(int *)e_arry[m];
if(l_arry)
{
do
{
element=(l_arry-l_arry_base)/disp_t;

for(k=DATA_LEN+element*(DATA_LEN+valori),l=E_ZN;l<=j;l++)
{
for(n=m=0;m<valori;m++)
{
if(st_arry[m+k]==f_elem[l])
{
n=1;
break;
}
}
if(n==0)
break;
}

if(l==(j+1))
{
if(e_find==0)
{
*((int *)output_buffer)=0x00202D2D;
output_buffer+=3;
for(k=0;k<=j;k++)
{
a=f_elem[k];
if(a<10)
*output_buffer++=a+'0';
else
{
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
}

if(k!=j)
*output_buffer++=',';
}
*((int *)output_buffer)=0x0A2D2D20;
output_buffer+=4;
e_find=1;
}

a=st_arry[element*(DATA_LEN+valori)];
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
*output_buffer++='/';

a=st_arry[element*(DATA_LEN+valori)+1];
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
*output_buffer++='/';

a=(int)(st_arry[element*(DATA_LEN+valori)+2]+Y_ZERO)/100;
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
a=(int)(st_arry[element*(DATA_LEN+valori)+2]+Y_ZERO)%100;
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';

*output_buffer++=' ';

k=0;
do
{
*output_buffer++=*(rt_name[element%ruote]+k++);
} while (*(rt_name[element%ruote]+k));

*output_buffer++=' ';

for(k=0;k<valori;k++)
{
a=st_arry[element*(DATA_LEN+valori)+DATA_LEN+k];
if(a<10)
*output_buffer++=a+'0';
else
{
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
}

if(k!=(valori-1))
*output_buffer++=',';
}
*output_buffer++=0x0A;
sol++;
}

l_arry=(int *)*l_arry;
} while (l_arry);
}
}

*output_buffer=0x00;
puts(output_buffer_tmp);

for(x = 0; x < numcomb; x++)
free(table_disp[x]);
free(table_disp);

clk[2]=clock();

printf("\n*** Soluzioni trovate: %d\n",sol);
printf("\n*** Tempo per caricamento dati e creazione strutture: %7.3f secondi\n",(double)(clk[1]-clk[0])/CLK_TCK);
printf("\n*** Tempo per ricerca della soluzione difficile: %7.3f secondi\n",(double)(clk[2]-clk[1])/CLK_TCK);
printf("\n*** Tempo totale per l'intera elaborazione: %7.3f secondi\n",(double)(clk[2]-clk[0])/CLK_TCK);

return 0;
}

int Get_Number(p_buffer)
char **p_buffer;

{
int rnum=0;
char *buffer;

buffer=*p_buffer;

for(;;buffer++)
{
if((*buffer>='0')&&(*buffer<='9'))
{
do
{
rnum=rnum*10+*buffer-'0';
buffer++;
} while ((*buffer>='0')&&(*buffer<='9'));
break;
}
}

*p_buffer=buffer;

return(rnum);
}

void combinations (int **pTable, int v[], int start, int n, int k, int maxk)
{
static int x = 0;
int i;

/* k here counts through positions in the maxk-element v.
* if k > maxk, then the v is complete and we can use it.
*/
if (k > maxk)
{
/* insert code here to use combinations as you please */
for (i = 1; i <= maxk; i++)
{
//printf ("%i ", v[i]);
pTable[x][i] = v[i] - 1;
}
//printf ("\n");
x++;
return;
}

/* for this k'th element of the v, try all start..n
* elements in that position
*/
for (i = start; i <= n; i++)
{
v[k] = i;
/* recursively generate combinations of integers
* from i+1..n
*/
combinations (pTable, v, i+1, n, k+1, maxk);
}
}

int NumCombinations(int n, int k)
{
int x, y, z = 0;

y = n;
for ( x = n - 1; x > n - k; x-- )
y *= x;

z = k;
for ( x = k-1; x >= 2; x-- )
z *= x;

return y/z;
}



Le modifiche che ho apportato sono queste:

1) all'inizio della funzione main:


int ** table_disp = NULL;
int numcomb;
int x;
int v[1000];
...


un po più giù:


...
// Allocare qui
// valori, E_ZN

numcomb = NumCombinations(valori, E_ZN);

table_disp = (int**)malloc(numcomb*sizeof(int*));
if ( table_disp != NULL )
{
for ( x = 0; x < numcomb; x++ )
{
table_disp[x] = (int*)malloc(E_ZN*sizeof(int));
if ( table_disp[x] == NULL )
{
printf("Memoria insufficiente.\n");
return 1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return 1;
}

combinations(table_disp, v, 1, valori, 1, E_ZN);
...

[Vincenzo1968]

praticamente la funzione combinations imposta gli indici a partire da 1:

1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 4 5
1 3 4 6
1 3 5 6
1 4 5 6
2 3 4 5
2 3 4 6
2 3 5 6
2 4 5 6
3 4 5 6

Ecco perchè il programma va in crash. Però non capisco perchè gli indici non partano da zero visto che sottraggo 1:


...
pTable[x][i] = v[i] - 1;
...

[Vincenzo1968]

Ci sono riuscito:


#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define N_CLK 10
#define N_MAGIC 3
#define MAX_N_DIM 10
#define MAX_N 90
#define E_ZN 4
#define DATA_LEN 3
#define Y_ZERO 1792
#define OUTPUT_BUFFER_LEN 10000000

//#define INPUT_FILE_NAME_D1 "LOTTO.D1"
//#define INPUT_FILE_NAME_D2 "LOTTO.D2"

//#define INPUT_FILE_NAME_D1 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrossoNew\\LOTTO.D1"
//#define INPUT_FILE_NAME_D2 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrossoNew\\LOTTO.D2"

#define INPUT_FILE_NAME_D1 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoEnorme\\LOTTO.D1"
#define INPUT_FILE_NAME_D2 "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoEnorme\\LOTTO.D2"

/*
#if E_ZN==2
#define TABLE_C table_disp[15][E_ZN]={{0,1},{0,2},{0,3},{0,4},{0,5},{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}}
#elif E_ZN==3
#define TABLE_C table_disp[20][E_ZN]={{0,1,2},{0,1,3},{0,1,4},{0,1,5},{0,2,3},{0,2,4},{0,2,5},{0,3,4},{0,3,5},{0,4,5},{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}}
#elif E_ZN==4
#define TABLE_C table_disp[15][E_ZN]={{0,1,2,3},{0,1,2,4},{0,1,2,5},{0,1,3,4},{0,1,3,5},{0,1,4,5},{0,2,3,4},{0,2,3,5},{0,2,4,5},{0,3,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}
#endif
*/

int Get_Number(char **);
void combinations(int **pTable, int v[], int start, int n, int k, int maxk);
int NumCombinations(int n, int k);

int main()
{
int *pTable = NULL;
int **table_disp = NULL;
int numcomb;
int x, y, z;
int v[1000];

clock_t clk[N_CLK];
char a,*buffer_file_d1,*buffer_file_d2,*buffer_file_tmp,*end_buffer_file,*output_buffer,*output_buffer_tmp,*st_arry,*st_arry_tmp,**rt_name,*magic[N_MAGIC]={"Ruote","Valori","Find"},f_elem[MAX_N];
FILE *input_file_handle_d1,*input_file_handle_d2;
int i,j,k,l,sol=0,m,n,m1,n1,mem_name=0,e_find,find,element,sp,rt_name_size,disp,disp_t,n_estr=0,input_file_size_d1,input_file_size_d2,ruote,valori,*e_arry,*l_arry,*l_arry_base,k1[E_ZN][MAX_N];

clk[0]=clock();

for(m1=1,n1=E_ZN;n1>=1;n1--,m1++)
{
for(l=0,k1[E_ZN-n1][m1-1]=0,i=m1;i<=(MAX_N-n1);i++)
{
for(k=1,j=1;j<n1;j++)
k*=(MAX_N-j-i);
for(j=1;j<n1;j++)
k/=j;
l+=k;
k1[E_ZN-n1][i]=l;
}
}

if((input_file_handle_d1=fopen(INPUT_FILE_NAME_D1,"rb"))==NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME_D1 "\n");
return 1;
}

if(fseek(input_file_handle_d1,0L,SEEK_END))
{
fprintf(stderr,"Errore interno: 001\n");
return 1;
}

if((input_file_size_d1=ftell(input_file_handle_d1))==-1)
{
fprintf(stderr,"Errore interno: 002\n");
return 1;
}

if(fseek(input_file_handle_d1,0L,SEEK_SET))
{
fprintf(stderr,"Errore interno: 003\n");
return 1;
}

if((buffer_file_d1=malloc(input_file_size_d1))==NULL)
{
fprintf(stderr,"Memoria insufficiente (001 : %d Byte)\n",input_file_size_d1);
return 1;
}
else
printf("001 - Allocati: %d Byte\n",input_file_size_d1);

if(fread(buffer_file_d1,input_file_size_d1,1,input_file_handle_d1)==0)
{
fprintf(stderr,"Errore interno: 004\n");
return 1;
}

if(fclose(input_file_handle_d1))
{
fprintf(stderr,"Errore interno: 005\n");
return 1;
}

end_buffer_file=buffer_file_d1+input_file_size_d1;

if(memcmp(magic[0],buffer_file_d1,strlen(magic[0])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (001)\n");
return 1;
}

buffer_file_d1+=strlen(magic[0]);
if((ruote=Get_Number(&buffer_file_d1))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (002)\n");
return 1;
}
buffer_file_d1+=2;

if((rt_name=malloc(ruote*sizeof(int)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (002 : %d Byte)\n",ruote*sizeof(int));
return 1;
}
else
printf("002 - Allocati: %d Byte\n",ruote*sizeof(int));

if(memcmp(magic[1],buffer_file_d1,strlen(magic[1])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (003)\n");
return 1;
}

buffer_file_d1+=strlen(magic[1]);
if((valori=Get_Number(&buffer_file_d1))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (004)\n");
return 1;
}
buffer_file_d1+=2;

buffer_file_tmp=buffer_file_d1;


// Allocare qui
// valori, E_ZN

numcomb = NumCombinations(valori, E_ZN);

pTable = (int*)malloc(numcomb*E_ZN*sizeof(int));
if ( !pTable )
{
printf("Memoria insufficiente.\n");
return 1;
}

table_disp = (int**)malloc(numcomb*sizeof(int*));
if ( table_disp != NULL )
{
for ( x = 0; x < numcomb; x++ )
{
table_disp[x] = (int*)malloc(E_ZN*sizeof(int));
if ( table_disp[x] == NULL )
{
printf("Memoria insufficiente.\n");
return 1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return 1;
}

combinations(&pTable, v, 1, valori, 1, E_ZN);

z = 0;
for(x = 0; x < numcomb; x++)
{
for(y = 0; y < E_ZN; y++)
{
table_disp[x][y] = pTable[z++];
}
}

free(pTable);

while (buffer_file_tmp<end_buffer_file)
{
if(*buffer_file_tmp==0x0D)
{
n_estr++;
buffer_file_tmp+=2;
}
else
buffer_file_tmp++;
}

if(n_estr%ruote)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D1 " non corretto - (005)\n");
return 1;
}
else
{
if((st_arry=malloc(n_estr*(DATA_LEN+valori)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (003 : %d Byte)\n",n_estr*(DATA_LEN+valori));
return 1;
}
else
printf("003 - Allocati: %d Byte\n",n_estr*(DATA_LEN+valori));
n_estr/=ruote;
}

for(disp_t=valori,i=valori-1;i>(valori-E_ZN);i--)
disp_t*=i;
for(i=2;i<=E_ZN;i++)
disp_t/=i;

if((l_arry=malloc(disp_t*n_estr*ruote*sizeof(int)))==NULL)
{
fprintf(stderr,"Memoria insufficiente (004 : %d Byte)\n",disp_t*n_estr*ruote*(sizeof(int)<<1));
return 1;
}
else
printf("004 - Allocati: %d Byte\n",disp_t*n_estr*ruote*sizeof(int));

l_arry_base=l_arry;

for(disp=1,i=MAX_N;i>(MAX_N-E_ZN);i--)
disp*=i;
for(i=2;i<=E_ZN;i++)
disp/=i;

if((e_arry=calloc(disp*sizeof(int),1))==NULL)
{
fprintf(stderr,"Memoria insufficiente (005 : %d Byte)\n",disp*sizeof(int));
return 1;
}
else
printf("005 - Allocati: %d Byte\n",disp*sizeof(int));

for(st_arry_tmp=st_arry,sp=i=0;i<n_estr;i++)
{
for(j=0;j<ruote;j++)
{
st_arry[0]=Get_Number(&buffer_file_d1);
st_arry[1]=Get_Number(&buffer_file_d1);
st_arry[2]=Get_Number(&buffer_file_d1);

buffer_file_d1++;
if(sp==0)
{
buffer_file_tmp=buffer_file_d1;
while (*buffer_file_tmp++!=' ');
rt_name_size=buffer_file_tmp-buffer_file_d1;
*(buffer_file_tmp-1)=0;
if((rt_name[j]=malloc(rt_name_size))==NULL)
{
fprintf(stderr,"Memoria insufficiente (006 : %d Byte)\n",rt_name_size);
return 1;
}
mem_name+=rt_name_size;
memcpy(rt_name[j],buffer_file_d1,rt_name_size);
buffer_file_d1+=rt_name_size;
}
else
while (*buffer_file_d1++!=' ');

for(k=0;k<valori;k++)
st_arry[DATA_LEN+k]=Get_Number(&buffer_file_d1);

do
{
l=0;
for(k=0;k<(valori-1);k++)
{
if(st_arry[DATA_LEN+k]>st_arry[DATA_LEN+k+1])
{
l=st_arry[DATA_LEN+k];
st_arry[DATA_LEN+k]=st_arry[DATA_LEN+k+1];
st_arry[DATA_LEN+k+1]=l;
}
}
} while (l);

for(k=0;k<disp_t;k++)
{
for(m=k1[0][st_arry[DATA_LEN+table_disp[k][0]]-1],l=1;l<E_ZN;l++)
m+=k1[l][st_arry[DATA_LEN+table_disp[k][l]]-1];

l_arry[0]=e_arry[m];
e_arry[m]=(int)l_arry++;
}

st_arry+=DATA_LEN+valori;
}
if(sp==0)
{
printf("006 - Allocati: %d Byte\n",mem_name);
sp=1;
}
}

st_arry=st_arry_tmp;

buffer_file_d1=end_buffer_file-input_file_size_d1;

free(buffer_file_d1);
printf("007 - Deallocati: %d Byte\n",input_file_size_d1);

clk[1]=clock();

if((input_file_handle_d2=fopen(INPUT_FILE_NAME_D2,"rb"))==NULL)
{
fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME_D2 "\n");
return 1;
}

if(fseek(input_file_handle_d2,0L,SEEK_END))
{
fprintf(stderr,"Errore interno: 006\n");
return 1;
}

if((input_file_size_d2=ftell(input_file_handle_d2))==-1)
{
fprintf(stderr,"Errore interno: 007\n");
return 1;
}

if(fseek(input_file_handle_d2,0L,SEEK_SET))
{
fprintf(stderr,"Errore interno: 008\n");
return 1;
}

if((buffer_file_d2=malloc(input_file_size_d2))==NULL)
{
fprintf(stderr,"Memoria insufficiente (007 : %d Byte)\n",input_file_size_d2);
return 1;
}
else
printf("008 - Allocati: %d Byte\n",input_file_size_d2);

if(fread(buffer_file_d2,input_file_size_d2,1,input_file_handle_d2)==0)
{
fprintf(stderr,"Errore interno: 009\n");
return 1;
}

if(fclose(input_file_handle_d2))
{
fprintf(stderr,"Errore interno: 010\n");
return 1;
}

if((output_buffer=malloc(OUTPUT_BUFFER_LEN))==NULL)
{
fprintf(stderr,"Memoria insufficiente (008 : %d Byte)\n",input_file_size_d2);
return 1;
}
else
printf("009 - Allocati: %d Byte\n\n",OUTPUT_BUFFER_LEN);

output_buffer_tmp=output_buffer;

if(memcmp(magic[2],buffer_file_d2,strlen(magic[2])))
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D2 " non corretto - (001)\n");
return 1;
}

buffer_file_d2+=strlen(magic[2]);

if((find=Get_Number(&buffer_file_d2))==0)
{
fprintf(stderr,"Formato del file " INPUT_FILE_NAME_D2 " non corretto - (002)\n");
return 1;
}

for(i=0;i<find;i++)
{
for(j=0;j<MAX_N;j++)
{
f_elem[j]=Get_Number(&buffer_file_d2);
if(*buffer_file_d2!=',')
break;
}

do
{
l=0;
for(k=0;k<(E_ZN-1);k++)
{
if(f_elem[k]>f_elem[k+1])
{
l=f_elem[k];
f_elem[k]=f_elem[k+1];
f_elem[k+1]=l;
l=1;
}
}
} while (l);

for(e_find=0,m=k1[0][f_elem[0]-1],l=1;l<E_ZN;l++)
m+=k1[l][f_elem[l]-1];

l_arry=(int *)e_arry[m];
if(l_arry)
{
do
{
element=(l_arry-l_arry_base)/disp_t;

for(k=DATA_LEN+element*(DATA_LEN+valori),l=E_ZN;l<=j;l++)
{
for(n=m=0;m<valori;m++)
{
if(st_arry[m+k]==f_elem[l])
{
n=1;
break;
}
}
if(n==0)
break;
}

if(l==(j+1))
{
if(e_find==0)
{
*((int *)output_buffer)=0x00202D2D;
output_buffer+=3;
for(k=0;k<=j;k++)
{
a=f_elem[k];
if(a<10)
*output_buffer++=a+'0';
else
{
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
}

if(k!=j)
*output_buffer++=',';
}
*((int *)output_buffer)=0x0A2D2D20;
output_buffer+=4;
e_find=1;
}

a=st_arry[element*(DATA_LEN+valori)];
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
*output_buffer++='/';

a=st_arry[element*(DATA_LEN+valori)+1];
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
*output_buffer++='/';

a=(int)(st_arry[element*(DATA_LEN+valori)+2]+Y_ZERO)/100;
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
a=(int)(st_arry[element*(DATA_LEN+valori)+2]+Y_ZERO)%100;
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';

*output_buffer++=' ';

k=0;
do
{
*output_buffer++=*(rt_name[element%ruote]+k++);
} while (*(rt_name[element%ruote]+k));

*output_buffer++=' ';

for(k=0;k<valori;k++)
{
a=st_arry[element*(DATA_LEN+valori)+DATA_LEN+k];
if(a<10)
*output_buffer++=a+'0';
else
{
*output_buffer++=a/10+'0';
*output_buffer++=(a%10)+'0';
}

if(k!=(valori-1))
*output_buffer++=',';
}
*output_buffer++=0x0A;
sol++;
}

l_arry=(int *)*l_arry;
} while (l_arry);
}
}

*output_buffer=0x00;
puts(output_buffer_tmp);

for(x = 0; x < numcomb; x++)
free(table_disp[x]);
free(table_disp);

clk[2]=clock();

printf("\n*** Soluzioni trovate: %d\n",sol);
printf("\n*** Tempo per caricamento dati e creazione strutture: %7.3f secondi\n",(double)(clk[1]-clk[0])/CLK_TCK);
printf("\n*** Tempo per ricerca della soluzione difficile: %7.3f secondi\n",(double)(clk[2]-clk[1])/CLK_TCK);
printf("\n*** Tempo totale per l'intera elaborazione: %7.3f secondi\n",(double)(clk[2]-clk[0])/CLK_TCK);

return 0;
}

int Get_Number(p_buffer)
char **p_buffer;

{
int rnum=0;
char *buffer;

buffer=*p_buffer;

for(;;buffer++)
{
if((*buffer>='0')&&(*buffer<='9'))
{
do
{
rnum=rnum*10+*buffer-'0';
buffer++;
} while ((*buffer>='0')&&(*buffer<='9'));
break;
}
}

*p_buffer=buffer;

return(rnum);
}

void combinations(int **pTable, int v[], int start, int n, int k, int maxk)
{
static int x = 0;
int i;

/* k here counts through positions in the maxk-element v.
* if k > maxk, then the v is complete and we can use it.
*/
if (k > maxk)
{
/* insert code here to use combinations as you please */
for (i = 1; i <= maxk; i++)
{
(*pTable)[x++] = v[i] - 1;
//printf ("%i ", pTable[x][i]);
}
//printf ("\n");
return;
}

/* for this k'th element of the v, try all start..n
* elements in that position
*/
for (i = start; i <= n; i++)
{
v[k] = i;
/* recursively generate combinations of integers
* from i+1..n
*/
combinations(pTable, v, i+1, n, k+1, maxk);
}
}

int NumCombinations(int n, int k)
{
int x, y, z = 0;

y = n;
for ( x = n - 1; x > n - k; x-- )
y *= x;

z = k;
for ( x = k-1; x >= 2; x-- )
z *= x;

return y/z;
}


:yeah: :winner: :yeah:

[cionci]

Con questa versione dovrei sicuramente risparmiare molta memoria. Inoltre il tempo è sceso del 15% sul mio sistema.
Indicizzo per due numeri. Inizialmente indicizzavo tutte le possibili coppie di numeri indipendentemente dall'ordine per evitare di ordinare i numeri.
Poi ho provato ad ordinare e ad inserire nella tabella solo le coppie in cui il primo indice è minore del secondo.
Risultato: tempo IDENTICO :eek: Non l'avrei mai detto. Il tempo perso nell'ordinamento compensava quello dell'inserimento. Certo l'utilizzo della memoria scende vertiginosamente.
Ho anche precalcolato la tabella di inserimento invece di usare i due for, ed anche qui tempo praticamente identico.
Poi ho cominciato a sostituire il qsort della libreria standard con un sorting fatto durante il parsing della stringa.
E dopo ho realizzato che i numeri da ricercare non ho bisogno di ordinarli, mi basta prendere una qualsiasi coppia mettendo nel primo indice il numero più basso e nel secondo quello più alto.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

//#define DATAFILENAME "LottoDataDifficile.txt"
//#define SEARCHFILENAME "LottoFindDifficile.txt"

#define DATAFILENAME "/home/cionci/Scrivania/LOTTO/LOTTO.D1"
#define SEARCHFILENAME "/home/cionci/Scrivania/LOTTO/LOTTO.D2"


class MyBitSet
{
unsigned int bits[3];
public:
MyBitSet()
{
bits[0] = bits[1] = bits[2] = 0;
}

void set(unsigned int n)
{
bits[n >> 5] |= 1 << (n & 0x1F);
}

bool test(MyBitSet & other)
{
return ((other.bits[0] & bits[0]) == other.bits[0]) &&
((other.bits[1] & bits[1]) == other.bits[1]) &&
((other.bits[2] & bits[2]) == other.bits[2]);
}
};


class Drawing
{
MyBitSet bits;
string text;
int *v;

int findInsertPosition(int value, int items)
{
int insertPosition = 0;
while (v[insertPosition] < value && insertPosition < items)
{
++insertPosition;
}
for (int k = items - 1; k >= insertPosition; --k)
{
v[k + 1] = v[k];
}
return insertPosition;
}

void parseString(const string &numbers)
{
unsigned int i = 0;
int items = 0;
while (i < numbers.size())
{
if (numbers[i] >= '0' && numbers[i] <= '9')
{
int value = numbers[i] - '0';
if (numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
value = value * 10 + (numbers[i] - '0');
}

v[findInsertPosition(value, items)] = value;
bits.set(value);
++items;
}
++i;
}
}

public:
Drawing(int numberCount, const string &city, const string &date, const string &numbers)
{
text = date;
text.append(" ");
text.append(city);
text.append(" ");
text.append(numbers);

v = new int[numberCount];
parseString(numbers);
}

const string & toString()
{
return text;
}

bool isMatching(MyBitSet &toBeTested)
{
return bits.test(toBeTested);
}

int getNumber(int i)
{
return v[i];
}
};

const unsigned int Bits = 10;
const unsigned int DataSize = 1 << Bits;
const unsigned int IndexMask = DataSize - 1;

class MyList
{
struct DataElement
{
Drawing * data[DataSize];
DataElement * next;

DataElement(): next(NULL)
{
}
};

int insertCounter;
int size;
int readCounter;

DataElement * first;
DataElement * last;
DataElement * current;

public:
MyList(): insertCounter(0), size(DataSize), readCounter(0)
{
current = last = first = new DataElement();
}

void insert(Drawing * d)
{
if (insertCounter == size)
{
last -> next = new DataElement();
last = last->next;
size += DataSize;
}
last->data[insertCounter++ & IndexMask] = d;
}

Drawing * getNext()
{
Drawing * tmp = current->data[readCounter++ & IndexMask];
if (!(readCounter & IndexMask))
{
current = current->next;
}
return tmp;
}

bool hasNext()
{
return readCounter < insertCounter;
}

void reset()
{
readCounter = 0;
current = first;
}
};


class Database
{
MyList drawings[91][91];
int numberCount;
int **couple;
int coupleSize;


void parseString(const string &numbers, int * v, MyBitSet & bits)
{
unsigned int i = 0;
int items = 0;
while (i < numbers.size())
{
if (numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if (numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}

v[items++] = item;
bits.set(item);
}
++i;
}
}

public:
Database(int numberCount): numberCount(numberCount)
{
coupleSize = (numberCount * (numberCount - 1)) / 2;
couple = new int * [coupleSize];

int counter = 0;
for (int i = 0; i < numberCount - 1; ++i)
{
for (int j = i + 1; j < numberCount; ++j, ++counter)
{
couple[counter] = new int [2];
couple[counter][0] = i;
couple[counter][1] = j;
}
}
}

void insertDrawing(Drawing * drawing)
{
for (int i = 0; i < coupleSize; ++i)
{
drawings[drawing->getNumber(couple[i][0])][drawing->getNumber(couple[i][1])].insert(drawing);
}
}

void printDrawings(const string &numbers)
{
MyBitSet bits;
int v[numberCount];
parseString(numbers, v, bits);


MyList &l = (v[0] < v[1]) ? drawings[v[0]][v[1]] : drawings[v[1]][v[0]];

bool print = false;

while (l.hasNext())
{
Drawing * d = l.getNext();

if (d->isMatching(bits))
{
if (!print)
{
print = true;
cout << "-- " << numbers << endl;
}

cout << d->toString() << endl;
}
}
l.reset();
}
};


int main()
{
ifstream f(DATAFILENAME);

string date, city, numbers;

if (f.fail())
{
cout << "Errore apertura file dati" << endl;
return 1;
}

getline(f, numbers);
getline(f, numbers, ' ');

int numberCount;
f >> numberCount;

if (f.fail())
{
cout << "Errore parametri file dati" << endl;
return 1;
}

Database db(numberCount);

getline(f, numbers);

while (1)
{
getline(f, date, ' ');
if (f.eof() || f.fail()) break;
getline(f, city, ' ');
getline(f, numbers);
Drawing * d = new Drawing(numberCount, city, date, numbers);
db.insertDrawing(d);
}

f.close();
f.clear();
f.open(SEARCHFILENAME);

if (f.fail())
{
cout << "Errore apertura file di ricerca" << endl;
return 1;
}

int count;
getline(f, date, ' ');
f >> count;

if (f.fail())
{
cout << "Errore parametri file di ricerca" << endl;
return 1;
}

getline(f, numbers);
for (int i = 0; i < count; ++i)
{
getline(f, numbers);

db.printDrawings(numbers);
}

return 0;
}

[rеpne scasb]

■

[rеpne scasb]

■

[dierre]

@rеpne scasb: con gcc devo usare qualche opzione particolare?

Cmq ho dovuto modificare mem.h in memory.h altrimenti non compilava.

al momento col file .D1 da 0.302

[gugoXX]

...
Grazie per la spiegazione.

[cionci]

@cionci - Ci vorrebbe un volenteroso che possa misurare tempi e rapporti di nuovo. Ti ci stai proprio applicando in modo lodevole! :)
Per carità, il tuo è irraggiungibile :)

[rеpne scasb]

■

[rеpne scasb]

■

[cionci]

@rеpne scasb: con gcc devo usare qualche opzione particolare?
Dagli un -O2

[Vincenzo1968]

Cionci,

mi dà questo errore:

expected constant expression

la linea di codice interessata è questa:


void printDrawings(const string &numbers)
{
MyBitSet bits;
int v[numberCount]; <----------- qui l'errore
parseString(numbers, v, bits);
...


Il compilatore giustamente si lamenta del fatto che utilizzo una variabile per dimensionare l'array.

[cionci]

Il gcc non crea problemi, anche perché bene o male il valore è recuperabile anche in fase di costruzione dello stack delle variabili locali.
in effetti non avevo mai usato una cosa del genere, ci sta che sia una "licenza" che si è concesso il g++, non so cosa dica lo standard in proposito.

Comunque sposta v all'interno delle variabili private della classe così:

int *v;

Poi come ultima istruzione del costruttore aggiungi:

v = new int[numberCount];

[Vincenzo1968]

Questi sono i tempi, sui file grossi(compilatore Visual Studio 2008):

http://www.guidealgoritmi.it/images/ImgForums/Contest07TempiRepneCionci.jpg

La mia macchina:


AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3

[cionci]

Ma il mio tempo è aumentato ?

[Vincenzo1968]

Ma il mio tempo è aumentato ?

Ehm,

che vuoi che ti dica? :confused:
Stasera faccio qualche altra prova e la posto.
Questo è il tuo codice modificato come mi hai detto:


#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

//#define DATAFILENAME "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrossoNew\\LOTTO.D1"
//#define SEARCHFILENAME "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoGrossoNew\\LOTTO.D2"

#define DATAFILENAME "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoEnorme\\LOTTO.D1"
#define SEARCHFILENAME "C:\\Scaricamenti\\Temp\\Gugo\\Contest 07 - Il Lotto\\LottoEnorme\\LOTTO.D2"


class MyBitSet
{
unsigned int bits[3];
public:
MyBitSet()
{
bits[0] = bits[1] = bits[2] = 0;
}

void set(unsigned int n)
{
bits[n >> 5] |= 1 << (n & 0x1F);
}

bool test(MyBitSet & other)
{
return ((other.bits[0] & bits[0]) == other.bits[0]) &&
((other.bits[1] & bits[1]) == other.bits[1]) &&
((other.bits[2] & bits[2]) == other.bits[2]);
}
};


class Drawing
{
MyBitSet bits;
string text;
int *v;

int findInsertPosition(int value, int items)
{
int insertPosition = 0;
while (v[insertPosition] < value && insertPosition < items)
{
++insertPosition;
}
for (int k = items - 1; k >= insertPosition; --k)
{
v[k + 1] = v[k];
}
return insertPosition;
}

void parseString(const string &numbers)
{
unsigned int i = 0;
int items = 0;
while (i < numbers.size())
{
if (numbers[i] >= '0' && numbers[i] <= '9')
{
int value = numbers[i] - '0';
if (numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
value = value * 10 + (numbers[i] - '0');
}

v[findInsertPosition(value, items)] = value;
bits.set(value);
++items;
}
++i;
}
}

public:
Drawing(int numberCount, const string &city, const string &date, const string &numbers)
{
text = date;
text.append(" ");
text.append(city);
text.append(" ");
text.append(numbers);

v = new int[numberCount];
parseString(numbers);
}

const string & toString()
{
return text;
}

bool isMatching(MyBitSet &toBeTested)
{
return bits.test(toBeTested);
}

int getNumber(int i)
{
return v[i];
}
};

const unsigned int Bits = 10;
const unsigned int DataSize = 1 << Bits;
const unsigned int IndexMask = DataSize - 1;

class MyList
{
struct DataElement
{
Drawing * data[DataSize];
DataElement * next;

DataElement(): next(NULL)
{
}
};

int insertCounter;
int size;
int readCounter;

DataElement * first;
DataElement * last;
DataElement * current;

public:
MyList(): insertCounter(0), size(DataSize), readCounter(0)
{
current = last = first = new DataElement();
}

void insert(Drawing * d)
{
if (insertCounter == size)
{
last -> next = new DataElement();
last = last->next;
size += DataSize;
}
last->data[insertCounter++ & IndexMask] = d;
}

Drawing * getNext()
{
Drawing * tmp = current->data[readCounter++ & IndexMask];
if (!(readCounter & IndexMask))
{
current = current->next;
}
return tmp;
}

bool hasNext()
{
return readCounter < insertCounter;
}

void reset()
{
readCounter = 0;
current = first;
}
};


class Database
{
MyList drawings[91][91];
int numberCount;
int **couple;
int coupleSize;
int *v;

void parseString(const string &numbers, int * v, MyBitSet & bits)
{
unsigned int i = 0;
int items = 0;
while (i < numbers.size())
{
if (numbers[i] >= '0' && numbers[i] <= '9')
{
int item = numbers[i] - '0';
if (numbers[i+1] >= '0' && numbers[i+1] <= '9')
{
++i;
item = item * 10 + (numbers[i] - '0');
}

v[items++] = item;
bits.set(item);
}
++i;
}
}

public:
Database(int numberCount): numberCount(numberCount)
{
coupleSize = (numberCount * (numberCount - 1)) / 2;
couple = new int * [coupleSize];

int counter = 0;
for (int i = 0; i < numberCount - 1; ++i)
{
for (int j = i + 1; j < numberCount; ++j, ++counter)
{
couple[counter] = new int [2];
couple[counter][0] = i;
couple[counter][1] = j;
}
}

v = new int[numberCount];
}

void insertDrawing(Drawing * drawing)
{
for (int i = 0; i < coupleSize; ++i)
{
drawings[drawing->getNumber(couple[i][0])][drawing->getNumber(couple[i][1])].insert(drawing);
}
}

void printDrawings(const string &numbers)
{
MyBitSet bits;
//int v[numberCount];
parseString(numbers, v, bits);


MyList &l = (v[0] < v[1]) ? drawings[v[0]][v[1]] : drawings[v[1]][v[0]];

bool print = false;

while (l.hasNext())
{
Drawing * d = l.getNext();

if (d->isMatching(bits))
{
if (!print)
{
print = true;
cout << "-- " << numbers << endl;
}

cout << d->toString() << endl;
}
}
l.reset();
}
};


int main()
{
ifstream f(DATAFILENAME);

string date, city, numbers;

if (f.fail())
{
cout << "Errore apertura file dati" << endl;
return 1;
}

getline(f, numbers);
getline(f, numbers, ' ');

int numberCount;
f >> numberCount;

if (f.fail())
{
cout << "Errore parametri file dati" << endl;
return 1;
}

Database db(numberCount);

getline(f, numbers);

while (1)
{
getline(f, date, ' ');
if (f.eof() || f.fail()) break;
getline(f, city, ' ');
getline(f, numbers);
Drawing * d = new Drawing(numberCount, city, date, numbers);
db.insertDrawing(d);
}

f.close();
f.clear();
f.open(SEARCHFILENAME);

if (f.fail())
{
cout << "Errore apertura file di ricerca" << endl;
return 1;
}

int count;
getline(f, date, ' ');
f >> count;

if (f.fail())
{
cout << "Errore parametri file di ricerca" << endl;
return 1;
}

getline(f, numbers);
for (int i = 0; i < count; ++i)
{
getline(f, numbers);

db.printDrawings(numbers);
}

return 0;
}

[cionci]

Ehm,

che vuoi che ti dica? :confused:
Ehm...se è aumentato o meno :asd:
Non mi ricordo l'ultimo tempo :D

[Vincenzo1968]

Ehm...se è aumentato o meno :asd:
Non mi ricordo l'ultimo tempo :D

boh! :confused:
Ogni volta che postate una nuova versione la sovrascrivo a quella vecchia. Non conservo le versioni precedenti. Dovresti vedere a ritroso tra i post, qual è l'ultima classifica che ho postato(la classifica, dico, sulla mia macchina, non su quella di Elche). ;)

[cionci]

E' questa per caso ?
http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica10.jpg

[Vincenzo1968]

E' questa per caso ?
http://www.guidealgoritmi.it/images/ImgForums/Contest07Classifica10.jpg

Mi pare di si. Dunque il tempo è diminuito di molto ;)

[malocchio]

Ho letto con interesse l'intero 3d... purtroppo quello che mi frega è che non conosco i puntatori e le strutture (odio il C) e così ho capito poco più di una mazza. :muro: Eppure il calcolo combinatorio mi riesce abbastanza



Per il prossimo contest ci vorrebbe un repository (SVN, CVS ecc.) . Così potete salvare tutte le versioni e le classifiche!

Se ho tempo e ispirazione scrivo una soluzione sempliciotta in Java.

Penso che dovrò stamparmi la spiegazione di Repne. Magari all'ITIS mi danno un credito formativo.

[^TiGeRShArK^]

Ho letto con interesse l'intero 3d... purtroppo quello che mi frega è che non conosco i puntatori e le strutture (odio il C) e così ho capito poco più di una mazza. :muro: Eppure il calcolo combinatorio mi riesce abbastanza



Per il prossimo contest ci vorrebbe un repository (SVN, CVS ecc.) . Così potete salvare tutte le versioni e le classifiche!

Se ho tempo e ispirazione scrivo una soluzione sempliciotta in Java.

Penso che dovrò stamparmi la spiegazione di Repne. Magari all'ITIS mi danno un credito formativo.
si.. sempre se i prof sono in grado di capire la spiegazione :asd:
..scherzi a parte..di solito i prof di informatica in italia non hanno una grande fama..
poi magari da te fanno eccezione, e non posso che esserne contento :p

[malocchio]

Scusate, ma nel programma bisogna controllare la correttezza dell'input oppure si dà per corretto??

Perché a controllare la non ripetizione degli estratti ci vuole un bel po' di calcoletti.

[rеpne scasb]

■

[dierre]

Dal 1° post del contest:

"I valori estratti per ciascuna ruota/estrazione saranno unici (estrazione senza reinserimento, come nel lotto vero)
I valori sono sempre nel range 1-90 estremi compresi (come il lotto vero)"

Quindi non deve controllarla, dice "saranno unici"

[malocchio]

Dal 1° post del contest:

"I valori estratti per ciascuna ruota/estrazione saranno unici (estrazione senza reinserimento, come nel lotto vero)
I valori sono sempre nel range 1-90 estremi compresi (come il lotto vero)"

Grazie, mi era sfuggita la sfumatura :doh:

[Vincenzo1968]

...
Penso che dovrò stamparmi la spiegazione di Repne. Magari all'ITIS mi danno un credito formativo.

Ohé,

non ti scordare la spiegazione del Contest 3 (http://www.hwupgrade.it/forum/showthread.php?t=1787500)

;)

[Vincenzo1968]

Alla fine vorrei raccogliere tutte le soluzioni(e le relative spiegazioni degli algoritmi) di Repne in un libro. Si potrebbe intitolarlo Soluzioni Matematiche in C: Tips & Tricks o qualcosa del genere ;)

[banryu79]

Ah, allora ti sei deciso a scrivere qualcosa ;)

[Vincenzo1968]

Va benissimo, fammi sapere come gira sotto un AMD.

Davvero, mi piacerebbe provare fra qualche anno come si attestano le differenze C - C# quando c'e' di mezzo il multithreading.
Il C standard non ha nulla per il parallelismo vero?
...
[/I]

si invece:

http://openmp.org/wp/

http://en.wikipedia.org/wiki/OpenMP

http://msdn.microsoft.com/en-us/library/tt15eb9t.aspx

OpenMP è di facile utilizzo, è portabile, ed è supportato dalla maggior parte dei compilatori C/C++.

:bimbo:

[cionci]

Ma non è standard. Allora ci sono anche i pthread ;)

[Vincenzo1968]

Ma non è standard. Allora ci sono anche i pthread ;)

Si ma guarda la facilità di utilizzo:

http://www.codeproject.com/KB/cpp/BeginOpenMP.aspx

Si tratta di includere il file <omp.h> e di utilizzare una serie di direttive, per esempio:


#pragma omp parallel for


È supportato benissimo dalla maggior parte dei compilatori (http://openmp.org/wp/openmp-compilers/)(compreso GCC).

Alla luce di questo, non è follia pura non utilizzare questa libreria? :D

:bimbo:

[cdimauro]

Non è standard. Una libreria standard per i thread arriverà con la prossima versione del C++.

[cionci]

Non è standard. Una libreria standard per i thread arriverà con la prossima versione del C++.
Usano quelli della libreria Boost, giusto ?

[cdimauro]

Non ho ancora letto il draft delle estensioni al linguaggio, ma già qualche anno fa l'idea era quella di far diventare BOOST parte della libreria standard, per cui a naso credo proprio che per i thread prenderanno a piene mani da questa libreria "standard di fatto".

[Vincenzo1968]

Ah, allora ti sei deciso a scrivere qualcosa ;)

Si si, mi sto attrezzando. ho comprato questo libro:

Gilbert K. Chesterton
Come si scrive un giallo (http://www.ibs.it/code/9788838917998/chesterton-gilbert-k/come-si-scrive-un.html)
Sellerio

:bimbo:

[banryu79]

Si si, mi sto attrezzando. ho comprato questo libro:

Gilbert K. Chesterton
Come si scrive un giallo (http://www.ibs.it/code/9788838917998/chesterton-gilbert-k/come-si-scrive-un.html)
Sellerio

:bimbo:

:asd: a giudicare da questo pensavo che volessi scrivere qualcosa di più tecnico, non un romanzo:

Alla fine vorrei raccogliere tutte le soluzioni(e le relative spiegazioni degli algoritmi) di Repne in un libro. Si potrebbe intitolarlo Soluzioni Matematiche in C: Tips & Tricks o qualcosa del genere

[Vincenzo1968]

:asd: a giudicare da questo pensavo che volessi scrivere qualcosa di più tecnico, non un romanzo:

Ma scrivere un giallo è molto più divertente.
Dalla quarta di copertina del libro:


...
"Il giallo è un gioco che il lettore gioca con l'autore" e "differisce da ogni altro racconto in questo: che il lettore è contento solo se si sente scemo". Ragion per cui si può essere buoni lettori di gialli solo se non si è scemi.
...


:bimbo:

[Vincenzo1968]

up

:bimbo: