Changeset 1254

Timestamp:

07/15/13 11:39:17 (11 years ago)

Author:

pharms

Message:

• performance improvement for log compression with a large numbers of events

File:

• trunk/autoquest-plugin-html/src/main/java/de/ugoe/cs/autoquest/plugin/html/HTMLLogCompressor.java (modified) (1 diff)

trunk/autoquest-plugin-html/src/main/java/de/ugoe/cs/autoquest/plugin/html/HTMLLogCompressor.java

@@ -253 +253 @@
         EventEntry newEvent = new EventEntry(type, parameters, timestamp);
         
-        boolean added = false;
-        for (int i = 0; i < sortedEvents.size(); i++) {
-            if (sortedEvents.get(i).timestamp > newEvent.timestamp) {
-                sortedEvents.add(i, newEvent);
-                added = true;
+        int start = 0;
+        int end = sortedEvents.size();
+        int center = 0;
+        long centerTimestamp;
+        
+        while (start != end) {
+            center = start + ((end - start) / 2);
+            
+            if ((center != start) || (center != end)) {
+                centerTimestamp = sortedEvents.get(center).timestamp;
+            
+                if (centerTimestamp < newEvent.timestamp) {
+                    start = Math.max(center, start + 1);
+                }
+                else if (centerTimestamp > newEvent.timestamp) {
+                    end = Math.min(center, end - 1);
+                }
+                else {
+                    // add the event directly where the center is, as the timestamps of the center
+                    // and the new event are equal
+                    start = end = center;
+                    break;
+                }
+            }
+            else {
+                // add the event to the position denoted by the add index
                 break;
             }
         }
         
-        if (!added) {
-            sortedEvents.add(newEvent);
-        }
+        sortedEvents.add(start, newEvent);
 
         return true;