☰

두 개의 정렬된 목록에 고유한 요소가 포함되어 있는지 확인하는 가장 빠른 방법

tag-icon • tag-icon text-processing search sort
두 개의 정렬된 목록에 고유한 요소가 포함되어 있는지 확인하는 가장 빠른 방법

A두 개의 정렬된 파일 이 있는데 B크기가 A훨씬 큽니다 B. 예를 들어 A는 100GB이고 B는 50MB입니다. 나는 원해요빠르게의 행이 B에 포함되어 있는지 확인하고 A일치하는 항목이 있으면 중지합니다. 현재 이 목적을 위한 Python 스크립트가 있지만 다른 프로세스에 대해 프로세스를 수천 번 반복해야 하면 느리게 실행됩니다 B.

답변1

를 사용하면 및 fifo를 사용하여 comm첫 번째 일치에서 스크립트가 반환되도록 할 수 있습니다.head

#!/bin/bash -e 

[ -p tmpfifo ] || mkfifo tmpfifo
comm -12 A B | head -n1 >tmpfifo &

# If this wc is zero, no matches.  Otherwise, a match was found. 
# You can use this directly in the script, echo it, 
# change the script exit value, or however else you need to use it.
wc -l tmpfifo

현재 이것은 백그라운드에서 계속 통신을 수행하고 있으며 PID죽일 권리( 살인이 아닌 $!주는 것 )를 찾는 데 어려움을 겪고 있습니다. 이것이 실행 중인 유일한 통신이라고 확신하는 경우에는 작동 하지만 다른 통신이 실행 중이면 위험할 수 있습니다. headcommkillall

답변2

AWK를 사용하여 파일을 구문 분석해 볼 수 있습니다. 처음에는 더 큰 파일을 분할하거나 A를 mem에 저장하고 B를 실행하여 각 행을 mem의 A와 비교하고 싶었습니다. 그러나 내 생각에는 AWK가 당신이 찾고 있는 것일 수도 있습니다.

http://www.linuxjournal.com/article/8913프라이머에요

http://forums.devshed.com/unix-help-35/compare-two-files-using-awk-or-sed-425150.html파일 비교에 대해 이야기합니다. 저는 지금 Linux를 사용하고 있지 않습니다. 아니면 테스트해 보겠습니다.

멍하니http://www.gnu.org/software/gawk/manual/html_node/index.html

답변3

파일이 정렬된 경우에는 Join(1) 또는 merge(1)를 사용하여 상당히 효율적으로 작업할 수 있습니다. head -1출력은 첫 번째 줄에서 중지되고 종료 시 SIGPIPE를 사용하여 명령의 나머지 부분을 종료합니다.

또한 더 큰 파일 A에서 uniq(1)을 사용하면 문제 크기를 줄일 수 있습니다. 이는 다른 라인 세트로 요약되어 B 파일 목록과 비교할 수 있습니다.

또 다른 가능성은 다음을 수행하도록 Python 스크립트를 조정하는 것입니다.

For each B file:
    Read in each line
    Add the file name to a list of files keyed on a hash of the line 

Loop through the A file:
    Look up each line in the dictionary
    Output the file name when a match is found.

"B" 파일의 다른 줄 수가 많으면 메모리를 많이 차지하므로 실용적일 수도 있고 그렇지 않을 수도 있습니다. 거짓 긍정을 제거하기 위한 사후 처리가 마음에 들지 않으면 이 단계에서 해시만 저장하여 메모리 소비를 줄일 수 있습니다.

세 번째 접근 방식은 모든 데이터를 데이터베이스에 로드하고 연결하는 것입니다. 그러나 이렇게 하면 데이터를 가져오는 오버헤드가 발생하여 너무 커질 수 있습니다. 적절한 인덱스를 사용하면 실제 일치 쿼리가 매우 빨라지고 모든 B 파일을 한 번에 확인할 수 있습니다.

Create table A (
       TextLine varchar (100) -- or whatever length you need
)

Create table B (
       TextLine varchar (100)
      ,Filename varchar (20)
)

Alter table B
  add constraint PK_B
      primary key (TextLine, FileName)


select distinct B.FileName
  from A
  join B
    on a.TextLine = B.TextLine

답변4

grep -F -x -f B A | head -n 1

이것은 grep의 잘 알려진 기능은 아니지만 각 패턴을 한 줄에 배치하여 단일 파일을 통해 여러 패턴을 전달할 수 있습니다. 이는 -F정확한 문자열을 찾기 위해 와 함께 사용할 때 가장 유용합니다 ( 를 사용할 경우 -E효과는 로 구분된 여러 패턴과 동일합니다 |).

아직 벤치마킹은 안해봤지만 A 전처리 없이 최대한 빨리 나왔으면 좋겠습니다.

관련 정보