제약이있는 다 대다 데이터 세트에서 중복을 효율적으로 찾을 수 있습니까?

Question

웹 응용 프로그램 을 사용하면 UI의 제한된 부분 만 수행 할 수있는 대량 작업 버전을 작성해야합니다. 원하는 작업은 개체를 범주에 할당하는 것입니다. 카테고리에는 개의 여러 객체가있을 수 있지만 특정 객체는 하나의 범주에만있을 수 있습니다.

작업에 대한 워크 플로는 다음과 같습니다 브라우저를 사용

1), 다음과 같은 형식의 파일이 업로드 :

# ObjectID, CategoryID 
Oid1, Cid1 
Oid2, Cid1 
Oid3, Cid2 
Oid4, Cid2 
[etc.] 

이 파일은 대부분 라인의 수십에서 수백있을 것이다

하지만, 에는 수천 개의 행이있을 수 있습니다.

주어진 개체 ID는 (개체가 하나의 범주에만 할당 될 수 있다는 사실을 반영하여)에 한 번만 발생합니다. 그러나 파일이 Google의 제어 외부에서 생성되었으므로 아무런 보장이 없습니다. 사실이며 처리는 그 가능성을 처리해야합니다.

2) 서버가 같은 페이지 뭔가를 구문 분석, 파일을받을 전처리 그것을 및 표시됩니다 : 사용자가 Yes 버튼을 클릭하면)

723 objects to be assigned to 126 categories 
142 objects not found 
42 categories not found 

Do you want to continue? 

[Yes]  [No] 

3 서버는 실제로 을 것이다 일해라.

나는 두 단계 (2)에서 파일을 구문 분석하고 싶지 않기 때문에 (3)의 일환으로 (2), 나는 요청에 걸쳐 살 것이다 컨테이너를 구축하고 유용한 표현을 개최합니다 데이터의 에 데이터를 쉽게 제공 할 수있게 해주는 "미리보기"페이지를 통해 을 효율적으로 처리 할 수 ​​있습니다. (분명히 우리가 세션을 가지고 있지만, 우리는 일반적으로 매우 작은 메모리 세션 상태를 유지 .)

할당이 UI를 통해 수행 할 때 사용되는 기존

assignObjectsToCategory(Set<ObjectId> objectIds, CategoryId categoryId) 

기능이 있습니다. 은 단순한 할당 외에도 다른 비즈니스 로직을 수행하며이 대량의 할당이 완료되면 동일한 비즈니스 로직이 필요하기 때문에 대량 작업을 위해이 API를 사용하는 것이 매우 바람직합니다. 이 파일은 과 관련된 범주 중 하나에 abitrarily 객체를 할당하는 것이 확인 될 것이다 -

처음에 그것은 "불법"파일이 지정된 객체에 대한 여러 범주를 지정한 경우 것으로 확인 될 것되었다.

그래서 나는 처음에 내가 구축하고 (특히 빠른 조회 및 삽입을위한 HashMap)는 Map<CategoryId, Set<ObjectId>> 다음 크로스 요청 용기에 넣어 것 파일을 통해 갔다 (2) 단계에서 그 생각 작업을 할 시간이었을 때 나는 을지도에서 반복하고 각각 을 Set<ObjectId>과 연결하여 assignObjectsToCategory()으로 전달했습니다.

그러나 중복을 처리하는 방법에 대한 요구 사항은 변경되었습니다. ObjectIdObjectId이 같은 CategoryId와 관련된 모든 시간을 파일에 여러 번 나타나고

• 경우, 해당 범주에 개체 를 할당 다음과 같이 그리고 그들은 지금 처리 할 수 ​​있습니다.
• 파일에 이 여러 번 나타나는 경우 CategoryId과 다른 경우 을 "미리보기"페이지에서 오류로 간주하십시오. 이 파일이 이미 CategoryId와 연관된의 ObjectId 난 그냥 읽어 을 감지 할 수있는 좋은 방법을 제공하지 않기 때문에 엉망 내 Map<CategoryId, Set<ObjectId>> 전략 을 보인다

.

그래서 내 질문은 가장 효율적으로 탐지하고 추적하는 방법입니다. 중복 ObjectId s입니까? 각 (ObjectId, CategoryId) 쌍에서 읽은대로

이

public CrossRequestContainer 
{ 
    ... 

    Map<CategoryId, Set<ObjectId>> objectsByCategory; // HashMap 
    Map<ObjectId, List<CategoryId>> categoriesByObject; // HashMap 
    Set<ObjectId> illegalDuplicates; 

    ... 
} 

다음에,이 모두지도에 넣어 얻을 것이다 : 마음에 와서 무엇

은 모두 "앞으로"사용지도를 "반대"하는 것입니다. 파일을 완전히 읽어 일단, 나는 은 할 수 :

for (Map.Entry<ObjectId, List<CategoryId>> entry : categoriesByObject.entrySet()) { 
    List<CategoryId> categories = entry.getValue(); 
    if (categories.size() > 1) { 
     ObjectId object = entry.getKey(); 
     if (!all_categories_are_equal(categories)) { 
      illegalDuplicates.add(object); 
      // Since this is an "illegal" duplicate I need to remove it 
      // from every category that it appeared with in the file. 
      for (CategoryId category : categories) { 
       objectsByCategory.get(category).remove(object); 
      } 
     } 
    } 
} 

이 루프가 완료되면, objectsByCategory는 더 이상 "불법" 중복 포함되지 않습니다 때, 그리고 illegalDuplicates는 에 모든 "불법"중복을 포함 할 수 필요에 따라 다시보고했다. 그런 다음 objectsByCategory을 반복하고 각 카테고리에 Set<ObjectId>을 입력하고 assignObjectsToCategory()으로 전화하여 할당을 수행 할 수 있습니다.

하지만이 방법이 효과가 있다고 생각되지만 입력 파일이 거대 할 때 특히 데이터를 두 번 저장하는 것이 걱정됩니다 (특히 ). 그리고 나는 또한 뭔가를 놓치고 있다고 걱정한다 : 효율성 그리고 이것은 매우 천천히 갈 것이다.

이중 메모리를 사용하지 않지만 빠르게 실행할 수있는 방법이 있습니까? 이중 메모리 사용으로도 여전히 많이 실행되는 것을 놓친 것입니까 내가 기대하는 것보다 느린가요?

Answer 1

주어진 제약 조건을 감안할 때 메모리를 적게 사용하는 방법은 없습니다.

한 가지 가능한 최적화하지만 즉, 단지 여러 범주에 나와있는 개체에 대한 범주의 목록을 유지하고, 그렇지 않으면 단지 범주에 개체를 매핑하는 것입니다,

Map<CategoryId, Set<ObjectId>> objectsByCategory; // HashMap 
Map<ObjectId, CategoryId> categoryByObject; // HashMap 
Map<ObjectId, Set<CategoryId>> illegalDuplicates; // HashMap 

예, 이것은 또 다른 컨테이너를 추가하지만 (희망을 갖고) 단지 몇개의 엔트리 만 포함합니다; 또한 categoryByObject 맵의 메모리 요구 사항이 줄어 듭니다 (항목 당 하나의 목록 오버 헤드가 줄어듬).

논리는 좀 더 복잡합니다.중복이 처음 발견되면 categoryByObject 맵에서 객체를 제거하고 illegalDuplicates 맵에 추가해야합니다. categoryByObject 맵에 오브젝트를 추가하기 전에 먼저 illegalDuplicates 맵을 점검해야합니다.

마지막으로 다른 두 개의지도를 작성한 후 후에 별도의 루프로 objectsByCategory 맵을 작성하는 것이 성능을 떨어 뜨리지는 않을 것이며 코드가 약간 단순해질 것입니다.