Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite4b6a0a

Browse files
committed
- performance optimizations for CharAcceptorBuilder
- fixed issue with SortedCharAcceptorBuilder
1 parent1575a31 commite4b6a0a

File tree

8 files changed

+251
-161
lines changed

8 files changed

+251
-161
lines changed

‎src/main/java/com/indoqa/fsa/character/CharAcceptorBuilder.java‎

Lines changed: 93 additions & 97 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@
2020

2121
importjava.io.*;
2222
importjava.util.*;
23-
importjava.util.concurrent.ConcurrentHashMap;
23+
importjava.util.Map.Entry;
2424
importjava.util.function.Consumer;
2525

2626
importcom.indoqa.fsa.AcceptorBuilder;
@@ -30,14 +30,14 @@ public class CharAcceptorBuilder implements AcceptorBuilder {
3030
publicstaticfinalintFILE_VERSION =2;
3131
publicstaticfinalintDEFAULT_CAPACITY_INCREMENT =16 *1024;
3232

33-
privatestaticfinalfloatLOAD_FACTOR =0.9f;
34-
3533
privatefinalbooleancaseSensitive;
3634

3735
privatechar[][]nodes =newchar[0][];
3836
privateintnodeCount;
3937
privateintcapacityIncrement;
4038

39+
privateReplacementsreplacements;
40+
4141
privateConsumer<String>messageConsumer;
4242

4343
privatebooleanminified;
@@ -88,25 +88,30 @@ public static CharAcceptor read(InputStream inputStream) throws IOException {
8888
returnnewCharAcceptor(data,caseSensitive);
8989
}
9090

91-
privatestatic <K,V>ConcurrentHashMap<K,V>createHashMap(intsize) {
92-
returnnewConcurrentHashMap<>((int) (size /LOAD_FACTOR +1),LOAD_FACTOR,1);
93-
}
94-
9591
privatestaticStringgetKey(char[]node) {
9692
StringBuilderstringBuilder =newStringBuilder();
9793

98-
for (inti =0;i <10;i++) {
99-
if (node.length <=CharDataAccessor.NODE_SIZE *i) {
100-
break;
101-
}
94+
for (inti =0;i <node.length;i +=CharDataAccessor.NODE_SIZE) {
95+
stringBuilder.append(CharDataAccessor.getLabel(node,i));
96+
}
10297

103-
stringBuilder.append(node[CharDataAccessor.NODE_SIZE *i]);
98+
returnstringBuilder.toString();
99+
}
100+
101+
privatestaticintsort(NodeReferencen1,NodeReferencen2) {
102+
if (n1 ==null &&n2 ==null) {
103+
return0;
104104
}
105105

106-
stringBuilder.append('_');
107-
stringBuilder.append(node.length);
106+
if (n1 ==null) {
107+
return1;
108+
}
108109

109-
returnstringBuilder.toString();
110+
if (n2 ==null) {
111+
return -1;
112+
}
113+
114+
returnn1.compareTo(n2);
110115
}
111116

112117
@Override
@@ -116,8 +121,10 @@ public void addAcceptedInput(CharSequence value, int start, int length) {
116121

117122
@Override
118123
publicCharAcceptorbuild() {
124+
this.replacements =newReplacements(this.nodeCount);
119125
this.minify();
120126
this.remap();
127+
this.replacements =null;
121128

122129
char[]data =this.buildData();
123130
returnnewCharAcceptor(data,this.caseSensitive);
@@ -129,8 +136,10 @@ public void setMessageConsumer(Consumer<String> messageConsumer) {
129136

130137
@Override
131138
publicvoidwrite(OutputStreamoutputStream)throwsIOException {
139+
this.replacements =newReplacements(this.nodeCount);
132140
this.minify();
133141
this.remap();
142+
this.replacements =null;
134143

135144
DataOutputStreamdataOutputStream =newDataOutputStream(newBufferedOutputStream(outputStream));
136145
dataOutputStream.writeInt(FILE_VERSION);
@@ -222,14 +231,34 @@ private void addNode() {
222231
this.nodeCount++;
223232
}
224233

225-
privatebooleanapplyReplacements(char[]nodeData,Map<Integer,Integer>replacements) {
234+
privateSet<String>applyReplacements() {
235+
this.sendMessage("Applying " +this.replacements.getCount() +" replacements");
236+
237+
Set<String>result =newHashSet<>();
238+
239+
for (inti =0;i <this.nodeCount;i++) {
240+
char[]node =this.nodes[i];
241+
if (node ==null) {
242+
continue;
243+
}
244+
245+
booleanupdated =this.applyReplacements(node);
246+
if (updated) {
247+
result.add(getKey(node));
248+
}
249+
}
250+
251+
returnresult;
252+
}
253+
254+
privatebooleanapplyReplacements(char[]nodeData) {
226255
booleanresult =false;
227256

228257
for (inti =0;i <nodeData.length;i +=CharDataAccessor.NODE_SIZE) {
229258
inttarget =getTarget(nodeData,i);
230259

231-
Integerreplacement =replacements.get(target);
232-
if (replacement ==null) {
260+
intreplacement =this.replacements.getReplacement(target);
261+
if (replacement ==-1) {
233262
continue;
234263
}
235264

@@ -246,25 +275,6 @@ private boolean applyReplacements(char[] nodeData, Map<Integer, Integer> replace
246275
returnresult;
247276
}
248277

249-
privateSet<String>applyReplacements(Map<Integer,Integer>replacements) {
250-
this.sendMessage("Applying " +replacements.size() +" replacements");
251-
252-
Set<String>result =newHashSet<>();
253-
254-
for (inti =0;i <this.nodeCount;i++) {
255-
char[]node =this.nodes[i];
256-
if (node ==null) {
257-
continue;
258-
}
259-
260-
if (this.applyReplacements(node,replacements)) {
261-
result.add(getKey(node));
262-
}
263-
}
264-
265-
returnresult;
266-
}
267-
268278
privatechar[]buildData() {
269279
char[]data =newchar[this.requiredLength];
270280
intoffset =0;
@@ -281,10 +291,8 @@ private char[] buildData() {
281291
returndata;
282292
}
283293

284-
privateMap<String,List<Integer>>buildGroups() {
285-
this.sendMessage("Building groups");
286-
287-
Map<String,List<Integer>>result =createHashMap(1000);
294+
privateMap<String,List<NodeReference>>buildGroups() {
295+
Map<String,List<NodeReference>>result =newHashMap<>();
288296

289297
for (inti =0;i <this.nodeCount;i++) {
290298
char[]node =this.nodes[i];
@@ -294,48 +302,55 @@ private Map<String, List<Integer>> buildGroups() {
294302

295303
Stringkey =getKey(node);
296304

297-
List<Integer>indexes =result.get(key);
305+
List<NodeReference>indexes =result.get(key);
298306
if (indexes ==null) {
299-
indexes =newLinkedList<>();
307+
indexes =newArrayList<>();
300308
result.put(key,indexes);
301309
}
302310

303-
indexes.add(i);
311+
indexes.add(newNodeReference(node,i));
304312
}
305313

314+
for (Iterator<Entry<String,List<NodeReference>>>iterator =result.entrySet().iterator();iterator.hasNext();) {
315+
if (iterator.next().getValue().size() <2) {
316+
iterator.remove();
317+
}
318+
}
319+
320+
this.sendMessage("Built " +result.size() +" groups");
306321
returnresult;
307322
}
308323

309-
privateMap<Integer,Integer>findReplacements(List<Integer>group) {
310-
Map<Integer,Integer>result =newHashMap<>();
311-
312-
List<NodeReference>references =newArrayList<>(group.size());
313-
314-
for (Iterator<Integer>iterator =group.iterator();iterator.hasNext();) {
315-
Integerindex =iterator.next();
316-
317-
char[]node =this.nodes[index];
318-
if (node ==null) {
319-
iterator.remove();
324+
privatevoidfindEndNodeReplacements() {
325+
for (inti =0;i <this.nodeCount;i++) {
326+
if (this.nodes[i] ==null ||this.nodes[i].length !=0) {
320327
continue;
321328
}
322329

323-
references.add(newNodeReference(node,index));
330+
this.nodes[i] =null;
331+
this.replacements.setReplacement(i,0);
324332
}
333+
}
325334

326-
references.sort(null);
335+
privatevoidfindReplacements(List<NodeReference>group) {
336+
group.sort(CharAcceptorBuilder::sort);
327337

328338
NodeReferencelastReference =null;
329-
for (NodeReferenceeachReference :references) {
330-
if (lastReference ==null || !eachReference.equals(lastReference)) {
331-
lastReference =eachReference;
332-
}else {
333-
result.put(eachReference.getIndex(),lastReference.getIndex());
334-
this.nodes[eachReference.getIndex()] =null;
339+
for (ListIterator<NodeReference>iterator =group.listIterator();iterator.hasNext();) {
340+
NodeReferencereference =iterator.next();
341+
if (reference ==null) {
342+
break;
335343
}
336-
}
337344

338-
returnresult;
345+
if (lastReference ==null || !reference.equals(lastReference)) {
346+
lastReference =reference;
347+
continue;
348+
}
349+
350+
this.replacements.setReplacement(reference.getIndex(),lastReference.getIndex());
351+
this.nodes[reference.getIndex()] =null;
352+
iterator.set(null);
353+
}
339354
}
340355

341356
privatevoidminify() {
@@ -345,30 +360,28 @@ private void minify() {
345360

346361
this.sendMessage("Minifying " +this.nodeCount +" nodes");
347362

348-
Map<Integer,Integer>replacements =this.replaceEndNodes();
349-
this.applyReplacements(replacements);
350-
351-
Map<String,List<Integer>>groups =this.buildGroups();
352-
Set<String>changedGroups =newHashSet<>(groups.keySet());
363+
Map<String,List<NodeReference>>groups =this.buildGroups();
364+
this.replacements.clear();
365+
this.findEndNodeReplacements();
366+
Set<String>changedGroups =this.applyReplacements();
353367

354368
while (true) {
355-
replacements.clear();
369+
this.replacements.clear();
356370

357-
this.sendMessage("Finding duplicates in " +changedGroups.size() +" groups");
358371
for (StringeachChangedGroup :changedGroups) {
359-
List<Integer>group =groups.get(eachChangedGroup);
360-
if (group ==null ||group.size() <2) {
372+
List<NodeReference>group =groups.get(eachChangedGroup);
373+
if (group ==null) {
361374
continue;
362375
}
363376

364-
replacements.putAll(this.findReplacements(group));
377+
this.findReplacements(group);
365378
}
366379

367-
if (replacements.isEmpty()) {
380+
if (this.replacements.getCount() ==0) {
368381
break;
369382
}
370383

371-
changedGroups =this.applyReplacements(replacements);
384+
changedGroups =this.applyReplacements();
372385
}
373386

374387
this.minified =true;
@@ -382,44 +395,27 @@ private void remap() {
382395
this.sendMessage("Remapping node addresses ...");
383396
this.requiredLength =0;
384397

385-
Map<Integer,Integer>replacements =createHashMap(this.nodeCount);
386-
387398
for (inti =0;i <this.nodeCount;i++) {
388399
char[]node =this.nodes[i];
389400
if (node ==null) {
390401
continue;
391402
}
392403

393404
if (node.length ==0) {
394-
replacements.put(i,0);
405+
this.replacements.setReplacement(i,0);
395406
}else {
396-
replacements.put(i,this.requiredLength);
407+
this.replacements.setReplacement(i,this.requiredLength);
397408
this.requiredLength +=node.length;
398409
}
399410
}
400411

401412
this.sendMessage("RequiredLength: " +this.requiredLength);
402413

403-
this.applyReplacements(replacements);
414+
this.applyReplacements();
404415

405416
this.remapped =true;
406417
}
407418

408-
privateMap<Integer,Integer>replaceEndNodes() {
409-
Map<Integer,Integer>result =createHashMap(1000);
410-
411-
for (inti =0;i <this.nodeCount;i++) {
412-
if (this.nodes[i] ==null ||this.nodes[i].length !=0) {
413-
continue;
414-
}
415-
416-
this.nodes[i] =null;
417-
result.put(i,0);
418-
}
419-
420-
returnresult;
421-
}
422-
423419
privatevoidsendMessage(Stringmessage) {
424420
if (this.messageConsumer !=null) {
425421
this.messageConsumer.accept(message);

‎src/main/java/com/indoqa/fsa/character/CharDataAccessor.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,26 @@ public class CharDataAccessor {
4141
}
4242
}
4343

44+
publicstaticintcompare(Strings1,Strings2,booleancaseSensitive) {
45+
for (inti =0;i <s1.length();i++) {
46+
if (s2.length() ==i) {
47+
returns1.length() -s2.length();
48+
}
49+
50+
charc1 =s1.charAt(i);
51+
charc2 =s2.charAt(i);
52+
53+
intresult =c1 -c2;
54+
if (result ==0 ||CharDataAccessor.equals(c1,c2,caseSensitive)) {
55+
continue;
56+
}
57+
58+
returnresult;
59+
}
60+
61+
returns1.length() -s2.length();
62+
}
63+
4464
publicstaticbooleanisDifferentCase(charchar1,charchar2) {
4565
returnCharacter.isUpperCase(char1) && !Character.isUpperCase(char2) ||
4666
Character.isLowerCase(char1) && !Character.isLowerCase(char2);

‎src/main/java/com/indoqa/fsa/character/NodeReference.java‎

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -21,9 +21,9 @@
2121
publicclassNodeReferenceimplementsComparable<NodeReference> {
2222

2323
privatefinalchar[]data;
24-
privatefinalIntegerindex;
24+
privatefinalintindex;
2525

26-
publicNodeReference(char[]data,Integerindex) {
26+
publicNodeReference(char[]data,intindex) {
2727
super();
2828
this.data =data;
2929
this.index =index;
@@ -49,7 +49,7 @@ public int compareTo(NodeReference other) {
4949
return -1;
5050
}
5151

52-
returnthis.index.compareTo(other.index);
52+
returnInteger.compare(this.index,other.index);
5353
}
5454

5555
@Override
@@ -62,7 +62,11 @@ public boolean equals(Object obj) {
6262
returnArrays.equals(this.data,other.data);
6363
}
6464

65-
publicIntegergetIndex() {
65+
publicchar[]getData() {
66+
returnthis.data;
67+
}
68+
69+
publicintgetIndex() {
6670
returnthis.index;
6771
}
6872

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp