java - 模拟退火 - 可以提高性能吗？

Question

我已将模拟退火算法(Java 语言)应用到我正在从事的个人项目中，但想知道如果用另一种语言(即 C++、Python、等)。

我创建的虚拟数据集包含 5000 个用户的姓名、邮政编码和出生日期。

SA 算法应用于数据集，以提取许多不同的信息。

目前，我最近的测试是尝试让 SA 算法检测出生日期彼此相差一周以内(在任何给定年份)的所有用户。现在，SA算法确实运行得很好；然而，由于我是一个完美主义者，我希望获得稍微更快的结果，并且想知道是否有人有过使用 SA 在类似大小的数据集上产生出色结果但用其他语言编写的良好经验？

目前，SA 算法只需不到五秒即可成功执行搜索。

Answer 1

我会用Java编写它

public class UserSearchMain {
    static class Person {
        int id;
        int dateOfBirth;

        static Person[] generatePeople(int num) {
            Random rand = new Random();
            Person[] people = new Person[num];
            for (int i = 0; i < num; i++) {
                Person p = new Person();
                p.id = i;
                p.dateOfBirth = rand.nextInt(80 * 365); // any day for 80 years.
                people[i] = p;
            }
            return people;
        }
    }

    public static void main(String... args) {
        Person[] people = Person.generatePeople(5000);
        List<List<Person>> peopleByDOB = new ArrayList<List<Person>>();
        for (Person person : people) {
            int dob = person.dateOfBirth;
            while (peopleByDOB.size() <= dob) peopleByDOB.add(new ArrayList<Person>());
            peopleByDOB.get(dob).add(person);
        }

        Random rand = new Random();

        int warmup = 12 * 1000;
        int runs = 1000 * 1000;
        long start = 0;

        for (int i = -warmup; i < runs; i++) {
            if (i == 0) start = System.nanoTime();
            int dayToSearch = rand.nextInt(80 * 365);
            for (int j = Math.max(0, dayToSearch - 7); j <= dayToSearch + 7 && j < peopleByDOB.size(); j++) {
                List<Person> peopleWithCloseDOM = peopleByDOB.get(j);
            }
        }
        long time = System.nanoTime() - start;
        System.out.printf("Each search took an average of %,d ns%n", time / runs);
    }
}

打印

Each search took an average of 85 ns

通常，您使用的算法比语言的选择更重要。

编辑:在回答您原来的问题时，您可以使用相同的算法在 C++ 中使其更快吗？我猜是的，但不是很多。

<小时/>

要进一步加快速度，您可以使用多个线程。

public static void main(String... args) throws ExecutionException, InterruptedException {
    Person[] people = Person.generatePeople(5000);
    final List<List<Person>> peopleByDOB = new ArrayList<List<Person>>();
    for (Person person : people) {
        int dob = person.dateOfBirth;
        while (peopleByDOB.size() <= dob) peopleByDOB.add(new ArrayList<Person>());
        peopleByDOB.get(dob).add(person);
    }

    final int runs = 10 * 1000 * 1000;
    long start = System.nanoTime();

    int processors = Runtime.getRuntime().availableProcessors();
    ExecutorService service = Executors.newFixedThreadPool(processors);
    List<Future> futures = new ArrayList<Future>();
    for (int i = 0; i < processors; i++) {
        futures.add(service.submit(new Runnable() {
            @Override
            public void run() {
                Random rand = new Random();
                for (int i = 0; i < runs; i++) {
                    int dayToSearch = rand.nextInt(80 * 365);
                    for (int j = Math.max(0, dayToSearch - 7); j <= dayToSearch + 7 && j < peopleByDOB.size(); j++) {
                        List<Person> peopleWithCloseDOM = peopleByDOB.get(j);
                    }
                }
            }
        }));
    }
    for (Future future : futures) {
        future.get();
    }
    service.shutdown();
    double timeSec = (System.nanoTime() - start) / 1e9;
    double rate = processors * runs / timeSec / 1e6;
    System.out.printf("The search throughput was %.1f million per second%n", rate);
}

打印

The search throughput was 32.4 million per second

这意味着每次搜索的平均时间约为 31 ns。