ARCHIV

V jave je alokace pameti mnohem rychlejsi nez v C++. Mam k tomu nejake slajdy z konference:

Garbage Collection is often faster than malloc/free
– Object allocation is on the order of 10 instructions
– Malloc implementations are 60 to 100 instructions
– Cost of freeing an object can be around 1 instruction per object
– Free implementations average ~100 instructions

Ono nejde az tak moc o tu alokaci jako o ty velke objektove struktury na heapu a tomu se clovek v Jave proste moc rozumne nevyhne.

Schválně si to někdy změřím :-)

Tak jsem si to změřil a zdá se že máte pravdu. Je to zajímavé. Špatně napsaný příklad v Javě je 3 krát rychlejší než stejně špatně napsaný příklad v C++. (Akorát, že v C++ by nikoho nenapadlo mít std::vector<CiselnaTrida *>, ale byl by tam std::vector<int>.)

import java.util.Vector;
import java.util.Date;

public class Mereni {

static int[] pole = {38, 20, 30, 15, 5, 12, 1, 17, 51, 25};
static int index = 0;

static int random() {
index %= pole.length;
return pole[index++];
}

static Vector<Integer> generujTahy() {
Vector<Integer> tahy = new Vector<Integer>();
int tahu = random();
for (int i = 0; i < tahu; i++)
tahy.add(new Integer(random()));
return tahy;
}

static int propocet(int hloubka) {
if (hloubka <= 0) return random();
Vector<Integer> tahy = generujTahy();
int r = 0;
for (int i = 0; i < tahy.size(); i++) {
r += propocet(hloubka - 1) + tahy.elementAt(i);
}
return r;
}
public static void main(String[] args) {
for (int i = 0; i < 7; i++) {
System.out.println("Propočet do hloubky " + i + " vrátil " + propocet(i) + " v čase " + new Date());
}
}
}

----------------------

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

int pole[] = {38, 20, 30, 15, 5, 12, 1, 17, 51, 25};
int index = 0;
int random() {
index %= (sizeof(pole) / sizeof(pole[0]));
return pole[index++];
}

class Cislo {
private:
int m_data;
public:
Cislo(int data): m_data(data){};
int getData() {return m_data;};
};

std::vector<Cislo *> *generujTahy() {
std::vector<Cislo *> *tahy = new std::vector<Cislo *>;
int tahu = random();
for (int i = 0; i < tahu; i++)
tahy->push_back(new Cislo(random()));
return tahy;
}

int propocet(int hloubka) {
if (hloubka <= 0) return random();
std::vector<Cislo *> *tahy = generujTahy();
int r = 0;
for (int i = 0; i < tahy->size(); i++) {
r += propocet(hloubka - 1) + (*tahy)[i]->getData();
delete (*tahy)[i];
}
delete tahy;
return r;
}

int main(void) {
for (int i = 0; i < 7; i++) {
int r = propocet(i);
printf("Propočet do hloubky %i vrátil %i v čase %i\n", i, r, (int)time(NULL));
}
return 0;
}

Ona je ta java v poměru 3:2 rychlejší i v porovnání s C++ a std::vector<int>. To už je fakt bomba.

Nemohla by byt probirana taky dama? Myslim tim ohodnocovaci funkci, zbytek bude zhruba stejny, pripadne jednodussi. Ja bych si rad zkusil nekdy naprogramovat damu.

S dámou bohužel nemám zkušenosti ani teoretické znalosti, tak neposloužím. Myslím, že jinak bude nejen ohodnocovací funkce, ale i část prohlubovacích a ořezávacích heuristik.

Dobrý den,
v článku je uvedeno, že konstanta MNOHO udávající velikost pole, do kterého ukládáme všechny vygenerované tahy je součin max. počtu tahů z dané pozice a maximální hloubky prohledávacího stromu. To mi ale nedává smysl, protože počet těch tahů přece roste exponenciálně se vzrůstající hloubkou zanoření. Nemělo by tedy být MNOHO = MAX_POCET_TAHU^MAX_HLOUBKA_PROHLEDAVANI ? Možná jsem to ale nepochopila, můžete mi to objasnit?

Aha, už tomu asi rozumím. V tom poli jsou uloženy tahy patřící pouze konkrétní cestě z kořene do určitého listu...

Ano, rozumíte tomu teď správně. To jste o tom v noci přemýšlela? :-)