질문자 :Partick Höse
저는 가계도 소프트웨어(C++ 및 Qt로 작성)의 개발자입니다. 고객 중 한 명이 버그 보고서를 메일로 보내기 전까지는 아무런 문제가 없었습니다. 문제는 그 고객에게 딸과 함께 두 자녀가 있는데, 그 결과 오류로 인해 내 소프트웨어를 사용할 수 없다는 것입니다.
이러한 오류는 처리 중인 가족 그래프에 대한 나의 다양한 주장과 불변의 결과입니다(예를 들어, 한 사이클을 걷고 난 후 프로그램은 X가 Y의 아버지이자 할아버지가 될 수 없다고 명시합니다).
모든 데이터 어설션을 제거하지 않고 이러한 오류를 어떻게 해결할 수 있습니까?
귀하(및/또는 귀하의 회사)가 가계도가 무엇인지에 대한 근본적인 오해를 갖고 있는 것 같습니다.
분명히 말씀드리자면, 저는 포트폴리오에 가계도가 있는 회사에서 일하고 있으며 비슷한 문제로 어려움을 겪고 있습니다.
우리의 경우, 그리고 귀하의 경우에도 문제는 가족이 어떠해야 하는지에 대해 극도로 독단적인 GEDCOM 형식에서 비롯됩니다. 그러나 이 형식에는 가계도가 실제로 어떻게 생겼는지에 대한 몇 가지 심각한 오해가 있습니다.
GEDCOM은 동성 관계와의 비호환성, 근친상간 등과 같은 많은 문제를 가지고 있습니다. 실제 생활에서는 상상하는 것보다 더 자주 발생합니다(특히 1700-1800년으로 시간을 되돌릴 때).
이벤트(예: 출생, 결혼, 약혼, 결합, 사망, 입양 등)와 같은 현실 세계에서 발생하는 가계도를 모델링했습니다. 논리적으로 불가능한 경우를 제외하고는 제한을 두지 않습니다.
검증의 부족은 우리에게 더 "실제", 더 단순하고 더 유연한 솔루션을 제공합니다.
이 특정 경우에 대해서는 주장이 보편적으로 적용되지 않으므로 제거하는 것이 좋습니다.
(발생할) 문제를 표시하기 위해 필요한 만큼 동일한 노드를 그리는 것이 좋습니다. 그 중 하나를 선택할 때 모든 복사본을 켜서 복제를 암시합니다.
주장을 진정시키십시오.
99.9%의 고객이 데이터 입력에서 실수를 포착하는 데 매우 도움이 되는 규칙을 변경하는 것이 아닙니다.
대신 "관계를 추가할 수 없음" 오류에서 "어쨌든 추가"가 포함된 경고로 변경하십시오.
가계도의 문제는 다음과 같습니다. 나무가 아닙니다. 방향성 비순환 그래프 또는 DAG입니다. 인간 생식 생물학의 원리를 올바르게 이해한다면 순환은 없을 것입니다.
내가 아는 한, 기독교인들도 사촌 간의 결혼(따라서 자녀)을 받아들입니다. 그러면 가계도가 가족 DAG가 됩니다.
이야기의 교훈은 올바른 데이터 구조를 선택하는 것입니다.
나는 당신이 당신의 수표의 근거가 될 수 있는 사람을 고유하게 식별하는 어떤 가치를 가지고 있다고 생각합니다.
이것은 까다로운 것입니다. 구조를 트리로 유지하고 싶다고 가정하면 다음과 같이 제안합니다.
가정: A 는 자신의 딸과 함께 자녀가 있습니다.
A A 와 B 로 프로그램에 추가합니다. 일단 아버지 역할을 하면 남자친구라고 합시다.
프로그램의 출력 생성 부분에 B 가는 모든 링크가 데이터 표시 시 A 가야 함 is_same_for_out() 함수를 추가합니다.
이렇게 하면 사용자에게 약간의 추가 작업이 발생하지만 IT는 구현 및 유지 관리가 비교적 쉬울 것입니다.
A 와 B 를 동기화하는 코드 작업을 수행하여 불일치를 방지할 수 있습니다.
이 솔루션은 확실히 완벽하지는 않지만 첫 번째 접근 방식입니다.
당신은 당신의 소프트웨어에 진정한 가치를 부여 하는 것에 집중해야 합니다. 한 명의 소비자를 위해 사용하는 시간이 라이선스 가격만큼 가치가 있습니까? 그렇지 않을 가능성이 높습니다.
나는 당신이 이 고객에게 사과하고 그의 상황이 당신의 소프트웨어 범위를 벗어났다고 말하고 환불해 줄 것을 조언합니다.
이것이 "Go"와 같은 언어에 어설션이 없는 이유 중 하나입니다. 그들은 아마도 너무 자주 생각하지 않은 경우를 처리하는 데 사용됩니다. 당신은 단지 있을 법하지 않은 것이 아니라 불가능한 것만 주장해야 합니다 . 후자를 하는 것은 주장에 나쁜 평판을 주는 것입니다. 입력 할 때마다 assert( 10 분 도보 거리에 정말 그것에 대해 생각합니다.
당신의 특히 불안한 경우에 그러한 주장이 드물지만 가능한 상황에서 가짜가 될 것이라는 것은 상상할 수 있고 소름 끼치는 일입니다. 따라서 "이 소프트웨어는 귀하가 제시한 시나리오를 처리하도록 설계되지 않았습니다"라고만 말하는 경우 앱에서 처리하십시오.
당신의 증조할아버지가 당신의 아버지가 될 수 없다고 주장하는 것은 합리적인 일입니다.
내가 당신의 소프트웨어를 테스트하기 위해 고용된 테스트 회사에서 일하고 있었다면 당연히 그 시나리오를 제시했을 것입니다. 왜요? 어리지만 지적인 '사용자'는 모두 똑같은 일 을 하고 결과로 나오는 '버그 보고'를 즐길 것입니다.
나는 그런 엉망인 상황에 대해 논평하는 것을 싫어하지만 모든 불변량을 재조정하지 않는 가장 쉬운 방법은 근친상간 아빠에게 프록시 역할을 하는 가상 정점을 그래프에 만드는 것입니다.
그래서 가계도 소프트웨어에 대한 작업을 수행했습니다. 해결하려는 문제는 무한 루프에 빠지지 않고 트리를 걸을 수 있어야 한다는 것입니다. 즉, 트리는 비순환적이어야 합니다.
그러나 한 사람과 그들의 조상 사이에는 단 하나의 경로만 있다고 주장하는 것 같습니다. 사이클이 없다는 것을 보장하지만 너무 엄격합니다. 생물학적으로 말하면, 자손은 방향성 비순환 그래프 (DAG)입니다. 당신이 가지고 있는 경우는 확실히 퇴화한 경우이지만, 그런 유형의 일은 더 큰 나무에서 항상 발생합니다.
예를 들어, n세대에 있는 2^n명의 조상을 보면 겹치는 부분이 없었다면 서기 1000년에 살았던 사람보다 더 많은 조상을 갖게 될 것입니다. 따라서 겹치는 부분이 있어야 합니다.
그러나 잘못된 데이터만 있는 잘못된 주기도 가져오는 경향이 있습니다. 트리를 횡단하는 경우 주기를 처리해야 합니다. 각 개별 알고리즘에서 또는 로드 시 이 작업을 수행할 수 있습니다. 나는 부하에서 그것을했다.
트리에서 실제 주기를 찾는 것은 몇 가지 방법으로 수행할 수 있습니다. 잘못된 방법은 주어진 개인의 모든 조상을 표시하고 횡단할 때 다음으로 이동하려는 사람이 이미 표시되어 있으면 링크를 끊는 것입니다. 이렇게 하면 잠재적으로 정확한 관계가 끊어집니다. 올바른 방법은 각 개인에서 시작하여 각 조상에 해당 개인의 경로를 표시하는 것입니다. 새 경로에 현재 경로가 하위 경로로 포함되어 있으면 순환이므로 끊어야 합니다. 경로를 vector<bool>(MFMF, MFFFMF 등)로 저장할 수 있으므로 비교 및 저장이 매우 빠릅니다.
두 개의 반복자를 보내고 하위 집합 테스트와 충돌하는지 확인하는 것과 같이 주기를 감지하는 몇 가지 다른 방법이 있지만 결국 로컬 저장 방법을 사용했습니다.
또한 실제로 링크를 끊을 필요는 없습니다. 일반 링크에서 일부 알고리즘이 따르지 않는 '약한' 링크로 링크를 변경할 수 있습니다. 약한 것으로 표시할 링크를 선택할 때도 주의해야 합니다. 때로는 생년월일 정보를 보고 주기를 끊어야 하는 위치를 파악할 수 있지만 데이터가 너무 많이 누락되어 아무 것도 파악할 수 없는 경우가 많습니다.
어리석은 질문에 대한 또 다른 모의 진지한 대답:
실제 답은 적절한 데이터 구조를 사용하는 것입니다. 순환이 없는 순수한 나무로는 인간의 족보를 완전히 표현할 수 없습니다. 일종의 그래프를 사용해야 합니다. 또한 "서구 가부장적 일부일처 결혼"과 같은 가장 간단한 경우에도 계보를 모델링하려고 시도하면 유사한 오류가 발생할 수 있는 다른 곳이 많이 있으므로 이에 대해 더 진행하기 전에 인류학자와 상담하십시오.
여기에서 논의된 것처럼 국지적으로 금기시되는 관계를 무시하고 싶어도 가계도에 주기를 도입하는 완전히 합법적이고 완전히 예상치 못한 방법이 많이 있습니다.
예: http://en.wikipedia.org/wiki/Cousin_marriage
기본적으로 사촌 결혼은 일반적이고 예상될 뿐만 아니라 인간이 수천 개의 작은 가족 그룹에서 60억의 전 세계 인구로 이동한 이유입니다. 다른 방법으로는 작동하지 않습니다.
족보, 가족 및 혈통에 관해서는 보편자가 거의 없습니다. 누가 이모가 될 수 있는지, 누가 누구와 결혼할 수 있는지, 또는 자녀가 상속을 목적으로 합법화되는 방식을 제안하는 규범에 대한 거의 모든 엄격한 가정은 세계 또는 역사의 어딘가에 있는 예외에 의해 뒤집힐 수 있습니다.
잠재적인 법적 의미는 제쳐두고, 가계도의 '노드'를 1인칭이 될 수 있다고 가정하기 보다는 가계도의 '노드'를 전임자로 취급해야 할 필요가 있는 것 같습니다.
트리 노드에 사람과 후임자가 포함되도록 하면 동일한 사람과 다른 후임자를 포함하는 더 깊은 트리 아래에 다른 노드가 있을 수 있습니다.
몇 가지 답변이 주장/불변을 유지하는 방법을 보여주었지만 이것은 주장/불변을 오용하는 것처럼 보입니다. 주장은 참이어야 하는 것이 참인지 확인하는 것이고 불변은 변경되어서는 안 되는 것이 변경되지 않는지 확인하는 것입니다.
여기서 주장하는 것은 근친상간 관계가 존재하지 않는다는 것입니다. 당신의 주장이 잘못 그래서 분명히 그들은 존재 해. 이 어설션을 해결할 수 있지만 실제 버그는 어설션 자체에 있습니다. 주장을 제거해야 합니다.
가계도는 지시된 관계를 사용해야 합니다. 이렇게 하면 주기가 없습니다.
계보 데이터는 순환적이며 비순환적 그래프에 맞지 않으므로 순환에 대한 주장이 있는 경우 이를 제거해야 합니다.
사용자 정의 보기를 생성하지 않고 보기에서 이것을 처리하는 방법은 순환 상위를 "고스트" 상위로 취급하는 것입니다. 즉, 한 사람이 한 사람의 아버지이자 할아버지인 경우에는 할아버지 노드가 정상적으로 표시되지만 아버지 노드는 ("할아버지 참조"와 같은 간단한 레이블을 가진 "유령" 노드로 렌더링됩니다. ) 할아버지를 가리킵니다.
계산을 수행하려면 주기가 있는 경우 노드를 두 번 이상 방문하지 않도록 순환 그래프를 처리하도록 논리를 개선해야 할 수 있습니다.
가장 중요한 것은 avoid creating a problem 것이므로 순환을 피하기 위해서는 직접적인 관계 를 사용해야 한다고 생각합니다.
@markmywords가 말했듯이 #include "fritzl.h".
마지막으로 recheck your data structure . 아마도 거기에 문제가 있을 수 있습니다(양방향 연결 목록이 문제를 해결할 수 있음).
일반적으로 주장은 실제 데이터와의 접촉에서 살아남지 못합니다. 처리하려는 데이터와 범위를 벗어난 데이터를 결정하는 것은 소프트웨어 엔지니어링 프로세스의 일부입니다.
가족 "나무"(실제로는 주기를 포함하여 완전한 그래프임)와 관련하여 다음과 같은 좋은 일화가 있습니다.
나는 장성한 딸이 있는 과부와 결혼했다. 우리를 자주 찾아오시던 아버지가 의붓딸과 사랑에 빠져 결혼했다. 그 결과 아버지는 아들이 되었고 딸은 어머니가 되었습니다. 얼마 후 나는 아버지의 동생인 아들과 삼촌을 아내에게 주었습니다. 아버지의 아내(내 딸이자 어머니이기도 함)에게는 아들이 있습니다. 그 결과 한 사람에게 형제와 손자를 갖게 되었습니다. 제 아내는 이제 제 할머니입니다. 왜냐하면 그녀는 제 어머니의 어머니이기 때문입니다. 그래서 저는 아내의 남편이자 아내의 의붓손자입니다. 즉, 나는 내 할아버지입니다.
대리모 또는 "흐릿한 아버지"를 고려할 때 상황은 더욱 이상해집니다.
귀하의 소프트웨어가 그러한 드문 경우를 처리해서는 안 된다고 결정할 수 있습니다. 이러한 경우 사용자는 다른 제품을 사용해야 합니다. 이렇게 하면 더 많은 주장과 더 간단한 데이터 모델을 유지할 수 있기 때문에 더 일반적인 경우를 훨씬 더 강력하게 처리할 수 있습니다.
이 경우 사용자가 필요할 때 다른 제품으로 쉽게 마이그레이션할 수 있도록 소프트웨어에 몇 가지 좋은 가져오기 및 내보내기 기능을 추가하십시오.
사용자가 수동 관계를 추가하도록 허용할 수 있습니다. 이러한 관계는 "일류 시민"이 아닙니다. 즉, 소프트웨어는 이러한 관계를 있는 그대로 가져오고 확인하지 않으며 기본 데이터 모델에서 처리하지 않습니다.
그러면 사용자가 손으로 드문 경우를 처리할 수 있습니다. 데이터 모델은 여전히 매우 단순하게 유지되고 주장은 유지됩니다.
수동 관계에 주의하십시오. 그것들을 완전히 구성 가능하게 만들고 완전히 구성 가능한 데이터 모델을 만들고 싶은 유혹이 있습니다. 이것은 작동하지 않습니다. 소프트웨어가 확장되지 않고 이상한 버그가 발생하고 마침내 사용자 인터페이스를 사용할 수 없게 됩니다. 이 안티 패턴을 "소프트 코딩" 이라고 하며 "The Daily WTF" 에는 이에 대한 예제가 가득합니다.
최후의 수단은 데이터 모델을 보다 유연하게 만드는 것입니다. 거의 모든 주장을 건너뛰고 완전한 그래프를 기반으로 데이터 모델을 만들어야 합니다. 위의 예에서 볼 수 있듯이 쉽게 자신의 할아버지가 될 수 있으므로 사이클을 가질 수도 있습니다.
이 경우 소프트웨어를 광범위하게 테스트해야 합니다. 거의 모든 어설션을 건너뛰어야 하므로 추가 버그가 발생할 가능성이 높습니다.
테스트 데이터 생성기를 사용하여 비정상적인 테스트 케이스를 확인하십시오. Haskell , Erlang 또는 C 에 대한 빠른 확인 라이브러리가 있습니다. Java / Scala의 경우 ScalaCheck 및 Nyaya가 있습니다. 한 가지 테스트 아이디어는 무작위 모집단을 시뮬레이션하고 무작위로 교배하도록 한 다음 소프트웨어가 먼저 결과를 가져온 다음 내보내도록 하는 것입니다. 출력의 모든 연결이 입력에도 있고 그 반대도 마찬가지입니다.
속성이 동일하게 유지되는 경우를 불변이라고 합니다. 이 경우 불변량은 시뮬레이션된 모집단의 개인 간의 "로맨틱 관계" 집합입니다. 가능한 한 많은 불변량을 찾고 무작위로 생성된 데이터로 테스트하십시오. 불변은 기능적일 수 있습니다. 예:
또는 기술적일 수 있습니다.
시뮬레이션된 테스트를 실행하면 이상한 코너 케이스를 많이 찾을 수 있습니다. 그것들을 고치는 데는 많은 시간이 걸릴 것입니다. 또한 많은 최적화가 손실되고 소프트웨어가 훨씬 느리게 실행됩니다. 그만한 가치가 있는지, 그리고 이것이 귀하의 소프트웨어 범위에 속하는지 결정해야 합니다.
모든 주장을 제거하는 대신, 여전히 사람이 자신의 부모이거나 기타 불가능한 상황을 확인하고 오류를 제시해야 합니다. 사용자가 여전히 일반적인 입력 오류를 감지할 수 있도록 가능성이 거의 없는 경우 경고를 발행할 수 있지만 모든 것이 정확하면 작동합니다.
각 사람에 대한 영구 정수가 있는 벡터에 데이터를 저장하고 해당 int가 벡터의 인덱스인 사람 개체에 부모와 자식을 저장합니다. 이것은 세대 간 이동에 매우 빠르지만 이름 검색과 같은 경우에는 느립니다. 객체는 생성된 순서대로 정렬됩니다.
아버지를 복제하십시오(또는 심볼릭 링크/참조 사용).
예를 들어, 계층적 데이터베이스를 사용하는 경우:
$ #each person node has two nodes representing its parents. $ mkdir Family $ mkdir Family/Son $ mkdir Family/Son/Daughter $ mkdir Family/Son/Father $ mkdir Family/Son/Daughter/Father $ ln -s Family/Son/Daughter/Father Family/Son/Father $ mkdir Family/Son/Daughter/Wife $ tree Family Family └── Son ├── Daughter │ ├── Father │ └── Wife └── Father -> Family/Son/Daughter/Father 4 directories, 1 file출처 : http:www.stackoverflow.com/questions/6163683/cycles-in-family-tree-software
| "git commit" 대신 수행된 "git commit --amend"를 실행 취소하는 방법 (0) | 2022.02.15 |
|---|---|
| 숨김에 대한 Git diff (0) | 2022.02.15 |
| Mathematica로 Waldo를 어떻게 찾나요? (0) | 2022.02.15 |
| 업데이트 및 삭제를 위한 HTTP 상태 코드? (0) | 2022.02.15 |
| stdin에서 어떻게 읽습니까? (0) | 2022.02.15 |