Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Structures de données pour haute performance

Présentation pour le le OpenCode 10 de Québec
by

Julien Marcil

on 3 April 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Structures de données pour haute performance

20 19 18 17 16 15 14 13 12 11 8 9 7 6 5 4 10 3 2 1 Structures de données
pour haute performance Julien Marcil Architecte Logiciel Solution au problème des triplets sur HackerRank avec Problème des triplets Soit d une séquence d de N entiers positifs
d = [d1, d2, ..., dN]
Combiens de triplets (d[i], d[j], d[k]) distincts peut-on faire tel que
d[i] < d[j] < d[k]
i < j < k contraites N <= 10^5
Chaque entier de la séquence n'est présent qu'au maximum deux fois. long result = 0;
for (int i = 0; i < N; ++i) {
for (int j = i+1; j < N; ++j) {
for (int k = j+1; k < N; ++k) {
if (isDistictTriplet(d[i], d[j], d[k])) {
++result;
}
}
}
}
return result; Trivial Solution Problème comportement assymptotique de l'algorithme trivial(N) est O(N^3) Optimization Simplification Pour simplifier le problème, je vais assumer qu'il n'y a pas de duplicats dans la séquence.

La solution avec duplicat est laissé en execise. {d[i] | i < j, d[i] < d[j]} Pour un j donné, l'ensemble des triplets
(d[i], d[j], d[k])
qu'il est possible de composer est donné par le produit cartesien des sous-ensembles suivant long result = 0;
for (int j = 0; j < N; ++j) {
result += smaller(j) * larger(j);
}
return result; smaller(N) et larger(N) sont O(N) Sommes des préfixes Soit une séquence de n nombres
x1, x2, ..., xn
Alors, la séquences des sommes des préfixes est
y0 = x0
y1 = x0 + x1
y2 = x0 + x1 + x2
...
yn = x0 + x1 + ... + xn {d[k] | k > j, d[k] > d[j]} X countSmaller(j) * countLarger(j) Optimized Solution 1 1 2 2 3 4 N=6 1 1 2 3 2 1 2 4 3 1 3 4 4 2 3 4 Example 1 3 8 6 9 2 10 Example {9, 10} {1, 3} Problème comportement assymptotique de l'algorithme optimized(N) est O(N^2) 1 3 8 6 9 2 10 Example x1=1 y1=1
x2=0 y2=1
x3=1 y3=2
x4=0 y4=2
x5=0 y5=2 Arbres de Fenwick 1 1 2 1 2 3 4 4 1 5 4 6 0 7 2 7 2 9 10 11 11 12 3 13 4 14 0 15 12 8 29 16 1 1 2 1 2 3 4 4 1 5 4 6 0 7 2 7 2 9 10 11 11 12 3 13 4 14 0 15 12 8 29 16 1 = 1 1 = 1 3 = 2+1 4 = 4 5 = 1+4 8 = 4+4 8 = 0+4+4 12 = 12 14 = 2+12 19 = 7+12 21 = 2+7+12 23 = 11+12 26 = 3+11+12 27 = 4+11+12 27 = 0+4+11+12 29 = 29 = 26 int read(int j) {
int sum = 0;
while (j > 0) {
sum += tree[j];
j -= (j & -j); //
}
return sum;
} Read void update(int j, int val) {
while (j <= MaxVal) {
tree[j] += val;
j += (j & -j);//
}
} Update WTF! 5 = 1+4 8 = 4+4 8 = 0+4+4 12 = 12 14 = 2+12 19 = 7+12 21 = 2+7+12 23 = 11+12 26 = 3+11+12 27 = 4+11+12 27 = 0+4+11+12 29 = 29 { { x Y13 = 3 +11 +12 HackerRank Les arbres de Fenwick sont aussi connus sous le nom d'arbre index binaire "Binary Index Tree". Nous allons garder des résulats intermédaire des sommes préfixer dans un arbre. //precompute smaller values
int[] smaller = new int[N];
for (int j = 0; j < N; ++j) {
updateSmallerCount(d[j])
smaller[j] = computeSmaller(d[j]);
} WTF! xi = 1 si i est un élément qui précède ou 0 sinon y(j-1) est le nombre d'entier plus petit que j julien@marcil.com @Nr9 http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
http://thecodersbreakfast.net/index.php?post/2012/10/06/Structures-de-donnees-arbres-de-Fenwick Arbre de Fenwick
Full transcript