[Index] Software : Coin des développeurs :]

Pour les gens qui ont simplement envie de discuter sans souhaiter faire passer d'information particulière.
Message
Auteur
regrepsa
Occasionnel
Messages : 24
Enregistré le : dimanche 14 février 2021 à 15:37

Re: [Index] Software : Coin des développeurs :]

#796 Message par regrepsa » mardi 16 février 2021 à 2:03

Salut les amis, en regardant le post sur les mathématiques, j'ai vu plein d'énigmes, de petits challenges pour le fun et aucun ici, donc je me lance :)

Pouvez vous rendre ce programme beaucoup plus rapide ? Il est en java mais peu importe c'est convertible dans votre langage préféré. Il est interdit d'utiliser la parallélisation ce serait trop facile :P
Quand je dis "beaucoup plus rapide", ça doit pouvoir gérer des tableau beaucoup plus grand que 1000 entrées sans problème.
(PS désolé pour l'indentation mais le forum ne garde pas les tabulations)
import java.util.Random;

public class Main {

private static Random rand = new Random();

static double[] tooSlow(double[] ta, double[] tb) {
if (ta.length != tb.length) {
throw new IllegalArgumentException();
}
int n = ta.length;
double[] result = new double[n];

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (i == j || i == k || j == k) {
continue;
}
if (i > j && i > k) {
result += ta[j] * tb[k];
}
if (i < j || i < k) {
result -= ta[j] * tb[k];
}
}
}
}

return result;
}

private static double[] generateRandomTable(int n) {
double[] t = new double[n];
for (int i = 0; i < n; i++) {
t = rand.nextDouble();
}

return t;
}

public static void main(String[] args) {
double[] ta = generateRandomTable(1000);
double[] tb = generateRandomTable(1000);
long t0 = System.currentTimeMillis();
tooSlow(ta, tb);
System.out.println((System.currentTimeMillis() - t0) + "ms");
}
}
suspicion de TSA

Avatar du membre
Tugdual
Modérateur
Messages : 30650
Enregistré le : jeudi 15 novembre 2012 à 0:13
Localisation : Nord-44
Contact :

Re: [Index] Software : Coin des développeurs :]

#797 Message par Tugdual » mardi 16 février 2021 à 9:04

regrepsa a écrit :
mardi 16 février 2021 à 2:03
(PS désolé pour l'indentation mais le forum ne garde pas les tabulations)
Pour cela, il faut utiliser la balise "code" (icone "</>") :

Code : Tout sélectionner

...
  ...
...
TCS = trouble de la communication sociale (24/09/2014).

Avatar du membre
Bubu
Forcené
Messages : 6068
Enregistré le : dimanche 19 mai 2013 à 12:03
Localisation : En haut à gauche

Re: [Index] Software : Coin des développeurs :]

#798 Message par Bubu » mardi 16 février 2021 à 13:19

Je donne ma langue aux chats .... (enfin pas aux miens). :mryellow:
Je n'ai pas compris ce que ce programme était censé calculer. A part des tableaux à deux dimensions de valeurs pseudo-aléatoires.

Qu'est-ce que calcule ce programme ?
Avoue ... :mryellow:
Diagnostiqué autiste asperger, diagnostic établi à mes 33 ans par le CRA de ma région.
"Ce syndrome est caractérisé chez ce patient par l’absence de détérioration intellectuelle, un syndrome dysexécutif, un déficit d'attention"

regrepsa
Occasionnel
Messages : 24
Enregistré le : dimanche 14 février 2021 à 15:37

Re: [Index] Software : Coin des développeurs :]

#799 Message par regrepsa » mardi 16 février 2021 à 15:39

Ce programme ne calcule rien de très intéressant un calcul d'espérance mathématique.

Petit indice , la version lente est en O(N cube) en terme de complexité algorithmique, en gros pour simplifier ça veux dire qu'on a 3 boucles for imbriqué donc un nombre d'itération de 1000 x 1000 x 1000 si n=1000.
Et bien il existe une solution en O(n) c'est à dire linéaire, on peux faire le même calcul en ayant jamais + de une boucle for imbriquée .
Du coup si n=1000 c'est 1 million de fois plus rapide !

Je donnerais la solution ce soir :wink:
suspicion de TSA

regrepsa
Occasionnel
Messages : 24
Enregistré le : dimanche 14 février 2021 à 15:37

Re: [Index] Software : Coin des développeurs :]

#800 Message par regrepsa » mardi 16 février 2021 à 20:14

La solution :
Spoiler : 

Code : Tout sélectionner

	static double[] cumul(double[] t) {
		double[] tCumul = t.clone();
		for (int i = 1; i < tCumul.length; i++) {
			tCumul[i] += tCumul[i - 1];
		}
		return tCumul;
	}

	static double[] fast(double[] ta, double[] tb) {
		int n = ta.length;

		double[] tac = cumul(tb);
		double[] tbc = cumul(ta);

		double[] tmax = new double[n];
		double[] tmin = new double[n];
		for (int i = 1; i < n; i++) {
			tmax[i] += ta[i] * tac[i - 1];
			tmax[i] += tb[i] * tbc[i - 1];
		}
		for (int i = 0; i < n - 1; i++) {
			tmin[i] += ta[i] * (tac[n - 1] - tac[i]);
			tmin[i] += tb[i] * (tbc[n - 1] - tbc[i]);
		}

		double[] tmaxc = cumul(tmax);
		double ttotal = tmaxc[n - 1];

		double[] result = new double[n];
		for (int a = 0; a < n; a++) {
			if (a > 0) {
				result[a] += (tmaxc[a - 1]);
			}
			if (a < n - 1) {
				result[a] -= (ttotal - tmaxc[a]) * (1.0 - tmin[a] / (ttotal - tmaxc[a]));
			}
		}

		return result;
	}
	
suspicion de TSA

Avatar du membre
Bubu
Forcené
Messages : 6068
Enregistré le : dimanche 19 mai 2013 à 12:03
Localisation : En haut à gauche

Re: [Index] Software : Coin des développeurs :]

#801 Message par Bubu » mercredi 17 février 2021 à 14:22

J'ai pas compris la solution non plus, désolé.
J'ai besoin de comprendre ce que calcule un algorithme avant de l'optimiser.

A mon tour de poser une énigme, qui est simple à résoudre grâce à la sémantique des variables :

Code : Tout sélectionner

float finalColor = (1.0f - alpha) * frontColor  + alpha * backgroundColor;
C'est l'équation des interpolations, mais qu'est-ce que cela donne ?

Le terme Alpha désigne l'opacité d'une surface, ou d'un pixel.
Diagnostiqué autiste asperger, diagnostic établi à mes 33 ans par le CRA de ma région.
"Ce syndrome est caractérisé chez ce patient par l’absence de détérioration intellectuelle, un syndrome dysexécutif, un déficit d'attention"

regrepsa
Occasionnel
Messages : 24
Enregistré le : dimanche 14 février 2021 à 15:37

Re: [Index] Software : Coin des développeurs :]

#802 Message par regrepsa » mercredi 17 février 2021 à 17:11

Ca te "fusionne" ou "mélange" 2 couleurs (background et foreground) en utilisant un "poids" (le paramètre alpha)
Plus alpha est élevé plus le background dominera dans la couleur finale et inversement pour le foreground.
C'est ça ?
suspicion de TSA

Avatar du membre
Bubu
Forcené
Messages : 6068
Enregistré le : dimanche 19 mai 2013 à 12:03
Localisation : En haut à gauche

Re: [Index] Software : Coin des développeurs :]

#803 Message par Bubu » mercredi 17 février 2021 à 17:34

regrepsa a écrit :
mercredi 17 février 2021 à 17:11
Ca te "fusionne" ou "mélange" 2 couleurs (background et foreground) en utilisant un "poids" (le paramètre alpha)
Plus alpha est élevé plus le background dominera dans la couleur finale et inversement pour le foreground.
C'est ça ?
Diagnostiqué autiste asperger, diagnostic établi à mes 33 ans par le CRA de ma région.
"Ce syndrome est caractérisé chez ce patient par l’absence de détérioration intellectuelle, un syndrome dysexécutif, un déficit d'attention"

Avatar du membre
Bubu
Forcené
Messages : 6068
Enregistré le : dimanche 19 mai 2013 à 12:03
Localisation : En haut à gauche

Re: [Index] Software : Coin des développeurs :]

#804 Message par Bubu » mercredi 17 février 2021 à 17:36

Oui c'est cela. :kiss:

EDIT :
On appelle ça l'alpha blending, qui permet de calculer la couleur d'une surface ou d'un pixel transparents par rapport au fond.
(alpha est l'opacité, entre 0 et 1, j'aurai dû le préciser au début)
C'est une interpolation entre la couleur à calculer par rapport à la couleur de fond. En effet, du coup, elles se mélangent.

Les GPUs le font de manière materielle, on a juste à le paramétrer, car il y a aussi d'autres façons de faire ce mélange des couleurs, notamment pour le rendu émissif. Là on les additionne directement (mais en les seuillant pour que cela ne vire pas au blanc par saturation), pour représenter les lampes, avec un flou gaussien pour faire l'aura de la lampe.

Désolé, le pire c'est que j'ai inversé les 2 termes.
La bonne équation de l'alpha blending classique est :

(Car alpha ne code pas la transparence, mais l'inverse : l'opacité)

Code : Tout sélectionner

float3 finalColor = foregroundColor * alpha + backgroundColor * (1.0f - alpha);
Diagnostiqué autiste asperger, diagnostic établi à mes 33 ans par le CRA de ma région.
"Ce syndrome est caractérisé chez ce patient par l’absence de détérioration intellectuelle, un syndrome dysexécutif, un déficit d'attention"

Avatar du membre
Tugdual
Modérateur
Messages : 30650
Enregistré le : jeudi 15 novembre 2012 à 0:13
Localisation : Nord-44
Contact :

Re: [Index] Software : Coin des développeurs :]

#805 Message par Tugdual » jeudi 25 février 2021 à 10:33

Agile pourrait conduire les organisations :
TCS = trouble de la communication sociale (24/09/2014).

Avatar du membre
Tugdual
Modérateur
Messages : 30650
Enregistré le : jeudi 15 novembre 2012 à 0:13
Localisation : Nord-44
Contact :

Re: [Index] Software : Coin des développeurs :]

#806 Message par Tugdual » vendredi 26 février 2021 à 10:35

Publié pour la première fois en 1970 :
TCS = trouble de la communication sociale (24/09/2014).

Avatar du membre
Tugdual
Modérateur
Messages : 30650
Enregistré le : jeudi 15 novembre 2012 à 0:13
Localisation : Nord-44
Contact :

Re: [Index] Software : Coin des développeurs :]

#807 Message par Tugdual » mercredi 3 mars 2021 à 12:46

TCS = trouble de la communication sociale (24/09/2014).

Avatar du membre
Tugdual
Modérateur
Messages : 30650
Enregistré le : jeudi 15 novembre 2012 à 0:13
Localisation : Nord-44
Contact :

Re: [Index] Software : Coin des développeurs :]

#808 Message par Tugdual » vendredi 5 mars 2021 à 9:22

TCS = trouble de la communication sociale (24/09/2014).

Avatar du membre
Bubu
Forcené
Messages : 6068
Enregistré le : dimanche 19 mai 2013 à 12:03
Localisation : En haut à gauche

Re: [Index] Software : Coin des développeurs :]

#809 Message par Bubu » vendredi 5 mars 2021 à 14:59

Le code désassemblé de super mario bros avec des commentaires, sur NES. Je l'ai déjà posté.
Le processeur de cette console étant un 6502, c'est mieux de connaître son jeu d'instructions, car à l'époque on programmait en assembleur pour les consoles.
Mais ça reste compréhensible. L'envers du décor !
smb_code.txt
(749.75 Kio) Téléchargé 12 fois
Modifié en dernier par Bubu le mardi 9 mars 2021 à 10:33, modifié 1 fois.
Diagnostiqué autiste asperger, diagnostic établi à mes 33 ans par le CRA de ma région.
"Ce syndrome est caractérisé chez ce patient par l’absence de détérioration intellectuelle, un syndrome dysexécutif, un déficit d'attention"

Avatar du membre
Tugdual
Modérateur
Messages : 30650
Enregistré le : jeudi 15 novembre 2012 à 0:13
Localisation : Nord-44
Contact :

Re: [Index] Software : Coin des développeurs :]

#810 Message par Tugdual » lundi 8 mars 2021 à 11:46

Ubuntu fait de Flutter un « choix par défaut » :
TCS = trouble de la communication sociale (24/09/2014).

Répondre