fork(1) download
copy 
  1. import java.util.Map;
  2. import java.util.HashMap;
  3. import java.util.Set;
  4. import java.util.HashSet;
  5. import java.util.ArrayList;
  6. import java.util.regex.Pattern;
  7. import java.util.regex.Matcher;
  8.  
  9. class Main {
  10.   private final String input;
  11.   private final String expected;
  12.   private final String[] search = new String[] { "foo", "bar", };
  13.   private final String[] replace = new String[] { "bar", "foo" };
  14.  
  15.   private Main() {
  16.     StringBuilder sb = new StringBuilder();
  17.     StringBuilder expectedSb = new StringBuilder();
  18.     for (int i = 0; i < 320000; i++) {
  19.               sb.append("ffffffffffoo baz quux bar");
  20.       expectedSb.append("fffffffffbar baz quux foo");
  21.     }
  22.     this.input = sb.toString();
  23.     this.expected = expectedSb.toString();
  24.     System.out.printf("Input size: %d chars%n", this.input.length());
  25.   }
  26.  
  27.   public static void main(String[] args) {
  28.   	Solution[] solutions = new Solution[] {
  29.   	  new RecursiveSolution(),
  30.   	  new JanosSolution(),
  31.   	  new ArshajiiSolution(),
  32.   	  new BoannSolution(),
  33.   	  new JeroenSolution(),
  34.   	  new ApacheSolution()
  35.   	};
  36.  
  37.     Main main = new Main();
  38.     for (int i = 0; i < 2; i++) {
  39.       for (Solution solution : solutions) {
  40.       	main.timeSolution(solution);
  41.       }
  42.     }
  43.   }
  44.  
  45.   private void timeSolution(Solution solution) {
  46.     long start = System.nanoTime();
  47.     String actual = solution.replaceAll(input, search, replace);
  48.     long now = System.nanoTime();
  49.     System.out.printf("%20s: %12d. Equals expected: %b%n", solution.getName(), now - start, actual.equals(this.expected));
  50.   }
  51.  
  52.   private interface Solution {
  53.     String getName();
  54.     String replaceAll(final String input, final String[] search, final String[] replace);
  55.   }
  56.  
  57.   private static class RecursiveSolution implements Solution {
  58.     public String getName() {
  59.       return "Recursive";
  60.     }
  61.  
  62.     public String replaceAll(String input, String[] search, String[] replace) {
  63.       StringBuilder sb = new StringBuilder();
  64.       replaceAll(sb, input, 0, input.length(), search, replace, 0);
  65.       return sb.toString();
  66.     }
  67.  
  68.     private static void replaceAll(StringBuilder sb, String input, int start, int end, String[] search, String[] replace, int i) {
  69.       while (i < search.length && start < end) {
  70.         int j = indexOf(input, search[i], start, end);
  71.         if (j == -1) {
  72.           i++;
  73.         } else {
  74.           replaceAll(sb, input, start, j, search, replace, i + 1);
  75.           sb.append(replace[i]);
  76.           start = j + search[i].length();
  77.         }
  78.       }
  79.       sb.append(input, start, end);
  80.     }
  81.  
  82.     private static int indexOf(final String source, final String target, final int start, final int end) {
  83.       int len = target.length();
  84.       if (len == 0) {
  85.         return start;
  86.       }
  87.       if (len > source.length()) {
  88.         return -1;
  89.       }
  90.       if (len == source.length()) {
  91.         return source.equals(target) ? 0 : -1;
  92.       }
  93.       int max = end - len;
  94.       char first = target.charAt(0);
  95.       for (int i = start; i <= max; i++) {
  96.         if (source.charAt(i) != first) {
  97.           while (++i <= max && source.charAt(i) != first);
  98.         }
  99.         if (i <= max) {
  100.           int j = i + 1;
  101.           int e = j + len - 1;
  102.           for (int k = 1; j < e && source.charAt(j) == target.charAt(k); j++, k++);
  103.           if (j == e) {
  104.             return i;
  105.           }
  106.         }
  107.       }
  108.       return -1;
  109.     }
  110.   }
  111.  
  112.   private static class JeroenSolution implements Solution {
  113.     public String getName() {
  114.       return "Jeroen";
  115.     }
  116.  
  117.     public String replaceAll(String subject, String[] search, String[] replace) {
  118.       subject = subject.replace("foo", "\uE000");
  119.       subject = subject.replace("bar", "foo");
  120.       subject = subject.replace("\uE000", "bar");
  121.       return subject;
  122.     }
  123.   }
  124.  
  125.   private static class JanosSolution implements Solution {
  126.   	public String getName() {
  127.   	  return "Janos";
  128.   	}
  129.  
  130.     public String replaceAll(String text, String[] searchList, String[] replacementList) {
  131.       // TODO: throw new IllegalArgumentException() if any param doesn't make sense
  132.       //validateParams(text, searchList, replacementList);
  133.  
  134.       SearchTracker tracker = new SearchTracker(text, searchList, replacementList);
  135.       if (!tracker.hasNextMatch(0)) {
  136.         return text;
  137.       }
  138.  
  139.       StringBuilder buf = new StringBuilder(text.length() * 2);
  140.       int start = 0;
  141.  
  142.       do {
  143.         SearchTracker.MatchInfo matchInfo = tracker.matchInfo;
  144.         int textIndex = matchInfo.textIndex;
  145.         String pattern = matchInfo.pattern;
  146.         String replacement = matchInfo.replacement;
  147.  
  148.         buf.append(text.substring(start, textIndex));
  149.         buf.append(replacement);
  150.  
  151.         start = textIndex + pattern.length();
  152.       } while (tracker.hasNextMatch(start));
  153.  
  154.       return buf.append(text.substring(start)).toString();
  155.     }
  156.  
  157.     private static class SearchTracker {
  158.  
  159.       private final String text;
  160.  
  161.       private final Map<String, String> patternToReplacement = new HashMap<>();
  162.       private final Set<String> pendingPatterns = new HashSet<>();
  163.  
  164.       private MatchInfo matchInfo = null;
  165.  
  166.       private static class MatchInfo {
  167.         private final String pattern;
  168.         private final String replacement;
  169.         private final int textIndex;
  170.  
  171.         private MatchInfo(String pattern, String replacement, int textIndex) {
  172.           this.pattern = pattern;
  173.           this.replacement = replacement;
  174.           this.textIndex = textIndex;
  175.         }
  176.       }
  177.  
  178.       private SearchTracker(String text, String[] searchList, String[] replacementList) {
  179.         this.text = text;
  180.         for (int i = 0; i < searchList.length; ++i) {
  181.           String pattern = searchList[i];
  182.           patternToReplacement.put(pattern, replacementList[i]);
  183.           pendingPatterns.add(pattern);
  184.         }
  185.       }
  186.  
  187.       boolean hasNextMatch(int start) {
  188.         int textIndex = -1;
  189.         String nextPattern = null;
  190.  
  191.         for (String pattern : new ArrayList<>(pendingPatterns)) {
  192.           int matchIndex = text.indexOf(pattern, start);
  193.           if (matchIndex == -1) {
  194.             pendingPatterns.remove(pattern);
  195.           } else {
  196.             if (textIndex == -1 || matchIndex < textIndex) {
  197.               textIndex = matchIndex;
  198.               nextPattern = pattern;
  199.             }
  200.           }
  201.         }
  202.  
  203.         if (nextPattern != null) {
  204.           matchInfo = new MatchInfo(nextPattern, patternToReplacement.get(nextPattern), textIndex);
  205.           return true;
  206.         }
  207.         return false;
  208.       }
  209.     }
  210.   }
  211.  
  212.   private static class ArshajiiSolution implements Solution {
  213.   	public String getName() {
  214.   	  return "arshajii";
  215.   	}
  216.  
  217.   	public String replaceAll(String input, String[] search, String[] replace) {
  218.   	  Pattern p = Pattern.compile("foo|bar");
  219.       Matcher m = p.matcher(input);
  220.       StringBuffer sb = new StringBuffer();
  221.       while (m.find()) {
  222.         /* do the swap... */
  223.         switch (m.group()) {
  224.         case "foo":
  225.           m.appendReplacement(sb, "bar");
  226.           break;
  227.         case "bar":
  228.           m.appendReplacement(sb, "foo");
  229.           break;
  230.         default:
  231.         /* error */
  232.           break;
  233.       }
  234.     }
  235.     m.appendTail(sb);
  236.     return sb.toString();
  237.   }
  238. }
  239.  
  240. /*
  241.  * Licensed to the Apache Software Foundation (ASF) under one or more
  242.  * contributor license agreements.  See the NOTICE file distributed with
  243.  * this work for additional information regarding copyright ownership.
  244.  * The ASF licenses this file to You under the Apache License, Version 2.0
  245.  * (the "License"); you may not use this file except in compliance with
  246.  * the License.  You may obtain a copy of the License at
  247.  *
  248.  *      http://w...content-available-to-author-only...e.org/licenses/LICENSE-2.0
  249.  *
  250.  * Unless required by applicable law or agreed to in writing, software
  251.  * distributed under the License is distributed on an "AS IS" BASIS,
  252.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  253.  * See the License for the specific language governing permissions and
  254.  * limitations under the License.
  255.  */
  256.  // From http://s...content-available-to-author-only...e.org/viewvc/commons/proper/lang/trunk/src/main/java/org/apache/commons/lang3/StringUtils.java?view=co
  257.   private static class ApacheSolution implements Solution {
  258.     public String getName() {
  259.       return "Apache";
  260.     }
  261.  
  262.     public String replaceAll(final String text, final String[] searchList, final String[] replacementList) {
  263.         return replaceEach(text, searchList, replacementList, false, 0);
  264.     }
  265.  
  266.    private static String replaceEach(
  267.             final String text, final String[] searchList, final String[] replacementList, final boolean repeat, final int timeToLive) {
  268.  
  269.         // mchyzer Performance note: This creates very few new objects (one major goal)
  270.         // let me know if there are performance requests, we can create a harness to measure
  271.  
  272.         if (text == null || text.isEmpty() || searchList == null ||
  273.                 searchList.length == 0 || replacementList == null || replacementList.length == 0) {
  274.             return text;
  275.         }
  276.  
  277.         // if recursing, this shouldn't be less than 0
  278.         if (timeToLive < 0) {
  279.             throw new IllegalStateException("Aborting to protect against StackOverflowError - " +
  280.                                             "output of one loop is the input of another");
  281.         }
  282.  
  283.         final int searchLength = searchList.length;
  284.         final int replacementLength = replacementList.length;
  285.  
  286.         // make sure lengths are ok, these need to be equal
  287.         if (searchLength != replacementLength) {
  288.             throw new IllegalArgumentException("Search and Replace array lengths don't match: "
  289.                 + searchLength
  290.                 + " vs "
  291.                 + replacementLength);
  292.         }
  293.  
  294.         // keep track of which still have matches
  295.         final boolean[] noMoreMatchesForReplIndex = new boolean[searchLength];
  296.  
  297.         // index on index that the match was found
  298.         int textIndex = -1;
  299.         int replaceIndex = -1;
  300.         int tempIndex = -1;
  301.  
  302.         // index of replace array that will replace the search string found
  303.         // NOTE: logic duplicated below START
  304.         for (int i = 0; i < searchLength; i++) {
  305.             if (noMoreMatchesForReplIndex[i] || searchList[i] == null ||
  306.                     searchList[i].isEmpty() || replacementList[i] == null) {
  307.                 continue;
  308.             }
  309.             tempIndex = text.indexOf(searchList[i]);
  310.  
  311.             // see if we need to keep searching for this
  312.             if (tempIndex == -1) {
  313.                 noMoreMatchesForReplIndex[i] = true;
  314.             } else {
  315.                 if (textIndex == -1 || tempIndex < textIndex) {
  316.                     textIndex = tempIndex;
  317.                     replaceIndex = i;
  318.                 }
  319.             }
  320.         }
  321.         // NOTE: logic mostly below END
  322.  
  323.         // no search strings found, we are done
  324.         if (textIndex == -1) {
  325.             return text;
  326.         }
  327.  
  328.         int start = 0;
  329.  
  330.         // get a good guess on the size of the result buffer so it doesn't have to double if it goes over a bit
  331.         int increase = 0;
  332.  
  333.         // count the replacement text elements that are larger than their corresponding text being replaced
  334.         for (int i = 0; i < searchList.length; i++) {
  335.             if (searchList[i] == null || replacementList[i] == null) {
  336.                 continue;
  337.             }
  338.             final int greater = replacementList[i].length() - searchList[i].length();
  339.             if (greater > 0) {
  340.                 increase += 3 * greater; // assume 3 matches
  341.             }
  342.         }
  343.         // have upper-bound at 20% increase, then let Java take over
  344.         increase = Math.min(increase, text.length() / 5);
  345.  
  346.         final StringBuilder buf = new StringBuilder(text.length() + increase);
  347.  
  348.         while (textIndex != -1) {
  349.  
  350.             for (int i = start; i < textIndex; i++) {
  351.                 buf.append(text.charAt(i));
  352.             }
  353.             buf.append(replacementList[replaceIndex]);
  354.  
  355.             start = textIndex + searchList[replaceIndex].length();
  356.  
  357.             textIndex = -1;
  358.             replaceIndex = -1;
  359.             tempIndex = -1;
  360.             // find the next earliest match
  361.             // NOTE: logic mostly duplicated above START
  362.             for (int i = 0; i < searchLength; i++) {
  363.                 if (noMoreMatchesForReplIndex[i] || searchList[i] == null ||
  364.                         searchList[i].isEmpty() || replacementList[i] == null) {
  365.                     continue;
  366.                 }
  367.                 tempIndex = text.indexOf(searchList[i], start);
  368.  
  369.                 // see if we need to keep searching for this
  370.                 if (tempIndex == -1) {
  371.                     noMoreMatchesForReplIndex[i] = true;
  372.                 } else {
  373.                     if (textIndex == -1 || tempIndex < textIndex) {
  374.                         textIndex = tempIndex;
  375.                         replaceIndex = i;
  376.                     }
  377.                 }
  378.             }
  379.             // NOTE: logic duplicated above END
  380.  
  381.         }
  382.         final int textLength = text.length();
  383.         for (int i = start; i < textLength; i++) {
  384.             buf.append(text.charAt(i));
  385.         }
  386.         final String result = buf.toString();
  387.         if (!repeat) {
  388.             return result;
  389.         }
  390.  
  391.         return replaceEach(result, searchList, replacementList, repeat, timeToLive - 1);
  392.     }
  393.   }
  394.  
  395.   private static class BoannSolution implements Solution {
  396.     public String getName() {
  397.       return "Boann";
  398.     }
  399.  
  400.     public String replaceAll(String subject, String[] search, String[] replace) {
  401.       if (search.length != replace.length) {
  402.         throw new IllegalArgumentException("Strings to find and replace are not paired.");
  403.       }
  404.       StringBuilder sb = new StringBuilder();
  405.   outer:
  406.       for (int i = 0; i < subject.length(); i++) {
  407.         for (int j = 0; j < search.length; j++) {
  408.           String find = search[j];
  409.           if (subject.regionMatches(i, find, 0, find.length())) {
  410.             sb.append(replace[j]);
  411.             i += find.length() - 1;
  412.             continue outer;
  413.           }
  414.         }
  415.         sb.append(subject.charAt(i));
  416.       }
  417.       return sb.toString();
  418.     }
  419.   }
  420. }
  421.  
Success #stdin #stdout 8.24s 380672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input size: 8000000 chars
           Recursive:    308135051. Equals expected: true
               Janos:    461886365. Equals expected: true
            arshajii:    881559778. Equals expected: true
               Boann:    486664087. Equals expected: true
              Jeroen:   1399020199. Equals expected: true
              Apache:    284353642. Equals expected: true
           Recursive:    322507125. Equals expected: true
               Janos:    477125970. Equals expected: true
            arshajii:    872026894. Equals expected: true
               Boann:    463323530. Equals expected: true
              Jeroen:   1327117256. Equals expected: true
              Apache:    286000230. Equals expected: true
https://ideone.com/z1zM5H
language:
Java (12.0.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!