bash: 주어진 부모-자식 세트의 루트 노드를 효율적으로 찾는 방법

Question 1

귀하의 파일에 특정 문자로 구분된 2개의 열이 있다고 가정합니다.

문제를 좀 더 자세히 살펴보면 루트 노드는 결코 자식 노드로 나타나지 않습니다. 배열의 부모를 추적하고 자식이면 개수를 늘립니다. 개수가 0인 배열 키가 루트 노드가 됩니다.

awk -F, '
   !($1 in p) {p[$1]=0}   # register a parent in the array
   {p[$2]++}              # increment the count when it's seen as a child
   END {for (n in p) if (p[n] == 0) print n}
' bigfile

@filbranden이 지적했듯이 이는 루트 노드만 찾습니다.

직장에서도 비슷한 상황이 있습니다. Oracle 데이터베이스에는 상위 항목과 하위 항목이 포함된 테이블이 있습니다. 우리는 하위 ID를 매핑하는 뷰를 만듭니다.길상위로 연결되는 ID:

id parent_id
 1 null
 2 1
 3 2
 4 1
 5 null
 6 5

보기는 다음과 같습니다

id id_path
 1 1
 2 1\2
 3 1\2\3
 4 1\4
 5 5
 6 5\6

이는 PL/SQL을 통해 달성됩니다.

CREATE OR REPLACE VIEW "SCHEMA"."ITEM_PATHS" ("ID", "ID_PATH") AS
SELECT 
    pci."ID",
    substr(SYS_CONNECT_BY_PATH(pci.id, '\'), 2)  AS ID_PATH
  FROM schema.parent_child_items pci
    START WITH parent_id IS NULL
    CONNECT BY prior id = parent_id;

따라서 데이터베이스에서도 이는 작은 문제가 아닙니다. 그러나 나는 데이터베이스가 더 큰 데이터 세트를 더 잘 처리할 수 있다고 믿습니다.

Answer

귀하의 파일에 특정 문자로 구분된 2개의 열이 있다고 가정합니다.

문제를 좀 더 자세히 살펴보면 루트 노드는 결코 자식 노드로 나타나지 않습니다. 배열의 부모를 추적하고 자식이면 개수를 늘립니다. 개수가 0인 배열 키가 루트 노드가 됩니다.

awk -F, '
   !($1 in p) {p[$1]=0}   # register a parent in the array
   {p[$2]++}              # increment the count when it's seen as a child
   END {for (n in p) if (p[n] == 0) print n}
' bigfile

@filbranden이 지적했듯이 이는 루트 노드만 찾습니다.

직장에서도 비슷한 상황이 있습니다. Oracle 데이터베이스에는 상위 항목과 하위 항목이 포함된 테이블이 있습니다. 우리는 하위 ID를 매핑하는 뷰를 만듭니다.길상위로 연결되는 ID:

id parent_id
 1 null
 2 1
 3 2
 4 1
 5 null
 6 5

보기는 다음과 같습니다

id id_path
 1 1
 2 1\2
 3 1\2\3
 4 1\4
 5 5
 6 5\6

이는 PL/SQL을 통해 달성됩니다.

CREATE OR REPLACE VIEW "SCHEMA"."ITEM_PATHS" ("ID", "ID_PATH") AS
SELECT 
    pci."ID",
    substr(SYS_CONNECT_BY_PATH(pci.id, '\'), 2)  AS ID_PATH
  FROM schema.parent_child_items pci
    START WITH parent_id IS NULL
    CONNECT BY prior id = parent_id;

따라서 데이터베이스에서도 이는 작은 문제가 아닙니다. 그러나 나는 데이터베이스가 더 큰 데이터 세트를 더 잘 처리할 수 있다고 믿습니다.

Question 2

제가 제안하는 것은 더 이상 진행이 불가능할 때까지 각 단계에서 한 단계 더 깊이 들어가 근본 원인을 발견하는 반복적 접근 방식을 사용하는 것입니다. 따라서 첫 번째 단계에서는 parent child쌍을 가져와 첫 번째 조상을 찾고 grandparent child쌍을 출력한 다음 두 번째 단계에서 쌍을 출력하는 great-grandparent child식으로 진행됩니다.

이것을 사용하여 달성할 수 있습니다.join(1), 여기서 한 파일의 첫 번째 필드를 다른 파일의 두 번째 필드와 일치시켜 노드를 상위 노드로 바꿉니다. join(1)파일을 정렬해야 하며 다음을 사용하여 쉽게 수행할 수 있습니다.sort(1).

이 작업을 수행하려면 아래 스크립트를 사용할 수 있습니다. 입력 파일에는 한 줄에 nodes.txt공백으로 구분된 한 쌍의 노드가 있다고 가정합니다. 각 행에 대한 행 쌍이 포함된 결과가 parent child생성됩니다 .roots.txtroot child

export LC_COLLATE=C
sort -k 2 nodes.txt -o nodes.bychild
: >roots.txt
sort -k 1 nodes.txt -o nodes.0
depth=0
while [[ -s nodes.0 ]]; do
  echo "Depth: $((depth++)) - $(date)"
  join -1 2 -2 1 -o '1.1 2.2' nodes.bychild nodes.0 | sort -k 1 -o nodes.1
  # Nodes not present in nodes.1 have
  # their root in nodes.0 already:
  join -1 2 -2 1 -v 2 -o '2.1 2.2' nodes.bychild nodes.0 >>roots.txt
  # Next step:
  mv nodes.1 nodes.0
done
rm nodes.0 nodes.bychild
sort -k 2 roots.txt -o roots.txt

당신은 할 수온라인으로 사용해 보세요작은 샘플 입력용.

이 방법을 사용하려면 하드 드라이브에 여유 공간을 확보하기 위해 데이터 세트 크기의 약 5배가 필요합니다(인덱스용으로 1개 , 동시에 존재하는 nodes.bychild2개 , 정렬용으로 1개, 결과 파일용으로 1개).nodes.0nodes.1roots.txt

각 반복에는 두 개의 호출이 있습니다 join(1). 하나는 한 수준 더 깊이 이동하고 다른 하나는 -v루트 노드가 발견될 때 감지하기 위해 일치하는 항목이 없는 경우를 찾는 것입니다. 이로 인해 몇 가지 단점이 드러나기 시작했으며 join(1)보다 유연한 도구를 사용하면 두 작업을 한 단계로 수행할 수 있습니다. 보다 유연한 도구의 또 다른 장점은 하위 항목에서 루트까지의 경로가 보존된다는 것입니다. 이는 join(1)단독으로 사용하면 그다지 명확하지 않습니다. 이를 join(1)고급 언어(예: Python)로 작성된 간단한 도구로 바꾸면 이 스크립트의 기능이 크게 향상될 수 있습니다.

복잡성 분석

이 join(1)도구는 O(1) 공간을 사용하고 O(n) 시간이 걸리기 때문에 사용하기 매우 쉽습니다. 파일을 정렬해야 하기 때문에 각 파일을 한 번에 한 줄만 고려하고 다음 줄(또는 일치하는 경우 동시에 두 줄 모두)을 진행하므로 공간이 일정합니다. 각 파일의 각 줄을 한 번만 읽기 때문에 선형 시간에 실행됩니다.

따라서 순환적 복잡성의 중요한 요소는 sort(1)O(n log n) 시간이 걸린다는 것입니다. 입력이 매우 큰 경우 Unix 구현에서는 sort(1)임시 파일을 사용하여 임시 결과를 저장하므로 메모리보다 훨씬 큰 데이터 세트를 정렬할 수 있습니다. 사용되는 임시 디스크 공간은 sort(1)O(n) 공간을 사용합니다(위의 디스크 요구 사항에서 언급됨).

각 루프 반복에는 O(n log n) 시간이 걸리므로 총 실행 시간은 이 루프가 실행되는 횟수에 비례하며 자식과 해당 루트 사이의 수준 수에 비례합니다. 최악의 경우는 자식 노드에서 루트 노드까지 단 하나의 체인만 있다는 것입니다. 이 경우 깊이는 다음과 같습니다.N이 알고리즘은 O(n² log n)을 사용하지만 대부분의 실제 경우 깊이는 다음보다 훨씬 낮을 것으로 예상됩니다.N따라서 시간 복잡도는 이것보다 훨씬 작습니다.

또한 더 깊은 깊이로 노드의 긴 꼬리에 들어가기 시작하면N일반적으로 더 빨리 작아지므로 귀하의 경우 100x(긴 꼬리의 경우 최악의 경우 깊이)보다는 5-10x(일반적인 깊이)를 생각하는 것이 더 쉬울 수 있습니다.

여기서 분명한 개선점은 현재 단계를 계산할 때 이전 단계의 출력을 고려하는 것입니다. 예를 들어 (3->2->1) 관계와 (5->4->3) 관계를 설정하면 (5-> 대신 (5->1)로 직접 이동할 수 있어야 합니다. 2) 추가 단계도 기하급수적으로 빨라집니다(예: 9->5 및 5->1은 9->1이 되며, 현재 방법은 8단계가 필요한 반면 최적화된 방법은 3단계만 필요합니다.) - 포즈 방법. 복잡성이 O(n log² n)인 경우(깊이는 이제 지수적이므로 최대값에 도달하는 데 O(log n) 단계만 소요됨) 일반적인 경우에도 매우 유용할 수 있습니다.

join(1)Custom-made를 이용하여 구현이 가능할 수도 있습니다

이것이 일반적인 사용 사례라면 시간을 내어 보다 현명한 접근 방식을 구현해 보세요. 이것이 일회성이라면 위의 빠르고 더러운 스크립트로 충분할 수 있습니다.

(중요한 사용 사례인 경우 대신 데이터베이스를 사용하세요!)

Answer

제가 제안하는 것은 더 이상 진행이 불가능할 때까지 각 단계에서 한 단계 더 깊이 들어가 근본 원인을 발견하는 반복적 접근 방식을 사용하는 것입니다. 따라서 첫 번째 단계에서는 parent child쌍을 가져와 첫 번째 조상을 찾고 grandparent child쌍을 출력한 다음 두 번째 단계에서 쌍을 출력하는 great-grandparent child식으로 진행됩니다.

이것을 사용하여 달성할 수 있습니다.join(1), 여기서 한 파일의 첫 번째 필드를 다른 파일의 두 번째 필드와 일치시켜 노드를 상위 노드로 바꿉니다. join(1)파일을 정렬해야 하며 다음을 사용하여 쉽게 수행할 수 있습니다.sort(1).

이 작업을 수행하려면 아래 스크립트를 사용할 수 있습니다. 입력 파일에는 한 줄에 nodes.txt공백으로 구분된 한 쌍의 노드가 있다고 가정합니다. 각 행에 대한 행 쌍이 포함된 결과가 parent child생성됩니다 .roots.txtroot child

export LC_COLLATE=C
sort -k 2 nodes.txt -o nodes.bychild
: >roots.txt
sort -k 1 nodes.txt -o nodes.0
depth=0
while [[ -s nodes.0 ]]; do
  echo "Depth: $((depth++)) - $(date)"
  join -1 2 -2 1 -o '1.1 2.2' nodes.bychild nodes.0 | sort -k 1 -o nodes.1
  # Nodes not present in nodes.1 have
  # their root in nodes.0 already:
  join -1 2 -2 1 -v 2 -o '2.1 2.2' nodes.bychild nodes.0 >>roots.txt
  # Next step:
  mv nodes.1 nodes.0
done
rm nodes.0 nodes.bychild
sort -k 2 roots.txt -o roots.txt

당신은 할 수온라인으로 사용해 보세요작은 샘플 입력용.

이 방법을 사용하려면 하드 드라이브에 여유 공간을 확보하기 위해 데이터 세트 크기의 약 5배가 필요합니다(인덱스용으로 1개 , 동시에 존재하는 nodes.bychild2개 , 정렬용으로 1개, 결과 파일용으로 1개).nodes.0nodes.1roots.txt

각 반복에는 두 개의 호출이 있습니다 join(1). 하나는 한 수준 더 깊이 이동하고 다른 하나는 -v루트 노드가 발견될 때 감지하기 위해 일치하는 항목이 없는 경우를 찾는 것입니다. 이로 인해 몇 가지 단점이 드러나기 시작했으며 join(1)보다 유연한 도구를 사용하면 두 작업을 한 단계로 수행할 수 있습니다. 보다 유연한 도구의 또 다른 장점은 하위 항목에서 루트까지의 경로가 보존된다는 것입니다. 이는 join(1)단독으로 사용하면 그다지 명확하지 않습니다. 이를 join(1)고급 언어(예: Python)로 작성된 간단한 도구로 바꾸면 이 스크립트의 기능이 크게 향상될 수 있습니다.

복잡성 분석

이 join(1)도구는 O(1) 공간을 사용하고 O(n) 시간이 걸리기 때문에 사용하기 매우 쉽습니다. 파일을 정렬해야 하기 때문에 각 파일을 한 번에 한 줄만 고려하고 다음 줄(또는 일치하는 경우 동시에 두 줄 모두)을 진행하므로 공간이 일정합니다. 각 파일의 각 줄을 한 번만 읽기 때문에 선형 시간에 실행됩니다.

따라서 순환적 복잡성의 중요한 요소는 sort(1)O(n log n) 시간이 걸린다는 것입니다. 입력이 매우 큰 경우 Unix 구현에서는 sort(1)임시 파일을 사용하여 임시 결과를 저장하므로 메모리보다 훨씬 큰 데이터 세트를 정렬할 수 있습니다. 사용되는 임시 디스크 공간은 sort(1)O(n) 공간을 사용합니다(위의 디스크 요구 사항에서 언급됨).

각 루프 반복에는 O(n log n) 시간이 걸리므로 총 실행 시간은 이 루프가 실행되는 횟수에 비례하며 자식과 해당 루트 사이의 수준 수에 비례합니다. 최악의 경우는 자식 노드에서 루트 노드까지 단 하나의 체인만 있다는 것입니다. 이 경우 깊이는 다음과 같습니다.N이 알고리즘은 O(n² log n)을 사용하지만 대부분의 실제 경우 깊이는 다음보다 훨씬 낮을 것으로 예상됩니다.N따라서 시간 복잡도는 이것보다 훨씬 작습니다.

또한 더 깊은 깊이로 노드의 긴 꼬리에 들어가기 시작하면N일반적으로 더 빨리 작아지므로 귀하의 경우 100x(긴 꼬리의 경우 최악의 경우 깊이)보다는 5-10x(일반적인 깊이)를 생각하는 것이 더 쉬울 수 있습니다.

여기서 분명한 개선점은 현재 단계를 계산할 때 이전 단계의 출력을 고려하는 것입니다. 예를 들어 (3->2->1) 관계와 (5->4->3) 관계를 설정하면 (5-> 대신 (5->1)로 직접 이동할 수 있어야 합니다. 2) 추가 단계도 기하급수적으로 빨라집니다(예: 9->5 및 5->1은 9->1이 되며, 현재 방법은 8단계가 필요한 반면 최적화된 방법은 3단계만 필요합니다.) - 포즈 방법. 복잡성이 O(n log² n)인 경우(깊이는 이제 지수적이므로 최대값에 도달하는 데 O(log n) 단계만 소요됨) 일반적인 경우에도 매우 유용할 수 있습니다.

join(1)Custom-made를 이용하여 구현이 가능할 수도 있습니다

이것이 일반적인 사용 사례라면 시간을 내어 보다 현명한 접근 방식을 구현해 보세요. 이것이 일회성이라면 위의 빠르고 더러운 스크립트로 충분할 수 있습니다.

(중요한 사용 사례인 경우 대신 데이터베이스를 사용하세요!)

Question 3

만약에귀하의 설명과 요구 사항을 잘 이해합니다. 계층적으로 관련된 노드 집합에서 트리를 재구성해야 하는 것 같습니다.

나는 이것이 적절한 데이터베이스 엔진을 위한 작업이라는 다른 모든 사람들의 의견에 동의하지만 표준 명령줄 도구를 사용해야 하는 경우 파일 시스템을 "데이터베이스", 즉 노드 인덱스로 사용하는 것이 또 다른 옵션일 수 있습니다.

따라서 최종 결과를 얻으려면 모든 노드를 2번 통과해야 합니다.

먼저 입력 데이터세트에서 전달되어 파일 시스템에 표현을 생성합니다. 여기서 각 개별 노드는 상위 노드/디렉토리에 대한 심볼릭 링크를 포함하는 디렉터리가 됩니다.
두 번째 패스는 모든 노드를 루트 노드까지 순회한 다음 요구 사항에 따라 상위 및 루트 노드와 함께 각 노드를 표시합니다.

개념적으로는 간단하지만 몇 가지 중요한 단점이 있습니다.

가장 큰 단점은 기본적으로 사용 중인 파일 시스템의 기능에 따라 달라지며 다음 요소를 고려하여 이러한 목적으로 설계된 전용 파일 시스템을 준비해야 할 가능성이 높다는 것입니다.

단일 디렉토리에 포함된 수백만 개의 디렉토리를 처리할 때 파일 시스템 성능: 예를 들어 ext4는 수만 개의 디렉토리를 처리한 후 많이 떨어지기 때문에 그다지 좋지 않습니다. 그러나 아마도 이것이 최선의 옵션은 reiserfs입니다. (아마 최고일 것임) 또는 btrfs(reiserfs보다 약간 느림) 그러나 언급한 숫자에 따르면 btrfs 또는 reiserfs를 사용하더라도 여전히 노드/디렉토리 수를 중간(하위 수준) 하위 디렉터리로 나누어야 합니다. 어떤 디렉토리에도 1M 이상을 넣지 마십시오. 디렉토리
너무 많은 노드/디렉터리를 저장할 때 파일 시스템의 압축성(필요한 디스크 공간)(각각은 심볼릭 링크만 포함하고 두 번째 패스 이후에는) 매우 작은 파일: 여기에서는 낭비되는 디스크 공간이 많이 필요합니다. 파일 시스템의 표준 구성은 일반적으로 디렉터리 또는 파일당 4k, 즉 노드당 총 8-12k를 할당합니다. 하지만 파일 시스템에서는 포맷할 때 이에 대한 일부 조정, 특히 최소 할당 크기를 허용하지만 그 이하도 기대할 수 없습니다. 노드당 2~3,000개보다 노드의 상위 및 루트를 저장하면 훨씬 더 컴팩트해질 수 있습니다.확장된 속성심볼릭 링크와 파일 대신에, 그래도 노드당 1,000개 이상일 것입니다.

또 다른 단점은 이 모든 것을 처리하기 위해 사용하는 언어입니다. 쉘 스크립트를 사용하는 것은매우mkdir각 단일 노드에는 해당 상위 노드에 대한 분기 및 실행 ln -s(또는 setfattrLinux에서는 단일, MacOS에서는 단일) 링크가 필요하기 때문에 첫 번째 패스는 느립니다. xattr이는 2개의 분기 및 실행 곱하기 수천만 번을 의미합니다. 이 분기 및 실행 작업은 관련 시스템 호출(예: mkdir(2) 및 Symlink(2)/setxattr(2))을 직접 사용할 수 있는 언어로 전체 첫 번째 단계를 개발할 수 있다면 좋을 것입니다. 제거되었습니다.

구체적으로, 간단한예첫 번째 패스에 대한 스크립트(주로 적용할 기본 작업을 표시하기 위한 의사코드)는 다음과 같습니다.

while read -r child parent; do
    # here I use '-p' only for 'no error if existing'
    mkdir -p $child $parent  # <-- note lack of quotes for once, so to ignore empty $parent
    [ $parent ] && (cd $child && ln -s ../${parent} parent)
done

스크립트는 각 하위/상위 쌍이 공백으로 분리되어 자체 줄에 있다고 가정하고, 알려진 루트가 각각 하나의 ID만 있는(즉, 상위 없음) 줄로 예상하며 모두 표준 입력에 제공됩니다.

데모를 단순화하기 위해 스크립트는 다음을 수행합니다.아니요중간 하위 디렉터리를 사용합니다. 즉, 하나의(실제로는 현재) 디렉터리에 모든 노드/디렉터리를 생성합니다. 말한 바와 같이,그건 금기야노드가 1M을 초과하는 경우.

하나 이상의 디렉터리 하위 수준을 제공하려면 최상의 분할 방법을 선택하기 위해 노드의 ID 특성에 대한 지식이 필요합니다. 예를 들어, 20비트 ID에서 사용하는 실제 주소 공간이 고르게 분산된 경우 간단한 모듈로 연산을 사용할 수 있으며 하위 디렉터리의 다른 수준에서 반복할 수도 있습니다. 중요한 점은 모든 하위 레벨이 ID를 기반으로 계산될 수 있다는 것입니다. 즉, 추가하는 각 노드에 증분 카운터를 사용할 수는 없다는 의미입니다.

첫 번째 단계(;-))에서 아직 살아 있다면 다음과 같은 쉘 스크립트만 사용하더라도 두 번째 단계는 아마도 매우 쉬울 것입니다.

#!/bin/bash

# make sure $PWD has physical dir
cd -P .
fs="${1:-$PWD}"

# for each node
while read -r node; do
    cd "$node"
    # check that node does not already have a root: if it does, read that and do not enter the loop
    while ! { [ -e myroot ] && read -r root < myroot; }; do
        # remember visited node
        traversed+=("$node")
        # if node does not have parent it is a root, so quit loop
        [ -L parent ] || { root="$node" && parents+=() && break; }
        # go up to parent, which becomes node to consider
        cd -P parent
        node="$PWD"
        # add to visited parents
        parents+=("$node")
    done
    # cd back to the root of this filesystem
    cd "$fs"
    for ((i=0; i < ${#traversed[@]}; i++)) ; do
        # for each traversed node (if any) set its root and display it
        echo "$root" > "${traversed[i]}/myroot"
        echo "${traversed[i]##*/}" "${parents[i]##*/}" "${root##*/}"
    done
    traversed=()
    parents=()
done < <(find "$fs" -mindepth "$((${2:-0}+1))" -type d)

컴파일된 언어는 당연히 더 빠르며, 상위 및 루트가 심볼릭 링크 및 파일이 아닌 각 노드/디렉토리의 확장 속성에 저장되면 확실히 더 빨라집니다.

스크립트는 분기하고 실행할 필요가 없으며 노드를 탐색하는 동안 발견된 상위 항목을 표시하여 분기가 여러 번 탐색되지 않도록 합니다. 또한 실제 노드를 포함하는 고정된 수의 중간 하위 디렉터리를 허용하고 파일 시스템의 루트와 중간 하위 디렉터리의 수를 인수로 예상하므로 다음과 같이 실행할 수 있습니다.

traverse.sh /mnt/dataset-on-filesystem 3

이는 3노드 자체 디렉터리 앞에 세 가지 수준의 하위 디렉터리가 있음을 의미합니다.

이 스크립트에서 사용하는 프로세스는 가장 깊은 체인을 먼저 수신함으로써 큰 이점을 얻을 수 있습니다. 단, 이 체인은 다른 많은 얕은 체인에서도 공유됩니다. 이렇게 하면 초기 단계에서 많은 상위 체인이 표시되어 많은 후속 체인에 더 적은 순회가 필요하게 되므로 스크립트는 모든 노드를 더 빠르게 소비합니다.

이 명령을 실행하면 원하는 전체 출력을 표준 출력으로 얻을 수 있을 뿐만 아니라 각 노드의 루트가 노드의 디렉터리 파일에 저장되어 언제든지 사용할 myroot수 있습니다.cat

마지막으로, 파일 시스템의 기능 외에도 이 솔루션의 많은 세부 사항에는 패스 간 캐싱을 수행하거나 ID가 패킹할 수 있는지 여부(또는 방법)에 따라 최적화할 여지가 있을 수 있습니다. 20비트 숫자는 실제 주소 공간과 희소성, 그리고 입력 데이터 세트가 어떻게 정렬되었는지(비)정렬되었는지에 따라 달라집니다.

Answer

만약에귀하의 설명과 요구 사항을 잘 이해합니다. 계층적으로 관련된 노드 집합에서 트리를 재구성해야 하는 것 같습니다.

나는 이것이 적절한 데이터베이스 엔진을 위한 작업이라는 다른 모든 사람들의 의견에 동의하지만 표준 명령줄 도구를 사용해야 하는 경우 파일 시스템을 "데이터베이스", 즉 노드 인덱스로 사용하는 것이 또 다른 옵션일 수 있습니다.

따라서 최종 결과를 얻으려면 모든 노드를 2번 통과해야 합니다.

먼저 입력 데이터세트에서 전달되어 파일 시스템에 표현을 생성합니다. 여기서 각 개별 노드는 상위 노드/디렉토리에 대한 심볼릭 링크를 포함하는 디렉터리가 됩니다.
두 번째 패스는 모든 노드를 루트 노드까지 순회한 다음 요구 사항에 따라 상위 및 루트 노드와 함께 각 노드를 표시합니다.

개념적으로는 간단하지만 몇 가지 중요한 단점이 있습니다.

가장 큰 단점은 기본적으로 사용 중인 파일 시스템의 기능에 따라 달라지며 다음 요소를 고려하여 이러한 목적으로 설계된 전용 파일 시스템을 준비해야 할 가능성이 높다는 것입니다.

단일 디렉토리에 포함된 수백만 개의 디렉토리를 처리할 때 파일 시스템 성능: 예를 들어 ext4는 수만 개의 디렉토리를 처리한 후 많이 떨어지기 때문에 그다지 좋지 않습니다. 그러나 아마도 이것이 최선의 옵션은 reiserfs입니다. (아마 최고일 것임) 또는 btrfs(reiserfs보다 약간 느림) 그러나 언급한 숫자에 따르면 btrfs 또는 reiserfs를 사용하더라도 여전히 노드/디렉토리 수를 중간(하위 수준) 하위 디렉터리로 나누어야 합니다. 어떤 디렉토리에도 1M 이상을 넣지 마십시오. 디렉토리
너무 많은 노드/디렉터리를 저장할 때 파일 시스템의 압축성(필요한 디스크 공간)(각각은 심볼릭 링크만 포함하고 두 번째 패스 이후에는) 매우 작은 파일: 여기에서는 낭비되는 디스크 공간이 많이 필요합니다. 파일 시스템의 표준 구성은 일반적으로 디렉터리 또는 파일당 4k, 즉 노드당 총 8-12k를 할당합니다. 하지만 파일 시스템에서는 포맷할 때 이에 대한 일부 조정, 특히 최소 할당 크기를 허용하지만 그 이하도 기대할 수 없습니다. 노드당 2~3,000개보다 노드의 상위 및 루트를 저장하면 훨씬 더 컴팩트해질 수 있습니다.확장된 속성심볼릭 링크와 파일 대신에, 그래도 노드당 1,000개 이상일 것입니다.

또 다른 단점은 이 모든 것을 처리하기 위해 사용하는 언어입니다. 쉘 스크립트를 사용하는 것은매우mkdir각 단일 노드에는 해당 상위 노드에 대한 분기 및 실행 ln -s(또는 setfattrLinux에서는 단일, MacOS에서는 단일) 링크가 필요하기 때문에 첫 번째 패스는 느립니다. xattr이는 2개의 분기 및 실행 곱하기 수천만 번을 의미합니다. 이 분기 및 실행 작업은 관련 시스템 호출(예: mkdir(2) 및 Symlink(2)/setxattr(2))을 직접 사용할 수 있는 언어로 전체 첫 번째 단계를 개발할 수 있다면 좋을 것입니다. 제거되었습니다.

구체적으로, 간단한예첫 번째 패스에 대한 스크립트(주로 적용할 기본 작업을 표시하기 위한 의사코드)는 다음과 같습니다.

while read -r child parent; do
    # here I use '-p' only for 'no error if existing'
    mkdir -p $child $parent  # <-- note lack of quotes for once, so to ignore empty $parent
    [ $parent ] && (cd $child && ln -s ../${parent} parent)
done

스크립트는 각 하위/상위 쌍이 공백으로 분리되어 자체 줄에 있다고 가정하고, 알려진 루트가 각각 하나의 ID만 있는(즉, 상위 없음) 줄로 예상하며 모두 표준 입력에 제공됩니다.

데모를 단순화하기 위해 스크립트는 다음을 수행합니다.아니요중간 하위 디렉터리를 사용합니다. 즉, 하나의(실제로는 현재) 디렉터리에 모든 노드/디렉터리를 생성합니다. 말한 바와 같이,그건 금기야노드가 1M을 초과하는 경우.

하나 이상의 디렉터리 하위 수준을 제공하려면 최상의 분할 방법을 선택하기 위해 노드의 ID 특성에 대한 지식이 필요합니다. 예를 들어, 20비트 ID에서 사용하는 실제 주소 공간이 고르게 분산된 경우 간단한 모듈로 연산을 사용할 수 있으며 하위 디렉터리의 다른 수준에서 반복할 수도 있습니다. 중요한 점은 모든 하위 레벨이 ID를 기반으로 계산될 수 있다는 것입니다. 즉, 추가하는 각 노드에 증분 카운터를 사용할 수는 없다는 의미입니다.

첫 번째 단계(;-))에서 아직 살아 있다면 다음과 같은 쉘 스크립트만 사용하더라도 두 번째 단계는 아마도 매우 쉬울 것입니다.

#!/bin/bash

# make sure $PWD has physical dir
cd -P .
fs="${1:-$PWD}"

# for each node
while read -r node; do
    cd "$node"
    # check that node does not already have a root: if it does, read that and do not enter the loop
    while ! { [ -e myroot ] && read -r root < myroot; }; do
        # remember visited node
        traversed+=("$node")
        # if node does not have parent it is a root, so quit loop
        [ -L parent ] || { root="$node" && parents+=() && break; }
        # go up to parent, which becomes node to consider
        cd -P parent
        node="$PWD"
        # add to visited parents
        parents+=("$node")
    done
    # cd back to the root of this filesystem
    cd "$fs"
    for ((i=0; i < ${#traversed[@]}; i++)) ; do
        # for each traversed node (if any) set its root and display it
        echo "$root" > "${traversed[i]}/myroot"
        echo "${traversed[i]##*/}" "${parents[i]##*/}" "${root##*/}"
    done
    traversed=()
    parents=()
done < <(find "$fs" -mindepth "$((${2:-0}+1))" -type d)

컴파일된 언어는 당연히 더 빠르며, 상위 및 루트가 심볼릭 링크 및 파일이 아닌 각 노드/디렉토리의 확장 속성에 저장되면 확실히 더 빨라집니다.

스크립트는 분기하고 실행할 필요가 없으며 노드를 탐색하는 동안 발견된 상위 항목을 표시하여 분기가 여러 번 탐색되지 않도록 합니다. 또한 실제 노드를 포함하는 고정된 수의 중간 하위 디렉터리를 허용하고 파일 시스템의 루트와 중간 하위 디렉터리의 수를 인수로 예상하므로 다음과 같이 실행할 수 있습니다.

traverse.sh /mnt/dataset-on-filesystem 3

이는 3노드 자체 디렉터리 앞에 세 가지 수준의 하위 디렉터리가 있음을 의미합니다.

이 스크립트에서 사용하는 프로세스는 가장 깊은 체인을 먼저 수신함으로써 큰 이점을 얻을 수 있습니다. 단, 이 체인은 다른 많은 얕은 체인에서도 공유됩니다. 이렇게 하면 초기 단계에서 많은 상위 체인이 표시되어 많은 후속 체인에 더 적은 순회가 필요하게 되므로 스크립트는 모든 노드를 더 빠르게 소비합니다.

이 명령을 실행하면 원하는 전체 출력을 표준 출력으로 얻을 수 있을 뿐만 아니라 각 노드의 루트가 노드의 디렉터리 파일에 저장되어 언제든지 사용할 myroot수 있습니다.cat

마지막으로, 파일 시스템의 기능 외에도 이 솔루션의 많은 세부 사항에는 패스 간 캐싱을 수행하거나 ID가 패킹할 수 있는지 여부(또는 방법)에 따라 최적화할 여지가 있을 수 있습니다. 20비트 숫자는 실제 주소 공간과 희소성, 그리고 입력 데이터 세트가 어떻게 정렬되었는지(비)정렬되었는지에 따라 달라집니다.

bash: 주어진 부모-자식 세트의 루트 노드를 효율적으로 찾는 방법

답변1

답변2

복잡성 분석

답변3

관련 정보