IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Java Discussion :

Dijkstra et Fibonacci


Sujet :

Java

  1. #1
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut Dijkstra et Fibonacci
    Salut, je dois faire une comparaison entre le temps d'execution de Dijkstra classqiue et Dijkstra avec Fibonacci. En fait, normalement Dijkstra avc les tas de Fibonacci donne une complexité O(m +n log n) et Dijkstra classique a une complexité de O (n²). Mon problème c'est que lors de l'execution, je trouve le contraire, et le temps d'execution de Dijkstra class est moins que celui avc Fibonacci..

    le code de Dijkstra avec Fibonacci est le suivant:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    public void dijkstr(double[][] graph, int dest,FIB Q,Node nd[])throws IOException{
                  int min,i=0;
               while(i<graph.length ){
                   min=Q.removeMin().indice;// removeMin() sa comlexité est: O(log n)
                  for( int j = 0; j < graph.length; j++ ){
                    if( nd[j].m_key>graph[ min ][ j ] + nd[min].m_key ){
                    Q.decreaseKey(nd[j], (int)graph[ min ][ j ] + nd[ min ].m_key); } }
                       i++;   //decreaseKey() sa complexité est : O(1)
                           }

    le code de Dijkstra classique est:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    public void dijkstr(double[][] graph, int dest ,Node nd[])throws IOException{
     
     
                    int dC[] = new int[ graph.length  ];
     
                    int p[] = new int[ graph.length  ];
     
                    for( int i = 0; i < graph.length ; i++ )
                    { 
                      dC[ i ] = 100; p[ i ] = -1; }
     
                     dC[ 0 ] = 0;
     
                 int i = 0;    int min = 1000, pos = 0; 
     
                    while( i<graph.length){
     
                            for( int j = 0; j < graph.length; j++ ){
     
                                    if( min > nd[ j ].m_key && dC[ j ] != -1 ){
     
                                            min = nd[ j ].m_key; pos = j;   }  }
     
                            dC[ pos ] = -1; 
     
                            for( int j = 0; j < graph.length; j++ ){
                            if( nd[ j ].m_key > graph[ pos ][ j ] + nd[ pos ].m_key ){
     
                              nd[ j ].m_key = (int)graph[ pos ][ j ] + nd[ pos ].m_key;
     
                             p[ j ] = pos; }   }
     
                            i++; min = 1000;  }
    Svp qui peut m'aider! merci d'avance

  2. #2
    Expert éminent sénior
    Avatar de tchize_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2007
    Messages
    25 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Avril 2007
    Messages : 25 481
    Points : 48 806
    Points
    48 806
    Par défaut
    Citation Envoyé par helamal Voir le message
    je trouve le contraire, et le temps d'execution de Dijkstra class est moins que celui avc Fibonacci..
    Tu pourrais nous montrer tous les chiffres de mesure que tu as obtenus?

    Faudrais voir aussi ton FIB là, parce que, si ça tombe, les méthodes n'ont pas la complexité annoncée

  3. #3
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    Citation Envoyé par tchize_ Voir le message
    Tu pourrais nous montrer tous les chiffres de mesure que tu as obtenus?

    Faudrais voir aussi ton FIB là, parce que, si ça tombe, les méthodes n'ont pas la complexité annoncée


    Merci pour votre réponse
    voila la classe Fibonacci que j'ai utilisé:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    338
    339
    340
    341
    342
    343
    344
    345
    346
    347
    348
    349
    350
    351
    352
    353
    354
    355
    356
    357
    358
    359
    360
    361
    362
    363
    364
    365
    366
    367
    368
    369
    370
    371
    372
    373
    374
    375
    376
    377
    378
    379
    380
    381
    382
    383
    384
    385
    386
    387
    388
    389
    390
    391
    392
    393
    394
    395
    396
    397
    398
    399
    400
    401
    402
    403
    404
    405
    406
    407
    408
    409
    410
    411
    412
    413
    414
    415
    416
    417
    418
    419
    420
    421
    422
    423
    424
    425
    426
    427
    428
    429
    430
    431
    432
    433
    434
    435
    436
    437
    438
    439
    440
    441
    442
    443
    444
    445
    446
    447
    448
    449
    450
    451
    452
    453
    454
    455
    456
    457
    458
    459
    460
    461
    462
    463
    464
    465
    466
    467
    468
    469
    470
    471
    472
    473
    474
    475
    476
    477
    478
    479
    480
    481
    482
    483
    484
    485
    486
    487
    488
    489
    490
    491
    492
    493
    494
    495
    496
    497
    498
    499
    500
    501
    502
    503
    504
    505
    506
    507
    508
    509
    510
    511
    512
    513
    514
    515
    516
    517
    518
    519
    520
    521
    522
    523
    524
    525
    526
    527
    528
    529
    530
    531
    532
    533
    534
    535
    536
    537
    538
    539
    540
    541
    542
    543
    544
    545
    546
    547
    548
    549
    550
    551
    552
    553
    554
    555
    556
    557
    558
    559
    560
    561
    562
    563
    564
    565
    566
    567
    568
    569
    570
    571
    572
    573
    574
    575
    576
    577
    578
    579
    580
    581
    582
    583
    584
    585
    586
    587
    588
    589
    590
    591
    592
    593
    594
    595
    596
    597
    598
    599
    600
    601
    602
    603
    604
    605
    606
    607
    608
    609
    610
    611
    612
    613
    614
    615
    616
    617
    618
    619
    620
    621
    622
    623
    624
    625
    626
    627
    628
    629
    630
    631
    632
    633
    634
    635
    636
    637
    638
    639
    640
    641
    642
    643
    644
    645
    646
    647
    648
    649
    650
    651
    652
    653
    654
    655
    656
    657
    658
    659
    660
    661
    662
    663
    664
    665
    666
    667
    668
    669
    670
    671
    672
    673
    674
    675
    676
    677
    678
    679
    680
    681
    682
    683
    684
    685
    686
    687
    688
    689
    690
    691
    692
    693
    694
    695
    696
    697
    698
    699
    700
    701
    702
    703
    704
    705
    706
    707
    708
    709
    710
    711
    /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */
     
    package aaaalgorithme;
     
    /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */
     
     
    /***********************************************************************
     * File: FibonacciHeap.java
     * Author: Keith Schwarz (htiek@cs.stanford.edu)
     *
     * An implementation of a priority queue backed by a Fibonacci heap,
     * as described by Fredman and Tarjan.  Fibonacci heaps are interesting
     * theoretically because they have asymptotically good runtime guarantees
     * for many operations.  In particular, insert, peek, and decrease-key all
     * run in amortized O(1) time.  dequeueMin and delete each run in amortized
     * O(lg n) time.  This allows algorithms that rely heavily on decrease-key
     * to gain significant performance boosts.  For example, Dijkstra's algorithm
     * for single-source shortest paths can be shown to run in O(m + n lg n) using
     * a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial
     * heap.
     *
     * Internally, a Fibonacci heap is represented as a circular, doubly-linked
     * list of trees obeying the min-heap property.  Each node stores pointers
     * to its parent (if any) and some arbitrary child.  Additionally, every
     * node stores its degree (the number of children it has) and whether it
     * is a "marked" node.  Finally, each Fibonacci heap stores a pointer to
     * the tree with the minimum value.
     *
     * To insert a node into a Fibonacci heap, a singleton tree is created and
     * merged into the rest of the trees.  The merge operation works by simply
     * splicing together the doubly-linked lists of the two trees, then updating
     * the min pointer to be the smaller of the minima of the two heaps.  Peeking
     * at the smallest element can therefore be accomplished by just looking at
     * the min element.  All of these operations complete in O(1) time.
     *
     * The tricky operations are dequeueMin and decreaseKey.  dequeueMin works
     * by removing the root of the tree containing the smallest element, then
     * merging its children with the topmost roots.  Then, the roots are scanned
     * and merged so that there is only one tree of each degree in the root list.
     * This works by maintaining a dynamic array of trees, each initially null,
     * pointing to the roots of trees of each dimension.  The list is then scanned
     * and this array is populated.  Whenever a conflict is discovered, the
     * appropriate trees are merged together until no more conflicts exist.  The
     * resulting trees are then put into the root list.  A clever analysis using
     * the potential method can be used to show that the amortized cost of this
     * operation is O(lg n), see "Introduction to Algorithms, Second Edition" by
     * Cormen, Rivest, Leiserson, and Stein for more details.
     *
     * The other hard operation is decreaseKey, which works as follows.  First, we
     * update the key of the node to be the new value.  If this leaves the node
     * smaller than its parent, we're done.  Otherwise, we cut the node from its
     * parent, add it as a root, and then mark its parent.  If the parent was
     * already marked, we cut that node as well, recursively mark its parent,
     * and continue this process.  This can be shown to run in O(1) amortized time
     * using yet another clever potential function.  Finally, given this function,
     * we can implement delete by decreasing a key to -\infty, then calling
     * dequeueMin to extract it.
     */
     
    import java.util.*; // For ArrayList
     
    /**
     * A class representing a Fibonacci heap.
     *
     * @param T The type of elements to store in the heap.
     * @author Keith Schwarz (htiek@cs.stanford.edu)
     */
    public final class FibonacciHeap<T> {
        /* In order for all of the Fibonacci heap operations to complete in O(1),
         * clients need to have O(1) access to any element in the heap.  We make
         * this work by having each insertion operation produce a handle to the
         * node in the tree.  In actuality, this handle is the node itself, but
         * we guard against external modification by marking the internal fields
         * private.
         */
        public static final class Entry<T> {
            private int     mDegree = 0;       // Number of children
            private boolean mIsMarked = false; // Whether this node is marked
     
            private Entry<T> mNext;   // Next and previous elements in the list
            private Entry<T> mPrev;
     
            private Entry<T> mParent; // Parent in the tree, if any.
     
            private Entry<T> mChild;  // Child node, if any.
     
            private T      mElem;     // Element being stored here
            private double mPriority; // Its priority
     
            /**
             * Returns the element represented by this heap entry.
             *
             * @return The element represented by this heap entry.
             */
            public T getValue() {
                return mElem;
            }
            /**
             * Sets the element associated with this heap entry.
             *
             * @param value The element to associate with this heap entry.
             */
            public void setValue(T value) {
                mElem = value;
            }
     
            /**
             * Returns the priority of this element.
             *
             * @return The priority of this element.
             */
            public double getPriority() {
                return mPriority;
            }
     
            /**
             * Constructs a new Entry that holds the given element with the indicated
             * priority.
             *
             * @param elem The element stored in this node.
             * @param priority The priority of this element.
             */
            private Entry(T elem, double priority) {
                mNext = mPrev = this;
                mElem = elem;
                mPriority = priority;
            }
        }
     
        /* Pointer to the minimum element in the heap. */
        private Entry<T> mMin = null;
     
        /* Cached size of the heap, so we don't have to recompute this explicitly. */
        private int mSize = 0;
     
        /**
         * Inserts the specified element into the Fibonacci heap with the specified
         * priority.  Its priority must be a valid double, so you cannot set the
         * priority to NaN.
         *
         * @param value The value to insert.
         * @param priority Its priority, which must be valid.
         * @return An Entry representing that element in the tree.
         */
        public Entry<T> enqueue(T value, double priority) {
            checkPriority(priority);
     
            /* Create the entry object, which is a circularly-linked list of length
             * one.
             */
            Entry<T> result = new Entry<T>(value, priority);
     
            /* Merge this singleton list with the tree list. */
            mMin = mergeLists(mMin, result);
     
            /* Increase the size of the heap; we just added something. */
            ++mSize;
     
            /* Return the reference to the new element. */
            return result;
        }
     
        /**
         * Returns an Entry object corresponding to the minimum element of the
         * Fibonacci heap, throwing a NoSuchElementException if the heap is
         * empty.
         *
         * @return The smallest element of the heap.
         * @throws NoSuchElementException If the heap is empty.
         */
        public Entry<T> min() {
            if (isEmpty())
                throw new NoSuchElementException("Heap is empty.");
            return mMin;
        }
     
        /**
         * Returns whether the heap is empty.
         *
         * @return Whether the heap is empty.
         */
        public boolean isEmpty() {
            return mMin == null;
        }
     
        /**
         * Returns the number of elements in the heap.
         *
         * @return The number of elements in the heap.
         */
        public int size() {
            return mSize;
        }
     
        /**
         * Given two Fibonacci heaps, returns a new Fibonacci heap that contains
         * all of the elements of the two heaps.  Each of the input heaps is
         * destructively modified by having all its elements removed.  You can
         * continue to use those heaps, but be aware that they will be empty
         * after this call completes.
         *
         * @param one The first Fibonacci heap to merge.
         * @param two The second Fibonacci heap to merge.
         * @return A new FibonacciHeap containing all of the elements of both
         *         heaps.
         */
        public static <T> FibonacciHeap<T> merge(FibonacciHeap<T> one, FibonacciHeap<T> two) {
            /* Create a new FibonacciHeap to hold the result. */
            FibonacciHeap<T> result = new FibonacciHeap<T>();
     
            /* Merge the two Fibonacci heap root lists together.  This helper function
             * also computes the min of the two lists, so we can store the result in
             * the mMin field of the new heap.
             */
            result.mMin = mergeLists(one.mMin, two.mMin);
     
            /* The size of the new heap is the sum of the sizes of the input heaps. */
            result.mSize = one.mSize + two.mSize;
     
            /* Clear the old heaps. */
            one.mSize = two.mSize = 0;
            one.mMin  = null;
            two.mMin  = null;
     
            /* Return the newly-merged heap. */
            return result;
        }
     
        /**
         * Dequeues and returns the minimum element of the Fibonacci heap.  If the
         * heap is empty, this throws a NoSuchElementException.
         *
         * @return The smallest element of the Fibonacci heap.
         * @throws NoSuchElementException If the heap is empty.
         */
        public Entry<T> dequeueMin() {
            /* Check for whether we're empty. */
            if (isEmpty())
                throw new NoSuchElementException("Heap is empty.");
     
            /* Otherwise, we're about to lose an element, so decrement the number of
             * entries in this heap.
             */
            --mSize;
     
            /* Grab the minimum element so we know what to return. */
            Entry<T> minElem = mMin;
     
            /* Now, we need to get rid of this element from the list of roots.  There
             * are two cases to consider.  First, if this is the only element in the
             * list of roots, we set the list of roots to be null by clearing mMin.
             * Otherwise, if it's not null, then we write the elements next to the
             * min element around the min element to remove it, then arbitrarily
             * reassign the min.
             */
            if (mMin.mNext == mMin) { // Case one
                mMin = null;
            }
            else { // Case two
                mMin.mPrev.mNext = mMin.mNext;
                mMin.mNext.mPrev = mMin.mPrev;
                mMin = mMin.mNext; // Arbitrary element of the root list.
            }
     
            /* Next, clear the parent fields of all of the min element's children,
             * since they're about to become roots.  Because the elements are
             * stored in a circular list, the traversal is a bit complex.
             */
            if (minElem.mChild != null) {
                /* Keep track of the first visited node. */
                Entry<?> curr = minElem.mChild;
                do {
                    curr.mParent = null;
     
                    /* Walk to the next node, then stop if this is the node we
                     * started at.
                     */
                    curr = curr.mNext;
                } while (curr != minElem.mChild);
            }
     
            /* Next, splice the children of the root node into the topmost list,
             * then set mMin to point somewhere in that list.
             */
            mMin = mergeLists(mMin, minElem.mChild);
     
            /* If there are no entries left, we're done. */
            if (mMin == null) return minElem;
     
            /* Next, we need to coalsce all of the roots so that there is only one
             * tree of each degree.  To track trees of each size, we allocate an
             * ArrayList where the entry at position i is either null or the
             * unique tree of degree i.
             */
            List<Entry<T>> treeTable = new ArrayList<Entry<T>>();
     
            /* We need to traverse the entire list, but since we're going to be
             * messing around with it we have to be careful not to break our
             * traversal order mid-stream.  One major challenge is how to detect
             * whether we're visiting the same node twice.  To do this, we'll
             * spent a bit of overhead adding all of the nodes to a list, and
             * then will visit each element of this list in order.
             */
            List<Entry<T>> toVisit = new ArrayList<Entry<T>>();
     
            /* To add everything, we'll iterate across the elements until we
             * find the first element twice.  We check this by looping while the
             * list is empty or while the current element isn't the first element
             * of that list.
             */
            for (Entry<T> curr = mMin; toVisit.isEmpty() || toVisit.get(0) != curr; curr = curr.mNext)
                toVisit.add(curr);
     
            /* Traverse this list and perform the appropriate unioning steps. */
            for (Entry<T> curr: toVisit) {
                /* Keep merging until a match arises. */
                while (true) {
                    /* Ensure that the list is long enough to hold an element of this
                     * degree.
                     */
                    while (curr.mDegree >= treeTable.size())
                        treeTable.add(null);
     
                    /* If nothing's here, we're can record that this tree has this size
                     * and are done processing.
                     */
                    if (treeTable.get(curr.mDegree) == null) {
                        treeTable.set(curr.mDegree, curr);
                        break;
                    }
     
                    /* Otherwise, merge with what's there. */
                    Entry<T> other = treeTable.get(curr.mDegree);
                    treeTable.set(curr.mDegree, null); // Clear the slot
     
                    /* Determine which of the two trees has the smaller root, storing
                     * the two tree accordingly.
                     */
                    Entry<T> min = (other.mPriority < curr.mPriority)? other : curr;
                    Entry<T> max = (other.mPriority < curr.mPriority)? curr  : other;
     
                    /* Break max out of the root list, then merge it into min's child
                     * list.
                     */
                    max.mNext.mPrev = max.mPrev;
                    max.mPrev.mNext = max.mNext;
     
                    /* Make it a singleton so that we can merge it. */
                    max.mNext = max.mPrev = max;
                    min.mChild = mergeLists(min.mChild, max);
     
                    /* Reparent max appropriately. */
                    max.mParent = min;
     
                    /* Clear max's mark, since it can now lose another child. */
                    max.mIsMarked = false;
     
                    /* Increase min's degree; it now has another child. */
                    ++min.mDegree;
     
                    /* Continue merging this tree. */
                    curr = min;
                }
     
                /* Update the global min based on this node.  Note that we compare
                 * for <= instead of < here.  That's because if we just did a
                 * reparent operation that merged two different trees of equal
                 * priority, we need to make sure that the min pointer points to
                 * the root-level one.
                 */
                if (curr.mPriority <= mMin.mPriority) mMin = curr;
            }
            return minElem;
        }
     
        /**
         * Decreases the key of the specified element to the new priority.  If the
         * new priority is greater than the old priority, this function throws an
         * IllegalArgumentException.  The new priority must be a finite double,
         * so you cannot set the priority to be NaN, or +/- infinity.  Doing
         * so also throws an IllegalArgumentException.
         *
         * It is assumed that the entry belongs in this heap.  For efficiency
         * reasons, this is not checked at runtime.
         *
         * @param entry The element whose priority should be decreased.
         * @param newPriority The new priority to associate with this entry.
         * @throws IllegalArgumentException If the new priority exceeds the old
         *         priority, or if the argument is not a finite double.
         */
        public void decreaseKey(Entry<T> entry, double newPriority) {
            checkPriority(newPriority);
            if (newPriority > entry.mPriority)
                throw new IllegalArgumentException("New priority exceeds old.");
     
            /* Forward this to a helper function. */
            decreaseKeyUnchecked(entry, newPriority);
        }
     
        /**
         * Deletes this Entry from the Fibonacci heap that contains it.
         *
         * It is assumed that the entry belongs in this heap.  For efficiency
         * reasons, this is not checked at runtime.
         *
         * @param entry The entry to delete.
         */
        public void delete(Entry<T> entry) {
            /* Use decreaseKey to drop the entry's key to -infinity.  This will
             * guarantee that the node is cut and set to the global minimum.
             */
            decreaseKeyUnchecked(entry, Double.NEGATIVE_INFINITY);
     
            /* Call dequeueMin to remove it. */
            dequeueMin();
        }
     
        /**
         * Utility function which, given a user-specified priority, checks whether
         * it's a valid double and throws an IllegalArgumentException otherwise.
         *
         * @param priority The user's specified priority.
         * @throws IllegalArgumentException If it is not valid.
         */
        private void checkPriority(double priority) {
            if (Double.isNaN(priority))
                throw new IllegalArgumentException(priority + " is invalid.");
        }
     
        /**
         * Utility function which, given two pointers into disjoint circularly-
         * linked lists, merges the two lists together into one circularly-linked
         * list in O(1) time.  Because the lists may be empty, the return value
         * is the only pointer that's guaranteed to be to an element of the
         * resulting list.
         *
         * This function assumes that one and two are the minimum elements of the
         * lists they are in, and returns a pointer to whichever is smaller.  If
         * this condition does not hold, the return value is some arbitrary pointer
         * into the doubly-linked list.
         *
         * @param one A pointer into one of the two linked lists.
         * @param two A pointer into the other of the two linked lists.
         * @return A pointer to the smallest element of the resulting list.
         */
        private static <T> Entry<T> mergeLists(Entry<T> one, Entry<T> two) {
            /* There are four cases depending on whether the lists are null or not.
             * We consider each separately.
             */
            if (one == null && two == null) { // Both null, resulting list is null.
                return null;
            }
            else if (one != null && two == null) { // Two is null, result is one.
                return one;
            }
            else if (one == null && two != null) { // One is null, result is two.
                return two;
            }
            else { // Both non-null; actually do the splice.
                /* This is actually not as easy as it seems.  The idea is that we'll
                 * have two lists that look like this:
                 *
                 * +----+     +----+     +----+
                 * |    |--N->|one |--N->|    |
                 * |    |<-P--|    |<-P--|    |
                 * +----+     +----+     +----+
                 *
                 *
                 * +----+     +----+     +----+
                 * |    |--N->|two |--N->|    |
                 * |    |<-P--|    |<-P--|    |
                 * +----+     +----+     +----+
                 *
                 * And we want to relink everything to get
                 *
                 * +----+     +----+     +----+---+
                 * |    |--N->|one |     |    |   |
                 * |    |<-P--|    |     |    |<+ |
                 * +----+     +----+<-\  +----+ | |
                 *                  \  P        | |
                 *                   N  \       N |
                 * +----+     +----+  \->+----+ | |
                 * |    |--N->|two |     |    | | |
                 * |    |<-P--|    |     |    | | P
                 * +----+     +----+     +----+ | |
                 *              ^ |             | |
                 *              | +-------------+ |
                 *              +-----------------+
                 *
                 */
                Entry<T> oneNext = one.mNext; // Cache this since we're about to overwrite it.
                one.mNext = two.mNext;
                one.mNext.mPrev = one;
                two.mNext = oneNext;
                two.mNext.mPrev = two;
     
                /* Return a pointer to whichever's smaller. */
                return one.mPriority < two.mPriority? one : two;
            }
        }
     
        /**
         * Decreases the key of a node in the tree without doing any checking to ensure
         * that the new priority is valid.
         *
         * @param entry The node whose key should be decreased.
         * @param priority The node's new priority.
         */
        private void decreaseKeyUnchecked(Entry<T> entry, double priority) {
            /* First, change the node's priority. */
            entry.mPriority = priority;
     
            /* If the node no longer has a higher priority than its parent, cut it.
             * Note that this also means that if we try to run a delete operation
             * that decreases the key to -infinity, it's guaranteed to cut the node
             * from its parent.
             */
            if (entry.mParent != null && entry.mPriority <= entry.mParent.mPriority)
                cutNode(entry);
     
            /* If our new value is the new min, mark it as such.  Note that if we
             * ended up decreasing the key in a way that ties the current minimum
             * priority, this will change the min accordingly.
             */
            if (entry.mPriority <= mMin.mPriority)
                mMin = entry;
        }
     
        /**
         * Cuts a node from its parent.  If the parent was already marked, recursively
         * cuts that node from its parent as well.
         *
         * @param entry The node to cut from its parent.
         */
        private void cutNode(Entry<T> entry) {
            /* Begin by clearing the node's mark, since we just cut it. */
            entry.mIsMarked = false;
     
            /* Base case: If the node has no parent, we're done. */
            if (entry.mParent == null) return;
     
            /* Rewire the node's siblings around it, if it has any siblings. */
            if (entry.mNext != entry) { // Has siblings
                entry.mNext.mPrev = entry.mPrev;
                entry.mPrev.mNext = entry.mNext;
            }
     
            /* If the node is the one identified by its parent as its child,
             * we need to rewrite that pointer to point to some arbitrary other
             * child.
             */
            if (entry.mParent.mChild == entry) {
                /* If there are any other children, pick one of them arbitrarily. */
                if (entry.mNext != entry) {
                    entry.mParent.mChild = entry.mNext;
                }
                /* Otherwise, there aren't any children left and we should clear the
                 * pointer and drop the node's degree.
                 */
                else {
                    entry.mParent.mChild = null;
                }
            }
     
            /* Decrease the degree of the parent, since it just lost a child. */
            --entry.mParent.mDegree;
     
            /* Splice this tree into the root list by converting it to a singleton
             * and invoking the merge subroutine.
             */
            entry.mPrev = entry.mNext = entry;
            mMin = mergeLists(mMin, entry);
     
            /* Mark the parent and recursively cut it if it's already been
             * marked.
             */
            if (entry.mParent.mIsMarked)
                cutNode(entry.mParent);
            else
                entry.mParent.mIsMarked = true;
     
            /* Clear the relocated node's parent; it's now a root. */
            entry.mParent = null;
        }
        public static class Node {
        /**
         * first child node
         */
        int indice;
        Node m_child;
     
        /**
         * left sibling node
         */
        Node m_left;
     
        /**
         * parent node
         */
        Node m_parent;
     
        /**
         * right sibling node
         */
        Node m_right;
     
        /**
         * true if this node has had a child removed since this node was added
         * to its parent
         */
        boolean m_mark;
     
        /**
         * key value for this node
         */
        int m_key;
     
        /**
         * number of children of this node (does not count grandchildren)
         */
        int m_degree;
     
        /**
         * Default constructor.  Initializes the right and left pointers,
         * making this a circular doubly-linked list.
         *
         * @param key initial key for node
         */
        public Node() {}
        public Node(int key, int ind) {
          m_right = this;
          m_left = this;
          m_key = key;
          indice=ind;
        }
     
        /**
         * Obtain the key for this node.
         *
         * @return the key
         */
        public final int getKey() {
          return m_key;
        }
        public final int getindice(){
            return indice;
     
        }
     
        /**
         * Return the string representation of this object.
         *
         * @return string representing this object
         */
        public String toString() {
          if (true) {
            return Double.toString(m_key);
          } else {
            StringBuffer buf = new StringBuffer();
            buf.append("Node=[parent = ");
     
            if (m_parent != null) {
              buf.append(Double.toString(m_parent.m_key));
            } else {
              buf.append("---");
            }
     
            buf.append(", key = ");
            buf.append(Double.toString(m_key));
            buf.append(", degree = ");
            buf.append(Integer.toString(m_degree));
            buf.append(", right = ");
     
            if (m_right != null) {
              buf.append(Double.toString(m_right.m_key));
            } else {
              buf.append("---");
            }
     
            buf.append(", left = ");
     
            if (m_left != null) {
              buf.append(Double.toString(m_left.m_key));
            } else {
              buf.append("---");
            }
     
            buf.append(", child = ");
     
            if (m_child != null) {
              buf.append(Double.toString(m_child.m_key));
            } else {
              buf.append("---");
            }
     
            buf.append(']');
     
            return buf.toString();
          }
        }
     
        // toString
      }
    }

  4. #4
    Expert éminent sénior
    Avatar de tchize_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2007
    Messages
    25 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Avril 2007
    Messages : 25 481
    Points : 48 806
    Points
    48 806
    Par défaut
    Et les mesures?

  5. #5
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    Citation Envoyé par tchize_ Voir le message
    Tu pourrais nous montrer tous les chiffres de mesure que tu as obtenus?

    Faudrais voir aussi ton FIB là, parce que, si ça tombe, les méthodes n'ont pas la complexité annoncée
    Si j'ai bien compris votre question: Pour un graphe avec 300 noeuds, j'ai obtenu : le temps d'execution de Dijkstra classique :0.0080 secondes
    et le temps d'execution de Dijkstra avec les tas de Fibonacci est:0.015 sec

    Merci tchize

  6. #6
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    Voila un fichier qui contient les classes utilisées dans mon programme
    Fichiers attachés Fichiers attachés

  7. #7
    Expert éminent sénior
    Avatar de tchize_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2007
    Messages
    25 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Avril 2007
    Messages : 25 481
    Points : 48 806
    Points
    48 806
    Par défaut
    Citation Envoyé par helamal Voir le message
    Si j'ai bien compris votre question: Pour un graphe avec 300 noeuds, j'ai obtenu : le temps d'execution de Dijkstra classique :0.0080 secondes
    et le temps d'execution de Dijkstra avec les tas de Fibonacci est:0.015 sec

    Merci tchize
    Ce n'est pas comme ça qu'on mesure si un algo est O(n) ou O(n²)

    Il ne faut pas perdre de vue, quand on calcule les temps d'exécution en fonction de n qu'on laisse tomber systématiquement les facteurs multiplicatifs et les constantes.

    Ainsi, O(n) peut vouloir dire un temps de 1s *n alors que O(n²) peut vouloir dire 1ms * n²

    Suivant la valeur de n l'un ou l'autre sera plus rapide.

    Si tu veux vérifier que tes deux algos suivent bien les courbes respectivement O(n²) et o(m+logn) tu dois faire plusieurs mesures avec des n et des m différents (Par exemple en testant de 10 noeuds à 300.000 noeuds).

    En java, pour courser le tout, il faudra que tu fasse, à chaque étape, plusieurs mesures. Il y a pas mal d'optimisation dynamique en java qui peux interférer avec les mesures, tu dois donc faire une moyenne (non pas calculer combien de temps pour 300 noeuds, mais combien de temps 1000x 300 noeuds, divisé par 1000)

    Une fois que tu aura fais ça, tu peux dessiner les deux courbes de mesure obtenues et les comparer. Et là tu verra qu'elle se croisent. Un algo sera plus rapide à faibles noeuds et l'autre plus rapide à beaucoup de noeuds.

    Pour reprendre mon exemple:

    O(n) = 1s * n:

    • 10 noeuds: 10s
    • 100 noeuds: 1m40s
    • 1.000 noeuds: ~16 minutes
    • 10.000 noeuds: 2.7 heures
    • 100.000 noeuds: 27 heures


    0(n²) = 1ms * n²
    • 10 noeuds: 0.1s
    • 100 noeuds: 10s
    • 1.000 noeuds: ~16 minutes
    • 10.000 noeuds: 27 heures
    • 100.000 noeuds: presque 4 mois!!

  8. #8
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    Citation Envoyé par tchize_ Voir le message
    Ce n'est pas comme ça qu'on mesure si un algo est O(n) ou O(n²)

    Il ne faut pas perdre de vue, quand on calcule les temps d'exécution en fonction de n qu'on laisse tomber systématiquement les facteurs multiplicatifs et les constantes.

    Ainsi, O(n) peut vouloir dire un temps de 1s *n alors que O(n²) peut vouloir dire 1ms * n²

    Suivant la valeur de n l'un ou l'autre sera plus rapide.

    Si tu veux vérifier que tes deux algos suivent bien les courbes respectivement O(n²) et o(m+logn) tu dois faire plusieurs mesures avec des n et des m différents (Par exemple en testant de 10 noeuds à 300.000 noeuds).

    En java, pour courser le tout, il faudra que tu fasse, à chaque étape, plusieurs mesures. Il y a pas mal d'optimisation dynamique en java qui peux interférer avec les mesures, tu dois donc faire une moyenne (non pas calculer combien de temps pour 300 noeuds, mais combien de temps 1000x 300 noeuds, divisé par 1000)

    Une fois que tu aura fais ça, tu peux dessiner les deux courbes de mesure obtenues et les comparer. Et là tu verra qu'elle se croisent. Un algo sera plus rapide à faibles noeuds et l'autre plus rapide à beaucoup de noeuds.

    Pour reprendre mon exemple:

    O(n) = 1s * n:

    • 10 noeuds: 10s
    • 100 noeuds: 1m40s
    • 1.000 noeuds: ~16 minutes
    • 10.000 noeuds: 2.7 heures
    • 100.000 noeuds: 27 heures


    0(n²) = 1ms * n²
    • 10 noeuds: 0.1s
    • 100 noeuds: 10s
    • 1.000 noeuds: ~16 minutes
    • 10.000 noeuds: 27 heures
    • 100.000 noeuds: presque 4 mois!!
    Merci tchize pour la reponse.. Ce que vous dites me parait l'analyse la plus realiste que j'ai entendu concernant ce probleme.. mais puisque je suis debutante en java et c'est le premier code java que j'ai ecrit, j'ai trouvé quelques points ambigus..
    1/ comment je peux savoir le temps O(n²) est calculé par seconde ou ms.. d'ailleurs, j'ai précisé dans la fonction void main des deux algorithmes que le temps doit etre en seconde
    2/ j'ai fais beaucoup de test avec plusieurs mesures ( nombre de noeuds: 10, 50...2000 Noeuds et j'ai changé aussi le nombre d'arc), je peux pas dépasser les 2000 noeuds, sinon lors de l'execution, un message d'erreur apparait qui annonce que je dois pas depasser l'espace mémoire disponible. Bref, je voulais dire, qu'avec tous ces tests, l'algorithme DIjkstra classique s'execute en un temps inférieur au temps de dijkstra avec Fibonacci
    Vraiment c'est etonannant
    j'espere que vous m'avez compri et merci encore une fois

  9. #9
    Expert éminent sénior
    Avatar de tchize_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2007
    Messages
    25 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Avril 2007
    Messages : 25 481
    Points : 48 806
    Points
    48 806
    Par défaut
    Citation Envoyé par helamal Voir le message
    1/ comment je peux savoir le temps O(n²) est calculé par seconde ou ms..
    Tu ne peux pas, c'est jsute un exempel théorique, les calcul O sont des calcul d'ordre de grandeur, c'est tout. Après, tu fais des mesures pour connaitre les temps réels sur une machine précise.

    Tu peux aussi augmenter la mémoire (paramùètre -Xmx) pour avoir plus de noeuds. Après si t'as fais plusieurs mesure, faudrais nous donner tout tes chiffre (et s'assurer que tu a bien mesure comme je l'ai indiqué)
    l'algorithme DIjkstra classique s'execute en un temps inférieur au temps de dijkstra avec Fibonacci
    Vraiment c'est etonannant
    Rien d'étonnant, les calcul O permettent d'évaluer comment l'algo tiens la montée en charge, pas de déterminer exactement quel algo est le plus rapide.

  10. #10
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    Citation Envoyé par tchize_ Voir le message
    Tu ne peux pas, c'est jsute un exempel théorique, les calcul O sont des calcul d'ordre de grandeur, c'est tout. Après, tu fais des mesures pour connaitre les temps réels sur une machine précise.

    Tu peux aussi augmenter la mémoire (paramùètre -Xmx) pour avoir plus de noeuds. Après si t'as fais plusieurs mesure, faudrais nous donner tout tes chiffre (et s'assurer que tu a bien mesure comme je l'ai indiqué)

    Rien d'étonnant, les calcul O permettent d'évaluer comment l'algo tiens la montée en charge, pas de déterminer exactement quel algo est le plus rapide.
    ok c'est trop compliqué franchement !! bon j'ai deja des mesures disponibles maintenant avec un nombre de noeuds de 10 à 2000).. c'est suffisant?? je peux les envoyer maintenant ! et merci

  11. #11
    Modérateur

    Profil pro
    Inscrit en
    Septembre 2004
    Messages
    12 545
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2004
    Messages : 12 545
    Points : 21 601
    Points
    21 601
    Par défaut
    Citation Envoyé par helamal Voir le message
    ok c'est trop compliqué franchement !!
    Oui, là on est dans la science informatique, pas dans le copier/coller de trucs trouvés sur le net.
    C'est compliqué.

    Citation Envoyé par helamal Voir le message
    bon j'ai deja des mesures disponibles maintenant avec un nombre de noeuds de 10 à 2000).. c'est suffisant??
    Carrément pas. 2000 c'est pas vraiment différent de rien du tout, pour un ordinateur.
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  12. #12
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    Citation Envoyé par thelvin Voir le message
    Oui, là on est dans la science informatique, pas dans le copier/coller de trucs trouvés sur le net.
    C'est compliqué.



    Carrément pas. 2000 c'est pas vraiment différent de rien du tout, pour un ordinateur.
    Salut j'ai augmenté la mémoire (-Xmx512m) et ca me permet de traiter au max 10000 noeuds.. Les resultats de l'experimentation sont les suivants:

    nœuds arcs Temps (secondes)
    2000 50000 0,184
    4000 100000 0,733
    6000 300000 1,604
    8000 800000 2,951
    10000 1000000 4,696


    nœuds arcs Temps (s)
    2000 50000 0,055
    4000 100000 0,542
    6000 300000 1,139
    8000 800000 2,32
    10000 1000000 3,603

  13. #13
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    Citation Envoyé par tchize_ Voir le message
    Tu ne peux pas, c'est jsute un exempel théorique, les calcul O sont des calcul d'ordre de grandeur, c'est tout. Après, tu fais des mesures pour connaitre les temps réels sur une machine précise.

    Tu peux aussi augmenter la mémoire (paramùètre -Xmx) pour avoir plus de noeuds. Après si t'as fais plusieurs mesure, faudrais nous donner tout tes chiffre (et s'assurer que tu a bien mesure comme je l'ai indiqué)

    Rien d'étonnant, les calcul O permettent d'évaluer comment l'algo tiens la montée en charge, pas de déterminer exactement quel algo est le plus rapide.
    Salut j'ai augmenté la mémoire (-Xmx512m) et ca me permet de traiter au max 10000 noeuds.. Les resultats de l'experimentation sont les suivants:

    nœuds arcs Temps (secondes)
    2000 50000 0,184
    4000 100000 0,733
    6000 300000 1,604
    8000 800000 2,951
    10000 1000000 4,696


    nœuds arcs Temps (s)
    2000 50000 0,055
    4000 100000 0,542
    6000 300000 1,139
    8000 800000 2,32
    10000 1000000 3,603

  14. #14
    Expert éminent sénior
    Avatar de tchize_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2007
    Messages
    25 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Avril 2007
    Messages : 25 481
    Points : 48 806
    Points
    48 806
    Par défaut
    Et bien, on peux constater deux choses:

    1 ta première série augmente moins vite que la deuxième
    2 da tous les cas, l'algo non optimisé est le plus rapide pour la quantité de donnée que ta mémoire est capable de gérer.

  15. #15
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    Citation Envoyé par tchize_ Voir le message
    Et bien, on peux constater deux choses:

    1 ta première série augmente moins vite que la deuxième
    2 da tous les cas, l'algo non optimisé est le plus rapide pour la quantité de donnée que ta mémoire est capable de gérer.
    j'ai oublié de preciser chaque experimentation appartient à quel algo:
    1/ Algorithme de Dijkstra classique : complexité theorique :O(n²)

    nœuds arcs Temps (secondes)
    2000 50000 0,184
    4000 100000 0,733
    6000 300000 1,604
    8000 800000 2,951
    10000 1000000 4,696

    2/ Algo de Dijkstra avec Fibonacci: Complexité theorique: O(m+n log n)

    nœuds arcs Temps (s)
    2000 50000 0,055
    4000 100000 0,542
    6000 300000 1,139
    8000 800000 2,32
    10000 1000000 3,603


    D'après cette experimentation, j'ai remarqué que dans les cas où le nombre des noeuds est inferieur à 2000, l'algo de Dijkstra fini avec un temps d'execution inferieur à celui de Dijkstra avec Fibonacci.. Par contre, pour un nombre des noeuds superieur à 2000, le temps d'execution de Dijkstra avec Fibonacci sera plus rapide que l'autre algo...
    de plus, je veux savoir si cette experimentation reflete vraiment la complexité theorique et merci

  16. #16
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    est ce que je peux augmenter la taille de stockage dans les fichiers documents texte.; je cherche à inserer une matrice de 10000 lignes et colonnes par exp dans un fichier pour que mon algorithme la traite plus tard, mais la taille de stockage des fichiers est limitée.. des proposition svp ?

  17. #17
    Expert éminent sénior
    Avatar de tchize_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2007
    Messages
    25 481
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Avril 2007
    Messages : 25 481
    Points : 48 806
    Points
    48 806
    Par défaut
    Citation Envoyé par helamal Voir le message
    mais la taille de stockage des fichiers est limitée.. des proposition svp ?
    Non, la taille des fichiers n'est pas limitée en java.

    Bien sur, une fat32 a une taille limite (1G si ma mémoire est bonne) mais NTFS / ext3, reiserfs, etc ne l'ont pas.

    Si tu as une limitation dans ton programme c'est surement que tu essaie de garder tout ton fichier en mémoire d'un coup.

  18. #18
    Futur Membre du Club
    Femme Profil pro
    Analyse système
    Inscrit en
    Décembre 2011
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : Analyse système
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2011
    Messages : 14
    Points : 6
    Points
    6
    Par défaut
    est ce possible de comparer deux algorithmes avec deux matrices differentes mais qui ont le meme nombre de noeuds et d'arcs.. est ce que la comparaison sera correcte ??? puisque je veux une comparaison basé sur des matrices de grandes tailles, et j'arrive pas à stocker des telles matrices dans aucune Variable!.. Merci

  19. #19
    Modérateur
    Avatar de wax78
    Homme Profil pro
    Chef programmeur
    Inscrit en
    Août 2006
    Messages
    4 072
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Belgique

    Informations professionnelles :
    Activité : Chef programmeur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2006
    Messages : 4 072
    Points : 7 974
    Points
    7 974
    Par défaut
    Citation Envoyé par tchize_ Voir le message
    Bien sur, une fat32 a une taille limite (1G si ma mémoire est bonne) mais NTFS / ext3, reiserfs, etc ne l'ont pas.
    Ca dépend du nombre de secteurs par cluster choisis lors de la création de la partition non ?
    (Les "ça ne marche pas", même écrits sans faute(s), vous porteront discrédit ad vitam æternam et malheur pendant 7 ans)

    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  20. #20
    Membre chevronné
    Inscrit en
    Mai 2006
    Messages
    1 364
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 1 364
    Points : 1 984
    Points
    1 984
    Par défaut
    Citation Envoyé par wax78 Voir le message
    Ca dépend du nombre de secteurs par cluster choisis lors de la création de la partition non ?
    Sauf erreur de ma part, c'est la taille de la partition qui dépend de la taille des clusters. Ca ne change pas la limite de taille de fichier qui doit etre de 2^32=4Go...

Discussions similaires

  1. Réponses: 4
    Dernier message: 26/03/2006, 00h05
  2. Dijkstra chemins disjoints??
    Par daliz dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 12/01/2006, 17h14
  3. Dijkstra: optimisation?
    Par Zogzog4 dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 15/11/2005, 13h56
  4. Suite de Fibonacci
    Par Évariste Galois dans le forum C++
    Réponses: 13
    Dernier message: 22/07/2005, 22h21
  5. algo de Dijkstra (+ court chemin d'un labyrinthe)
    Par gg14bis dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 25/03/2005, 09h57

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo