"일정"을 가장 효율적으로 편집하기 위한 좋은 알고리즘은 무엇입니까?
https://stackoverflow.com/questions/172302
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
소규모 일정 관리 앱용입니다.두 개의 "일정"을 효율적으로 비교하고, 차이점을 찾고, 변경된 데이터 행과 이 테이블을 외래 키로 갖는 다른 테이블의 항목만 업데이트하는 알고리즘이 필요합니다.이건 큰 질문이므로 바로 다음 중 하나를 찾고 있다고 말씀드리겠습니다. 일반적인 조언 또는 특정 솔루션.
편집하다: 제안한 대로 질문을 크게 줄였습니다.
한 테이블에서는 리소스를 사용되는 기간과 연결합니다.
또한 테이블 A의 ID를 외래 키로 사용하는 두 번째 테이블(테이블 B)도 있습니다.
테이블 B에 해당하는 테이블 A의 항목은 다음과 같은 시간 범위를 갖습니다. 포함한다 표 B의 시간 범위테이블 A의 모든 항목이 테이블 B의 항목을 갖는 것은 아닙니다.
사용자가 표 A의 리소스 일정을 편집할 수 있는 인터페이스를 제공하고 있습니다.기본적으로 테이블 A에 대해 처리해야 하는 새로운 데이터 세트를 제공합니다. 차이점 DB의 버전에서.
테이블 B가 가리키는 개체를 테이블 A에서 완전히 제거하면 테이블 B에서도 해당 항목을 제거하고 싶습니다.
따라서 다음 3개 세트가 주어집니다.
- 테이블 A의 원본 개체(DB에서)
- 테이블 B의 원본 개체(DB에서)
- 테이블 A에서 편집된 개체 세트(사용자가 제공하므로 고유 ID가 없음)
다음과 같은 알고리즘이 필요합니다.
- 해당 개체에 대해 변경이 필요하지 않은 경우 테이블 A와 테이블 B의 행을 그대로 둡니다.
- 필요에 따라 테이블 A에 행을 추가합니다.
- 필요에 따라 테이블 A와 테이블 B에서 행을 제거합니다.
- 필요에 따라 테이블 A와 테이블 B의 행을 수정합니다.
적절한 데이터베이스 작업을 적용할 수 있는 배열로 개체를 정렬하는 것만으로도 솔루션에 적합합니다.
다시 한번 다음과 같이 답변해 주십시오. 구체적으로 또는 일반적으로 당신이 원하는 대로 조언을 구하고 있지만 누군가가 내 하루를 즐겁게 해줄 완전한 알고리즘을 가지고 있다면요.:)
편집하다: lassvek에 대한 응답으로 몇 가지 추가 세부 정보를 제공합니다.
테이블 B의 항목은 단순히 겹치는 것이 아니라 항상 테이블 A 항목 내에 완전히 포함됩니다.
중요한 것은, 테이블 B의 항목은 양자화되어 있으므로 완전히 내부에 속하거나 외부에 속해야 합니다.이것이 발생하지 않으면 별도로 처리해야 하는 데이터 무결성 오류가 발생합니다.
예를 들어(약칭을 사용하려면):
Table A ID Resource Start End 01 Resource A 10/6 7:00AM 10/6 11:00AM 02 Resource A 10/6 1:00PM 10/6 3:00PM Table B ID Table_A_ID Start End 01 02 10/6 1:00PM 10/6 2:00PM
그래서 나는 다음과 같은 행동을 원합니다.
- 테이블 A에서 ID 02를 제거하거나 오후 2시~오후 3시로 줄이면 테이블 B에서 ID 01을 제거해야 합니다.
- 테이블 A ID 01을 오후 1시에 끝나는 위치로 확장하면, 이 두 항목은 하나의 행으로 병합되어야 합니다, 테이블 B ID 01은 이제 테이블 A ID 01을 가리켜야 합니다.
- 테이블 A ID 01에서 오전 8시~오전 10시를 제거하면 해당 항목은 두 개의 항목으로 분할되어야 합니다.하나는 오전 7시~8시이고 새 항목(ID 03)은 오전 10시~11시입니다.
해결책
나는 마침표를 사용하여 광범위하게 작업했지만 표 A와 B가 어떻게 함께 작동하는지 완전히 이해하지 못합니다. 아마도 단어일 것입니다. 포섭하다 나는 이해하지 못한다.
당신이 원하는 일에 대한 구체적인 예를 들어줄 수 있나요?
이렇게 테이블 A에 기록된 기간이 테이블 B의 기간 전체를 포함한다는 뜻인가요?
|---------------- A -------------------|
|--- B ----| |--- B ---|
아니면 겹칠까?
|---------------- A -------------------|
|--- B ----| |--- B ---|
아니면 반대로 B의 기간이 A와 포함/겹치나요?
B의 시간 범위가 테이블 A의 연결된 시간 범위와 동일하거나 내부에 있는 첫 번째 것이라고 가정해 보겠습니다.
이는 다음을 의미합니까?
* A removed A-timespan removes all the linked timespans from B
* An added A-timespan, what about this?
* A shortened A-timespan removes all the linked timespans from B that now falls outside A
* A lenghtened A-timespan, will this include all matching B-timespans now inside?
예는 다음과 같습니다.
|-------------- A1 --------------| |-------- A2 --------------|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
그런 다음 A1을 늘리고 A2를 줄여서 이동합니다.
|-------------- A1 ---------------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
이는 다음과 같이 데이터를 수정하고 싶다는 의미입니다.
1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead
이 수정은 어떻습니까? A1은 길어지지만 B3을 완전히 포함할 만큼 충분하지 않으며 A2도 같은 방식으로 이동/단축됩니다.
|-------------- A1 -----------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
이제 B3이 A1이나 A2에 완전히 속하지 않으므로 제거하시겠습니까?
당신이 원하는 것이 무엇인지에 대한 구체적인 예가 필요합니다.
편집하다 더 많은 질문
좋습니다. 다음은 어떻습니까?
|------------------ A -----------------------|
|------- B1 -------| |------- B2 ------|
|---| <-- I want to remove this from A
이건 어때?
어느 하나:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------| |B3| |--- B2 ---|
또는:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------|
지금까지 제가 본 관점을 질문과 함께 요약하자면 다음과 같습니다.
- A에서 다음 작업을 수행할 수 있기를 원합니다.
- 줄이다
- 길게 하다
- 인접한 경우 결합, 두 개 이상을 하나로 결합
- 마침표를 제거하여 구멍을 뚫어 분할합니다.
- 위 업데이트 후에도 여전히 A 내에 포함된 B는 필요한 경우 다시 연결합니다.
- 격리되었으나 지금은 완전히 외부에 있는 B, 삭제하세요.
- 격리되었으나 지금은 부분적으로 외부에 있는 B, 편집하다:이를 삭제하고 참조 데이터 무결성을 확인하세요.
- 위의 모든 작업에 대해 데이터를 작업에 맞춰 가져오는 데 필요한 최소한의 작업을 수행합니다(단순히 모든 것을 제거하고 새로 삽입하는 대신).
저는 직장에서 집에 돌아올 때 작동할 수 있는 C# 구현에 대해 연구할 예정이며, 오늘 밤 나중에 더 많은 내용을 가지고 돌아오겠습니다.
편집하다 여기 알고리즘이 있습니다.
- 먼저 새 목록을 최적화합니다(예:인접한 기간을 결합하는 등)
- 다음과 같은 방법으로 이 목록을 데이터베이스의 마스터 기간과 "병합"합니다.
- 두 목록의 위치를 추적합니다(예:신규 및 기존) 귀하는
- 현재 새 기간이 현재 기존 기간보다 완전히 이전인 경우 이를 추가한 후 다음 새 기간으로 이동합니다.
- 현재 새 기간이 현재 기존 기간보다 완전히 이후인 경우 기존 기간과 모든 하위 기간을 제거한 후 다음 기존 기간으로 이동합니다.
- 두 기간이 겹치는 경우 다음과 같은 방법으로 현재 기존 기간을 새 기간과 동일하게 조정한 후 다음 신규 및 기존 기간으로 이동합니다.
- 새 기간이 기존 기간보다 먼저 시작되면 시작 부분을 이동하면 됩니다.
- 기존 생리 기간 이후에 새 생리 기간이 시작되면 차등 생리 기간에 속하는 하위 생리 기간이 있는지 확인하고 이를 기억한 후 시작 위치를 이동합니다.
- 반대쪽도 똑같이 하세요
- "기억"한 기간이 있으면 다시 연결하거나 삭제해야 하는지 확인하세요.
대규모 단위 테스트 세트를 생성하고 모든 수정 조합을 포괄하는지 확인해야 합니다.
다른 팁
질문을 두 가지 별도의 질문으로 해체하는 것이 좋습니다. 첫 번째는 다음과 같은 것이어야합니다. "스케줄을 시작 시간과 종료 시간을 가진 리소스로 표현할 때 자원 스케줄링에 대한 이유는 무엇입니까?" 여기서 Adept의 Interval Algebra를 사용하겠다는 제안은 적합합니다. 참조하십시오 Wikipedia 항목 '간격 그래프' 그리고 스케줄링시 SUNY 알고리즘 저장소 항목. 두 번째 질문은 데이터베이스 질문입니다. "간격을 예약하고 두 간격이 겹치거나 다른 하나가 포함되어 있는지 여부를 나타내는 알고리즘이 주어지면이 정보를 사용하여 주어진 스키마에서 데이터베이스를 관리하는 방법은 무엇입니까?" 일단 스케줄링 알고리즘이 마련되면 데이터베이스 질문을 훨씬 쉽게 해결할 수 있다고 생각합니다. HTH, 유발
당신은 게시물이 거의 "너무 길다; 읽지 않았다"카테고리에 있습니다. 단축은 아마도 더 많은 피드백을 줄 것입니다.
어쨌든, 주제 : 당신은 "Interval Algebra"
제가 이해하는 바에 따르면 귀하의 사용자는 테이블 A에만 직접적인 영향을 미칠 수 있습니다.C#으로 프로그래밍한다고 가정하면 간단한 ADO.Net DataSet을 사용하여 테이블 A에 대한 수정 사항을 관리할 수 있습니다.TableAdapter는 변경되지 않은 행을 그대로 두고 새 행, 수정된 행, 삭제된 행을 적절하게 처리하는 방법을 알고 있습니다.
또한 테이블 B에서 해당 개체를 자동으로 제거하려면 계단식 삭제를 정의해야 합니다.
이런 방식으로 처리되지 않는 유일한 경우는 테이블 A의 기간이 단축되는 경우입니다.더 이상 테이블 B의 해당 레코드를 포함하지 않습니다.업데이트 저장 프로시저에서 해당 사례를 확인하거나 테이블 A에 업데이트 트리거를 정의할 수도 있습니다.
이에 대한 알고리즘은 나에게 NewA를 통과하는 패스, 일치 ResourceId, StartTime 및 EndTime을 통과하고 Olda의 어떤 요소가 맞는지 추적하는 것 같습니다. 그런 다음 비 일치하지 않는 데이터의 두 세트의 비 칭칭 네웨어와 타의 추종을 불허합니다.
내가 진행할 수있는 가장 간단한 방법은 기본적으로 다음과 같은 점을 시작하는 것입니다. 비 칭찬 네웨어를 DB에 쓰지 말고, B의 B의 요소를 undateedolda에서 가능한 경우 새로운 키 (생성)로 전송하여, 그렇지 않은 경우 삭제하십시오. 그런 다음 모든 타의 추종을 불러 일으키십시오.
많은 변화가 있다면, 이것은 확실히 효율적인 진행 방법이 아닙니다. 그러나 데이터의 크기가 압도적이지 않은 경우 영리한 최적화보다 단순성을 선호합니다.
이 최종 제안이 더 많은 배경없이 의미가 있는지 여부를 아는 것은 불가능하지만, 이런 식으로 생각하지 않았을 가능성이 있습니다.
전체 컬렉션을 앞뒤로 전달하는 대신 이벤트 리스너 또는 유사한 것을 사용하여 변경 사항이 필요한 경우에만 데이터 모델을 업데이트 할 수 있습니까? 이런 식으로 변경되는 객체는 즉시 필요한 DB 작업이 필요한 DB 작업을 결정할 수 있습니다.
