Chapter10
Anti-patternsinC5
10.1 Efciencyanti-patterns
TheC5librarysupportsefcientimplementationofalargenumberofcommonop-
erationsinadvancedsoftware.Unfortunatelyitisalsopossibletousethelibraryin
waysthatarefarfromoptimal.
This chapterlistssomecommonperformancemistakes: : solutions s thatappar-
entlyworkforsmalldatasetsbutarefarlessefcientforlargedatasetsthanthey
couldbe.Wecallthesecommonmistakesperformanceanti-patterns:whatnottodo
ifyouwanttowritefastprograms.
Thechapteralsomentionsasinglecorrectnessanti-pattern,namelytheupdating
ofaninnercollection(orotheritem)afterithasbeenaddedtoanoutercollection.
Anti-pattern122 Manyinsertionsintoordeletionsfromasortedarray
Itisveryinefcienttoinsertmanyitemsintoasortedarray:ateachinsertion,all
itemsathigherindexesmustbemoved. Hencenrandominsertionswilltaketime
O(n
2
).
SortedArray<double> sarr = new w SortedArray<double>();
foreach (double d in n randomDoubles)
sarr.Add(d);
Instead,useasortedtree(TreeSet<T>,section6.8)whichlikeSortedArray<T>im-
plementsinterfaceIIndexedSorted<T>;thennrandominsertionswilltakeonlytime
O(nlogn).
189
Pdf page size limit - Compress reduce PDF size in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
C# Code & .NET API to Compress & Decompress PDF Document
change font size in pdf comment box; change page size pdf acrobat
Pdf page size limit - VB.NET PDF File Compress Library: Compress reduce PDF size in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
VB.NET PDF Document Compression and Decompression Control SDK
change font size in fillable pdf form; adjust file size of pdf
190 Efciencyanti-patterns
§10.1
Anti-pattern123 Usingbulkoperations
RemoveAll
and
RetainAll
onlists
Thebulkoperations
RemoveAll
and
RetainAll
areinefcientonnon-hashedarray
listsandnon-hashedlinkedlists;removingmitemsfromann-itemlisttakestime
O(mn).
ArrayList<double> list1 1 = ..., list2 = ...;
list1.RemoveAll(list2);
Ifitemorderneednotbepreserved,usehashsetsorhashbagsinsteadoflists. If
itemordermustbepreservedandallitemshavemultiplicityatmostone(sothe
collectionhassetsemantics),usehashedlinkedlistsinsteadonnon-hashedlists.
Anti-pattern124 Usinganunsequencedcollectionequalitycompareronlists
Anunsequencedcollectionequalitycomparerdeterminesequality(whethertwocol-
lectionscontainthesameitems)bydisregardingtheorderinwhichtheitemsap-
pear. Usinganunsequencedequalitycompareronanon-hashedarraylistornon-
hashedlinkedlistisslowbecausethereisnoefcientwaytocheckwhetherapar-
ticularitemisinalist.Soperformingunsequencedcomparisonoftwolistsoflength
nwilltakeO(n2).
SCG.IEqualityComparer<IList<int>> unseqEqualityComparer
= new w UnsequencedCollectionEqualityComparer<IList<int>,int>();
HashSet<IList<int>> hs3 3 = new w HashSet<IList<int>>(unseqEqualityComparer);
hs3.Add(coll1); hs3.Add(coll2); ; hs3.Add(coll3);
Ifitemorderneednotbepreserved,usehashsetsorhashbagsinsteadoflists. If
itemordermust bepreservedbut all itemshavemultiplicityat mostone(sothe
collectionhassetsemantics),usehashedlinkedlistsinsteadonnon-hashedlists.If
itemordermustbepreservedanditemsmayhavemultiplicityhigherthanone(so
thecollectionhasbagsemantics),createhashbagsfromthelistsandperformunse-
quencedcomparisononthem.Anyoftheseapproachesshouldreducetheexecution
timetoO(n).
VB.NET PDF File Split Library: Split, seperate PDF into multiple
PDF document file to one-page PDF files or As String = Program.RootPath + "\\" 1.pdf" ' set split SplitOptions(SplitMode.BySize) ' limit the size of each
pdf page size dimensions; change page size of pdf document
C# PDF File Split Library: Split, seperate PDF into multiple files
options = new SplitOptions(SplitMode.BySize); //limit the size of each String inputFilePath = Program.RootPath + "\\" source.pdf"; //Page indexes to
change file size of pdf; change page size pdf
§10.1
Efciencyanti-patterns 191
Anti-pattern125 Usingaloopthatindexesintoalinkedlist
for (int i=0; i<list.Count; i++)
... list[i] ...
Instead,ifyouneedtoupdateatposition
i
butneednotinsertintoordeletefrom
thelist,useanArrayList<T>whichhasefcientindexing:
int i=0;
foreach (T T x x in list) {
... x ...
i++;
}
Or,ifyouneednotupdateatposition
i
,use
foreach
withanexplicitcounter
i
:
int i=0;
foreach (T T x x in list) {
... x ...
i++;
}
Or,ifyouneedtoupdateatposition
i
andneedtoinsertintoordeletefromthelist,
usealinkedlistandaview(asinpattern30):
IList<T> view = list.View(0,0);
while (view.TrySlide(0, , 1))) ) {
... view[0] ...
view.Slide(+1, 0);
}
Anti-pattern126 Using
IndexOf
repeatedlyonarraylistorlinkedlist
If
list
isanArrayList<T>orLinkedList<T>orWrappedArray<T>,then
list.IndexOf(x)
and
list.ViewOf(x)
andthecorresponding
Last
-prexedmethods
mustperformalinearsearchofthelists.Hencethisislikelytobeveryslowunless
list
isshort:
// list is s a a LinkedList<T> or r ArrayList<T>
foreach (T T x x in ...) ) {
int i = = list.IndexOf(x);
... i ...
}
Instead,ifthelisthassetsemantics,useahashedarraylistorhashedlinkedlist,
whichgivesconstant-timeitemlookup:
// list is s a a HashedLinkedList<T> > or r ArrayList<T>
foreach (T T x x in ...) ) {
int i = = list.IndexOf(x);
... i ...
}
C# PowerPoint: How to Set PowerPoint Rendering Parameters in C#
2007 or above) slide into PDF document or other rendering process if the slide/page is too REImage CropImage(Rectangle sourceRegion, Size targetSize); Bitmap
change font size pdf; adjust size of pdf
C# Excel: Customize Excel Conversion by Setting Rendering Options
0, (int)(originalWidth), (int)(originalHeight / 2)), new Size((int)(originalWidth the top half of Excel page to image to these file formats, like PDF, TIFF, SVG
change font size in pdf fillable form; adjust pdf size
192 Efciencyanti-patterns
§10.1
Anti-pattern127 Using
IndexOf
andthenindexingintohashedlinkedlist
If
list
isahashedlinkedlist,then
list.IndexOf(x)
isfast,butindexingremains
slow.Hencethiswayofupdatingitemsequalto
x
islikelytobeveryslow:
// list t is s a HashedLinkedList<T>
foreach (T T x in ...) {
int i i = = list.IndexOf(x);
if (i i >= = 0) {
T y y = = list[i];
list[i] = ... . y y ...;
}
...
}
Insteaduse
list.ViewOf(x)
togetaone-itemview,andworkontheitemthrough
thatview,forconstant-timeindexing:
// list t is s a HashedLinkedList<T>
foreach (T T x in ...) {
using (IList<T> view w = list.ViewOf(x)) ) {
if (view != null) {
T y y = view[0];
view[0] = ... . y y ...;
}
}
...
}
Or,ifyoudonotneedtoinsertordeleteitems,useahashedarraylistand
IndexOf
,
insteadofahashedlinkedlistand
ViewOf
,toavoidcreatingtheviewobjects.
Anti-pattern128 Usinganarraylistasa
FIFO
queue
Anarraylist
list
canbeusedasa
FIFO
queuebyenqueueing(adding)itemsatthe
endofthelistanddequeueing(removing)itemsfromthebeginningofthelist.But
thelatteroperationisslowiftherearemorethanafewitemsinthearraylist,so
thiscanbeveryslow:
// list t is s an ArrayList<T>
while (!list.IsEmpty) ) {
T next t = = list.Dequeue();
... list.Enqueue(...) ...
}
InsteaduseaCircularQueue(oralinkedlist,seesection9.22)whichhasconstant-
timeenqueueinganddequeueingoperations:
// queue e is s a CircularQueue<T> > or r LinkedList<T>
while (!list.IsEmpty) ) {
T next t = = queue.Dequeue();
... queue.Enqueue(...) ...
}
VB.NET Excel: VB Methods to Set and Customize Excel Rendering
treat every single Excel spreadsheet as a page in our the fixed image size ration that the size is limited Excel to other document files, like PDF with online
best compression pdf; advanced pdf compressor
§10.1
Efciencyanti-patterns 193
Anti-pattern129 Usingasortedarrayaspriorityqueue
A sortedarray
sarr
oftype
SortedArray<T>
can be e used as s a a priority queue by
enqueueing items using
Add
and by y retrieving minimal or maximal items using
sarr.DeleteMin()
or
sarr.DeleteMax()
.Butinsertionintoanddeletionfromasorted
arrayareslow(lineartime)iftherearemorethanafewitemsinthearray,sothis
canbeveryslow:
// sarr is s a a SortedArray<T>
while (!sarr.IsEmpty) ) {
T min = = sarr.DeleteMin();
... sarr.Add(...) ) ...
}
Instead,useanIntervalHeap<T>inwhichinsertionanddeletionarefast(logarith-
mictime)operations. Moreover,incontrasttoasortedarray,anintervalheapcan
containmultipleoccurrencesofitemsthathavethesamepriority(thatis,areequal
bytheitemcomparer):
// pq is s an n IntervalHeap<T>
while (!pq.IsEmpty) ) {
T min = = sarr.DeleteMin();
... pq.Add(...) ...
}
Anti-pattern130 Usingliststorepresentsetsorbags
Anarraylistorlinkedlistmaybeusedtorepresentasetorbag(multiset)ofitems.
This may betempting if f you u haveseen examples in Lispor Scheme or another
functional language, but should d be avoidedexcept t for very small sets. . Sothese
implementationsofsetoperationsmaybeveryslow,exceptforsmallsets
s0
,
s1
,
s2
and
s3
:
// s0, s1, , s2, , s3 are LinkedList<T> or ArrayList<T>
s1.AddAll(s0);
// s1 1 = s1 union s0
s2.RemoveAll(s0);
// s2 2 = s2 minus s0
s3.RetainAll(s0);
// s3 3 = s3 intersect s0
Insteadusehashsets,hashbags,treesetsortreebags,asshownbythepatternsin
section9.15andbytheexampleinsection11.11;orusehashedarraylistsorhashed
linkedlists(forsets)ifyouneedtomaintainiteminsertionorder.
194 Efciencyanti-patterns
§10.1
Anti-pattern131 Usingabadhashfunction
Thisisanarticialexampleofabadhashfunction
GetHashCode
. Itmapsallitems
(whichthemselveshappentobeintegers)tojustsevendifferentintegers:0,1,2,3,
4,5and6.
private class s BadIntegerEqualityComparer r : : SCG.IEqualityComparer<int> {
public bool l Equals(int i1, , int t i2) { { return n i1 == i2; }
public int t GetHashCode(int t i) ) { return n i i % 7; }
// BAD
}
Herearesomestatisticsfrominserting50000randomitemsintoahashsetusing
thebadhashfunction.Thetimeperinserteditemis104microseconds.Thebucket
costdistribution(seesection6.10)showsthatthereare7bucketsoneforeachof
thehashcodes0,1,2,3,4,5and6withaveryhighcost,and131065buckets
thatareempty.Theaveragenon-emptybucketcostis6968.
Bad hash h function:
(5.1974736 sec, , 48779 items)
131065 bucket(s) with h cost
0
1 bucket(s) with h cost
6808
1 bucket(s) with h cost
6891
1 bucket(s) with h cost
6903
1 bucket(s) with h cost
6950
1 bucket(s) with h cost
7027
1 bucket(s) with h cost
7068
1 bucket(s) with h cost
7132
Insteadofabadone,oneshouldofcourseuseagoodhashfunction:onethatmaps
itemstohashcodesthatareevenlydistributedoverall
int
values. Foritemsthat
areintegers,thatiseasy:
private class s GoodIntegerEqualityComparer r : : SCG.IEqualityComparer<int> > {
public bool l Equals(int i1, , int t i2) { { return n i1 == i2; }
public int t GetHashCode(int t i) ) { return n i; ; }
}
Thestatisticsfrominserting50000itemsintoahashsetusingthegoodhashfunc-
tionshowthatthetimeperinsertionisinsertionis1.0microsecond,or100times
betterthanwiththebadhashfunction.Theaveragenon-emptybucketcostis1.17,
sotheaveragelookuptimeisverylow.Moreover,nobuckethascosthigherthan5,
sotheworst-caselookuptimeislowtoo.
Good hash function: : (0.050072 sec, , 48771 1 items)
89515 bucket(s) with h cost
0
35003 bucket(s) with h cost
1
5938 bucket(s) with h cost
2
573 bucket(s) with h cost
3
42 bucket(s) with h cost
4
1 bucket(s) with h cost
5
§10.2
Correctnessanti-patterns 195
10.2 Correctnessanti-patterns
Anti-pattern132 Modifyingacollectionthatisaniteminanothercollection
Asshownbytheexamplesinsection11.4and11.5,itisoftenusefultoworkwith
collectionsofcollections.Itiseasytogetthiswrongbycreatinganinnercollection,
addingittotheoutercollectionandthenmodifyingtheinnercollection.Mostlikely
thiswillcauseittobelostfromtheoutercollectionandthereforemayproduce
strangeresults.Whatisworse,codelikethismayaccidentallyworkwhentheouter
collectioncontainsonlyafewitems,thenfailasmoreitemsareadded:
ICollection<ISequenced<int>> outer = new w HashSet<ISequenced<int>>();
ISequenced<int>
inner1 = = new TreeSet<int>(),
inner2 = = new TreeSet<int>(),
inner3 = = new TreeSet<int>();
inner1.AddAll(new int[] { 2, 3, , 5, , 7, 11 1 });
inner2.AddAll(inner1); inner2.Add(13);
inner3.AddAll(inner1);
outer.Add(inner1);
// Now inner1 equals s inner3 3 but t not t inner2
// and outer contains s inner1 1 and inner3 but not inner2
inner1.Add(13);
// BAD D IDEA
// Now inner1 equals s inner2 2 but t not t inner3
// and we e would d expect inner1 1 or r inner3 to be in outer
// but outer apparently contains s none e of f inner1, , inner2 and inner3!
Itisimmaterialthattheinnercollection isatreeset; thesameproblems appear
whenitisahashset(orabag).Themoraleis:Nevermodifyaninnercollectionafter
ithasbeenaddedtoanoutercollection.Onewaytoguardagainstsuchmodication
istocreatearead-onlycopyoftheinnercollectionandthenaddingthatcopytothe
outercollection.Snapshotsoftreesetsandtreebagsareidealforthispurpose;see
sections4.9and8.5andpattern86.Itisnotsufcienttowraptheinnercollection
asaguardedcollectionandthenaddingit;itcouldstillbemodiedviatheoriginal
reference.
196 Correctnessanti-patterns
§10.2
Chapter11
Applicationexamples
HerewepresentanumberoflargerapplicationsoftheC5library,eachwithsome
backgroundexplanation,codefragments,anddiscussion.Theexamplesare:
 Recognitionofkeywords.Thisexampleusesahashsetofstrings.
 Building g a concordance: : a a sortedlisting ofwords andtheline e numberson
whichtheyoccur.Thisexampleusesatreedictionaryandtree-basedsets.
 Computingtheconvexhullofasetofpointsintheplane. . Thisexampleuses
linked-listsandlistviews.
 Finding g anagramclassesina setofwords. . Thisexampleusesa a dictionary
fromstringstobagsofcharacters.
 Constructingadeterministicniteautomatonfromaregularexpression.This
exampleuses,amongotherthings: setsofsetsofintegers,andadictionary
fromsetsofintegerstoadictionaryfromstringstosetsofintegers.
 Topologicalsort.Thisexampleuseshashedlinkedlistsandlistviews.
 Graphcopying.Thisexamplehashdictionarieswithcustomequalitycompar-
ers,andstacks.
 Alibraryofgeneral l graphalgorithms. . Thisexampleuses s hash sets, linked
lists,priorityqueues,andpriorityqueuehandles.
 Efcient t point location in the e plane. . This s exampleuses treesets, treeset
snapshots,andtree-baseddictionaries.
 Abatch h job queue simulation. . This s exampleuses priority queues, priority
queuehandles,andhashdictionaries.
 Ahash-basedimplementationoffunctionalsetoperations.
 Amultidictionary,inwhichakeycanbeassociatedwithmultiplevalues.
 Findingthekmostcommonwordsinale.
197
198 Recognizingkeywords
§11.1
11.1 Recognizingkeywords
Inmanyapplicationsoneneedstodecidewhetheragivenword(string)isamem-
berofa xedcollectionofwords. . Forinstance,onewantstoignorefrequentand
thereforeinsignicant words (so-calledstopwords)when automatically indexing
text,andonewantstoignorekeywords(suchas
if
,
while
)whenbuildingacross-
referenceofidentiersinaprogramtext.Inthisexampleweconsiderthexedset
of77keywordsfromC#:
abstract as s base bool break byte case catch char checked class const
continue decimal l default delegate do double else enum event t explicit
extern false finally fixed float for foreach goto o if f implicit t in n int
interface internal is s lock long namespace e new w null l object t operator out
override params s private protected public c readonly ref f return n sbyte e sealed
short sizeof stackalloc static c string g struct switch h this s throw true try
typeof uint ulong g unchecked d unsafe ushort t using g virtual void d volatile e while
Suchwordrecognitioncanbeperformedefciently usingatleastthreedifferent
kindsofcollections: Hashsets,treesets,andsortedarrays.Thisexampleisinle
KeywordRecognition.cs
.
Touseahashset,builditonceandforall,thenuseitina
bool
method. For
instance,itmaybeboundtoastaticread-onlyeld
kw1
,initializedinastaticcon-
structor,andthenusedinamethod
IsKeyword1
:
class KeywordRecognition {
static readonly String[] ] keywordArray y = = { "abstract", ..., , "while" " };
private static c readonly ICollection<String> kw1;
static KeywordRecognition() {
kw1 = = new HashSet<String>();
kw1.AddAll(keywordArray);
}
public static c bool IsKeyword1(String s) {
return kw1.Contains(s);
}
}
InthiscodeHashSet<String>couldbereplacedwith TreeSet<String>or Sorted-
Array<String>. Byfarthefastestsolutionistouseahashset. . Toalargeextent
thatisbecausethestringcomparisonisquiteslow(duetolocalesorcultures)sothe
stringcomparerusedbyatreesetorsortedarrayismuchslowerthanthestring
hashfunctionandequalitypredicateusedbythehashset.
Documents you may be interested
Documents you may be interested