Changeset 787685 in git


Ignore:
Timestamp:
May 14, 2009, 10:47:01 AM (14 years ago)
Author:
Christian Eder
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a657104b677b4c461d018cbf3204d72d34ad66a9')
Children:
cef7eedebae73877347e466c8c9eea48e5da8b11
Parents:
21cb46b885ab1b05f213bba73b625f4c6a4ad9e8
Message:
insertion of rules ordered by their monomials, bit slower than without sorting


git-svn-id: file:///usr/local/Singular/svn/trunk@11802 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
kernel
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • kernel/f5gb.cc

    r21cb46 r787685  
    597597                                                        reductionsToZero++;
    598598                        //Print("IN SPOLS 1\n");
    599                             rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     599                            Rule* rNew  =  new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     600                            rules->insertOrdered(rNew);
     601                            //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    600602                            //Print("RULE ADDED: \n");
    601603                            //pWrite(rules->getFirst()->getRuleTerm());
    … …  
    607609                        else {
    608610                        //Print("IN SPOLS 2\n");
    609                             rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     611                            Rule* rNew  =  new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     612                            rules->insertOrdered(rNew);
     613                            //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    610614                            //Print("RULE ADDED: \n");
    611615                            //pWrite(rules->getFirst()->getRuleTerm()); 
    612616                            //rules->print();
    613                             sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
     617                            //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
     618                            sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rNew);
    614619                        }
    615620                        // data is saved in sPolyList or zero => delete sp
    … …  
    641646                    else {
    642647                        //Print("IN SPOLS 4\n");
    643                         rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     648                       
     649                        //////////////////////////////////////////////////////////
     650                        //////////////////////////////////////////////////////////
     651                        // TODO: Rules inserted ordered by their label monomial!//
     652                        //////////////////////////////////////////////////////////
     653                        //////////////////////////////////////////////////////////
     654
     655                        Rule* rNew      =   new Rule(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
     656                        //RNode* rNodeNew =   new RNode(rNew);
     657                        rules->insertOrdered(rNew);
     658                        //rules->insert(temp->getLp1Index(),ppMult_qq(temp->getT1(),temp->getLp1Term()));
    644659                        //Print("RULE ADDED: \n");
    645660                        //pWrite(rules->getFirst()->getRuleTerm());
    … …  
    647662                        //Print("%d\n",rules->getFirst()->getRuleIndex());
    648663                        //Print("%p\n",sPolyList->getFirst());
    649                         sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
     664                        //sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rules->getFirst()->getRule());
     665                        sPolyList->insertByLabel(ppMult_qq(temp->getT1(),temp->getLp1Term()),temp->getLp1Index(),sp,rNew);
    650666                    }
    651667                }
    … …  
    795811    while(NULL != tempMon) {
    796812        // iteration over all monomials in tempMon
    797         //tempPoly    =   pCopy(l->getPoly());
    798         //tempPoly    =   tempMon->getPoly();
    799         //pWrite(tempPoly);
    800         //Print("______________________NEW POLYNOMIAL TESTED IN MONOMIALS_______________________\n");
    801813        //kBucket* bucket  =   kBucketCreate();
    802814        //kBucketInit(bucket,tempPoly,0);
    803815        //tempPoly    =   kBucketGetLm(bucket);
    804         //pWrite(tempPoly);
    805816        while(NULL != tempPoly) {
    806817            // iteration of all elements in gPrev of the current index
    807            
    808             //Print("LABEL OF REDUCED ELEMENT:    ");
    809             //Print("%p\n",tempPoly);
    810             //pWrite(tempPoly);
    811             //Print("RED\n");
    812             //Print("L:  ");
    813             //pWrite(l->getPoly());
    814             //pNorm(tempPoly);
    815             //pWrite(l->getTerm());
    816818            tempRed =   gPrev->getFirst();
    817             //tempRed =   lTag->getFirstCurrentIdx();
    818819            while(NULL != tempRed) {
    819                 //Print("POSSIBLE REDUCER:  ");
    820                 //pWrite(tempRed->getPoly());
    821                 //pWrite(tempRed->getTerm());
    822                 //Print("TO BE REDUCED:     ");
    823                 //pWrite(tempPoly);
    824                 //Print("DIVISIBLE? %d\n",pDivisibleBy(tempRed->getPoly(),tempPoly));
    825820                if(pLmDivisibleByNoComp(tempRed->getPoly(),tempPoly)) {
    826821                    u   =   pDivideM(pHead(tempPoly),pHead(tempRed->getPoly()));
    827                     //number n    =  pGetCoeff(tempPoly) / pGetCoeff
    828                     //Print("U: ");
    829                     //pWrite(u);
    830                     //pSetCoeff(u,nOne);
    831                     //pWrite(u);
    832                     //poly red =   ppMult_qq(u,tempRed->getPoly());
    833                     //pNorm(red);
    834                     //pWrite(red);
    835                     // check if both have the same label
    836822                    if(tempRed->getIndex() != l->getIndex()) {
    837823                            // passing criterion1 ?
    838824                            if(!criterion1(gPrev,u,tempRed,lTag)) {
    839                                     //Print("TO BE REDUCED:     ");
    840                                     //pWrite(tempPoly);
    841                                     //Print("REDUCER: ");
    842                                     //pWrite(tempRed->getPoly());
    843                                     //pWrite(ppMult_qq(u,tempRed->getPoly()));
    844                                     //pWrite(ppMult_qq(u,tempRed->getTerm()));
    845                                     //Print("%d\n",tempRed->getIndex());
    846                                     //Print("+++++++++++++LIST OF MONOMIALS1+++++++++++++++++\n");
    847                                     //poly tempRedPoly    =  ksOldSpolyRedNew(ppMult_qq(u,tempRed->getPoly()),pHead(ppMult_qq(u,tempRed->getPoly())));
    848825                                    poly tempRedPoly    =   tempRed->getPoly();
    849                                     //Print("TEMPREDPOLY: \n");
    850                                     //pWrite(tempRedPoly);
    851826                                    pIter(tempRedPoly);
    852                                     //pWrite(tempRedPoly);
    853                                     //Print("U: ");
    854                                     //pWrite(u);
    855827                                    tempRedPoly =   ppMult_qq(u,tempRedPoly);
    856                                     //Print("TEMPPOLYRED\n");
    857                                     //pWrite(tempRedPoly);
    858828                                    pMult_nn(tempRedPoly,sign);
    859                                     //pWrite(tempRedPoly);
    860                                     // throw away head monomial as it cancels when computing "bucket - u * tempRedPoly"
    861                                     //Print("MULTIPLICATION DONE: \n");
    862                                     //pWrite(tempRedPoly);
    863                                     //pWrite(ppMult_qq(u,tempRed->getPoly()));
    864                                     //int lRedPoly   =   pLength(tempRedPoly);
    865                                     //kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lRedPoly);
    866                                     //pWrite(tempPoly);
    867                                     //pWrite(tempRedPoly);
    868829                                    pAdd(tempPoly,tempRedPoly);
    869                                     //Print("MERGED POLYNOMIAL: ");
    870                                     //pWrite(tempPoly);
    871                                     //Print("REDUCTION STEP: \n");
    872                                     //pWrite(l->getPoly());
    873                                     //l->setPoly(pSub(l->getPoly(),ppMult_qq(u,tempRed->getPoly())));
    874                                     //pNorm(tempRedPoly);
    875                                     //pWrite(l->getPoly());
    876                                     //monomials->insert(ppMult_qq(u,tempRed->getTerm()), tempRed->getIndex(), tempRedPoly,NULL);
    877                                     //Print("+++++++++++++LIST OF MONOMIALS2+++++++++++++++++\n");
    878                                     //monomials->print();
    879 
    880830                                    good->insert(pOne(),1,ppMult_qq(u,tempRed->getPoly()),NULL);
    881                                     //Print("GOOD ELEMENTS: \n");
    882                                     //Print("%p\n",good->getFirst());
    883                                     //good->print();
    884831                                    break;
    885832                             }   
    … …  
    894841                                if(pLmCmp(ppMult_qq(u,tempRed->getTerm()),l->getTerm()) == 1) {
    895842                                    //Print("BAD REDUCTION STUFF\n");
    896                                     //pWrite(ppMult_qq(u,tempRed->getPoly()));
    897                                     //pWrite(ppMult_qq(u,tempRed->getTerm()));
    898                                     //rules->print();
    899                                     //rules->insert(tempRed->getIndex(),ppMult_qq(u,tempRed->getTerm()));
    900                                     //l->setTerm(ppMult_qq(u,tempRed->getTerm()));
    901                                     //l->setRule(rules->getFirst()->getRule());
    902                                     //poly tempRedPoly    =  ksOldSpolyRedNew(ppMult_qq(u,tempRed->getPoly()),pHead(ppMult_qq(u,tempRed->getPoly())));
    903                                     //pAdd(tempPoly,tempRedPoly);
    904                                     //Print("NEW TERM: ");
    905                                     //pWrite(l->getTerm());
    906                                     //Print("\n\nRules:\n");
    907                                     //rules->print();
    908843                                    bad->insert(tempRed->getLPoly());
    909                                     //good->insert(pOne(),1,ppMult_qq(u,tempRed->getPoly()),NULL);
    910                                     //pWrite(tempRed->getPoly());
    911                                     //sleep(5);
    912844                                    break;
    913845                                }
    914846                                else {
    915                                     //Print("TO BE REDUCED:     ");
    916                                     //pWrite(tempPoly);
    917                                     //Print("REDUCER: ");
    918                                     //pWrite(tempRed->getPoly());
    919                                     //pWrite(ppMult_qq(u,tempRed->getPoly()));
    920                                     //pWrite(ppMult_qq(u,tempRed->getTerm()));
    921                                     //Print("%d\n",tempRed->getIndex());
    922                                     //Print("+++++++++++++LIST OF MONOMIALS1+++++++++++++++++\n");
    923                                     //pIter(tempRedPoly);
    924847                                    poly tempRedPoly    =   tempRed->getPoly();
    925                                     // throw away head monomial as it cancels when computing "bucket - u * tempRedPoly"
    926848                                    pIter(tempRedPoly);
    927849                                    tempRedPoly =   ppMult_qq(u,tempRedPoly);
    928850                                    pMult_nn(tempRedPoly,sign);
    929                                     //Print("HERE\n");
    930                                     //int lRedPoly    =   pLength(tempRedPoly);
    931                                     //kBucket_Minus_m_Mult_p(bucket,u,tempRedPoly,&lRedPoly);
    932                                     //poly tempRedPoly    =  ksOldSpolyRedNew(ppMult_qq(u,tempRed->getPoly()),pHead(ppMult_qq(u,tempRed->getPoly())));
    933                                     timerRed    =   initTimer();
    934                                     startTimer();
     851                                    //timerRed    =   initTimer();
     852                                    //startTimer();
    935853                                    pAdd(tempPoly,tempRedPoly);
    936                                     timerRed    =   getTimer();
    937                                     reductionTime   = reductionTime + timerRed;
    938                                     //Print("MERGED POLYNOMIAL: ");
    939                                     //pWrite(tempPoly);
    940                                     //Print("REDUCTION STEP: \n");
    941                                     //pWrite(l->getPoly());
    942                                     //l->setPoly(pSub(l->getPoly(),ppMult_qq(u,tempRed->getPoly())));
    943                                     //pNorm(tempRedPoly);
    944                                     //pWrite(l->getPoly());
    945                                     //monomials->insert(ppMult_qq(u,tempRed->getTerm()), tempRed->getIndex(), tempRedPoly,NULL);
    946                                     //Print("+++++++++++++LIST OF MONOMIALS2+++++++++++++++++\n");
    947                                     //monomials->print();
     854                                    //timerRed    =   getTimer();
     855                                    //reductionTime   = reductionTime + timerRed;
    948856                                    good->insert(pOne(),l->getIndex(),ppMult_qq(u,tempRed->getPoly()),NULL);
    949                                     //Print("GOOD ELEMENTS: \n");
    950                                     //Print("%p\n",good->getFirst());
    951                                     //good->print();
    952857                                    break;
    953858                                }
    … …  
    959864                }
    960865                tempRed =   tempRed->getNext();
    961                 //Print("HERE TOO\n");
    962                 //pWrite(tempRed->getPoly());
    963             }
    964             //pWrite(tempPoly);
     866            }
    965867            pIter(tempPoly);
    966             //Print("ITERATION\n");
    967             //Print("L:  ");
    968             //pWrite(l->getPoly());
    969             //Print("ITERATION:  ");
    970             //pWrite(tempPoly);
    971868        }
    972869       
    973870        tempMon =   tempMon->getNext();
    974         //Print("NEXT ELEMENT TO BE REDUCED:   ");
    975         //if(NULL != tempMon) {
    976         //    pWrite(tempMon->getPoly());
    977         //}
    978         //else {
    979         //    Print("NICHTS MEHR DA\n");
    980         //}
    981871    }
    982872                // if there are reducers than reduce l

  • kernel/f5lists.cc

    r21cb46 r787685  
    880880    newElement->next    =   this;
    881881    return newElement;
    882    
    883     /*
    884      * not useful, as it does not only adds new rules to be tested but also
    885      * deletes rules to be tested if a rule is set to another place in the line
    886      *
    887     if(NULL == this || this->getRuleIndex() < newElement->getRuleIndex()) {
    888         newElement->next    =   this;
     882}
     883
     884
     885RNode* RNode::insertOrdered(Rule* r) {
     886    RNode* newElement   =   new RNode(r);
     887    RNode* temp         =   this;
     888    if(NULL == temp) {
     889        newElement->next =   temp;
     890        return newElement;
     891    }
     892    if(1 == pLmCmp(newElement->getRuleTerm(),temp->getRuleTerm())) {
     893        newElement->next =   temp;
     894        return newElement;
    889895    }
    890896    else {
    891         if(pDeg(newElement->getRuleTerm()) > pDeg(this->getRuleTerm())) {
    892                 newElement->next    =   this;
    893         }
    894         if(-1 == pLmCmp(newElement->getRuleTerm(),this->getRuleTerm())) {
    895             Print("HAHI\n");
    896             Print("%ld\n",pDeg(newElement->getRuleTerm()));
    897             Print("%ld\n",pDeg(this->getRuleTerm()));
    898            
    899             pWrite(newElement->getRuleTerm());
    900             pWrite(this->getRuleTerm());
    901             RNode* temp    =   this;
    902             while(NULL != temp->next && pDeg(newElement->getRuleTerm()) <= pDeg(temp->next->getRuleTerm())
    903                     && -1 == pLmCmp(newElement->getRuleTerm(),temp->next->getRuleTerm())) {
    904                 temp    =   temp->next;
    905             }
    906             newElement->next    =   temp->next;
    907             temp->next          =   newElement;
    908             return this;
    909         }
    910         else {
    911             newElement->next    =   this;
    912             return newElement;
    913         }
    914     }
    915     return newElement;
    916     */
    917 }
     897        while(NULL != temp && 1 ==  pLmCmp(temp->getRuleTerm(),newElement->getRuleTerm())) {
     898            temp    =   temp->getNext();
     899            Print("HIER\n");
     900        }
     901        newElement->next =   temp;
     902        return this;
     903    }
     904}
     905
    918906
    919907RNode* RNode::getNext() {
    … …  
    981969}
    982970
     971void RList::insertOrdered(Rule* r) {
     972    first   =   first->insertOrdered(r);
     973}
     974
    983975RNode* RList::getFirst() {
    984976    return first;

  • kernel/f5lists.h

    r21cb46 r787685  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5lists.h,v 1.19 2009-05-13 16:55:03 ederc Exp $ */
     4/* $Id: f5lists.h,v 1.20 2009-05-14 08:47:01 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
    … …  
    265265        RNode*  insert(Rule* r);
    266266        RNode*  insert(int i, poly t);
     267        RNode*  insertOrdered(Rule* r);
    267268        RNode*  getNext();
    268269        Rule*   getRule();
    … …  
    288289        void    insert(Rule* r);
    289290        void    insert(int i, poly t);
     291        void    insertOrdered(Rule* r);
    290292        RNode*  getFirst();
    291293        Rule*   getRule();
Note: See TracChangeset for help on using the changeset viewer.