시뮬레이션 된 어닐링 - 성능 향상 가능?

Question

나는 시뮬레이트 된 어닐링 알고리즘 (Java)을 내가 연구하고있는 개인 프로젝트에 적용했지만 다른 언어 (예 : C++, Python 등)로 작성된 경우 SA 알고리즘이 동일한 데이터 세트에서 약간 더 잘 수행되는지 궁금합니다.).

내가 만든 더미 데이터 세트는 5 천 명의 사용자 이름, 우편 번호 및 생년월일로 구성됩니다.

많은 다른 정보를 추출하기 위해 SA 알고리즘이 데이터 세트에 적용됩니다.

현재 가장 최근의 테스트에서는 생년월일이 1 주일 이내 인 모든 사용자를 검색하도록 SA 알고리즘을 시도하고 있습니다. 이제 SA 알고리즘은 실제로 잘 작동합니다. 그러나 나는 완벽 주의자로서 조금 더 빠른 결과를 얻고 싶습니다. SA가 비슷한 크기의 데이터 세트에서 훌륭한 결과를 산출하는 좋은 경험을했는지 알고 싶지만 다른 언어로 쓰여 있습니까?

현재 SA 알고리즘은 성공적인 검색을 수행하는 데 5 초 미만의 시간이 걸립니다.

Answer 1

내가 자바

에

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 

를 작성합니다 종종 언어의 선택보다 더 중요한 사용하는 algorithim.

EDIT : 원래의 질문에 대한 답변으로, 같은 알고리즘을 사용하여 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); 
} 

인쇄 됨 약 31 ns의 평균을 의미

The search throughput was 32.4 million per second 

.