Builder.cz - Informacni server o programovani

Odběr fotomagazínu

Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!

 

Zadejte Vaši e-mailovou adresu:

Kamarád fotí rád?

Přihlas ho k odběru fotomagazínu!

 

Zadejte e-mailovou adresu kamaráda:



stupen usporadanosti

Seznam témat     Nová odpověď

Přihlásit se     Registrace     Zapomenuté heslo

Re: stupen usporadanosti

Autor: tcesky

10:59:20 02.08.2010

Stupidni ale presto mozna vyhovujici:

[code]

Value for random data 2599
Value for sorted data 1
Press any key to continue . . .


[color=#0000ff]using[/color][color=#000000] System;
[/color][color=#0000ff]using[/color][color=#000000] System.Collections.Generic;
[/color][color=#0000ff]using[/color][color=#000000] System.Linq;
[/color][color=#0000ff]using[/color][color=#000000] System.Text;

[/color][color=#0000ff]namespace[/color][color=#000000] Radek.R
{
[/color][color=#808080]///[/color][color=#008000] [/color][color=#808080]


[/color][color=#000000] [/color][color=#808080]///[/color][color=#008000] Da se nejak urcit neco jako index usporadanosti (resp. entropie) obou souboru ?
[/color][color=#000000] [/color][color=#808080]///[/color][color=#008000] [/color][color=#808080]

[/color][color=#000000] [/color][color=#0000ff]class[/color][color=#000000] [/color][color=#2b91af]Program
[/color][color=#000000] {
[/color][color=#0000ff]static[/color][color=#000000] [/color][color=#0000ff]void[/color][color=#000000] Main([/color][color=#0000ff]string[/color][color=#000000][[/color][color=#000000]] args)
{
[/color][color=#0000ff]var[/color][color=#000000] tmp = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>(); [/color][color=#0000ff]for[/color][color=#000000] ([/color][color=#0000ff]int[/color][color=#000000] i = 0; i < 100; i++) tmp.Add(i);

[/color][color=#0000ff]var[/color][color=#000000] rnd = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]Random[/color][color=#000000]();
[/color][color=#0000ff]var[/color][color=#000000] src = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>();
[/color][color=#0000ff]for[/color][color=#000000] (; tmp.Count > 0; ) { [/color][color=#0000ff]int[/color][color=#000000] ind = rnd.Next(tmp.Count); src.Add(tmp[[/color][color=#000000]ind]); tmp.RemoveAt(ind); }

[/color][color=#2b91af]Console[/color][color=#000000].WriteLine([/color][color=#a31515]"Value for random data {0,4}"[/color][color=#000000], [/color][color=#2b91af]RadekSwapper[/color][color=#000000].StupidSort(src));
[/color][color=#2b91af]Console[/color][color=#000000].WriteLine([/color][color=#a31515]"Value for sorted data {0,4}"[/color][color=#000000], [/color][color=#2b91af]RadekSwapper[/color][color=#000000].StupidSort(src));
}
[/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]class[/color][color=#000000] [/color][color=#2b91af]RadekSwapper
[/color][color=#000000] {
[/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]static[/color][color=#000000] [/color][color=#0000ff]int[/color][color=#000000] StupidSort([/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]> lst)
{
[/color][color=#0000ff]int[/color][color=#000000] i,j, n = lst.Count;
[/color][color=#0000ff]for[/color][color=#000000] (i = 1, j=0; i < n;j++ )
{
[/color][color=#0000ff]for[/color][color=#000000] (i=1; i < n; i++)
[/color][color=#0000ff]if[/color][color=#000000] (lst[[/color][color=#000000]i - 1] > lst[[/color][color=#000000]i])
{
[/color][color=#0000ff]int[/color][color=#000000] x = lst[[/color][color=#000000]i - 1];
lst[[/color][color=#000000]i - 1] = lst[[/color][color=#000000]i];
lst[[/color][color=#000000]i] = x;
[/color][color=#0000ff]break[/color][color=#000000];
}
}
[/color][color=#0000ff]return[/color][color=#000000] j;
}
}
}
}
[/color][/code]
[size=10px]Designed for "uvadeni kodu bez jakehokoliv vysvetleni, ktere mozna pomuze v dany okamzik, ale nic nevyresi do budoucna a takovy clovek se stejne nestane vyvojarem a na slozitejsi otazky uz nedojde"[/size]

Zdravim

TC

[/color][color=#000000] [/color][color=#808080]///[/color][color=#008000] Da se nejak urcit neco jako index usporadanosti (resp. entropie) obou souboru ? [/color][color=#000000] [/color][color=#808080]///[/color][color=#008000] [/color][color=#808080] [/color][color=#000000] [/color][color=#0000ff]class[/color][color=#000000] [/color][color=#2b91af]Program [/color][color=#000000] { [/color][color=#0000ff]static[/color][color=#000000] [/color][color=#0000ff]void[/color][color=#000000] Main([/color][color=#0000ff]string[/color][color=#000000][[/color][color=#000000]] args) { [/color][color=#0000ff]var[/color][color=#000000] tmp = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>(); [/color][color=#0000ff]for[/color][color=#000000] ([/color][color=#0000ff]int[/color][color=#000000] i = 0; i < 100; i++) tmp.Add(i); [/color][color=#0000ff]var[/color][color=#000000] rnd = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]Random[/color][color=#000000](); [/color][color=#0000ff]var[/color][color=#000000] src = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>(); [/color][color=#0000ff]for[/color][color=#000000] (; tmp.Count > 0; ) { [/color][color=#0000ff]int[/color][color=#000000] ind = rnd.Next(tmp.Count); src.Add(tmp[[/color][color=#000000]ind]); tmp.RemoveAt(ind); } [/color][color=#2b91af]Console[/color][color=#000000].WriteLine([/color][color=#a31515]"Value for random data {0,4}"[/color][color=#000000], [/color][color=#2b91af]RadekSwapper[/color][color=#000000].StupidSort(src)); [/color][color=#2b91af]Console[/color][color=#000000].WriteLine([/color][color=#a31515]"Value for sorted data {0,4}"[/color][color=#000000], [/color][color=#2b91af]RadekSwapper[/color][color=#000000].StupidSort(src)); } [/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]class[/color][color=#000000] [/color][color=#2b91af]RadekSwapper [/color][color=#000000] { [/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]static[/color][color=#000000] [/color][color=#0000ff]int[/color][color=#000000] StupidSort([/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]> lst) { [/color][color=#0000ff]int[/color][color=#000000] i,j, n = lst.Count; [/color][color=#0000ff]for[/color][color=#000000] (i = 1, j=0; i < n;j++ ) { [/color][color=#0000ff]for[/color][color=#000000] (i=1; i < n; i++) [/color][color=#0000ff]if[/color][color=#000000] (lst[[/color][color=#000000]i - 1] > lst[[/color][color=#000000]i]) { [/color][color=#0000ff]int[/color][color=#000000] x = lst[[/color][color=#000000]i - 1]; lst[[/color][color=#000000]i - 1] = lst[[/color][color=#000000]i]; lst[[/color][color=#000000]i] = x; [/color][color=#0000ff]break[/color][color=#000000]; } } [/color][color=#0000ff]return[/color][color=#000000] j; } } } } [/color][/code] [size=10px]Designed for "uvadeni kodu bez jakehokoliv vysvetleni, ktere mozna pomuze v dany okamzik, ale nic nevyresi do budoucna a takovy clovek se stejne nestane vyvojarem a na slozitejsi otazky uz nedojde"[/size] Zdravim TC

Citovat příspěvek

 

Re: stupen usporadanosti

Autor: tcesky

10:46:00 02.08.2010

[ital]* Dale mne napada pouzit usporavani nejakym rychlym quick sort nebo necim tak a sledovat cas, za jak dlouho. [/ital] neni stastne reseni.

Priklad nahodna vs. serazena data:

[code]

926 comparisons was needed to sort the data.
768 comparisons was needed to sort the data.
Press any key to continue . . .

[color=#0000ff]using[/color][color=#000000] System;
[/color][color=#0000ff]using[/color][color=#000000] System.Collections.Generic;
[/color][color=#0000ff]using[/color][color=#000000] System.Linq;
[/color][color=#0000ff]using[/color][color=#000000] System.Text;

[/color][color=#0000ff]namespace[/color][color=#000000] Radek.R
{
[/color][color=#808080]///[/color][color=#008000] [/color][color=#808080]


[/color][color=#000000] [/color][color=#808080]///[/color][color=#008000] Da se nejak urcit neco jako index usporadanosti (resp. entropie) obou souboru ?
[/color][color=#000000] [/color][color=#808080]///[/color][color=#008000] [/color][color=#808080]

[/color][color=#000000] [/color][color=#0000ff]class[/color][color=#000000] [/color][color=#2b91af]Program
[/color][color=#000000] {
[/color][color=#0000ff]static[/color][color=#000000] [/color][color=#0000ff]void[/color][color=#000000] Main([/color][color=#0000ff]string[/color][color=#000000][[/color][color=#000000]] args)
{
[/color][color=#0000ff]var[/color][color=#000000] tmp = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>(); [/color][color=#0000ff]for[/color][color=#000000] ([/color][color=#0000ff]int[/color][color=#000000] i = 0; i < 100; i++) tmp.Add(i);

[/color][color=#0000ff]var[/color][color=#000000] rnd = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]Random[/color][color=#000000]();
[/color][color=#0000ff]var[/color][color=#000000] src = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>();
[/color][color=#0000ff]for[/color][color=#000000] (; tmp.Count > 0; ) { [/color][color=#0000ff]int[/color][color=#000000] ind = rnd.Next(tmp.Count); src.Add(tmp[[/color][color=#000000]ind]); tmp.RemoveAt(ind); }

[/color][color=#0000ff]var[/color][color=#000000] rc = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]RadekComparer[/color][color=#000000]();
src.Sort(rc);
[/color][color=#2b91af]Console[/color][color=#000000].WriteLine(rc);

rc.Reset();
src.Sort(rc);
[/color][color=#2b91af]Console[/color][color=#000000].WriteLine(rc);
}
[/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]class[/color][color=#000000] [/color][color=#2b91af]RadekComparer[/color][color=#000000] : [/color][color=#2b91af]IComparer[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>
{
[/color][color=#0000ff]int[/color][color=#000000] cnt = 0;
[/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]int[/color][color=#000000] Compare([/color][color=#0000ff]int[/color][color=#000000] x, [/color][color=#0000ff]int[/color][color=#000000] y) { cnt++; [/color][color=#0000ff]return[/color][color=#000000] x.CompareTo(y); }
[/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]void[/color][color=#000000] Reset() { cnt = 0; }
[/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]override[/color][color=#000000] [/color][color=#0000ff]string[/color][color=#000000] ToString() { [/color][color=#0000ff]return[/color][color=#000000] [/color][color=#0000ff]string[/color][color=#000000].Format([/color][color=#a31515]"{0} comparisons was needed to sort the data."[/color][color=#000000], cnt); }
}
}
}
[/color][/code]
[size=10px]Designed for "uvadeni kodu bez jakehokoliv vysvetleni, ktere mozna pomuze v dany okamzik, ale nic nevyresi do budoucna a takovy clovek se stejne nestane vyvojarem a na slozitejsi otazky uz nedojde"[/size]

Zdravim

TC

[/color][color=#000000] [/color][color=#808080]///[/color][color=#008000] Da se nejak urcit neco jako index usporadanosti (resp. entropie) obou souboru ? [/color][color=#000000] [/color][color=#808080]///[/color][color=#008000] [/color][color=#808080] [/color][color=#000000] [/color][color=#0000ff]class[/color][color=#000000] [/color][color=#2b91af]Program [/color][color=#000000] { [/color][color=#0000ff]static[/color][color=#000000] [/color][color=#0000ff]void[/color][color=#000000] Main([/color][color=#0000ff]string[/color][color=#000000][[/color][color=#000000]] args) { [/color][color=#0000ff]var[/color][color=#000000] tmp = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>(); [/color][color=#0000ff]for[/color][color=#000000] ([/color][color=#0000ff]int[/color][color=#000000] i = 0; i < 100; i++) tmp.Add(i); [/color][color=#0000ff]var[/color][color=#000000] rnd = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]Random[/color][color=#000000](); [/color][color=#0000ff]var[/color][color=#000000] src = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]List[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]>(); [/color][color=#0000ff]for[/color][color=#000000] (; tmp.Count > 0; ) { [/color][color=#0000ff]int[/color][color=#000000] ind = rnd.Next(tmp.Count); src.Add(tmp[[/color][color=#000000]ind]); tmp.RemoveAt(ind); } [/color][color=#0000ff]var[/color][color=#000000] rc = [/color][color=#0000ff]new[/color][color=#000000] [/color][color=#2b91af]RadekComparer[/color][color=#000000](); src.Sort(rc); [/color][color=#2b91af]Console[/color][color=#000000].WriteLine(rc); rc.Reset(); src.Sort(rc); [/color][color=#2b91af]Console[/color][color=#000000].WriteLine(rc); } [/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]class[/color][color=#000000] [/color][color=#2b91af]RadekComparer[/color][color=#000000] : [/color][color=#2b91af]IComparer[/color][color=#000000]<[/color][color=#0000ff]int[/color][color=#000000]> { [/color][color=#0000ff]int[/color][color=#000000] cnt = 0; [/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]int[/color][color=#000000] Compare([/color][color=#0000ff]int[/color][color=#000000] x, [/color][color=#0000ff]int[/color][color=#000000] y) { cnt++; [/color][color=#0000ff]return[/color][color=#000000] x.CompareTo(y); } [/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]void[/color][color=#000000] Reset() { cnt = 0; } [/color][color=#0000ff]public[/color][color=#000000] [/color][color=#0000ff]override[/color][color=#000000] [/color][color=#0000ff]string[/color][color=#000000] ToString() { [/color][color=#0000ff]return[/color][color=#000000] [/color][color=#0000ff]string[/color][color=#000000].Format([/color][color=#a31515]"{0} comparisons was needed to sort the data."[/color][color=#000000], cnt); } } } } [/color][/code] [size=10px]Designed for "uvadeni kodu bez jakehokoliv vysvetleni, ktere mozna pomuze v dany okamzik, ale nic nevyresi do budoucna a takovy clovek se stejne nestane vyvojarem a na slozitejsi otazky uz nedojde"[/size] Zdravim TC

Citovat příspěvek

 

Re: stupen usporadanosti

Autor: peta1

10:30:37 02.08.2010

* Take bych zkusil kompresni algoritmy (rar, zip). Cas a velikost souboru pred a po by rozhodoval o usporadani. Pokud je zdroj usporadany, dokaze jej algoritmus vetsinou lepe zakomprimovat.

* Pak je tu problem, ktery zminil tcesky (Tomas Cesky), co se rozumi tim, usporadat?

* Jeste muzes zkusit udelat toto:
A
B = random A
(A[i] - B[i]) <> 0
Cili z pole A a B vybrat prvek na stejnem miste a pokud je rozdil jiny nez nula, tak je prvek umisten nespravne.

* Dale mne napada pouzit usporavani nejakym rychlym quick sort nebo necim tak a sledovat cas, za jak dlouho.

* A jeste muzes pouzit algoritmus, ktery nahodne vygeneruje 10 prvku a zkusis je najit v poli random. Sledujes cas. Nastavis, ze pokud je hledani do ms, pak je to stale dobre usporadane.

Nevyhoda sledovani casu je v tom, ze pc muze pracovat na vice programech a nektery to muze pretizit a tim se ti cas vyrazne meni.

Citovat příspěvek

 

Re: stupen usporadanosti

Autor: grafnev

10:11:29 02.08.2010

Myslim si, ze neco o entropii informace je v kompresi (huffman, aritmeticka komprese hlavne).

Jinak si myslim, ze obecne to vyresit nejde, protoze "komprese" kazdeho pripadu muze byt zalozena na uplne jinem principu.
- pokud plivnu primo proti vetru o rychlosti 2 ms/s, pod uhlem 45% od zeme normovanou slinu CSN 12345 a zaznamenam cas dopadu jednotlivych kapek s presnosti na 0.01s dostanu tento soubor 521 desetinnych cisel

Btw. kdyz uz jsme u te entropie informace, pokud budete mit mnozinu generovanou nahodnym generatorem z pocitace ... tak k jeji kompresi staci vedet seed a vzorecek ktery byl pouzit ... paradoxne tak bude mozna potreba mene informaci nez na to 010203..99

K te entropii informace (nezkousel jsem, pouze jsem o tom cetl) ... 3D parba na 96KB http://kk.kema.at/files/kkrieger-beta.zip ... vsechny textury a prostredi se generuji.

Citovat příspěvek

 

Re: stupen usporadanosti

Autor: ondro1234

9:25:27 02.08.2010

Nestacila by korelacia k rastucej postupnosti?

Citovat příspěvek

 

Re: stupen usporadanosti

Autor: tcesky

8:18:18 02.08.2010

123 100% usporadanost (vzestupne)
321 100% usporadanost (sestupne)
132 100% usporadanost (napred licha cisla vzestupne, pak suda)
312 100% usporadanost (podle vzoru 312)
atd.

TC

Citovat příspěvek

 

Re: stupen usporadanosti

Autor: Maaartin

1:44:12 02.08.2010

Jo, teoreticky neco takovyho existuje
http://en.wikipedia.org/wiki/Kolmogorov_complexity
ale ma to jednu chybku - nejde to spocitat. Dokonce je dokazano ze to nejde; ze to nejde prakticky je bohuzel dost nepochybny fakt.

Co jde je prohnat to komprimacnim programem, treba by to mohlo stacit. Ale ty neuvazuji aritmeticky relace, pro ne je
123456789
a
134297865
stejne slozity, znaji jen opakovani podretezcu.

Pokud bys vedel jakyho typu ty relace muzou byt tak bys tomu mohl snad nejak dopomoct. Treba zderivovanim 01 02 03 04 .... dostavas konstantu a to uz se krasne komprimuje.

Citovat příspěvek

 

stupen usporadanosti

Autor: radek.r

0:08:17 02.08.2010

Dobry den,

rekneme, ze mam dva soubory. V prvnim je posloupnost 010203..99, ve druhem je stejne mnozstvi cislic vygenerovane nejakym random() generatorem.

Da se nejak urcit neco jako index usporadanosti (resp. entropie) obou souboru ?

Napada me, ze by mohlo byt relativne jednoduche urcit miru usporadanosti vzhledem ke konkretni metode usporadavani, ale nevim jestli jde uvazovat o usporadanosti obecne. Nebo alespon nejak vyrazne obecne, napr. v tom smyslu, ze bych se pokusil ohodnotit, ktera ciselna rada z tech dvou souboru tvori pro vsechny kombinace "podretezcu" te rady vetsi mnozstvi nejakych jednoduchych matematickych vztahu. Tenhle pristup by byl z mnoha duvodu nepouzitelny, chci jen priblizit otazku.

Smyslem je udelat si predstavu o tom, kolik informace (komplexita informace) je v danych datech. Muzete me nasmerovat na nejake metody / oblasti, ktere se podobnou problematikou zabyvaji ?

Diky.

Citovat příspěvek

 

 

 

Přihlášení k mému účtu

Uživatelské jméno:

Heslo: