代码之家  ›  专栏  ›  技术社区  ›  Ahmad Al-Khazraji

多核前缀搜索算法

  •  1
  • Ahmad Al-Khazraji  · 技术社区  · 6 年前

    我有一个任务,从单词中过滤前缀列表(向量)。 该算法应该使用现代多核处理器。

    解决方案是使用许多线程来处理列表。

    //      PrintWriter writer = new PrintWriter("C:\\DemoList.txt", "UTF-8");
    //      
    //      for(char i = 'A'; i<= 'Z'; i++) {
    //          for(char j = 'A'; j<= 'Z'; j++) {
    //              for(char n = 'A'; n<= 'Z'; n++) {
    //                  for(char m = 'A'; m<= 'Z'; m++) {
    //                      writer.println("" + i + j + n + m );
    //                  }
    //                      
    //              }
    //          }
    //      }
        List<String> allLines = Files.readAllLines(Paths.get("C:\\", "DemoList.txt"));
        Collections.shuffle(allLines);
        String pattern = "AA";
    
        List<String> result = new ArrayList<>();
        int cores = Runtime.getRuntime().availableProcessors();
        int threadsNum = allLines.size() / cores;
    
        long start_time = System.nanoTime();
    
        for (String word : allLines) {
            if (word.startsWith(pattern))
                result.add(word);
    
        }
    
        long end_time = System.nanoTime();
        double difference = (end_time - start_time) / 1e6;
        System.out.println("Time difference in Milliseconds with Brute-Force: " + difference);
    
    //With Parallisim:
        long new_start_time = System.nanoTime();
    
        List<String> filteredList = allLines.parallelStream().filter(s -> s.startsWith(pattern))
                .collect(Collectors.toList());
    
        long new_end_time = System.nanoTime();
    
        double new_difference = (new_end_time - new_start_time) / 1e6;
        System.out.println("Time difference in Milliseconds with Stream from Java 8: " + new_difference);   
    

    结果: 强力时的时差(毫秒):33.033602 从Java 8流到毫秒的时间差:65.017069

    每个线程都应该过滤列表中的一个范围。

    你有更好的主意吗? 你认为,我应该对原始列表进行排序,而不是对其进行二进制搜索吗?我应该在二进制排序中也使用多线程,还是应该使用collections.sort? 您将如何实现这一点?

    2 回复  |  直到 6 年前
        1
  •  3
  •   GPI    6 年前

    从代码示例来看,时间测量方法接近于微观基准测试,对于微观基准测试而言,简单地测量单个执行的时间是误导性的。

    您可以在下面的stackoverflow post中看到它的详细讨论: How do I write a correct micro-benchmark in Java?

    我已经编写了一个更精确的基准来获得对您的示例代码更精确的度量。代码运行在具有多线程的四核i7上(但它是一台笔记本电脑,由于电源和热量管理,结果可能会稍微偏向于产生更多热量的多线程代码)。

    @Benchmark
    public void testSequentialFor(Blackhole bh, Words words) {
        List<String> filtered = new ArrayList<>();
        for (String word : words.toSort) {
            if (word.startsWith(words.prefix)) {
                filtered.add(word);
            }
        }
        bh.consume(filtered);
    }
    
    @Benchmark
    public void testParallelStream(Blackhole bh, Words words) {
        bh.consume(words.toSort.parallelStream()
                .filter(w -> w.startsWith(words.prefix))
                .collect(Collectors.toList())
        );
    }
    
    @Benchmark
    public void testManualThreading(Blackhole bh, Words words) {
        // This is quick and dirty, bit gives a decent baseline as to
        // what a manually threaded partitionning can achieve.
        List<Future<List<String>>> async = new ArrayList<>();
        // this has to be optimized to avoid creating "almost empty" work units
        int batchSize = words.size / ForkJoinPool.commonPool().getParallelism();
        int numberOfDispatchedWords = 0;
        while (numberOfDispatchedWords < words.toSort.size()) {
            int start = numberOfDispatchedWords;
            int end = numberOfDispatchedWords + batchSize;
            async.add(words.threadPool.submit(() -> {
                List<String> batch = words.toSort.subList(start, Math.min(end, words.toSort.size()));
                List<String> result = new ArrayList<>();
                for (String word : batch) {
                    if (word.startsWith(words.prefix)) {
                        result.add(word);
                    }
                }
                return result;
            }));
            numberOfDispatchedWords += batchSize;
        }
        List<String> result = new ArrayList<>();
        for (Future<List<String>> asyncResult : async) {
            try {
                result.addAll(asyncResult.get());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        bh.consume(result);
    }
    
    @State(Scope.Benchmark)
    public static class Words {
    
        ExecutorService threadPool = ForkJoinPool.commonPool();
    
        List<String> toSort;
    
        @Param({"100", "1000", "10000", "100000"})
        private int size;
    
        private String prefix = "AA";
    
        @Setup
        public void prepare() {
            //a 4 to 13 letters long, random word
            //for more precision, it should not be that random (use a fixed seed), but given the simple nature of the fitlering, I guess it's ok this way
            Supplier<String> wordCreator = () -> RandomStringUtils.random(4 + ThreadLocalRandom.current().nextInt(10));
            toSort = Stream.generate(wordCreator).limit(size).collect(Collectors.toList());
        }
    }
    

    这是结果

    Benchmark                     (size)   Mode  Cnt        Score       Error  Units
    PerfTest.testManualThreading     100  thrpt    6    95971,811 ±  1100,589  ops/s
    PerfTest.testManualThreading    1000  thrpt    6    76293,983 ±  1632,959  ops/s
    PerfTest.testManualThreading   10000  thrpt    6    34630,814 ±  2660,058  ops/s
    PerfTest.testManualThreading  100000  thrpt    6     5956,552 ±   529,368  ops/s
    PerfTest.testParallelStream      100  thrpt    6    69965,462 ±   451,418  ops/s
    PerfTest.testParallelStream     1000  thrpt    6    59968,271 ±   774,859  ops/s
    PerfTest.testParallelStream    10000  thrpt    6    29079,957 ±   513,244  ops/s
    PerfTest.testParallelStream   100000  thrpt    6     4217,146 ±   172,781  ops/s
    PerfTest.testSequentialFor       100  thrpt    6  3553930,640 ± 21142,150  ops/s
    PerfTest.testSequentialFor      1000  thrpt    6   356217,937 ±  7446,137  ops/s
    PerfTest.testSequentialFor     10000  thrpt    6    28894,748 ±   674,929  ops/s
    PerfTest.testSequentialFor    100000  thrpt    6     1725,735 ±    13,273  ops/s
    

    所以顺序版本看起来 方式 速度快到几千个元素,它们可以与10公里之前的手动线程和10公里之后的并行流相媲美,线程代码从那时起性能更好。

    考虑到编写“手动线程变量”所需的代码量,以及在那里创建错误的风险,或者由于计算批大小而导致效率低下,我可能不会选择该选项,即使它看起来可能比大型列表的流速度更快。

    我不会尝试先进行排序,然后进行二进制搜索,因为过滤是一个O(N)操作,然后对O(nlog(N))进行排序(在上面必须添加一个二进制搜索)。所以,除非您对数据有一个非常精确的模式,否则我看不到它对您有利。

    要知道,虽然不能得出结论,但这个基准不能支持。一方面,它基于这样一个假设:过滤是程序中唯一发生的事情,并且为CPU时间而战。如果您使用的是任何类型的“多用户”应用程序(例如Web应用程序),那么这可能不是真的,并且您很可能会失去通过多线程获得的一切。

        2
  •  2
  •   GDC    6 年前

    自Java 8以来,您可以使用流来解决以下问题:

    List<String> yourList = new ArrayList<>(); // A list whose size requires parallelism
    String yourPrefix = ""; // Your custom prefix
    final List<String> filteredList = yourList.parallelStream()
                   .filter(s -> s.startsWith(yourPrefix))
                   .collect(Collectors.toList());
    

    我建议你 this reading 看看 this question 了解并行性是否对您有帮助。