0

シミュレーテッドアニーリングアルゴリズム（Java）を、作業中の個人プロジェクトに適用しましたが、別の言語（C ++、Pythonなど）で記述した場合、SAアルゴリズムのパフォーマンスが同じデータセットでわずかに向上するかどうか疑問に思いました。

私が作成したダミーのデータセットは、5,000人のユーザーの名前、郵便番号、生年月日で構成されています。

SAアルゴリズムは、さまざまな情報を抽出するためにデータセットに適用されます。

現在、私の最新のテストでは、SAアルゴリズムを取得して、生年月日が互いに1週間以内（任意の年）にあるすべてのユーザーを検出しようとしています。現在、SAアルゴリズムは実際に非常にうまく機能します。しかし、私は完璧主義者なので、少し速い結果を達成したいと思います。同じサイズのデータ​​セットで優れた結果を生成するが、他の言語で書かれたSAで良い経験をした人がいるかどうか知りたいですか？

現時点では、SAアルゴリズムが検索を成功させるのに5秒弱かかります。

4

1 に答える 1

3

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

これは、検索ごとに平均約31nsを意味します。

于 2012-05-01T09:50:30.550 に答える